Software Engineer Interview Tips - Using Hashtable to Reduce Runtim...

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:

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)

最近在刷题，倒不是为了找工作，主要是为了练练脑子，日子过得太舒服，人脑不动容易变笨。

程序员应该都了解并能熟悉使用 Hash 哈希表，哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N)。我们来看一道简单的面试题：

给定一个数组，找出相差为2的数对，比如：

{1, 3, 5, 6, 9}

输出为: (1, 3), (3, 5)

拿到这题的时候第一感觉是暴力是否可行? 暴力搜索复杂度为 O(N^2), 大概代码如下：

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 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)

以上就变成了 O(N) 的算法。

另：再次推荐一下这本书，我从AMAZON买的，花了26英镑。很值。

Originally Published in Steemit. Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.