Google onsite归来 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Google onsite归来

Google onsite归来# JobHunting - 待字闺中

T*72012-03-28 07:03

1 楼

☆─────────────────────────────────────☆
judyzx (judy) 于 (Mon Jun 15 17:00:59 2009, 美东) 提到:
各位慢慢看，前面是今天的故事，8楼是自己对问题的分析。B是我lg.没想到写了那么长。
我还没有和家里人商量，怕刺激到他们，家里人都觉得我们两都好好的。但是事实不是
这样的。
周末B要我陪他加班.我不喜欢,但是为了他高兴,就去了.
在那里看书,很闷.待着一点没有意思,又不能走动，也不能说话，而且有点感冒想早点
回来.待了大概3个多小时的时候说要回家.
我说了你老是让我陪你加班,我那里很没意思.而且我今天不舒服.这时候还挺好的,b说
那以后不让你陪着加班了.
b说要去中国城,(看上去兴致挺高的样子)我说跑这么远去一次也没有什么意思.而且那
个地方那么破。他有点郁闷，说，那就回去吧.
后来到了门口,他不愿意上去,说要去转转,我赌气说那我也去,否则我没地吃饭去.平时5
天每天我做的饭,周末我和他说让他负责,否则我满脑子都是每天做什么吃.
再后来,在开往中国城的路上,都一大半了.好像我们又说了些什么,后来他

D*g2012-03-28 07:03

2 楼

面经回馈本版，只列出technical question.
P1:
A. Add next pointer to each node on a BTree to its next sibling on the same
level.
B. Boggle题，find all possible words from a 2D character array.
P2:
A. Given
interface Iterator {
T next();
boolean hasNext();
}
interface Predicate {
boolean accept(T t);
}
Implement a method that creates an "accept" iterator that returns items
accepted by the passedin pred variable.
Iterator conditionIterator(Iterator input, Predicate pred) {
}
B. Concurrent programming.
P3：
Find # of elements that are equal to a given value in a sorted array. O(lgn)
solution. O(n) solution is not good enough.
P4:
Design and implement a class to train from a input string like "ape apple
ace" to generate new words based on conditional probability of P(c_i|c_j).
e.g., P(p|a), P(e|p), P(l|p).
class TokenGenerator {
public void train(String t) {...}
public String generate() {...}
}
How to optimize generate() method.
P5:
A. Given an input string and an order string, e.g., "house" and "soup",
print out characters in input string according to character order in output
string. For characters in input string but not in output string, output them
in the end, their relative order doesn't matter.
So for "house", "souhe" and "soueh" are valid outputs.
B. Design Google suggests.

a*o2012-03-28 07:03

3 楼

楼主是不是dm的phd？
有道train的题目没看懂。。。

same

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

