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:

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.

原创首发 SteemIt, 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.     

// 同步到 我的 英文算法博客

// 同步到 我的 中文博客 JustYY

近期热贴 Recent Popular Posts 

1. 记录那些值得回忆的精彩瞬间
2. I wrote a Chinese Chess Program 软件分享: 智慧中国象棋 (Chinese Chess)
3. One Day Visit to Fen Drayton Lake (Photography) - 村庄附近的 Fen Drayton 湖
4. One Night in Luton. 回到Luton十一年前打工的酒巴Brookes喝酒
5. One Day Travel (Photography) Fen Drayton Lake + St Ives 英国 Fen Drayton Lake 坐公交到 St Ives 游玩
6. What is Data Overfitting in Machine Learning? 机器学习中的过拟现象
7. Just throw away the things you don't need 断舍离