forked from HuskyBin/Need-To-Do
-
Notifications
You must be signed in to change notification settings - Fork 3
/
Google_Interview
218 lines (157 loc) · 8.26 KB
/
Google_Interview
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
帮朋友转一下面经:
不是牛人,也没有遇到牛人那么难的面试。
4个多月前面的,整理过几个国人论坛半年内的G面经,周围也有不少人面,感觉还是比
百分之七八十的面经难,擦。
之前准备了一些最近常考的G家独有题,结果一个都没碰到。。。也没碰到过leetcode
,CC150原题。之前也看了不少杂书和advanced topic, 花了不少功夫准备,不过因为
其他事情中断了复习,最后突击了一下,这点还是希望大家引以为戒。
也许是大家都刷题bar高了,基本上全是算法而且要求写code且量不小,所有题都要推
到optimal解法, 至少有三个面试官没有循循善诱,而是赤裸裸的不到最优解不让写
code外加鄙视。后来自己从最优解回头看所有题目,各种呵呵。
面经只包括主要的题目,面试前后扯淡神聊的都没记录在内。我的表现也自然有好有坏
, 面试官看上去都很nice,可惜题目摆在那里,我水平不够,想放水都难。我简历是越
来越挫,G家还这样招待我教我做人,水平确实有限就不高攀了,自己回去闭关反省了
,希望能帮到大家。
电面1:
expr ::= int | ‘(‘ op expr… ‘)’;
op ::= ‘+’ | ‘*’;
“( * 1 ( + 1 2 3 ) )” => 6
“( * ( + 1 1 ) 17 )” => 34
“7” => 7
( * ( + 1 1 ) 17 )
( * 17 ( + 1 1 ) )
operator: *+
oprands: (1 (1 2 3)
这题特别要求一个运算符可以对应任意个数。
电面2:
Q1: Hash VS BST
Q2:
Suppose we are planning a company party. The company organizational
structure is so that there is a single Owner who runs the place.
Everyone has one direct manager, but a manager may have any number of direct
reports. Everyone must report to the owner, possibly indirectly.
Each employee has associated with him a non-negative “fun” value. What we
want to do is invite the set of employees to make the party as fun as
possible.
Here is the only constraint: If you invite an employee, you cannot invite
that employee’s direct manager.
A
B C
I J D E
F G H
If we include A: total fun value should Fun(A)=sum_{i=I,J,D,E}(Fun(i))
no A: Fun(A)={Fun(B)+Fun(C)}
It’s legal to invite B and C
Or it’s legal to invite D, E, A, but you cannot invite D and C, or B and A.
后来复习时才注意到这是party at Hali-Bula,经典树形dp。面试时现推的树形dp,才
拿到positive feedback。
Q3:
machine learning 101 若干题
Onsite:
1
a) counting sort 变种
b) 有若干个盒子,每个盒子有length和width,不考虑高度。只要尺寸fit,大盒子就
可以放小盒子,但是一层只能套一个,即便还有空余;但可以多层嵌套。
求最小的面积放所有的盒子
比如 7*7 5*5, 4*6, 3*3
答案是7*7+4*6
2什么时候 java memory leak: 吓唬了我很久,给了一个得是多年互联网架构从业经
验的答案。
Given a single list
A->B->C->E….->Z A is Node type, B is Node Type
Node[] result = compute()….
Node {
T value;
Node next;
}
Find how many clusters in the array “result” Node’s value could be
anything, not directly comparable, the LinkedList is the order.
the cluster means all the Node in the cluster is consecutive in the list.
for instance,
result: D E F J G H C
cluster 1 c d e fg h
cluster 2 j
3
n x n parcels in city; matrix M contains the cost of each parcel; budget B
largest rectangular area in the city you can afford.
4
在social network中,如何推荐陌生人中和自己共同好友最多的人。不用想歪了,直接
要求用mapreduce解,完全是考这个经典算法的trick。
5
a) you have a Queue array, Queue<Integer>[] queues,get the shortest length
queue,返回的是queue的index。pop is expensive.这个queue是动态更新的,肯定不能
直接size();
b) find the queue with min sum queue, all with non-negative numbers.
剰20分钟不到时,狗血follow-up: implement a heap from scratch, all member
functions
写出来后,面试官居然不知道先fill了然后建heap是O(n),给他解释了半天。
让我瞬间想起了ak47关于代码量训练的经典文章。
电话面试45分钟,上来问了一下简历和project,然后两道coding.
1.数组nums中有n个非负整数(整数用字符串表示),将它们以一定的顺序拼接,得到最小的整数。
样例:n=4 nums: ["54", "546", "548", "60"] 可以拼接得到的最小整数为"5454654860"。
2.给一个n个node的BST,给一个Key,返回与key最接近的m个node(m<N).
(二叉树 找前驱 和 后继)
四叉树 serialization和deserialization
Onsite完,应该是挂了。
第一轮,越南人,黑脸
问google search的时候auto complete怎么弄的,答trie, 然后要求实现建树,和给出
所有auto complete的结果。然后follow up了结果有序,如果是非英文情况和在多台机
器上如何优化。都答出来了,写了80多行code累死我了。
第二轮,亚裔,很友好。
leetcode俩题,加一个design,关于音乐app的。都不难,应该没什么问题。
第三轮,中年老美+shadow,正常
read4k,我应该是可以写出来的,不过面试官尝试给hint然后要我按照他的套路写,结
果就写的略混乱。
第四轮,年轻老美,黑脸
有一个无序数组, 和一个数 x,要你找这个数组里triplet, a + b + c <= x 的个数
。这个题只给了基本解之上的优化,回来之后查了好像用什么binary indexed tree.
非常不好想。。。
第五轮,欧洲人?很友好
给你一些string,比如
A: BCD
B:E
F:G
表示A和B, C, D有关联,B和E有关联,F和G有关联,
然后再给你两个字符问这两个是不是有关联,建图, DFS搞定。
第二题问了anagram substring match的问题。 sliding window + rotate hashing 搞
定。
1. 国男
2sum
数字有重复,比如如果sum是10,{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
Merge interval
对我的最后solution表示很满意。
2. 国男
stream of strings like this
"1 34 5 6"
"3 4 5 6 3"
"4 5 6 3 3"
...
每行是一个包含数字的string。去除所有数字完全重复的strings.比如这里的第二和第
三行数字完全相同,可以合并成一个。要求合并所有数字完全重复的strings。
最后表示对我的优化结果不满意。
3. 有点像东南亚或者拉美后裔,英文无口音
Reverse linkedlist
不断要求优化。
4. 欧洲人
写一个小游戏。MxN 的格子上有一条蛇,蛇头可以向前,左,右移动,撞到自己身体任
何部位或者撞到边界就算死。
5. 阿三
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
我给的方案是用HashMap<Timestamp, count>,分布存到多台机器上面。阿三表示数据很
多,每台机器的内存都存不下,让我优化。我的进一步方案是再设定一个时限T,过期
的数据可以丢掉。阿三要求进一步优化。我的再进一步方案是对于这个对于这个时限T
再分割成n个小格。这个n需要通过实验根据具体实际情况来确定。如果在T/n时间里面
,某些Timestamp的count小于某个设定值,比如0.01N,认为这个timestamp被收集到0.
99N的可能性已经趋近于0,可以忽略了,从HashMap里面删除。最后阿三还是表示不满
意,不能完全理解我的方案。
已挂,感觉比较大可能是挂在国男2和那个阿三手上了,当然不排除其他人表面表示满
意,实际有保留。不管怎样,下面接着投简历,接着面。Offer总会来的,祝版上所有
人都拿到理想的offer。
顺便给自己求一下内推:
背景:CS Master一年半工作经验,最近主要用Java开发web,Master期间做过涉及Data
Mining的项目。好几年前有过第一次尝试startup的经历,目前在尝试第二次,希望能
relocate到湾区,因为这里是我一直向往的创业圣地。所以我找工的目标是湾区的
Software Engineer。我同样也很想结交有创业意愿的朋友。非常感谢!