Google onsite问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Google onsite问题

Google onsite问题# JobHunting - 待字闺中

D*g2006-08-24 07:08

1 楼

6 interviewers, the last one discusses my thesis, and answers questions. We
asked him a lot about google's relation with the open source community. it's
very relaxed. He didn't ask any tough questions. One is my friend who
referred me. He just had lunch with me. Other 4 each asks 1-2 questions.
1. Compute the quotient and remainder of m/n, without using division
operator.
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change.
3. Given an array,

z*t2006-08-24 07:08

2 楼

For the 6-th question: Stack with a function to get the minimum elment,
there is a wonderful blog for it:
http://codercareer.blogspot.com/2011/09/no-02-stack-with-functi
It provides a solution with O(1) auxiliary space. Time efficiency for min,
pop and push are all O(1). Enjoy it :-)

We
's

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

: 6 interviewers, the last one discusses my thesis, and answers questions. We
: asked him a lot about google's relation with the open source community. it's
: very relaxed. He didn't ask any tough questions. One is my friend who
: referred me. He just had lunch with me. Other 4 each asks 1-2 questions.
: 1. Compute the quotient and remainder of m/n, without using division
: operator.
: 2. Given a set of coin denominators, find the minimum number of coins to
: give a certain amount of change.
: 3. Given an array,

r*g2006-08-24 07:08

3 楼

everyone knows how to solve the problems?
1. Compute the quotient and remainder of m/n, without using division
operator.
我会用二分法找到商a，a是第一个使m-n*a>0的数，减去a这个部分，再继续找。
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change.
貌似用dp？从要求得到的值向下dp还是从0开始向上dp？这样的题一直没弄明白怎么做
最好。
3. Given an array,
i) Find the longest continuous increasing subsequence.
ii) Find the longest increasing subsequence.
这道题怎么解？？谢谢了，google出来发现并不简单。
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.
old question, 很多地方有。
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?
这种题怎么回答？

r*g2006-08-24 07:08

4 楼

我看到这个帖子有很多回复，为何点击开只有3个？

We
's

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

h*n2006-08-24 07:08

5 楼

mark

We
's

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

i*h2006-08-24 07:08

6 楼

?????:
1.repeat m-n until the result is smaller than n, also count how many repeats.
2.Assume that we have 1 cent denominator. This is reasonable, why? :)
sort the denominators array in reversed order.
int count=0
for each denominator[i]
{
count += sum/denominator[i];
sum = sum%denominator[i];
}
3.1
int max=0;
int count=0;
int old=a[0];
for(int i=1;i{
if(a[i]>old)
count++;
else
{count=0;
if(maxmax=count;
}
old = a[i];
}
3.2
This is a classic algorithm. You have many ways, but here is a simpler
solution:
The longest increasing subsequence of a sequence S is the longest common
subsequence of S and T, where T is the result of sorting S.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Eff

i*h2006-08-24 07:08

7 楼

i*h2006-08-24 07:08

8 楼

继续
4.
http://www.jokelibrary.net/education/m_files/m4s-eggs.html
我初始的想法是把100层均分为x份，第一个蛋按x跳着drop，如果破了就从下一个节点
逐级往上drop，直到破掉。这样越往上总的drop次数越多一个。所以想到第一次跳x，
第二次跳x-1，一直这样下去，这样无论N出现在哪一个段，我顶多扔x次，解 x+x-1+x-
2+..+1=100,得到x=??
6.我觉得可以用个min heap和stack一起来，但楼上的链接的trick更简单。
7.这个怎解？DP？