昨晚的Google Intern Interview - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

昨晚的Google Intern Interview

昨晚的Google Intern Interview# JobHunting - 待字闺中

P*A2010-05-28 07:05

1 楼

有生一来第一次interview，题很简单，但是表现的很糟糕；看来需要补的功课还很多
啊:)
1. 在n x n matrix中查找一个元素，row都是有序的。
2. 25匹赛马，5条跑道，最少赛几次找出最快的3匹马。
3. （Coding）一个binary sequence，找一个划分位置尽量使1分在一边，0分在另一边
；混在0堆
里面的1和混在1里面的0都是error。设计算法使error最小。
第一位阿三兄还问了些数据结构的问题，很窘的是我居然吧heap解释成binary search
tree了。
第二位是个名校的fresh phd，他跟我说是第一次面人，还聊了聊research，由于面的
不好，我都想
赶快挂电话回家睡觉了（人在新加坡，已经半夜了），他还非跟我聊（估计是安慰我一
下，哈）。
两大哥都挺nice的，让你明明知道面的不好，没啥戏了，心情也不会难受。
主要是没办法静下心来思考，经验少，基础也不好。
祝大家都有好offer:)

h*k2010-05-28 07:05

2 楼

1.对每个row做binary search?有更好的方法么？
2.突然发现这题其实是young tableau的一个应用。
3.应该就是线性扫描一遍了，

search

【在 P*A 的大作中提到】

: 有生一来第一次interview，题很简单，但是表现的很糟糕；看来需要补的功课还很多
: 啊:)
: 1. 在n x n matrix中查找一个元素，row都是有序的。
: 2. 25匹赛马，5条跑道，最少赛几次找出最快的3匹马。
: 3. （Coding）一个binary sequence，找一个划分位置尽量使1分在一边，0分在另一边
: ；混在0堆
: 里面的1和混在1里面的0都是error。设计算法使error最小。
: 第一位阿三兄还问了些数据结构的问题，很窘的是我居然吧heap解释成binary search
: tree了。
: 第二位是个名校的fresh phd，他跟我说是第一次面人，还聊了聊research，由于面的

Z*Z2010-05-28 07:05

3 楼

3. 一遍是怎么做到的？我觉得怎么也得2、3遍？

【在 h**k 的大作中提到】

: 1.对每个row做binary search?有更好的方法么？
: 2.突然发现这题其实是young tableau的一个应用。
: 3.应该就是线性扫描一遍了，
:
: search

z*n2010-05-28 07:05

4 楼

两遍吧
就是每一个位置（一遍），算下error（需要左右scan，第二遍），选error最小的位置

【在 Z*****Z 的大作中提到】

: 3. 一遍是怎么做到的？我觉得怎么也得2、3遍？

p*h2010-05-28 07:05

5 楼

弱弱地问下，young tableau是什么，有通俗点的做法么？

P*A2010-05-28 07:05

6 楼

1我也是说这个，但他说应该有更好的。我觉得应该把row之间在联系一下，但是没想出来
3咋一遍做好，能细说说么

【在 h**k 的大作中提到】

: 1.对每个row做binary search?有更好的方法么？
: 2.突然发现这题其实是young tableau的一个应用。
: 3.应该就是线性扫描一遍了，
:
: search

l*a2010-05-28 07:05

7 楼

for(i=0;i{
//a is how many 1's appeared till Array[i]
//b is how many 0's appeared till Array[i]
//if we split the array after a[i],then the error number in the left
side is b(leave 1 on the left) or a(leave 0 on the left)
//for another side, assume there are c 1 and d 0,then the error umber
is c(leave1 on the left) or d(leave 0 on the left) ,but pay attention that
a+c is fixed and b+d is fixed,
so c=NumOne-a and d=NumZero-b
//so b+c=numOne+b-a, a+d=NumZero+a-b
//what

【在 P*A 的大作中提到】

: 1我也是说这个，但他说应该有更好的。我觉得应该把row之间在联系一下，但是没想出来
: 3咋一遍做好，能细说说么

l*a2010-05-28 07:05

8 楼

there is no any condition between rows..
is it possible that u lost some conditions?
such as the famous issue:row/column are all sorted

出来

【在 P*A 的大作中提到】

: 1我也是说这个，但他说应该有更好的。我觉得应该把row之间在联系一下，但是没想出来
: 3咋一遍做好，能细说说么

s*n2010-05-28 07:05

9 楼

See: http://en.allexperts.com/q/Puzzle-Solving-1841/f/Puzzle-5.htm
Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.
Have a race each for all the horses in each set. This makes it a total of 5
races, one for each set.
Now, have a race for the winners of each of the previous 5 races. This makes
it a total of 6 races.
Observe the position of each horse in the 6th race and correspondingly
number the sets. i.e. the set of the winner of 6th race will be said to be
set no. 1 wh

s*n2010-05-28 07:05

10 楼