tmobile信号挺烂的# PDA - 掌中宝
u*n
1 楼
这家也遇到两个三哥，挂了。不过还好，没遇到三哥的公司给了offer。
Phone：
求两个List的交集，假设每个list中的interval都是disjoint的。
onsite:
1）给你一个list的字符串，找出一个list的prefix，从而可以uniquely identify每个
字符串。
Hint：此题可以用trie来解决
2）给你一棵树，implement一个iterator，可以是BFS或者DFS。要求用iterative
method来实现。
Hint：选择DFS
3）压缩算法。用树的变形来表示一个string，比如 B->left = A, B->right = A, 此
种情况我们可以把B的left, right同时指向A。
问题1）对于一个有n个节点的树，可以表示的最长string的长度
问题2）implement get(Tree t, int position)，返回这个字符串在position的字符。
Hint：exponential + binary search
4)猜字游戏，有一个board和dictionary，从一个字符出发，你被允许走8个方向。如果
已经有了以下method，
isWord(String str)和isPrefix(String str)。你怎么把所有的词打印出来。你可以假
设解法唯一。
Hint： BFS
Phone：
求两个List
onsite:
1）给你一个list的字符串，找出一个list的prefix，从而可以uniquely identify每个
字符串。
Hint：此题可以用trie来解决
2）给你一棵树，implement一个iterator，可以是BFS或者DFS。要求用iterative
method来实现。
Hint：选择DFS
3）压缩算法。用树的变形来表示一个string，比如 B->left = A, B->right = A, 此
种情况我们可以把B的left, right同时指向A。
问题1）对于一个有n个节点的树，可以表示的最长string的长度
问题2）implement get(Tree t, int position)，返回这个字符串在position的字符。
Hint：exponential + binary search
4)猜字游戏，有一个board和dictionary，从一个字符出发，你被允许走8个方向。如果
已经有了以下method，
isWord(String str)和isPrefix(String str)。你怎么把所有的词打印出来。你可以假
设解法唯一。
Hint： BFS
