真的愤怒的小鸟 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

真的愤怒的小鸟

真的愤怒的小鸟# Joke - 肚皮舞运动

k*n2011-05-03 07:05

1 楼

发面经攒rp，没有NDA，不是中国人面试，题也很trivial，就不用忌讳了。
电面45分钟，没有寒暄上来就coding。
两道题，都是现成的面经题。
一道是有序数组转BST，一道随机数生成。
第一道没思考的直接写出来了，第二道我突然自己发神经要从头推导
结果他把我的意思弄拧了，一着急又讲不明白了
一边举例子一边写，二十分钟一些border case还是没弄清楚。
最后也没写完，不过我的思路他最后突然明白了
剩两分钟问了问他组里的情况。
最后我问他的email，他不给，郁闷死我，以为已经挂了。
不过总体似乎还过得去，过两天就安排onsite了。
总结：
1。能写出来的题直接写出来就好，千万别整妖蛾子，自己把自己玩死。
2。如果要从头推导什么东西，一定老老实实在纸上自己想清楚，
迅速设计好例子，把算法走一边。走通了再讲，不要自己还没讲清楚就讲

r*e2011-05-03 07:05

2 楼

真的。。。

s*y2011-05-03 07:05

3 楼

local的，一个电面就onsite了？

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

: 发面经攒rp，没有NDA，不是中国人面试，题也很trivial，就不用忌讳了。
: 电面45分钟，没有寒暄上来就coding。
: 两道题，都是现成的面经题。
: 一道是有序数组转BST，一道随机数生成。
: 第一道没思考的直接写出来了，第二道我突然自己发神经要从头推导
: 结果他把我的意思弄拧了，一着急又讲不明白了
: 一边举例子一边写，二十分钟一些border case还是没弄清楚。
: 最后也没写完，不过我的思路他最后突然明白了
: 剩两分钟问了问他组里的情况。
: 最后我问他的email，他不给，郁闷死我，以为已经挂了。

b*x2011-05-03 07:05

4 楼

这是北美红雀吗？
好像它头顶上的翎毛老这么竖着。。。

【在 r*********e 的大作中提到】

: 真的。。。

k*n2011-05-03 07:05

5 楼

不是local，不过是在加州。

【在 s*****y 的大作中提到】

: local的，一个电面就onsite了？

Z*e2011-05-03 07:05

6 楼

zan

【在 r*********e 的大作中提到】

: 真的。。。

c*t2011-05-03 07:05

7 楼

这个“随机数生成”到底是什么题目？
是要实现一个类似glibc中的rand()吗？
谢谢！

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

B*e2011-05-03 07:05

8 楼

确定不是PS的？

a*m2011-05-03 07:05

9 楼

一个电话技术面试就onsite很正常呀

【在 s*****y 的大作中提到】

: local的，一个电面就onsite了？

a*e2011-05-03 07:05

10 楼

NG要付钱给AB，用了人家名字

s*y2011-05-03 07:05

11 楼

I thought google always do 2 round phone except for ppl in bay area.

【在 a********m 的大作中提到】

: 一个电话技术面试就onsite很正常呀

s*e2011-05-03 07:05

12 楼

哈哈。太像了。

d*g2011-05-03 07:05

13 楼

俺今天和狗狗电面, 是硬件, 问RLC, MOSFET, 等等, 也很trivial.
还是和果果面爽啊, 三下五除二就搞好了.
不知道狗狗还有木有下文.

a*y2011-05-03 07:05

14 楼

你还别说,北美有很多漂亮的小鸟,就在house周围.

【在 r*********e 的大作中提到】

: 真的。。。

W*r2011-05-03 07:05

15 楼

去G家Onsite的太多了，他们家现在电面标准是越来越松了，有拉大队人马来搞
Sampling的嫌疑

o*12011-05-03 07:05

16 楼

这是哪一期？我是定阅了ngm的，乍没看到涅？？

【在 r*********e 的大作中提到】

: 真的。。。

a*m2011-05-03 07:05

17 楼

据俺所知不是，而且一个在google两年多的朋友跟俺说的也是一次技术店面，如果不是
很肯定留或者据会有第二次店面。bay area和其他地方标准是一样的。

【在 s*****y 的大作中提到】

: I thought google always do 2 round phone except for ppl in bay area.

c*w2011-05-03 07:05

18 楼

ps的...

【在 r*********e 的大作中提到】

: 真的。。。

g*i2011-05-03 07:05

19 楼

第二题随机数生成能具体点吗?谢谢

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

b*x2011-05-03 07:05

20 楼

的确很多，颜色还都很鲜艳。每年都有1-2窝的小鸟在我家后院出生，
嗷嗷待哺的样子，太俘获人心了！

【在 a***y 的大作中提到】

: 你还别说,北美有很多漂亮的小鸟,就在house周围.

l*82011-05-03 07:05

21 楼

我同学，不仅是在bay area, 而且离google office很近。第一轮面试就到google
office去了，不过第一轮也是45分钟。

【在 s*****y 的大作中提到】

: I thought google always do 2 round phone except for ppl in bay area.

k*n2011-05-03 07:05

22 楼

