Google 2 轮店面

02-08  第一轮店面
        2题
第一题： 判断一个set of word 是不是unique abbreviation 规则
internationalization" -> "i18n", "localization" -> "l10n"   这题比较简单
[size=14.666666984558105px]第二题： 利口 乌尔齐
[size=14.666666984558105px]之前没刷过，写完之后有些bug  写之前一致跟面试官确定我那个方案行不行，没有直接回应我 写完之后跟我指出来的，然后我跟他说了solution 这个fixed 这个bug
[size=14.666666984558105px]这个可能是见面的原因
[size=14.666666984558105px]02-22 第二轮店面
[size=14.666666984558105px]听声音 感觉是一个慢资深大叔，说话感觉带有命令口气。
[size=14.666666984558105px]就一起设计API， 千万没想到店面会考这个。

template <typename K, typename V>

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

或者其他data structure 里面处理 做到内存最优 而且还说了 如果数据量很大怎么办？？？   

这题绕来绕去 在时间跟内存 这个找最好solution， 最后实在没办法 想不到最优解 用embedded map 给做了。。。。

中间我在思考怎么找最优解的时间 没说话 听到他在那边吐痰的声音。而且面试的时候还迟到10分钟。

挂在这个的design API的题上 心里有点不舒服。 本想着应该就是解2道题的。。。。

各位求加米啊。 欢迎大家在这个帖子下面讨论这个，， 如果做到用最少的内存。。。

move on 下一家了。

补充内容 (2019-2-26 02:48):
编辑不了帖子。。。

补充内容 (2019-2-26 13:48):
   m.get("a"); // returns "duplicate"

我的想法是用一个Dictionary of List，每次同时存取当前Snapshot ID和存取值，Get就直接拿尾端的值，Get with Snapshot ID 就用哈希后用二分法查询，这样内存只会存取需要改变的值，Get, Put 都是O(1)，只是Snapshot ID 查找需要Log(该值的版本修改数)，如有更好的请多指教

1. 
   
2. 
   
3. class VersionDict:
   
4. 
   
5.     def __init__(self):
   
6.         self.version = 0
   
7.         self.map = defaultdict(list)
   
8.    
   
9.     def _bsearch(self, arr, condition):
   
10.         left, right = 0, len(arr)
    
11.         while left < right:
    
12.             mid = (left + right) // 2
    
13.             if condition(arr[mid]):
    
14.                 right = mid
    
15.             else:
    
16.                 left = mid + 1
    
17.         return left
    
18. 
    
19.     def get(self, key):
    
20.         if not self.map[key]:
    
21.             return None
    
22.         return self.map[key][-1][1]
    
23. 
    
24.     def get_with_version(self, key, version):
    
25.         if not self.map[key] or version > self.version:
    
26.             return None
    
27.         ind = self._bsearch(self.map[key], lambda ele : ele[0] > version)
    
28.         if ind == 0:
    
29.             return None
    
30.         return self.map[key][ind-1][1]
    
31. 
    
32.     def put(self, key, value):
    
33.         if not self.map[key] or self.map[key][-1][0] < self.version:
    
34.             self.map[key].append([self.version, value])
    
35.         else:
    
36.             self.map[key][-1][1] = value
    
37. 
    
38.     def take_snapshot(self):
    
39.         self.version += 1
    
40.         return self.version - 1
    
41. 
    
42. 
    
43. class TestVersionDict(unittest.TestCase):
    
44. 
    
45.     def test_basics(self):
    
46.         vdict = VersionDict()
    
47.         vdict.put("a", "foo")
    
48.         vdict.put("b", "bar")
    
49.         assert vdict.get("a") == "foo"
    
50.         assert vdict.get("b") == "bar"
    
51.         assert vdict.get("c") is None
    
52.         vdict.put("a", "duplicate")
    
53.         assert vdict.get("a") == "duplicate"
    
54.         assert vdict.get("b") == "bar"
    
55.         assert vdict.get("c") is None
    
56. 
    
57.         snapshot_id_1 = vdict.take_snapshot()
    
58.         vdict.put("b", "hello")
    
59.         vdict.put("c", "world")
    
60.         assert vdict.get("b") == "hello"
    
61.         assert vdict.get_with_version("b", snapshot_id_1) == "bar"
    
62.         assert vdict.get("a") == "duplicate"
    
63.         assert vdict.get_with_version("a", snapshot_id_1) == "duplicate"
    
64.         assert vdict.get("c") == "world"
    
65.         assert vdict.get_with_version("c", snapshot_id_1) is None
    
66.         assert vdict.get("d") is None
    
67.         assert vdict.get_with_version("d", snapshot_id_1) is None
    
68. 
    
69.         snapshot_id_2 = vdict.take_snapshot()
    
70.         vdict.put("b", "new")
    
71.         assert vdict.get("a") == "duplicate"
    
72.         assert vdict.get_with_version("a", snapshot_id_1) == "duplicate"
    
73.         assert vdict.get_with_version("a", snapshot_id_2) == "duplicate"
    
74.         assert vdict.get("b") == "new"
    
75.         assert vdict.get_with_version("b", snapshot_id_1) == "bar"
    
76.         assert vdict.get_with_version("b", snapshot_id_2) == "hello"
    
77.         assert vdict.get("c") == "world"
    
78.         assert vdict.get_with_version("c", snapshot_id_1) is None
    
79.         assert vdict.get_with_version("c", snapshot_id_2) == "world"
    
80.         assert vdict.get("d") is None
    
81.         assert vdict.get_with_version("d", snapshot_id_1) is None
    
82.         assert vdict.get_with_version("d", snapshot_id_2) is None

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个排版给乱了

是设计有snapshot的Hashtable吗？

ＬＺ给的例子在第一次take snapshot之前就把"a"改为 "duplicate"了，为何之后的 m.get("a")是return "foo"而非"duplicate"?

pengdu 发表于 2019-2-26 09:31
是设计有snapshot的Hashtable吗？

不是。 数据结构可以自己定义，但要保证内存用的最少

用map<key, vector<pair<version number, value>>>其实就可以了，每次take snapshot的时候，对于那些有更改的点，push back一个pair就好了，这样只有更改的key才会生成一个新的pair记录，查找其实就是binary search。这样做不行么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies