好久没有看算法相关的，竟然毕业一年了，还是考了个算法题（😂）由此可见，做计算机的，不论哪块（现在是安全），都要经常复习算法，包括基础选择，排序，还有专业相关，安全加密算法，通信加密算法等等。
题目：给出两个已经是Sorted 的列表，然后求两个的交集
1. 直接上python ，两下写:
#!/usr/bin/env python
A = [1, 3, 4, 5, 9, 10]
B = [2, 4, 6, 10]
res = set()
for item in A:
if item in B:
res.add(item)
然后面试官说：这么快就写完了？我说python 嘛，对用户很友好，就很快，哈哈
2. 面试官问这个的时空复杂度：
时间复杂度： O(n^2) （N*M）(N,M分别是两个列表的长度)
空间复杂度：好像没说，当然了，这个应该是O(n/m) 吧（就res最多把最短列表里的全部放进去）
3. 还有优化的想法吗：N平方的复杂度太大了，元素多的时候会特别慢
好，我就说那就先排序，经提醒，已经是排序好的了。
然后我就说了下比的思路：
从短B的列表开始，每一个元素，都和另一个列表里的比较，如果相等，塞进res; 如果大，则和A下一个元素比；如果小，则B的下一个和A的这个元素相比。然后不断循环。知道一个边界到最终。
一开始，在想怎么用Python在一个for循环里有两个迭代值，妈蛋，最后说百度都没找到，然后面试官很nice地说可以用C的形式来定义两个迭代值，然后竟然想了好一会儿才弄对。真是紧张。
写的代码大概如下：
#!/usr/bin/env python
"""
C式的写法，好惭愧~~~
"""
def cmp(a, b)
if a == b:
return 0
elif a < b:
return 1
else:
return 2
def cmp_do(B, A):
i = 0
j = 0
res = set()
while 1:
if i > len(B) or j > len(A):
break
r1 = cmp(B[i], A[j])
if r1 == 0:
res.add(B[i])
i += 1
j += 1
elif r1 == 1:
i += 1
else:
j += 1
if __name__ == '__main__':
cmp_do()
print res
Python的二分查找算法：（面试前就准备了一个冒泡排序算法，结果GG。真的好后悔。现在贴出来这个二分查找）
#No.1: while循环写法：
def BinSearch(alist, item):
low = 0
high = len(alist) - 1
mid = high // 2
while low <= high: # 最后可能两个重合，即高低中位都是同一个位置
if alist[mid] == item:
return True
elif item < alist[mid]:
high = mid - 1
else:
low = mid + 1
return False
#No.2 递归写法：
def Bin_S(alist , item):
low = 0
high = len(alist)
if high == 0: ## 全部元素比较完了，没有可比的了
return False
mid = high // 2
if alist[mid] == item:
return True
elif item > alist[mid]:
return Bin_S(alist[mid+1:], item)
else:
return Bin_S(alist[:mid], item)
#No.3 Github 上看到用标准库写法：
#!/usr/bin/env python
import bisect
def bi_sea_std_lib(sorted_list, item):
index = bisect.bisect_left(sorted_list, item)
if index != len(sorted_list) and sorted_list[index] == item:
return index ## 返回下标
return None
# 测试
if __name__ == '__main__':
A = [1, 3, 4, 7, 9, 10]
r1 = BinSearch(A, 10)
print r1 ## True
r2 = Bin_S(A, 6)
print r2 ## False
r3 = bi_sea_std_lib(A, 4)
print r3 ## 2
### 二分查找的时间复杂度：最好情况：O(1); 最坏：O(log N)
>二分查找比其他算法快的本质精髓：采用二分，在最换情况下，都能每次比较，都少比较当前集合的一半元素。当然快了。（每次比较都是只比较当前集合的一半元素）
4. 恩，现在的时间复杂度呢？ O(N) （N是两个列表长度最长那个）
5. 还有更好的时间负责度算法吗？： 立马想到: 二分！！
是的，那二分的时间复杂度是多少呢？ 我：??? O(1/2 N)
不对啊，1/2 N也是 N啊。我说，这个上学的时候学过，给忘了。。。面试官给我解释后，然后最后说log2(N). 对数。
我：哦，恍然大悟。。。
哇，终于过去了。
6. 对于爬虫，一个对互联网上的爬虫，你有想过怎么架构吗？
- 首先考虑性能。这个多是网络IO，所以要用多进程。
- 存储，为了快一点，应该用redis
问题： redis存在内存里，确实快，可是容量不大，存不下。我说那就用一个单独的进程监控饱和度，一旦到了80%之类，就同步到数据库Mysql之类。（感觉也是不怎么样的回答）
然后问还有什么其他方面考虑吗？我：没有了
漂亮回答：（待补充）
7. 问TCP里面的那个keep alive; 设置成True或False有什么区别。。。
我说这个真没怎么细研究过，但应该是长连接之类，不用多次的进行TCP三次握手。应该是对安全要求较低的系统
漂亮回答：（待补充）
8. HTTP传输，一般是加密，我说对，是用HTTPS嘛。那你能说说HTTPS加密通信的过程吗？
我：（手到擒来，blabla...）
面试官：你对这个还挺熟嘛； 我：我是做安全的啊（笑哭）
答案连接：（阮一峰）
http://www.ruanyifeng.com/blog/2014/09/illustration-ssl.html
主要就是3个随机数，然后两个hello, 然后是用公钥加密传输第三个随机数，然后用三个随机数在两边各自生成同样的对称加密的密钥，然后就开始通信了。问题点在于3个随机数传输过程都是没有加密的，那么中间人要是获取到了这三个随机数，还有加密算法，不就可以知道对称加密的密钥了吗，是的（只要中间人做好client，server的伪装），但关键在于，第三个随机数：(Pre-master)，这个是client用server给的公钥（证书里）加密的，一般公钥长度越长，越难以被反向解密出来。（理论上来说，只有服务端的私钥可以解开，一旦解密出来，那就没有安全可言了）
9. 最后问我有什么问题，我就说公司对算法性能之类考虑的很多啊，（算法）还有他私人问题，原来nice的面试官已经在Singapo带了20多年了，已经是永久居民。。。然后说那边的互联网要比国内落后几年，我还很吃惊。然后说了总部的人数。（全集团有5K多人。散落在台湾，泰国等东南亚国家）我就表示很想去新加坡，去那边嘛。然后就说HR应该很快就会联系我。
开心，好事多磨，耐心等待吧。。
后记：
最终等的消息是悲剧了，这是合乎常理的，毕竟二分这么基础的算法竟然搞了一个多小时。。。都怪自己没复习算法，能怪谁呢？教训：以后面试不能只看什么多进程，多线程，Python的语言特性之类，还是要把算法抓起来。。妈蛋，毕竟是Coding面试，怎么能不准备算法（实际上自己偷懒，只准备了冒泡排序）唉，好好准备，下次再战。
网友评论