Google SVL onsite

昨天剛 onsite 所以又來發面經贊人品。本來快寫完了手殘按到 refresh 全沒了...就簡單寫一寫= =
p.s. 1 和 Facebook 比起來 Google 的 onsite 題目感覺真的變化相對多。

p.s. 當天在 SVL onsite 的人多到炸...多到面試官帶錯人（同姓的）花了 15 分鐘才發現...發現的原因還是帶錯的面試官真正要帶的人出了車禍來不了 HR 通知才一臉矇逼XD


第一輪：給一個 city 的左邊視角和下面視角，求最大可能 volume。
例如用以下 matrix 表示一個 city 每棟大樓的高度：
[
[1,2,2,3],
[2,1,2,1],
[1,1,1,1]

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

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

根據這兩個條件設計 solution： 用長度 60 的 integer array 存過去 60 秒每一秒的次數，並維護一個 sum 以便隨時回傳。每當 call increment() 或 get60sCount() 時根據兩次 request 的時間差 update array 和 sum 的值。

第五輪： thesis discussion。 簡介了下 thesis 內容，對方算是相關背景所以問得問題都比較深入，幸虧自己 thesis 還是自己熟所以都還能答出來。

楼主第一轮第二个solution是不是这样：算出都少个B[j] >= A[i], 剩下的 B[j] < A[i].
代码对不对？

1. public static int maxShiJiao2(int[] A, int[] B) {
   
2.                 int m = A.length, n = B.length;
   
3.                 Arrays.sort(A);
   
4.                 Arrays.sort(B);
   
5.                 int cnt = 0;
   
6.                 int j = 0;
   
7.                 int sumB = 0;
   
8.                 for (int i = 0; i < m; i++) {
   
9.                         while (j < n && B[j] < A[i]) {
   
10.                                 sumB += B[j++];
    
11.                         }
    
12.                         cnt += (n - j) * A[i] + sumB;
    
13.                         // (n-j)个 B[j] >= A[i]
    
14.                 }
    
15.         
    
16.         return cnt;
    
17.     }

复制代码

第四轮有点像 蠡口刘斯幺 （Design Circular Deque）

sifangyou1 发表于 2018-12-6 18:22
楼主第一轮第二个solution是不是这样：算出都少个B[j] >= A, 剩下的 B[j] < A.
代码对不对？

嗯對的，關鍵就是一個 partial sum (sumB) 和長方形計算 (n - j) * A[i] + sumB

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

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

第二题

1. class TreeNode:
   
2. 
   
3.     def __init__(self, val, left, right):
   
4.         self.val = val
   
5.         self.left = left
   
6.         self.right = right
   
7. 
   
8. def getNode(tree, id):
   
9.     path = []
   
10.     while id > 0:
    
11.         path.append(id)
    
12.         id = id / 2
    
13.     path = path[::-1]
    
14. 
    
15.     print path
    
16. 
    
17.     c_node = tree
    
18.     current = path[0]
    
19.     for val in path[1:]:
    
20.         print 'node val', c_node.val
    
21.         print val
    
22.         if val == current * 2:
    
23.             if c_node.left:
    
24.                 c_node = c_node.left
    
25.             else:
    
26.                 return False
    
27.         else:
    
28.             if c_node.right:
    
29.                 c_node = c_node.right
    
30.             else:
    
31.                 return False
    
32.         current = val
    
33. 
    
34.     if c_node:
    
35.         print c_node.val
    
36.     return c_node if c_node else False
    
37. 
    
38. 
    
39. 
    
40. 
    
41. 
    
42. 
    
43. 
    
44. 
    
45. node1 = TreeNode(1, None, None)
    
46. node3 = TreeNode(3, None, None)
    
47. node6 = TreeNode(6, None, None)
    
48. node7 = TreeNode(7, None, None)
    
49. 
    
50. node1.right = node3
    
51. node3.left = node6
    
52. node3.right = node7
    
53. 
    
54. 
    
55. 
    
56. print getNode(node1, 5)
    
57. print '.........'
    
58. print getNode(node1, 6)
    
59. 
    
60. 
    
61. from collections import deque
    
62. def fullSizeTreeMaxid(tree):
    
63.     def getHeight(node):
    
64.         if node is None:
    
65.             return 0
    
66.         return 1 + getHeight(node.left)
    
67. 
    
68.     height = getHeight(tree)
    
69.     max_id = 2 ** height - 1
    
70.     while not getNode(tree, max_id):
    
71.         max_id -= 1
    
72.     return max_id
    
73. 
    
74. 
    
75. node1 = TreeNode(1, None, None)
    
76. node2 = TreeNode(2, None, None)
    
77. node3 = TreeNode(3, None, None)
    
78. node4 = TreeNode(4, None, None)
    
79. node5 = TreeNode(5, None, None)
    
80. 
    
81. node1.left = node2
    
82. node1.right = node3
    
83. node2.left = node4
    
84. node2.right = node5
    
85. 
    
86. 
    
87. print fullSizeTreeMaxid(node1)

复制代码

求问楼主第二题的followup是不是只能搜一遍整个树，取最深的那个了？

gogoii 发表于 2019/01/17 17:53:35
求问楼主第二题的followup是不是只能搜一遍整个树，取最深的那个了？

不用。由於是 full binary tree，一旦找到任一層最右邊的 node 就說明那一層是滿的可以往下一層去找