|
|---|
|
|
|
|
|
|
g**u
发帖数: 583 | 1 马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
3，number of unique url accesses in huge log files
hashtable + bit vector
讨论hash的实现，bit vector如何快速统计有多少个entry
onsite：
4，老题，爬楼梯一次可以走一级或者两级，爬N级有多少种走法
5，文件读写
有个封装好的函数 int block_reader(char *buf)
内部有个静态文件指针，只能向文件末尾移动，不能rewind
每次只能读取4K的block到buf里，返回读取的字节数（除非到文件尾，否则总是4K）
要求实现 int anysize_reader(char *buf, int size)
从文件的当前位置读取任意大小的数据存入buf，并返回实际读到的数据字节数
白板写code
问题的关键在于anysize_reader会被多次调用，每次都可能不是4K对齐
所以需要自己维护一个4K的buffer
6，系统设计
讨论gmail的user authentication，描述详细的流程，性能瓶颈
如何做load balancing
7，写code实现int sqrt(int n)
用binary search，需要考虑比较多的细节
8，老题，实现分布的LRU cache，要求存取时间O(1)
9，Unix file path化简，写code
例如 /a/./b/../../c/ ，化简为 /c/
用stack或者d-queue，有些细节需要考虑，例如 /..//.. 还是输出 /
10，write code to find all the possible combinations of chars in a given
string
11，a set of intervals, how to tell if a given value is in any of the
intervals
讨论了overlapping的情况，interval tree，etc
还有一些类似难度的题，记不大清楚了。总之不是很难
俺基本功不扎实，倒在了胜利的前夕
希望后来的xdjm们都能传捷报～～～～
http://www.qiuzhihaoyue.com/article_t1/JobHunting/31598671_3160
周二进行了google电面，今天刚刚收到了recruiter的email，说
电面还不错，正在安排onsite。
在版上得意于广大同志们的热心帮助，非常感谢！
分享一下我的电面经过:
我的电面开始的时候interviewer就问我的research背景和相关
一些课题，我在phd期间发表过一些不错的paper，interviewer对于
最好的一篇看起来很有兴趣，让我解释一下motivation，method，
performance，可能存在的性能问题，等等，这个过程大约15mins，因为自己本身比较熟
悉，所以回答的比较主动流利，感觉他也很满意。
然后是算法和coding问题，我觉得我比较幸运，他问的2个算法问题，都是我之前看过的
，出自"Hacking_a_google_interview"那几个pdf里面，其中一个是"Axis-Aligned Rec
tangle"问题，我觉得是因为我是来自computer graphics的方向，interviewer特地挑了
这个和graphics背景相关的问题问我，因为这个和Axis-Aligned BoundingBox其实是差
不多的。还有一个问题就是median value from an int array,我说了那个O(N)的divid
e-and-conquer的解之后，他又问我，如果他要经常地取从index=0到index=k的元素之间
(k是变化的)median值，提示可以预计算一些数据，问如何处理，我想了一会没有答上来
。他又问如果是一个binary search tree如何寻找median值，我当时因为紧张也没想出
来，（面试之后，平静了一下就想明白了，其实只需要做inorder traversal找到N/2元
素就可以）
coding题目比较简单就是非迭代的binary tree preorder traversal，我之前有练过这
个code，所以应该还行。
之后他说我可以问他1-2个问题，我问了他觉得如果是phd进google，research ability
对于product的贡献一般体现在什么地方？他很nice的回答了我。
然后我问了他是那个group的，然后问了他的email。
结束总共大约40分钟。
我第二天清醒之后，给interviewer发了一封thanks letter，基本都是自己的体会和想
法，应该比较真诚。
整体的过程就差不多这样，我自己当时其实感觉不好，觉得自己当时算法有一些没有回
答出来，以为就挂了，今天突然收到说interview went well正在安排onsite，觉得有些
幸运，我觉得可能google对于我的research background还是很有兴趣的，能够onsite我
觉得可能有这个原因，至少我之前准备了一些dp，在电面的时候还是没用上。
最好祝福所有后来的电面同志们都好运！
并向大家请教一下onsite的建议，是不是会很多白板coding？我可能需要大量地联系算
法coding了，还有就是关于软件设计方面？说实话，自己平时写自己的程序框架做rese
arch coding，但是设计肯定是不专业的，有些担心这个方面，大家如果有什么好的建议
，请不吝赐教，非常感谢！
http://www.mitbbs.com/article_t/JobHunting/31610567.html
第一轮电面通过了，之前recruiter说安排onsite
但因为我在欧洲，recruiter希望我能飞到US来onsite，
也许为了保险起见，要求进行第二轮电面，今天晚上
刚刚电面结束了。准备面试过程中一直得到板上朋友
的帮助，非常感谢！把问的问题和大家分享一下:
上来第一个问题是问我为什么对于google有兴趣?
我自己是computer graphics的PHD背景，我按照
我自己的情况和他说了一下发现google最近推出了
webGL标准的O3D SDK， 还有就是最新的3D google
map，其中我发现3D map在terrain方面感觉绘制还
需要提高，balabala。。。 这个过程大约10分钟
左右。
第二个问题是关于描述一个自己coding以来最难的
debug case。 我结合自己的背景，讲了一个自己
当时在GPU shader里面debug linear quadtree
traversal的问题。其实不是很难，不过我自己觉得是一个
有意思的问题。大约10分钟。
第三个问题是给一个simple code:
char* F()
{
char S[100];
sprintf(S,"Hello World!\n");
return (S+6);
}
void main()
{
printf("%s\n", F);
}
分析这个程序的结果。 我指出这个S[100]是local
变量 in stack，这个程序有问题， 讲了一下
应该如何修改的几种可能性。
最后一个问题是问，如果设计一个web crawler，
抓一个页面的url只好，分析这个页面里面所有的
link url，记录不重复的new url，问需要什么样
的数据结构。
我回答是url不重复，有unique性，可以考虑hashmap。
另外从一个url到下一层url，设计一个tree，每个treenode
里面包含一个vector动态数组来记录新的子节点的pointer。
然后进一步问，如果有1000台电脑运行web crawler，应该
如何设计程序运行。
最后我问了他一个问题。想问一下email写thanks letter，
interviewer说不太愿意leak私人信息，口头表示感谢。
整体的过程大约就是这样的，
我自己的感觉其实回答的一般，特别是最后一个设计题，
我自己没有这个方面的经验，也从来没做过，所以只能
是按照自己的理解和临场发挥去表达，肯定不是最优的。
应该3天左右就有消息吧，希望自己好运，
最后祝福大家jobseek都好运！
Google phone screen
http://www.mitbbs.com/article_t/JobHunting/31533727.html
刚刚面的电面，心里没底啊。
1. Given a sorted integer array and a specific integer, find the
first position of that integer. Array contains lots of
duplicate.
我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
该是会快点啊。
2. 有很多doc，里面有很多电话，怎么查找电话。
我说只是一次用的，hash一下找，如果以后还得用的话，就sort他们，然后按area
code做一个B tree什么的。
3. 在一个resume里面找电话。
我说如果是US的话找一个连续是10个digit的，或者中间有（）或-的，然后查头三个
digits是不是valid的area code。 这样对吗？
4. 电话key pad上2-9每个代表了3个char，给你一个字典，还有一串数，找出
valid的word。
一开始他给我的是3个digit的，然后我就说找出这27个combinations,然后去字典里
找是不是valid的。他问那这个有什么问题，想了想说是不是如果digit太多的话，
combination算很久。他也没对还是不对。就说如果给你一个很长的digit，怎么找。
我就说在字典里找出长度为这么长的所有单词。然后从第一个digit开始，选出第一个
字母是这个个digit表示的单词。全选完之后再接着第二个数字那样筛选。最后得出来
的就是valid的。
心里没底，也没想到更好的方法。面得那个人也好像没什么hint，不知道是对还是错。
sigh~~ 牛人们，有什么更好的方法吗？
Google phone screen
http://www.mitbbs.com/article_t/JobHunting/31569139.html
刚面完，感觉一般，估计挂了....
寒暄，文件里上的project,接下来算法：
find majority element in an array. 我说用hash table，但是空间效率
低，我自己说了个constant space的idea, 写code。 写完问我怎么extend
to最一般的情况, 我说了自己的idea, 然后说什么时间不够了，就不用写代码了，
他理解啥的.....
http://www.mitbbs.com/article_t/JobHunting/31831221.html
Google two phone screen
Phone 1:
:
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra space
Binary search? No, worst case is O(n)
1) # of unique chars
2) Bit vector for each
I did not know KMP and Robin Karp at that time, i guess it is the desirable
solution for the interview :(
Given a perfect random generator Random(n) which can generate number between
[0,1], write a program to generate a random pair of (x, y) within a circle
of radius 1, and with (0,0) center with uniform distribution inside the
circle. What is the expect probability of values fall into the circle? | S*****e
发帖数: 229 | 2 感谢分享，收藏了。
bless!
【在 g**u 的大作中提到】
: 马上就要G on site了，
: 求祝福。
: 下面是从本版收集到的Google的试题，便于大家查询。
: 申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
: http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
: 本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
: 同学内部推荐的，很简单的一次电面就给了onsite
: 题都不难，但是自己没把握好机会，出了一些小bug。
: 总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
: 电面：
| R********s
发帖数: 3420 | 3 big bless ...
【在 g**u 的大作中提到】
: 马上就要G on site了，
: 求祝福。
: 下面是从本版收集到的Google的试题，便于大家查询。
: 申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
: http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
: 本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
: 同学内部推荐的，很简单的一次电面就给了onsite
: 题都不难，但是自己没把握好机会，出了一些小bug。
: 总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
: 电面：
| i**********e
发帖数: 1145 | 4 感谢分享，并祝福 LZ.
【在 g**u 的大作中提到】
: 马上就要G on site了，
: 求祝福。
: 下面是从本版收集到的Google的试题，便于大家查询。
: 申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
: http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
: 本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
: 同学内部推荐的，很简单的一次电面就给了onsite
: 题都不难，但是自己没把握好机会，出了一些小bug。
: 总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
: 电面：
| t********r
发帖数: 847 | | A*****1
发帖数: 1738 | | x******2
发帖数: 546 | 7 赞
【在 g**u 的大作中提到】
: 马上就要G on site了，
: 求祝福。
: 下面是从本版收集到的Google的试题，便于大家查询。
: 申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
: http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
: 本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
: 同学内部推荐的，很简单的一次电面就给了onsite
: 题都不难，但是自己没把握好机会，出了一些小bug。
: 总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
: 电面：
| f**b
发帖数: 3043 | |
|
|
|
|
|
|
|
