已经很久没有更新过博客，因为论文和自己的学习的事情，也因为自己的懒惰疏于书写。仿佛时间已经过去了很久，现在毕业了，因为一些原因没有参加秋招，而且也错过了春招，现在才开始到北京来面试找工作。寄居在同学这里，感谢他们的收留。第一家面试的公司是一家做K12的线上的公司，面试的题目不难，但是可能是第一次准备了很久，但是面试的时候感觉发挥的很差，自己的知识也确实不到位，所以，以后每次面试一家公司都要进行总结和学习，希望自己加油。
进入正题吧。首先上来就是笔试做题，题目简单但是我都做得不是很好。
题目1：定义一个哈希表的成员和方法。
这个题目我大致写了一下，还是写出来了，采用的线性散列的方式。面试官看了下感觉还行。下面结合网友的答案给出完整的实现。这是一个简单的哈希表的实现。
#实现哈希表（线性地址再散列） def ChangeKey(key, m, di): key01 = (key+di) % m return key01 a = input("Please entry the numbers(split by space!): ").split() m = len(a) dict01 = {} for i in a: key = int(i) % m if "%s" % key in dict01: # 如果该键值已经在列表中存在，则改变该值，加一向后顺延 NewKey = ChangeKey(key, m, 1) while "%s" % NewKey in dict01: #因为下面的dict01的key值是以字符串来保存，因此这里作判断时也要用字符串格式 # 如果新产生的键值也是重复的在此顺延一位 NewKey = ChangeKey(NewKey, m, 1) dict01["%s" % NewKey] = int(i) else: dict01["%s" % key] = int(i) print(dict01)
# 测试数据运行结果
Please entry the numbers(split by space!):
5 6 9 89 5 66 56 99
{'5': 5, '6': 6, '1': 9, '2': 89, '7': 5, '3': 66, '0': 56, '4': 99}
要实现一个哈希表的成员和方法，首先需要定义一个类，然后要有初始化的方法，其次给定实现哈希表的方法。
1 class LinearMap(object): 2 """ 线性表结构 """ 3 def __init__(self): 4 self.items = [] 5 6 def add(self, k, v): # 往表中添加元素 7 self.items.append((k,v)) 8 9 def get(self, k): # 线性方式查找元素 10 for key, val in self.items: 11 if key==k: # 键存在，返回值，否则抛出异常 12 return val 13 raise KeyError
此时在哈希表中查找一个元素的时间复杂度是O（logn）。python的内建数据类型：字典，就是用哈希表实现的。下面给出完整的实现。
class HashMap(object): def __init__(self): # 初始化总表为，容量为2的表格（含两个子表） self.maps = BetterMap(2) self.num = 0 # 表中数据个数 def get(self,k): return self.maps.get(k) def add(self, k, v): # 若当前元素数量达到临界值（子表总数）时，进行重排操作 # 对总表进行扩张，增加子表的个数为当前元素个数的两倍！ if self.num == len(self.maps.maps): self.resize() # 往重排过后的 self.map 添加新的元素 self.maps.add(k, v) self.num += 1 def resize(self): """ 重排操作，添加新表, 注意重排需要线性的时间 """ # 先建立一个新的表,子表数 = 2 * 元素个数 new_maps = BetterMap(self.num * 2) for m in self.maps.maps: # 检索每个旧的子表 for k,v in m.items: # 将子表的元素复制到新子表 new_maps.add(k, v) self.maps = new_maps # 令当前的表为新表
题目2：写一个方法输出1-100之间的素数。
就这个题目非常之简单但是我写错了各位老铁。哎。。。感觉脑袋是蒙的，后面面试官提示了我很久，才慢慢的写了出来。但是肯定是完了，觉得我逻辑和代码能力都差，也确实是如此，希望大家不要像我一样，引以为戒吧。
for i in range(1,101): if i == 1: print(i) continue for j in range(2,i): if i % j == 0: break else: print(i)
题目3：给定一个数组，用快排实现升序排序。
def quick_sort(li, start, end): # 分治 一分为二 # start=end ,证明要处理的数据只有一个 # start>end ,证明右边没有数据 if start >= end: return # 定义两个游标，分别指向0和末尾位置 left = start right = end # 把0位置的数据，认为是中间值 mid = li[left] while left < right: # 让右边游标往左移动，目的是找到小于mid的值，放到left游标位置 while left < right and li[right] >= mid: right -= 1 li[left] = li[right] # 让左边游标往右移动，目的是找到大于mid的值，放到right游标位置 while left < right and li[left] < mid: left += 1 li[right] = li[left] # while结束后，把mid放到中间位置，left=right li[left] = mid # 递归处理左边的数据 quick_sort(li, start, left-1) # 递归处理右边的数据 quick_sort(li, left+1, end) if __name__ == '__main__': l = [6,5,4,3,2,1] # l = 3 [2,1,5,6,5,4] # [2, 1, 5, 6, 5, 4] quick_sort(l,0,len(l)-1) print(l) # 稳定性：不稳定 # 最优时间复杂度：O(nlogn) # 最坏时间复杂度：O(n^2)
阿里云新用户注册连接：欢迎大家使用。