google面经

发信人: monopoly86 (monopoly), 信区: JobHunting
标  题: google面经
发信站: BBS 未名空间站 (Sat Aug  2 17:36:57 2014, 美东)

LZ在GOOGLE面试过两次， 第一次是大学毕业。 为了追CHICAGO的一个女孩子， 申请了
GOOGLE CHICAGO的位子。第一轮CAMPUS面试通过， 第二轮NEW YORK后， 收到CHICAGO
的EMAIL问我availability说要为我订机票第三轮面试， 三天后却收到NEW YORK的电话
说我申请的位子取消了， 我没被录用。后来我在NEW YORK找了一份IT的工作。 三年后
， 我决定跳槽其他的IT工作， GOOGLE刚巧邀请我去面试， 所以我第二次去GOOGLE面
试。 这次拿到了offer， 但是也拿到了更好的HFT的offer。虽然没去GOOGLE工作， 但
是我很喜欢GOOGLE的面试， 觉得每次都有收获。在此分享一下我被问过的问题。我也
很希望看到其他朋友们的面试问题， 我会当兴趣爱好来试解答。

Behavior Questions:

1. In java, a method declared as private restrict access to within the class
. For example, a private void doHeartbeat() method within Heartbeat class
can only be called within the Heartbeat class. However, it doesn't prevent
the Heartbeat class to access the method of a different Heartbeat object.
For example, a private void forceHeartbeat(Heartbeat other) method is
allowed to call other.doHeartbeat(). Java doesn't provide a way to limit
access to a per object level. Why not?

2. Given set amount of memory and ram, how do you implement a process that
takes the longest amount of time to finish? The process has to finish, it
can not be an infinite loop. (Of all of the questions I got asked from
Google, I'm not sure I know the right answer to this one to this day)

Coding Questions:

1. Bar chart island. Given a two dimensional island that looks like a bar
chart represented by an int array. Calculate the amount of water it can
collect when it rains on the island. For example, [1,2,3] collects no water,
[2,1,3] collects 1 unit of water, [3,2,1,4] collects 3 units of water, [3,2
,4,1,5] collects 4 units of water.

2. Ancestor. You are ancestry.com, you have a graph of related ancestors.
One ancestor node contains the following fields: Node mother, Node father,
Node[] children. Write a method that checks if two Nodes are blood related.
For example, you and your half brother is blood related, your father and
your mother are (hopefully but not guaranteed to be ) not blood related.
Please note that information might be incomplete meaning mother, father or
children can all be null.

3. Eviction Hash Map. Write a hash map that can store at most N key value
pairs. If more than N key value pairs are associated, the least recently
accessed key value pair is removed from the map. For example, for a map of
capacity 3. put(1,1), put(2,2), put(3,3), put(4,4) will cause key 1 to be
removed. However, put(1,1), put(2,2), put(3,3), get(1), put(4,4) will cause
key 2 to be removed, put(5,5) will cause key 3 to be removed.

4. Meeting place. You have a city with streets running parallel both
horizonally and vetically creating a giant grid. The dimension of each grid
is 1 X 1. All street corners in the city can be represented by a coordinate
(int x, int y). Given an array of people represented by their closest street
corner, calculate a street corner to meet where their combined traveling
distance is the shortest. Assume everyone can only travel on road. For
example, the traveling distance from [1,1] to [2,2] is 2.

5. Nth largest from tree. Given a binary search tree where the left node is
smaller and the right node is larger. Calculate the Nth largest number in
the tree throwing exception when there is less than N elements in the tree.

6. Anagram solver. An anagram is two words that contains the same letters
the same amount of times. For example, angle and angel are anagrams. Given a
dictionary, perform some preprocessing for a anagram solver. The anagram
solver takes a string as input and prints out a list of all anagrams
contained in the dictionary.

7. Next tree sibling. Given a tree where each node has left and right
pointers
, implement a function that sets the next pointer. Next pointer will point
to a node in the same level immediately to the right. For example, if a node
has both left and right children, next pointer of the left child will point
to the right child. The next pointer of the right child will point to
parent's sibling's left child. The fact that left child and right child can
both be null make things complicated.

--
※ 修改:·monopoly86 於 Aug  2 18:47:10 2014 修改本文·[FROM: 68.]
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 68.]

http://www.mitbbs.com/article_t/JobHunting/32749835.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东北京出版集团图书满200立减50元 ， 更多京东优惠券