惨烈的google onsite (11.5)

新鲜的谷歌onsite。
早上到的早，怕路上堵车，提前一个半小时就到了，前台不让进，就在谷歌园区里散步。
九点半去check in的，结果我的第一个面试官没来，临时换了一个，耽误了二十分钟，导致整个流程都比较赶。
第一轮是一个烙印，上来就问问题。说有一个坐标系，只有第一象限，写addX, addY，和getPartition三个函数。
addX就是在x = input的那里画条竖线,把象限分隔开。addY就是在y = input那里画条横线。getPartition就是问你一个点x,y属于那个部分。
没划线的时候，全都是partition 0。画了线之后遵守从下到上，从左到右，partition += 1。比如一个井字，partition就是
[[6,7,8]
[3,4,5]
[0,1,2]]
一开始说二分查找树，面试官说不行，然后我说那就用列表存。写出来之后他又说应该用二分查找树，

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

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

，就这点奢望了。


补充内容 (2018-11-7 14:35):
有些同学问了写法的问题，正好我再回来的飞机上强忍悲痛写了一遍代码。在后面的楼里有补充。飞机上写的有些匆忙，写的不对的地方只能贻笑大方了。大家有什么意见可以随意说

补充内容 (2018-11-7 14:38):
因为大家都问第一题，所以暂时只贴了第一题的代码，如果有其他的问题之后再更新

guo0693 发表于 2018-11-6 07:55
lz good luck, 同样是今天的onsite

you too. 倒下了一个我，还有千千万万个我！

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))

复制代码

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

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

lz good luck, 同样是今天的onsite

我也是今天MTV刚面完，下午的第一轮跪的特别惨，回酒店之后脑壳疼的厉害

哈哈，很详细。祝你好运！

二是扫地机器人
三是猜词
leetcode G家高频

canoee 发表于 2018-11-6 08:45
第一题我不确定，但是二，三两题刷题网上都有

可以麻烦问下第二三题的题号是什么吗， 好像没有见到过

LZ，你可以立刻给HR说你这个情况当中没有休息太累了什么的，然后再告诉HR你第一轮明明一开始二叉查找树答对了但是印度人不让你用，这样加面的几率应该会变大。可以随时和HR交流的。