: 面经回馈本版，只列出technical question.
: P1:
: A. Add next pointer to each node on a BTree to its next sibling on the same
: level.
: B. Boggle题，find all possible words from a 2D character array.
: P2:
: A. Given
: interface Iterator {
: T next();
: boolean hasNext();

d*u2012-03-28 07:03

4 楼

bless! Thanks for sharing

H*y2012-03-28 07:03

5 楼

bless

same

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

p*22012-03-28 07:03

6 楼

多些分享。

p*22012-03-28 07:03

7 楼

P2A没看懂。

f*t2012-03-28 07:03

8 楼

bless

g*y2012-03-28 07:03

9 楼

Google suggest那个你怎么答的？我也被问过，回答得一塌糊涂。

c*p2012-03-28 07:03

10 楼

Big Bless!

same

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

w*y2012-03-28 07:03

11 楼

thx and bless!!!!

D*g2012-03-28 07:03

12 楼

updated questions to clarify.

i*e2012-03-28 07:03

13 楼

bless and 赞。
B. Concurrent programming.
这是问的什么问题呢？

p*p2012-03-28 07:03

14 楼

bless you!

w*x2012-03-28 07:03

15 楼

3个基础题都不难, data mining的题一个都不会
楼主肯定是data mining的phd??

w*y2012-03-28 07:03

16 楼

Boggle题，find all possible words from a 2D character array.
这是什么样的题目? 能具体说说么? 看样子是老题, 但是我没见过//囧

w*y2012-03-28 07:03

17 楼

java里面的iterator, 怎么还有专门问java的题目?
当然c++的iterator从来没用过//汗

【在 p*****2 的大作中提到】

: P2A没看懂。

w*y2012-03-28 07:03

18 楼

P5:A. 我也完全看懵了....... 这题想考什么呀? 因为我有一个很圡的法子
1. 把input string的char做一个set
2. 一个 dupSet, 刚开始为空
3. scan order string
出现在set OR dupSet里面的char,
print,
set.remove,
dupSet.add
4. scan完order string之后,如果set不为空, 就把剩下的都打印出来
可是这出题的本意是什么呀?

z*g2012-03-28 07:03

19 楼

谢谢！我本来不会的，被你这么一写，感觉不算难啊。
我有一个问题，如果iterator的用户不停调用next，而不用hasNext，怎么处理。
这算是需要考虑的问题吗？
谢谢！

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

: java里面的iterator, 怎么还有专门问java的题目?
: 当然c++的iterator从来没用过//汗

z*g2012-03-28 07:03

20 楼

一起请教concurrent programming的具体内容。

p*22012-03-28 07:03

21 楼

用DFS，其实写起来也不算很容易。
从每个点开始做DFS，找单词。

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

: Boggle题，find all possible words from a 2D character array.
: 这是什么样的题目? 能具体说说么? 看样子是老题, 但是我没见过//囧

w*y2012-03-28 07:03

22 楼

我写的不对, 所以删掉了
你说的就是这个出题的point, 这些都要考虑

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

: 谢谢！我本来不会的，被你这么一写，感觉不算难啊。
: 我有一个问题，如果iterator的用户不停调用next，而不用hasNext，怎么处理。
: 这算是需要考虑的问题吗？
: 谢谢！

p*22012-03-28 07:03

23 楼

需要考虑。

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

w*y2012-03-28 07:03

24 楼

okok
那这种题目是不是有个dictionary, 好知道哪些是valid words?
做DFS的时候也是从valid starting char开始?
写起来貌似很多麻烦, 我把题目搞清楚了要写写看

【在 p*****2 的大作中提到】

:
: 需要考虑。

z*g2012-03-28 07:03

25 楼

boggle 那题 dfs + tire 就好了。
请教 iterator + predicate 那题。

p*22012-03-28 07:03

26 楼

我写了一个。
Iterator it=null;
Predicate pr=null;
T next=null;
Iterator conditionIterator(Iterator input, Predicate pred)
{
it=input;
pr=pred;
hasNext();
}
T next()
{
T ret=next;
hasNext();
return ret;
}
T hasNext()
{
if(next==null)
{
while(it.hasNext())
{
next=it.hasNext();
if(pr.accept(next))
break;
else
next=null;
}
}
return next!=null;
}

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

: 我写的不对, 所以删掉了
: 你说的就是这个出题的point, 这些都要考虑

p*22012-03-28 07:03

27 楼

应该是有个字典，你能够查是不是有效单词。至于字典是hashtable还是trie无所谓。
不是考察重点。

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

: okok
: 那这种题目是不是有个dictionary, 好知道哪些是valid words?
: 做DFS的时候也是从valid starting char开始?
: 写起来貌似很多麻烦, 我把题目搞清楚了要写写看

w*y2012-03-28 07:03

28 楼

找到一个答案
http://code.vith.me/2011/05/finding-words-in-2d-character-array
面试的时候竟然要写这么多code!!!!!!!

【在 p*****2 的大作中提到】

:
: 应该是有个字典，你能够查是不是有效单词。至于字典是hashtable还是trie无所谓。
: 不是考察重点。

p*22012-03-28 07:03

29 楼

所以说这题不算容易写。

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

: 找到一个答案
: http://code.vith.me/2011/05/finding-words-in-2d-character-array
: 面试的时候竟然要写这么多code!!!!!!!

z*g2012-03-28 07:03

30 楼

Great!
But I think the next function should be
T next()
{
hasNext();
T ret = next;
next = null;
return ret;
}

【在 p*****2 的大作中提到】

:
: 所以说这题不算容易写。

i*e2012-03-28 07:03

31 楼

那个链接好像是找 crossword 解，跟 boggle 不一样。
boggle 是每个字都可以往 8 个方向转，而crossword不行。

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

: 找到一个答案
: http://code.vith.me/2011/05/finding-words-in-2d-character-array
: 面试的时候竟然要写这么多code!!!!!!!

p*22012-03-28 07:03

32 楼

不用吧？next总是应该return的item，直接return就可以了。不需要调hasNext()

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

: Great!
: But I think the next function should be
: T next()
: {
: hasNext();
: T ret = next;
: next = null;
: return ret;
: }

z*g2012-03-28 07:03

33 楼

In your original implementation, if the user call next() after
initialization, it will return null, right?

【在 p*****2 的大作中提到】

:
: 不用吧？next总是应该return的item，直接return就可以了。不需要调hasNext()

p*22012-03-28 07:03

34 楼

constructor里边调了hasnext了。

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

: In your original implementation, if the user call next() after
: initialization, it will return null, right?

z*g2012-03-28 07:03

35 楼

sorry, I missed it. but you still need to set next = null before hasNext()
in next(), right?

【在 p*****2 的大作中提到】

:
: constructor里边调了hasnext了。

p*22012-03-28 07:03

36 楼

对

sorry, I missed it. but you still need to set next = null before hasNext()
in next(), ri........
★ Sent from iPhone App: iReader Mitbbs Lite 7.51

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

: sorry, I missed it. but you still need to set next = null before hasNext()
: in next(), right?

L*k2012-03-28 07:03

37 楼

zan!

same

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

b*g2012-03-28 07:03

38 楼

我的理解是每次都预读一个next, 然后就ok 了
Iterator it = null;
Predicate pr = null;
T next =null;
Iterator conditionIterator(Iterator input, Predicate pred)
{
it = input;
pr = pred;
next();
}
T next() {
T ret = next;
bool found = false;
while(it.hasNext()) {
T val = it.next();
if(pr.accept(val))｛
next = val;
found = true;
break;
｝
}
if(!found) next = NULL;
return ret;
}
bool hasnext() {
return !next;
}

【在 p*****2 的大作中提到】

: 对
:
: sorry, I missed it. but you still need to set next = null before hasNext()
: in next(), ri........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.51

b*g2012-03-28 07:03

39 楼

为什么不BFS?

【在 p*****2 的大作中提到】

: 对
:
: sorry, I missed it. but you still need to set next = null before hasNext()
: in next(), ri........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.51

p*22012-03-28 07:03

40 楼

感觉不太合适。没怎么多想。感觉DFS很直接的思路。

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

: 为什么不BFS?

d*y2012-03-28 07:03

41 楼

这位童鞋你不想要offer了吗回来就上题啊？

same

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

d*y2012-03-28 07:03

42 楼

这位童鞋你不想要offer了吗回来就上题啊？

same

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

g*y2012-03-28 07:03

43 楼

不要这么说，不管哪种方式，互相帮助找工都是好的。祝福楼主拿到。

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

: 这位童鞋你不想要offer了吗回来就上题啊？
:
: same

z*g2012-03-28 07:03

44 楼

回答一下如何design google suggest. 抛砖引玉。
我想基本的structure应该是trie + minheap.
First, we need to assume that popular search phases' search frequencies are
known. I think this can be achieved by map reduce easily, and the result is
stored at a database called DB.
Then, build a trie according to those popular search phases. Each node in
the trie has a pointer to a minHeap. The minHeap has a fixed size of 10.
Each node in minHeap stores a word and its frequency.
Suppose we want to insert a word craigslist into the trie, we need to update
every node's minHeap along the path, namely c, cr, cra, crai, craig, craigs
, craigsl, cragisli, cragislis and craigslist.
Please note this approach builds the trie according to DB statically,
and I think we need to reconstruct a new trie according to new DB every
month.

j*92012-03-28 07:03

45 楼

bless

l*d2012-03-28 07:03

46 楼

参照 peking2 的写了一个：
public Iterator conditionIterator(final Iterator input,
final Predicate pred) {
return new Iterator() {
T next = null;
public T next() {
if (!hasNext()) throw new NoSuchElementException("no more element");
T ret = next;
next = null;
return ret;
}
public boolean hasNext() {
if (next != null) return true;
else if (!input.hasNext()) return false;
else {
next = input.next();
while (!pred.accept(next) && input.hasNext()) {
next = input.next();
}
if (pred.accept(next)) return true;
else {
next = null;
return false;
}
}
}
};
}

g*y2012-03-28 07:03

47 楼

方向不对，他们关心的是大规模数据，每时每刻都有新的数据进来，这些东西不能保存
在一台机器上，计算不可能实时同步，但是又不能滞后太多。而且你需要把历史数据和
当前热点都考虑进去。然后全球时差，中国发生大事时，美国可能在睡觉，所以需要
roll along时区。这是G的architect这么跟我提的几点。当然那些什么edit distance,
字/词匹配也是要考虑的。
我当时听着就心想，谁要是不做这个方向，能考虑全这些方面，也太神了。

are
is
update
craigs

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

: 回答一下如何design google suggest. 抛砖引玉。
: 我想基本的structure应该是trie + minheap.
: First, we need to assume that popular search phases' search frequencies are
: known. I think this can be achieved by map reduce easily, and the result is
: stored at a database called DB.
: Then, build a trie according to those popular search phases. Each node in
: the trie has a pointer to a minHeap. The minHeap has a fixed size of 10.
: Each node in minHeap stores a word and its frequency.
: Suppose we want to insert a word craigslist into the trie, we need to update
: every node's minHeap along the path, namely c, cr, cra, crai, craig, craigs

z*c2012-03-28 07:03

48 楼

说个我原来G电面类似题面试官告诉我要注意的地方。。
next不能设为null，因为他提示我iterator给的值可能是null，然后pred可能null的返
回是true
所以这样对于T的假设是错误的，NULL对调用者可能是有意义的
正确的方法是设一个validNext的bool，看next是不是刚从iterator里拿出来的

【在 p*****2 的大作中提到】

:
: 感觉不太合适。没怎么多想。感觉DFS很直接的思路。

J*F2012-03-28 07:03

49 楼

请问edit distance 和这个search suggestion 有什么关系？

distance,

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

: 方向不对，他们关心的是大规模数据，每时每刻都有新的数据进来，这些东西不能保存
: 在一台机器上，计算不可能实时同步，但是又不能滞后太多。而且你需要把历史数据和
: 当前热点都考虑进去。然后全球时差，中国发生大事时，美国可能在睡觉，所以需要
: roll along时区。这是G的architect这么跟我提的几点。当然那些什么edit distance,
: 字/词匹配也是要考虑的。
: 我当时听着就心想，谁要是不做这个方向，能考虑全这些方面，也太神了。
:
: are
: is
: update

g*y2012-03-28 07:03

50 楼

用户的输入不是完美的，很可能多/错/漏一个字母，所以计算输入的时候，通常会考虑
edit distance = 1范围内的其它词。你试试google suggest就知道了。

【在 J**F 的大作中提到】

: 请问edit distance 和这个search suggestion 有什么关系？
:
: distance,

J*F2012-03-28 07:03

51 楼

明白你的意思了，这个想法很正确。
如果面试的时候能把这个也说出来应该还是很加分的：）

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

: 用户的输入不是完美的，很可能多/错/漏一个字母，所以计算输入的时候，通常会考虑
: edit distance = 1范围内的其它词。你试试google suggest就知道了。

h*g2012-03-28 07:03

52 楼

P2 这题是啥意思？谁能帮忙解释一下，最好给个例子

same

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

p*22012-03-28 07:03

53 楼

学习了。

【在 z********c 的大作中提到】

: 说个我原来G电面类似题面试官告诉我要注意的地方。。
: next不能设为null，因为他提示我iterator给的值可能是null，然后pred可能null的返
: 回是true
: 所以这样对于T的假设是错误的，NULL对调用者可能是有意义的
: 正确的方法是设一个validNext的bool，看next是不是刚从iterator里拿出来的