Software Engineer Interview Tips - Using Hashtable to Reduce Runtime Complexity

I am recently reviewing the data structure & algorithms. And the hash table is one of the key knowledge that you can’t miss before you attend a coding interview.

The hashtable has O(1) complexity of insert and lookup, whilst it has O(N) space complexity. Take this for example, given an array of integers, please find the pairs that has difference of two.

{1, 3, 5, 6, 9}
Output: (1, 3), (3, 5)

The bruteforce O(N^2) code is straightforward:

1
2
3

for i = 0 to len - 1
  for j = i + 1 to len
     if abs(arr[i] - arr[j]) = 2) then print_pair_at(i, j)

for i = 0 to len - 1
  for j = i + 1 to len
     if abs(arr[i] - arr[j]) = 2) then print_pair_at(i, j)

With Hashtable, we store the numbers in the table at first iteration, then look it up the value +-2 in the second iteration, which makes O(N).

for i in arr:
  put i in hash table
for i in arr:
  if hash table contains (i - 2) then print(i, i - 2)
  if hash table contains (i + 2) then print(i, i + 2)

for i in arr:
  put i in hash table
for i in arr:
  if hash table contains (i - 2) then print(i, i - 2)
  if hash table contains (i + 2) then print(i, i + 2)

Highly recommend this book to you if you prepare for the I.T interviews.

<br />