D********g
发帖数: 650 | 1 面经回馈本版，只列出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***o
发帖数: 1182 | 2 楼主是不是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******u
发帖数: 397 | 3 bless! Thanks for sharing |
H**********y
发帖数: 7928 | 4 bless
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();
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | |
f*******t
发帖数: 7549 | |
g**********y
发帖数: 14569 | 8 Google suggest那个你怎么答的？我也被问过，回答得一塌糊涂。 |
c***p
发帖数: 221 | 9 Big Bless!
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();
|
w***y
发帖数: 6251 | |
|
|
D********g
发帖数: 650 | 11 updated questions to clarify. |
i**********e
发帖数: 1145 | 12 bless and 赞。
B. Concurrent programming.
这是问的什么问题呢？ |
p**p
发帖数: 2493 | |
w****x
发帖数: 2483 | 14 3个基础题都不难, data mining的题一个都不会
楼主肯定是data mining的phd?? |
w***y
发帖数: 6251 | 15 Boggle题，find all possible words from a 2D character array.
这是什么样的题目? 能具体说说么? 看样子是老题, 但是我没见过//囧 |
w***y
发帖数: 6251 | 16 java里面的iterator, 怎么还有专门问java的题目?
当然c++的iterator从来没用过//汗
【在 p*****2 的大作中提到】
: P2A没看懂。
|
w***y
发帖数: 6251 | 17 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**********g
发帖数: 209 | 18 谢谢！ 我本来不会的，被你这么一写，感觉不算难啊。
我有一个问题，如果iterator的用户不停调用next，而不用hasNext，怎么处理。
这算是需要考虑的问题吗？
谢谢！
【在 w***y 的大作中提到】
: java里面的iterator, 怎么还有专门问java的题目?
: 当然c++的iterator从来没用过//汗
|
z**********g
发帖数: 209 | 19 一起请教concurrent programming的具体内容。 |
p*****2
发帖数: 21240 | 20
用DFS，其实写起来也不算很容易。
从每个点开始做DFS，找单词。
【在 w***y 的大作中提到】
: Boggle题，find all possible words from a 2D character array.
: 这是什么样的题目? 能具体说说么? 看样子是老题, 但是我没见过//囧
|
|
|
w***y
发帖数: 6251 | 21 我写的不对, 所以删掉了
你说的就是这个出题的point, 这些都要考虑
【在 z**********g 的大作中提到】
: 谢谢！ 我本来不会的，被你这么一写，感觉不算难啊。
: 我有一个问题，如果iterator的用户不停调用next，而不用hasNext，怎么处理。
: 这算是需要考虑的问题吗？
: 谢谢！
|
p*****2
发帖数: 21240 | 22
需要考虑。
【在 z**********g 的大作中提到】
: 谢谢！ 我本来不会的，被你这么一写，感觉不算难啊。
: 我有一个问题，如果iterator的用户不停调用next，而不用hasNext，怎么处理。
: 这算是需要考虑的问题吗？
: 谢谢！
|
w***y
发帖数: 6251 | 23 okok
那这种题目是不是有个dictionary, 好知道哪些是valid words?
做DFS的时候也是从valid starting char开始?
写起来貌似很多麻烦, 我把题目搞清楚了要写写看
【在 p*****2 的大作中提到】
:
: 需要考虑。
|
z**********g
发帖数: 209 | 24 boggle 那题 dfs + tire 就好了。
请教 iterator + predicate 那题。 |
p*****2
发帖数: 21240 | 25
我写了一个。
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*****2
发帖数: 21240 | 26
应该是有个字典，你能够查是不是有效单词。至于字典是hashtable还是trie无所谓。
不是考察重点。
【在 w***y 的大作中提到】
: okok
: 那这种题目是不是有个dictionary, 好知道哪些是valid words?
: 做DFS的时候也是从valid starting char开始?
: 写起来貌似很多麻烦, 我把题目搞清楚了要写写看
|
w***y
发帖数: 6251 | 27 找到一个答案
http://code.vith.me/2011/05/finding-words-in-2d-character-array
面试的时候竟然要写这么多code!!!!!!!
【在 p*****2 的大作中提到】
:
: 应该是有个字典，你能够查是不是有效单词。至于字典是hashtable还是trie无所谓。
: 不是考察重点。
|
p*****2
发帖数: 21240 | 28
所以说这题不算容易写。
【在 w***y 的大作中提到】
: 找到一个答案
: http://code.vith.me/2011/05/finding-words-in-2d-character-array
: 面试的时候竟然要写这么多code!!!!!!!
|
z**********g
发帖数: 209 | 29 Great!
But I think the next function should be
T next()
{
hasNext();
T ret = next;
next = null;
return ret;
}
【在 p*****2 的大作中提到】
:
: 所以说这题不算容易写。
|
i**********e
发帖数: 1145 | 30 那个链接好像是找 crossword 解，跟 boggle 不一样。
boggle 是每个字都可以往 8 个方向转，而crossword不行。
【在 w***y 的大作中提到】
: 找到一个答案
: http://code.vith.me/2011/05/finding-words-in-2d-character-array
: 面试的时候竟然要写这么多code!!!!!!!
|
|
|
p*****2
发帖数: 21240 | 31
不用吧？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**********g
发帖数: 209 | 32 In your original implementation, if the user call next() after
initialization, it will return null, right?
【在 p*****2 的大作中提到】
:
: 不用吧？next总是应该return的item，直接return就可以了。不需要调hasNext()
|
p*****2
发帖数: 21240 | 33
constructor里边调了hasnext了。
【在 z**********g 的大作中提到】
: In your original implementation, if the user call next() after
: initialization, it will return null, right?
|
z**********g
发帖数: 209 | 34 sorry, I missed it. but you still need to set next = null before hasNext()
in next(), right?
【在 p*****2 的大作中提到】
:
: constructor里边调了hasnext了。
|
p*****2
发帖数: 21240 | 35 对
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*****k
发帖数: 327 | 36 zan!
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();
|
b********g
发帖数: 43 | 37 我的理解是每次都预读一个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********g
发帖数: 43 | 38 为什么不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*****2
发帖数: 21240 | 39
感觉不太合适。没怎么多想。感觉DFS很直接的思路。
【在 b********g 的大作中提到】
: 为什么不BFS?
|
d*****y
发帖数: 205 | 40 这位童鞋你不想要offer了吗 回来就上题 啊？
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*****y
发帖数: 205 | 41 这位童鞋你不想要offer了吗 回来就上题 啊？
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();
|
g**********y
发帖数: 14569 | 42 不要这么说，不管哪种方式，互相帮助找工都是好的。祝福楼主拿到。
【在 d*****y 的大作中提到】
: 这位童鞋你不想要offer了吗 回来就上题 啊？
:
: same
|
z**********g
发帖数: 209 | 43 回答一下如何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********9
发帖数: 1099 | |
l*********d
发帖数: 78 | 45 参照 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**********y
发帖数: 14569 | 46 方向不对，他们关心的是大规模数据，每时每刻都有新的数据进来，这些东西不能保存
在一台机器上，计算不可能实时同步，但是又不能滞后太多。而且你需要把历史数据和
当前热点都考虑进去。然后全球时差，中国发生大事时，美国可能在睡觉，所以需要
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********c
发帖数: 72 | 47 说个我原来G电面类似题面试官告诉我要注意的地方。。
next不能设为null，因为他提示我iterator给的值可能是null，然后pred可能null的返
回是true
所以这样对于T的假设是错误的，NULL对调用者可能是有意义的
正确的方法是设一个validNext的bool，看next是不是刚从iterator里拿出来的
【在 p*****2 的大作中提到】
:
: 感觉不太合适。没怎么多想。感觉DFS很直接的思路。
|
J**F
发帖数: 144 | 48 请问edit distance 和这个search suggestion 有什么关系？
distance,
【在 g**********y 的大作中提到】
: 方向不对，他们关心的是大规模数据，每时每刻都有新的数据进来，这些东西不能保存
: 在一台机器上，计算不可能实时同步，但是又不能滞后太多。而且你需要把历史数据和
: 当前热点都考虑进去。然后全球时差，中国发生大事时，美国可能在睡觉，所以需要
: roll along时区。这是G的architect这么跟我提的几点。当然那些什么edit distance,
: 字/词匹配也是要考虑的。
: 我当时听着就心想，谁要是不做这个方向，能考虑全这些方面，也太神了。
:
: are
: is
: update
|
g**********y
发帖数: 14569 | 49 用户的输入不是完美的，很可能多/错/漏一个字母，所以计算输入的时候，通常会考虑
edit distance = 1范围内的其它词。你试试google suggest就知道了。
【在 J**F 的大作中提到】
: 请问edit distance 和这个search suggestion 有什么关系？
:
: distance,
|
J**F
发帖数: 144 | 50 明白你的意思了，这个想法很正确。
如果面试的时候能把这个也说出来应该还是很加分的 ：）
【在 g**********y 的大作中提到】
: 用户的输入不是完美的，很可能多/错/漏一个字母，所以计算输入的时候，通常会考虑
: edit distance = 1范围内的其它词。你试试google suggest就知道了。
|
|
|
h*****g
发帖数: 312 | 51 P2 这题是啥意思？谁能帮忙解释一下，最好给个例子
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();
|
p*****2
发帖数: 21240 | 52
学习了。
【在 z********c 的大作中提到】
: 说个我原来G电面类似题面试官告诉我要注意的地方。。
: next不能设为null，因为他提示我iterator给的值可能是null，然后pred可能null的返
: 回是true
: 所以这样对于T的假设是错误的，NULL对调用者可能是有意义的
: 正确的方法是设一个validNext的bool，看next是不是刚从iterator里拿出来的
|