给一个integer数组，一个integer N
要求生成1-N的随机数，但是避开integer数组
数组大小是k的话，可以logK做到
都是套路题，面经看熟就行

【在 g*****i 的大作中提到】

: 第二题随机数生成能具体点吗?谢谢

w*r2011-05-03 07:05

23 楼

哪里有google的面经啊？

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

: 给一个integer数组，一个integer N
: 要求生成1-N的随机数，但是避开integer数组
: 数组大小是k的话，可以logK做到
: 都是套路题，面经看熟就行

k*n2011-05-03 07:05

24 楼

面经是不分公司的，挨排看吧

【在 w****r 的大作中提到】

: 哪里有google的面经啊？

w*r2011-05-03 07:05

25 楼

是本版精华区？还是有哪个网站？

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

: 面经是不分公司的，挨排看吧

k*n2011-05-03 07:05

26 楼

不知道，我是直接扫版面的

【在 w****r 的大作中提到】

: 是本版精华区？还是有哪个网站？

d*n2011-05-03 07:05

27 楼

是指实现大概这样一个函数吗？
int random(int n, int blackList[])
使用现有库随机函数还是自己实现？

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

: 给一个integer数组，一个integer N
: 要求生成1-N的随机数，但是避开integer数组
: 数组大小是k的话，可以logK做到
: 都是套路题，面经看熟就行

k*n2011-05-03 07:05

28 楼

是的，随机函数使用库函数

【在 d***n 的大作中提到】

: 是指实现大概这样一个函数吗？
: int random(int n, int blackList[])
: 使用现有库随机函数还是自己实现？

d*n2011-05-03 07:05

29 楼

这题的考点是什么，没太看出来。

k*n2011-05-03 07:05

30 楼

个人认为没考点，就是拍脑袋。。。

【在 d***n 的大作中提到】

: 这题的考点是什么，没太看出来。

i*e2011-05-03 07:05

31 楼

这个题目是说，产生一个在区间【1，N】的一个数，而且这个数不在这个array 里面
了？如何这样的话LZ怎么可能做到O(logK)呢？ sort 一下区间，或者用hash table
最少也得O(K）了。还是我理解错误了？
bless lz onsite!

k*n2011-05-03 07:05

32 楼

It is easy to simulate a real case.
suppose you have N=15, K={3, 5, 6, 7, 8, 12}
then a function
f(x) = { f(1) => 1, 2=>2, 4=>3, 9=>4, 10=>5, 11=>6, 13=>7, 14=>8, 15=>9 }
maps [1,N] with gaps to [1, N-K]
so g(x) = f^(-1)(x) is what we need.
and g(x) = { g[1,2] = x, g[3] = x+1, g[4-6] = x+5, g[7-9] = x+6 }
the upper limits of the above segments ( with 0-len segments omitted) are
2 => K[1] - 1;
3 => K[2] - 2;
3 => K[3] - 3;
3 => K[4] - 4;
3 => K[5] - 5;
6 => K[6] - 6;
the virtual sentinel is
9 => (N+1) - 7;
So generate a random number x in [1,9], use binary search to find the
segment it resides,
then calculate g(x).
We have (K+1) segments at most, so this is a O(logK) solution

table

【在 i***e 的大作中提到】

: 这个题目是说，产生一个在区间【1，N】的一个数，而且这个数不在这个array 里面
: 了？如何这样的话LZ怎么可能做到O(logK)呢？ sort 一下区间，或者用hash table
: 最少也得O(K）了。还是我理解错误了？
: bless lz onsite!

c*t2011-05-03 07:05

33 楼

kevinn,
你说的是要生成一个数，这个数介于[1, N],但是不在blacklist数组里，对吗？
是指实现大概这样一个函数吗？
int random(int n, int blackList[])
使用现有库随机函数还是自己实现？

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

: 给一个integer数组，一个integer N
: 要求生成1-N的随机数，但是避开integer数组
: 数组大小是k的话，可以logK做到
: 都是套路题，面经看熟就行

s*02011-05-03 07:05

34 楼

多谢如此详细的解说，但这里还是有点弄不清楚segment怎么选，各个segment 2,3,3,3
,3,6代表什么意思 9=〉N+1 - 7是什么意思

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

: It is easy to simulate a real case.
: suppose you have N=15, K={3, 5, 6, 7, 8, 12}
: then a function
: f(x) = { f(1) => 1, 2=>2, 4=>3, 9=>4, 10=>5, 11=>6, 13=>7, 14=>8, 15=>9 }
: maps [1,N] with gaps to [1, N-K]
: so g(x) = f^(-1)(x) is what we need.
: and g(x) = { g[1,2] = x, g[3] = x+1, g[4-6] = x+5, g[7-9] = x+6 }
: the upper limits of the above segments ( with 0-len segments omitted) are
: 2 => K[1] - 1;
: 3 => K[2] - 2;

k*n2011-05-03 07:05

35 楼

可能我表达能力的确很差，所以面试官也被我搞的很晕，唉
所以得多练习啊，苦恼死了

,3

【在 s*********0 的大作中提到】

: 多谢如此详细的解说，但这里还是有点弄不清楚segment怎么选，各个segment 2,3,3,3
: ,3,6代表什么意思 9=〉N+1 - 7是什么意思