惨烈的google onsite (11.5)

很详细。加油LZ!

nhqgoal 发表于 2018-11-6 11:41
请问猜字母到只剩一个下划线再开始猜词的策略是怎么得出的？ 如果是aabbcc这种没有单独出现的字母呢？

那就不需要猜词了，因为在猜字母的阶段就猜出来了

nole 发表于 2018-11-6 23:36
请问最后一轮求汇率的题， 是哪到题？谢谢

不记得是哪道题了，大致的意思就是，比如给你A到B的汇率，B到C的汇率，C到D的汇率。有可能问你：
1. A到B的汇率
2. C到A的汇率
3. A到D的汇率
4. A到E的汇率（没有就返回0）

wtcupup 发表于 2018-11-6 11:34
请问LZ在Mountain View 面的还是Sunnyvale ?

mountain view

martinchia 发表于 2018-11-7 00:19
不记得是哪道题了，大致的意思就是，比如给你A到B的汇率，B到C的汇率，C到D的汇率。有可能问你：
1. A到 ...

散酒酒吧应该是

谢谢楼主。应该是散酒酒。

楼主第一题如果你用两个bst存x 和 y的partition坐标， 那么怎么知道找到的坐标是第几个区间呢？

第一题感觉可以用两个BST with count of nodes of subtree做。
一个subtree代表横坐标切得刀未知，一个代表纵坐标切得位置
给定x，y 搜索时候分别找到X对应的column和Y对应row，最后的number = row * number of columns + columns就好
砍一刀的时候就是常规log n往下找 + update subtree sum
这个思路对嘛？

请问第一题怎么做呢？binary tree 怎么构建啊

1. class BinarySearchTree:
   
2.     def __init__(self, val):
   
3.         self.val = val
   
4.         self.less_num = 0
   
5.         self.greater_num = 0
   
6.         self.left = None
   
7.         self.right = None
   
8. 
   
9. class Partitions:
   
10.     def __init__(self):
    
11.         self.xTree = None
    
12.         self.yTree = None
    
13.         self.max_x = 0
    
14.         self.x_total = 1
    
15. 
    
16.     def getPartition(self, x, y):
    
17.         def getLess(tree, val):
    
18.             cur = tree
    
19.             total = 0
    
20.             while cur:
    
21.                 if val > cur.val:
    
22.                     total += cur.less_num + 1
    
23.                     cur = cur.right
    
24.                 else:
    
25.                     cur = cur.left
    
26.             return total
    
27. 
    
28.         if not self.xTree:
    
29.             less_x = 0
    
30.         else:
    
31.             less_x = getLess(self.xTree, x)
    
32.         if not self.yTree:
    
33.             less_y = 0
    
34.         else:
    
35.             less_y = getLess(self.yTree, y)
    
36.         if less_y == 0:
    
37.             return less_x
    
38.         else:
    
39.             return less_y * self.x_total + less_x
    
40. 
    
41.     def addVal2Tree(self, tree, val):
    
42.         cur = tree
    
43.         while cur:
    
44.             if val > cur.val:
    
45.                 cur.greater_num += 1
    
46.                 if cur.right:
    
47.                     cur = cur.right
    
48.                 else:
    
49.                     cur.right = BinarySearchTree(val)
    
50.                     break
    
51.             else:
    
52.                 cur.less_num += 1
    
53.                 if cur.left:
    
54.                     cur = cur.left
    
55.                 else:
    
56.                     cur.left = BinarySearchTree(val)
    
57.                     break
    
58. 
    
59.     def addX(self, x):
    
60.         if not self.xTree:
    
61.             self.xTree = BinarySearchTree(x)
    
62.             self.x_total = 2
    
63.         else:
    
64.             self.addVal2Tree(self.xTree, x)
    
65.             self.x_total += 1
    
66. 
    
67.     def addY(self, y):
    
68.         if not self.yTree:
    
69.             self.yTree = BinarySearchTree(y)
    
70.         else:
    
71.             self.addVal2Tree(self.yTree, y)
    
72. 
    
73. if __name__ == "__main__":
    
74.     p = Partitions()
    
75.     p.addX(1)
    
76.     print(p.getPartition(1, 2))

复制代码