http://www.mitbbs.com/article_t/JobHunting/32960525.html
1. 一块矩形面板上有黑点， 白点， 红点
给一个起点，找出和这个点颜色相同，且相连的点组。 求这个点组的周长
给一个字典，一个字符串， 找出可以由这个字串合法转成的最长单词。 转换操作
时删除一个或多个字符
2. 设计贪吃蛇
怎么定义蛇， 怎么移动， 怎么吃， 怎么判断时候活着， 怎么定义游戏版
3. 设计售票系统， 要求
1. 每次返回5张可选最为
2. 保证不会给两个不同user返回同一个可选座位
3. 用户2分钟之内，没有购买，重新开始
moving average
要求， 内部用一个 固定大小数组
4. letter combination of phone number.
我写了递归的， 要求继续写迭代版本的。 这个在它提示下，才做出来了， 很
tricky ， 没练过
5. 一个circle 列表。Circle 有x,y,r
1 ------------------------
0 ----------------------------
判断是否有一条路径可以从 负无穷到正无穷。
如果一个活多个circle完全block了通道，就没有路径
http://www.mitbbs.com/article_t1/JobHunting/32961687_0_1.html
（1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
而index 1 上 s1和s2都是b，则不是difference.现在只许你swap一次 S2
的两个字母，问如何才能
最大程度的减少difference， 需要return swap的两个index，比如上面的例子， 我们
swap s2的 0 和 2， 就会把s2变成 abc， 和 s1的 difference 是 0.
这题我用hashmap 做的，注意考虑difference最多只能减少1的情况
（2）小哥很nice的问我咱是来个简单的还是难的，我自信的花样作死说咱要来就来
难的，小哥说好。
桌子上有3n个object围成一个圈， 每个object都有一个value， 你和你的两个好朋友
每次各从桌子上拿一个，你先选，之后你的朋友再选，而且你的朋友只能拿你拿的那个
object的左右相邻的两个。问如何才能让你自己拿的objects的value的总和最大
？（注意不是总和比朋友大，而是在自己所有不同拿法中总和的值最大）
这题就卡住了，我只能勉强总结出自己拿的两个object不能相邻，但是不能证明
面完这轮后小哥很nice的跟我说做不出来没关系，这题没人做出来，接下来好好面就行
了，感谢啊！
第二轮白人小哥
new grad面system design也是醉了，问有个服务器，如果有用户短时间内向服务器发
送大量的request如何处理
这题只能闭着眼睛瞎说了，扯扯sampling，last request time，呵呵呵。。。
lunch
第三轮南美小哥
问如果找一棵树里面所有和为target的path，path可以从任何node开始，不一定要从
root开始
follow up，如果不是和为target，而是乘积为target呢？
follow up， 如果树很大，如何distributed 处理？
第四轮白人大叔
（1）有一个数列，数列中的数range在0-100之间，而且每个数最多只出现一次
如何找出这个数列中的missing range？
如果不用hashmap，用其他数据结构怎么做？大叔提示说用一个101bits的数来表示
（2）有个string， 找出第一个出现的unique char，比如google，return“l”
面试感慨，瞎准备了半天range tree， binary indexed tree， sweep line，结果还是
白忙了
http://www.mitbbs.com/article_t/JobHunting/32542339.html
leetcode原题，Valid Panlindrome
"A man, a plan, a canal: Panama" is a palindrome.
这题之前做过，也很简单，但当时太紧张出了一个很sb的bug，还是在面试官提示下找
到的。15行的代码出bug实在是不能犯的错误。另外在判断一个char是否letter的时候
没有另用函数把一堆&&写了两次，被批评不够简洁。
第二题，将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，不能用额外空间
第一遍用了recursive很快解决，被指出用了stack额外空间，开始改iterative
facebook非常重视coding的clean和bugfree。 这两题都没什么算法但是如果
coding不过硬第一遍很容易有bug
CSS里面表示颜色用
#abcdef (eg 0x1F2A3B) 这种形式， 每个字母代表四个bit (hex)，两个字母代表一种
原色
比如 ab = R, cd = G, ef = B (每种原色整个是0-255间的一个数字)
现在需要压缩空间改#abcdef 为 #xyz
实际上#xyz = #xxyyzz,所以减小一半，问怎么找到最好的压缩让
（ab-xx）^2 + (cd - yy)^2 + (ef - zz)^2 最小
这题其实数学上很简单因为三个维度是分开的，其实就是找#ab到#xx的压缩。
贡献一下：本版上搜集的 Google 面试题
1)Using c/c++ or Java, how to track stack grow up or shrink down
2)Assuming speed is more important than storage, how do you count the number
of bits that will set in 32 bit integer.
Q: 如何count任意一个整数中有多少个二进制的1
Q:在Web Crawler中，如何快速检查一个URL是否已经被check过
Bloom Filter
我的回答：建立一批Hash table，每个表用不同的Hash Function，对每个URL，检查每一个Hash 表。具体算法，如何计算conflict，我也不清楚，但这是NLP中的常规方法。
Q:如何很快地确定某一页是否是黄色网页
我的回答：训练一个分类器，对training data中的每个网页提取一些
描述参数 （举一些可能的属性），训练classifer，然后用。
我推荐C4.5，他就说你文章上好像是Boosted Naive Bayes最好，解释
那是旧的，新的结果是C4.5最好，申明应该试不同的classifer，然后
选一个最好的，例如：NN, SVMs,... It really depends.
Q: 具体编程中的实际最大问题
我的是bound check 和memory leak，我是真的花上过2 weeks去找一个memory leak。
1. Find links/urls from one html page using C++, then how do you store those
links that you found.
2. Design a schema for actors and movies database (one actor can be act one
or
more movies and one movie has more than one actor). Search name of actor,
you
can get a list of movies and search name of movie, you can get a list of
actors. 我数据库老早以前上过一门课，现在全忘光了。:(
3. In a linked list find the nth node from the end of this list.
4. questions about interface and abstract class.
1. design a data structure, this data structure have four functions: pop,
push
, min, top. DO NOT use any stack, queue, list, array or things like this.
2. two binary trees, write a compare function to check if they are equal or
not. equal means they have the same value and same structure.
3. how do you test a calculator.
4. questions about c++, like virtual functions, etc.
Given N computers networked together, with each computer storing N integers,
describe a procedure for finding the median of all of the numbers. Assume
that
a computer can only hold O(N) integers (i.e. no computer can store all N^2
integers). Also assume that there exists a computer on the network without
integers, that we can use to interface with the computers storing the
integers
.
step 1:
sort on each one of those N computers. takes N*N*longN time. If we consider
the
concurrency the overall time taken could be NlogN
step2:
transfer the smallest number on each of thse N computers to the spare box
and
sort them, also need to keep the information about which computer the
number
comes from.
this takes NlogN time
step3:
after sorting, throw the smallest number out and ask that speicific computer
where the smallest number come from to get the second smallest number, then
resort the numbers on the spare computer. repeat this step untill u have
thrown out N*N/2-1 numbers out, then on the spare
computer the smallest number is the global median number
This step takes NlogN+N*N/2*longN
How to serialize and deserialize 1) a binary tree and 2) a binary graph?
1. How did you get to us ?
2. Which group are you interested in ?
3. Describw what kind of new product you have in mind for google ?
technical :
1. grid problem, how to find the number of paths leading to a character ?
A B D C A
C D A B C
B A C D B
note: any path should startng with A and path should go strictly
alphabetical order. For example, the B in the second row could have two
paths.
2. Book database(very large), how to remove duplicates ? The same book might
have several records in the database due to title misspelling or name
aliases.
- implement a fixed size cache put and get methods. and Least Recently Used
discards
- 两个排序的数组, 找出交集.
=================
Onsite Questions:
=================
The first one: Write the code using an optimization algriothm to calcuate
the
intersection and union of two sets. (30 mins)
The second one: Write the code for an algriothm to transfrom the index in
excel to the number, and write a class to call this function without
declearing an object. for example: "A, B, C,....AB,AC,..BA,BB,....AAA,AAB,..
."
, transform to "1,2,3,.....", and also transform back.(30 mins)
1. 用hash table
2. 基本相当于26进制。比如 aa=26*1+1=27, aaa=26*26*1+26*1+1=something
--------------
1. Compute the quotient and remainder of m/n, without using divisionoperator.
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change.
3. Given an array,
i) Find the longest continuous increasing subsequence.
ii) Find the longest increasing subsequence.
4. A building of 100 floors, there is a threshold N s.t. if an egg drops
from Nth floor and above it will break. If it's dropped from any floor below
, it will not break. Given 2 eggs, find this N, and minimize the number of
drops for the worse case.
5. An OO design problem. It's a problem related to his work, I am not
supposed to disclose details.
6. Design a stack. We want to push, pop, and also, retrieve the minimum
element in constant time.
7. Suppose we have N companies, and we want to eventually merge them into
one big company. How many ways are there to merge?
===============
自己提问的问题：
===============
what the search engine will be in its next step?
他们现在的pagerank基于heuristic，有没有进行利用machine learning 去学习
ranking
other questions
===============
Given a list of numbers ( fixed list) Now given any other list, how can you
efficiently find out if there is any element in the second list that is an
element of the first list (fixed list).
两个很长的string，找出它们的longest common string (连续的），要求n*log(n)时
间。
suffix tree
发些收集到的Google的面经
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
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
其中一个是"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的回答了我。
第二个问题是关于描述一个自己coding以来最难的debug case。 我结合自己的背景，讲了一个自己当时在GPU shader里面debug linear quadtreetraversal的问题。其实不是很难，不过我自己觉得是一个有意思的问题
最后一个问题是问，如果设计一个web crawler，抓一个页面的url只好，分析这个页面里面所有的link url，记录不重复的new url，问需要什么样的数据结构。
我回答是url不重复，有unique性，可以考虑hashmap。另外从一个url到下一层url，设计一个tree，每个treenode里面包含一个vector动态数组来记录新的子节点的pointer。
然后进一步问，如果有1000台电脑运行web crawler，应该如何设计程序运行。
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什么的。
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的。
find majority element in an array. 我说用hash table，但是空间效率
低，我自己说了个constant space的idea, 写code。
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?
Google 的21道面试问题(ZZ)
10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理
》等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。
试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成
为我们其中一员”。
1. 一块矩形面板上有黑点， 白点， 红点
给一个起点，找出和这个点颜色相同，且相连的点组。 求这个点组的周长
给一个字典，一个字符串， 找出可以由这个字串合法转成的最长单词。 转换操作
时删除一个或多个字符
2. 设计贪吃蛇
怎么定义蛇， 怎么移动， 怎么吃， 怎么判断时候活着， 怎么定义游戏版
3. 设计售票系统， 要求
1. 每次返回5张可选最为
2. 保证不会给两个不同user返回同一个可选座位
3. 用户2分钟之内，没有购买，重新开始
moving average
要求， 内部用一个 固定大小数组
4. letter combination of phone number.
我写了递归的， 要求继续写迭代版本的。 这个在它提示下，才做出来了， 很
tricky ， 没练过
5. 一个circle 列表。Circle 有x,y,r
1 ------------------------
0 ----------------------------
判断是否有一条路径可以从 负无穷到正无穷。
如果一个活多个circle完全block了通道，就没有路径
http://www.mitbbs.com/article_t1/JobHunting/32961687_0_1.html
（1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
而index 1 上 s1和s2都是b，则不是difference.现在只许你swap一次 S2
的两个字母，问如何才能
最大程度的减少difference， 需要return swap的两个index，比如上面的例子， 我们
swap s2的 0 和 2， 就会把s2变成 abc， 和 s1的 difference 是 0.
这题我用hashmap 做的，注意考虑difference最多只能减少1的情况
（2）小哥很nice的问我咱是来个简单的还是难的，我自信的花样作死说咱要来就来
难的，小哥说好。
桌子上有3n个object围成一个圈， 每个object都有一个value， 你和你的两个好朋友
每次各从桌子上拿一个，你先选，之后你的朋友再选，而且你的朋友只能拿你拿的那个
object的左右相邻的两个。问如何才能让你自己拿的objects的value的总和最大
？（注意不是总和比朋友大，而是在自己所有不同拿法中总和的值最大）
这题就卡住了，我只能勉强总结出自己拿的两个object不能相邻，但是不能证明
面完这轮后小哥很nice的跟我说做不出来没关系，这题没人做出来，接下来好好面就行
了，感谢啊！
第二轮白人小哥
new grad面system design也是醉了，问有个服务器，如果有用户短时间内向服务器发
送大量的request如何处理
这题只能闭着眼睛瞎说了，扯扯sampling，last request time，呵呵呵。。。
lunch
第三轮南美小哥
问如果找一棵树里面所有和为target的path，path可以从任何node开始，不一定要从
root开始
follow up，如果不是和为target，而是乘积为target呢？
follow up， 如果树很大，如何distributed 处理？
第四轮白人大叔
（1）有一个数列，数列中的数range在0-100之间，而且每个数最多只出现一次
如何找出这个数列中的missing range？
如果不用hashmap，用其他数据结构怎么做？大叔提示说用一个101bits的数来表示
（2）有个string， 找出第一个出现的unique char，比如google，return“l”
面试感慨，瞎准备了半天range tree， binary indexed tree， sweep line，结果还是
白忙了
http://www.mitbbs.com/article_t/JobHunting/32542339.html
leetcode原题，Valid Panlindrome
"A man, a plan, a canal: Panama" is a palindrome.
这题之前做过，也很简单，但当时太紧张出了一个很sb的bug，还是在面试官提示下找
到的。15行的代码出bug实在是不能犯的错误。另外在判断一个char是否letter的时候
没有另用函数把一堆&&写了两次，被批评不够简洁。
第二题，将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，不能用额外空间
第一遍用了recursive很快解决，被指出用了stack额外空间，开始改iterative
facebook非常重视coding的clean和bugfree。 这两题都没什么算法但是如果
coding不过硬第一遍很容易有bug
CSS里面表示颜色用
#abcdef (eg 0x1F2A3B) 这种形式， 每个字母代表四个bit (hex)，两个字母代表一种
原色
比如 ab = R, cd = G, ef = B (每种原色整个是0-255间的一个数字)
现在需要压缩空间改#abcdef 为 #xyz
实际上#xyz = #xxyyzz,所以减小一半，问怎么找到最好的压缩让
（ab-xx）^2 + (cd - yy)^2 + (ef - zz)^2 最小
这题其实数学上很简单因为三个维度是分开的，其实就是找#ab到#xx的压缩。
贡献一下：本版上搜集的 Google 面试题
1)Using c/c++ or Java, how to track stack grow up or shrink down
2)Assuming speed is more important than storage, how do you count the number
of bits that will set in 32 bit integer.
Q: 如何count任意一个整数中有多少个二进制的1
Q:在Web Crawler中，如何快速检查一个URL是否已经被check过
Bloom Filter
我的回答：建立一批Hash table，每个表用不同的Hash Function，对每个URL，检查每一个Hash 表。具体算法，如何计算conflict，我也不清楚，但这是NLP中的常规方法。
Q:如何很快地确定某一页是否是黄色网页
我的回答：训练一个分类器，对training data中的每个网页提取一些
描述参数 （举一些可能的属性），训练classifer，然后用。
我推荐C4.5，他就说你文章上好像是Boosted Naive Bayes最好，解释
那是旧的，新的结果是C4.5最好，申明应该试不同的classifer，然后
选一个最好的，例如：NN, SVMs,... It really depends.
Q: 具体编程中的实际最大问题
我的是bound check 和memory leak，我是真的花上过2 weeks去找一个memory leak。
1. Find links/urls from one html page using C++, then how do you store those
links that you found.
2. Design a schema for actors and movies database (one actor can be act one
or
more movies and one movie has more than one actor). Search name of actor,
you
can get a list of movies and search name of movie, you can get a list of
actors. 我数据库老早以前上过一门课，现在全忘光了。:(
3. In a linked list find the nth node from the end of this list.
4. questions about interface and abstract class.
1. design a data structure, this data structure have four functions: pop,
push
, min, top. DO NOT use any stack, queue, list, array or things like this.
2. two binary trees, write a compare function to check if they are equal or
not. equal means they have the same value and same structure.
3. how do you test a calculator.
4. questions about c++, like virtual functions, etc.
Given N computers networked together, with each computer storing N integers,
describe a procedure for finding the median of all of the numbers. Assume
that
a computer can only hold O(N) integers (i.e. no computer can store all N^2
integers). Also assume that there exists a computer on the network without
integers, that we can use to interface with the computers storing the
integers
.
step 1:
sort on each one of those N computers. takes N*N*longN time. If we consider
the
concurrency the overall time taken could be NlogN
step2:
transfer the smallest number on each of thse N computers to the spare box
and
sort them, also need to keep the information about which computer the
number
comes from.
this takes NlogN time
step3:
after sorting, throw the smallest number out and ask that speicific computer
where the smallest number come from to get the second smallest number, then
resort the numbers on the spare computer. repeat this step untill u have
thrown out N*N/2-1 numbers out, then on the spare
computer the smallest number is the global median number
This step takes NlogN+N*N/2*longN
How to serialize and deserialize 1) a binary tree and 2) a binary graph?
1. How did you get to us ?
2. Which group are you interested in ?
3. Describw what kind of new product you have in mind for google ?
technical :
1. grid problem, how to find the number of paths leading to a character ?
A B D C A
C D A B C
B A C D B
note: any path should startng with A and path should go strictly
alphabetical order. For example, the B in the second row could have two
paths.
2. Book database(very large), how to remove duplicates ? The same book might
have several records in the database due to title misspelling or name
aliases.
- implement a fixed size cache put and get methods. and Least Recently Used
discards
- 两个排序的数组, 找出交集.
=================
Onsite Questions:
=================
The first one: Write the code using an optimization algriothm to calcuate
the
intersection and union of two sets. (30 mins)
The second one: Write the code for an algriothm to transfrom the index in
excel to the number, and write a class to call this function without
declearing an object. for example: "A, B, C,....AB,AC,..BA,BB,....AAA,AAB,..
."
, transform to "1,2,3,.....", and also transform back.(30 mins)
1. 用hash table
2. 基本相当于26进制。比如 aa=26*1+1=27, aaa=26*26*1+26*1+1=something
--------------
1. Compute the quotient and remainder of m/n, without using divisionoperator.
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change.
3. Given an array,
i) Find the longest continuous increasing subsequence.
ii) Find the longest increasing subsequence.
4. A building of 100 floors, there is a threshold N s.t. if an egg drops
from Nth floor and above it will break. If it's dropped from any floor below
, it will not break. Given 2 eggs, find this N, and minimize the number of
drops for the worse case.
5. An OO design problem. It's a problem related to his work, I am not
supposed to disclose details.
6. Design a stack. We want to push, pop, and also, retrieve the minimum
element in constant time.
7. Suppose we have N companies, and we want to eventually merge them into
one big company. How many ways are there to merge?
===============
自己提问的问题：
===============
what the search engine will be in its next step?
他们现在的pagerank基于heuristic，有没有进行利用machine learning 去学习
ranking
other questions
===============
Given a list of numbers ( fixed list) Now given any other list, how can you
efficiently find out if there is any element in the second list that is an
element of the first list (fixed list).
两个很长的string，找出它们的longest common string (连续的），要求n*log(n)时
间。
suffix tree
发些收集到的Google的面经
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
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
其中一个是"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的回答了我。
第二个问题是关于描述一个自己coding以来最难的debug case。 我结合自己的背景，讲了一个自己当时在GPU shader里面debug linear quadtreetraversal的问题。其实不是很难，不过我自己觉得是一个有意思的问题
最后一个问题是问，如果设计一个web crawler，抓一个页面的url只好，分析这个页面里面所有的link url，记录不重复的new url，问需要什么样的数据结构。
我回答是url不重复，有unique性，可以考虑hashmap。另外从一个url到下一层url，设计一个tree，每个treenode里面包含一个vector动态数组来记录新的子节点的pointer。
然后进一步问，如果有1000台电脑运行web crawler，应该如何设计程序运行。
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什么的。
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的。
find majority element in an array. 我说用hash table，但是空间效率
低，我自己说了个constant space的idea, 写code。
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?
Google 的21道面试问题(ZZ)
10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理
》等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。
试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，并成
为我们其中一员”。
