w****a
发帖数: 710 | 1 Google Onsite (onsite 地点在欧洲，伦敦)
本人 2013 9月毕业的master,在欧洲上学,申请 mountain view Software engineer,
new Grad.
现场提供Chrome book+Google Docs,如果有需要,不必白板
1. 简单的 if n even then n = n/2, if n odd then n = 3*n-1;
终止条件是 n==1
这似乎是一个数学证明上的难题,面试要求只是让我 n总共的 even count 和 odd
count
面试官从一开始就表示会有overflow,并且我们无法知道overflow的上界是多少.
我先无视overflow 条件,写出一般解法
然后接着分析: if n == odd, 3*n + 1 is even, then we can do: n = (3*n+1)/2 =
n + (n+1)/2
发现依然无法解决overflow的问题
然我我建议用BigInteger(面试官提示:you are on the right track). 此时我仍没想
到更好的解法
于是用C++ 写了BigInteger(也就是大数组)的 一个 multiple 和 一个 divide 函数
接着面试官说对于每一位我用vector 太浪费,怎么优化. 我说 可以用char/或者
把一个int来装8位
面试官依然不满意,要求我不能浪费任何资源,我才灵光一闪:bitset
好吧 time out. 估计没什么好feedback...
2. find min and max in an array. 我用了最基本的解法
if (arr[i]
else if (arr[i]>max) max = arr[i]
然后面试官直接告诉我 有一个算法(算法导论上好像见过):
compare arr[i], arr[i+1] -> tmin, tmax
compare min, tmin
compare max, tmax
然后问我我的算法时空复杂度,最坏情况,以及他的算法的时空复杂度和最坏情况
并让我比较哪个方法在什么时候好
Snake and ledder: 求从src 到dest至少需要要多少次dice(dice:1-6)
不需要写代码. 让我跟他讲解决思路
我就给他走了一遍BFS.
follow up是:"how you gonna test it". 我想不到好方法.于是说:设计多个算法.比较
result.
3. 这家伙出了一个貌似自己也不怎么会做的题:
在x,y平面上有一些正方形的房子. 如果用它top, down, left, righ(data type:
float)来描述这些房子的话, down永远是0 (房子不会在天上)
接着把所有房子的正方形涂黑,要我list 黑色区域的顶点
我先打算枚举所有的case.枚举到一半面试官不是很满意,给我一个hint,让我先focus
on x轴
我和他一起试了一下 发现他的建议还不如我的(其实当时我也是脑子一片空白,所以如
果真有好解法没想到也未可知)
我后来跟他说一个computer vision里面常用的contour following 于是这道题变得非
常简单
把float映射到int,然后做contour following
可惜.我现在白板上写的,发现不合适,写起来太慢太麻烦,转到用Google Docs的时候,只
够把整个prototype写好,里面的细节没时间写了..
最悲催的一轮.一开始在Chrome book 里写就好了
午饭,一个中国小哥带我吃的. 不敢吃很多啊
4. 一个疑似巴基斯坦哥.(老印也有可能)
Topological sort. 他不让我写完代码,让我建个图就完事了,不用写后面的sort (不知
道是不是在整我)
一个更儿戏的设计题 根本没让我整理思路 就他一直在follow up:
先问我怎么设计一个 刷卡开门系统的数据库. 我还打算画一个state machine 给他
(这里略过我具体的回答)
a. 他说不用,就考虑lock - unlock状态,假设每个卡有一个id
b. 假设不同的门有不同的priority
c. 假设有些人的id可以同时打开Google Lond 和 Google MV的门
d. 假设这个人的卡丢了
, etc.
整个过程我都在见招拆招(所以feedback可能不会很好). 如果一开始把所有东西都考虑
一遍一步到位就好了.
5. 一个中国人
上来先问我对什么技术感兴趣啊什么的. 我先跟他走了一遍我学CS五年的历程已经自学
的经历.并说喜欢C++的开发之类的
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
int data;
list nodes;
};
我一开始写成vector了,后来改的list
5.2 an online stream, with infinite numbers, tell me the most frequent
number
经典题啊 见过好多次,可惜我每次都没到google搜一下好的做法..囧
我先建议用 array 计算count + heap 得到the most frequent number. 由于 max
number = 2^64
这个方法要消耗大量的空间
接着我建议用hash + heap.
然后我主动说 由于是infinite的. 如果我们空间不够的时候.我们需要抛弃一些数据
于是我建议抛弃 heap的底部那些数据..
面试官不会上这个网站吧.. 遮脸 奔走..
去面试就是为了圆个Google onsite梦,结果已经不重要了.
由于习惯见招拆招,不善于未雨绸缪,可能有些面试官不会喜欢.
Anyway. Good luck everyone. | w****a
发帖数: 710 | | a******e
发帖数: 5411 | | q****x
发帖数: 7404 | 4 5.2 an online stream, with infinite numbers, tell me the most frequent
number
没好解法吧。
【在 w****a 的大作中提到】
: 大家bless吧！
| c***s
发帖数: 192 | 5 第三题应该是长方形吧，就是skyline的另外一种说法。
其实就是interval merge的一个变种，这个我面google的时候也碰到了。
可惜当时想到了讲题目转化成interval merge，但忘了应该利用priority queue。
结果给了两种解法，一个是O(N^2) (排序直接一个一个比较), 一个是O(N(logN)^2) (
divide and conquer).
但就是没给出最优的也是最简单的算法O(NlogN).
结果onsite就悲剧了。
【在 w****a 的大作中提到】
: Google Onsite (onsite 地点在欧洲，伦敦)
: 本人 2013 9月毕业的master,在欧洲上学,申请 mountain view Software engineer,
: new Grad.
: 现场提供Chrome book+Google Docs,如果有需要,不必白板
: 1. 简单的 if n even then n = n/2, if n odd then n = 3*n-1;
: 终止条件是 n==1
: 这似乎是一个数学证明上的难题,面试要求只是让我 n总共的 even count 和 odd
: count
: 面试官从一开始就表示会有overflow,并且我们无法知道overflow的上界是多少.
: 我先无视overflow 条件,写出一般解法
| a*******3
发帖数: 27 | 6 5.1感觉没那么简单？
主要是没明白“split”的定义是什么？树种的任一条边都可以cut么？ | x*****0
发帖数: 452 | | l*****a
发帖数: 559 | | c****m
发帖数: 179 | 9 5.1？是说尽量把每两个node划分为一个subtree，递归枚举所有情况，寻找valid的
case？ | d*******3
发帖数: 58 | 10 这题是InterviewStreet上EvenTree那题，就是cut掉尽可能多的边，形成子树，同时要
保证子树包含的节点数是偶数的。这个递归的计算以每个节点为根的子树包含的节点个
数，如果是偶数直接cut掉就行。
【在 a*******3 的大作中提到】
: 5.1感觉没那么简单？
: 主要是没明白“split”的定义是什么？树种的任一条边都可以cut么？
| | | l**b
发帖数: 457 | | w********p
发帖数: 948 | | w****a
发帖数: 710 | 13 Google Onsite (onsite 地点在欧洲，伦敦)
本人 2013 9月毕业的master,在欧洲上学,申请 mountain view Software engineer,
new Grad.
现场提供Chrome book+Google Docs,如果有需要,不必白板
1. 简单的 if n even then n = n/2, if n odd then n = 3*n-1;
终止条件是 n==1
这似乎是一个数学证明上的难题,面试要求只是让我 n总共的 even count 和 odd
count
面试官从一开始就表示会有overflow,并且我们无法知道overflow的上界是多少.
我先无视overflow 条件,写出一般解法
然后接着分析: if n == odd, 3*n + 1 is even, then we can do: n = (3*n+1)/2 =
n + (n+1)/2
发现依然无法解决overflow的问题
然我我建议用BigInteger(面试官提示:you are on the right track). 此时我仍没想
到更好的解法
于是用C++ 写了BigInteger(也就是大数组)的 一个 multiple 和 一个 divide 函数
接着面试官说对于每一位我用vector 太浪费,怎么优化. 我说 可以用char/或者
把一个int来装8位
面试官依然不满意,要求我不能浪费任何资源,我才灵光一闪:bitset
好吧 time out. 估计没什么好feedback...
2. find min and max in an array. 我用了最基本的解法
if (arr[i]
else if (arr[i]>max) max = arr[i]
然后面试官直接告诉我 有一个算法(算法导论上好像见过):
compare arr[i], arr[i+1] -> tmin, tmax
compare min, tmin
compare max, tmax
然后问我我的算法时空复杂度,最坏情况,以及他的算法的时空复杂度和最坏情况
并让我比较哪个方法在什么时候好
Snake and ledder: 求从src 到dest至少需要要多少次dice(dice:1-6)
不需要写代码. 让我跟他讲解决思路
我就给他走了一遍BFS.
follow up是:"how you gonna test it". 我想不到好方法.于是说:设计多个算法.比较
result.
3. 这家伙出了一个貌似自己也不怎么会做的题:
在x,y平面上有一些正方形的房子. 如果用它top, down, left, righ(data type:
float)来描述这些房子的话, down永远是0 (房子不会在天上)
接着把所有房子的正方形涂黑,要我list 黑色区域的顶点
我先打算枚举所有的case.枚举到一半面试官不是很满意,给我一个hint,让我先focus
on x轴
我和他一起试了一下 发现他的建议还不如我的(其实当时我也是脑子一片空白,所以如
果真有好解法没想到也未可知)
我后来跟他说一个computer vision里面常用的contour following 于是这道题变得非
常简单
把float映射到int,然后做contour following
可惜.我现在白板上写的,发现不合适,写起来太慢太麻烦,转到用Google Docs的时候,只
够把整个prototype写好,里面的细节没时间写了..
最悲催的一轮.一开始在Chrome book 里写就好了
午饭,一个中国小哥带我吃的. 不敢吃很多啊
4. 一个疑似巴基斯坦哥.(老印也有可能)
Topological sort. 他不让我写完代码,让我建个图就完事了,不用写后面的sort (不知
道是不是在整我)
一个更儿戏的设计题 根本没让我整理思路 就他一直在follow up:
先问我怎么设计一个 刷卡开门系统的数据库. 我还打算画一个state machine 给他
(这里略过我具体的回答)
a. 他说不用,就考虑lock - unlock状态,假设每个卡有一个id
b. 假设不同的门有不同的priority
c. 假设有些人的id可以同时打开Google Lond 和 Google MV的门
d. 假设这个人的卡丢了
, etc.
整个过程我都在见招拆招(所以feedback可能不会很好). 如果一开始把所有东西都考虑
一遍一步到位就好了.
5. 一个中国人
上来先问我对什么技术感兴趣啊什么的. 我先跟他走了一遍我学CS五年的历程已经自学
的经历.并说喜欢C++的开发之类的
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
int data;
list nodes;
};
我一开始写成vector了,后来改的list
5.2 an online stream, with infinite numbers, tell me the most frequent
number
经典题啊 见过好多次,可惜我每次都没到google搜一下好的做法..囧
我先建议用 array 计算count + heap 得到the most frequent number. 由于 max
number = 2^64
这个方法要消耗大量的空间
接着我建议用hash + heap.
然后我主动说 由于是infinite的. 如果我们空间不够的时候.我们需要抛弃一些数据
于是我建议抛弃 heap的底部那些数据..
面试官不会上这个网站吧.. 遮脸 奔走..
去面试就是为了圆个Google onsite梦,结果已经不重要了.
由于习惯见招拆招,不善于未雨绸缪,可能有些面试官不会喜欢.
Anyway. Good luck everyone. | r****r
发帖数: 54 | 14 求大牛
这道题有没有最优解。。感觉楼主的解法已经接近最优了
5.2 an online stream, with infinite numbers, tell me the most frequent
number | w********s
发帖数: 1570 | 15 typedef std::vector > CountList
typedef std::map IntegerToListMap
CountList list
IntegerToListMap map
然后，读到一个元素，如果map[n] == null, 则把n插入到list[1]的set中去
否则，把n插入到list[map[n] + 1]的set中去，并删除在list[map[n]]的set中的n；
最大的frequency元素就是list最末对应的set中的那些元素
插入和删除的时间开销都可以做到O(1)
【在 r****r 的大作中提到】
: 求大牛
: 这道题有没有最优解。。感觉楼主的解法已经接近最优了
: 5.2 an online stream, with infinite numbers, tell me the most frequent
: number
| w********s
发帖数: 1570 | 16 抛弃是有问题的，如果stream接下去的元素都是你抛弃的，咋办？
【在 w****a 的大作中提到】
: Google Onsite (onsite 地点在欧洲，伦敦)
: 本人 2013 9月毕业的master,在欧洲上学,申请 mountain view Software engineer,
: new Grad.
: 现场提供Chrome book+Google Docs,如果有需要,不必白板
: 1. 简单的 if n even then n = n/2, if n odd then n = 3*n-1;
: 终止条件是 n==1
: 这似乎是一个数学证明上的难题,面试要求只是让我 n总共的 even count 和 odd
: count
: 面试官从一开始就表示会有overflow,并且我们无法知道overflow的上界是多少.
: 我先无视overflow 条件,写出一般解法
| r****r
发帖数: 54 | 17 如果超过最大内存怎么办？
对于infinite stream 如果一直不停地记录，总归会超出最大内存，问题就是如何再
不丢失数据的情况下避免这种情况。
我能找到最接近的答案是：http://stackoverflow.com/a/3260905/1074468
不过这个不是最佳答案。最佳答案里的paper大概读了一点感觉太复杂...
不知道还有没有更好的解法...
【在 w********s 的大作中提到】
: typedef std::vector > CountList
: typedef std::map IntegerToListMap
: CountList list
: IntegerToListMap map
: 然后，读到一个元素，如果map[n] == null, 则把n插入到list[1]的set中去
: 否则，把n插入到list[map[n] + 1]的set中去，并删除在list[map[n]]的set中的n；
: 最大的frequency元素就是list最末对应的set中的那些元素
: 插入和删除的时间开销都可以做到O(1)
| w********s
发帖数: 1570 | 18 超出内存么还有外存硬盘。
没有不丢数据的办法，除非按概率给出不精确解。
【在 r****r 的大作中提到】
: 如果超过最大内存怎么办？
: 对于infinite stream 如果一直不停地记录，总归会超出最大内存，问题就是如何再
: 不丢失数据的情况下避免这种情况。
: 我能找到最接近的答案是：http://stackoverflow.com/a/3260905/1074468
: 不过这个不是最佳答案。最佳答案里的paper大概读了一点感觉太复杂...
: 不知道还有没有更好的解法...
| l**********a
发帖数: 181 | | C******w
发帖数: 23 | | f******n
发帖数: 279 | |
|
