G电面面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

G电面面经

G电面面经# JobHunting - 待字闺中

r*t2012-10-26 07:10

1 楼

第一题
Find deepest nodes in a binary tree.
Q: binary search tree? A: no (这个问题好像没什么用……)
Q: all of the deepest nodes, or just one? A: find the right-most deepest
node
第二题
Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
determine if it is unique in the dictionary.
Q: rephrasing the question, determine if no other words can be abbreviated
as "i18n", correct? A: yes

p*22012-10-26 07:10

2 楼

“i18n” 是什么的abbreviation?

q*m2012-10-26 07:10

3 楼

第一题是 leetcode上的 level order traversal的一个衍生题目吧？
就是一层层的往下走.

,

【在 r*****t 的大作中提到】

: 第一题
: Find deepest nodes in a binary tree.
: Q: binary search tree? A: no (这个问题好像没什么用……)
: Q: all of the deepest nodes, or just one? A: find the right-most deepest
: node
: 第二题
: Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
: determine if it is unique in the dictionary.
: Q: rephrasing the question, determine if no other words can be abbreviated
: as "i18n", correct? A: yes

r*t2012-10-26 07:10

4 楼

internationalization，所以才会简写:P

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

: “i18n” 是什么的abbreviation?

q*m2012-10-26 07:10

5 楼

第二道题感觉如何确定 abbreviation 不是很清楚阿。比如 doctor ,我可以
用 dr.，也可以用 dctr

,

【在 r*****t 的大作中提到】

p*22012-10-26 07:10

6 楼

简写都有什么格式？
i18n 是因为i和n之间有18个字母？这是唯一的简写格式？

【在 r*****t 的大作中提到】

: internationalization，所以才会简写:P

S*w2012-10-26 07:10

7 楼

第一题：
//return the right most deepest node
int deepest (struct node * root, struct node ** result) {
struct node * deepest_l;
struct node * deepest_r;
int l, r;
if(root == NULL) {
*result = NULL;
return 0;
}
l = deepest(root->left, &deepest_l);
r = deepest(root->right, &deepest_r);
if(l > r) {
if(deepest_l != NULL) *result = deepest_l;
else *result = root;
return 1 + l;
} else {
if(deepest_r != NULL) *result = deepest_r;
else *result = root;
return 1 + r;
}
}
请指正。

,

【在 r*****t 的大作中提到】

e*s2012-10-26 07:10

8 楼

第一题。
BFS最后一个节点不就是了吗？

e*s2012-10-26 07:10

9 楼

你是想找出树的深度？题目好像不是这样说的啊

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

: 第一题：
: //return the right most deepest node
: int deepest (struct node * root, struct node ** result) {
: struct node * deepest_l;
: struct node * deepest_r;
: int l, r;
: if(root == NULL) {
: *result = NULL;
: return 0;
: }

e*s2012-10-26 07:10

10 楼

第二题O(n) n = 字典大小？
难点在哪？

C*U2012-10-26 07:10

11 楼

题目不是很懂

w*z2012-10-26 07:10

12 楼

二爷一点就透啊，l10n, localization.

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

:
: 简写都有什么格式？
: i18n 是因为i和n之间有18个字母？这是唯一的简写格式？

p*22012-10-26 07:10

13 楼

大牛有什么想法？感觉建立一个hashmap就可以了？

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

: 二爷一点就透啊，l10n, localization.

S*w2012-10-26 07:10

14 楼

result返回deepest node

【在 e***s 的大作中提到】

: 你是想找出树的深度？题目好像不是这样说的啊

C*U2012-10-26 07:10

15 楼

可不可以根据首字母尾字母长度构建array? 然后每个位置对应一个linked list?

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

:
: 大牛有什么想法？感觉建立一个hashmap就可以了？

e*s2012-10-26 07:10

16 楼

但是你return type 是 int啊

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

: result返回deepest node

r*t2012-10-26 07:10

17 楼

i18n是唯一的简写格式，表示i跟n之间有18个字母，doctor会被简写成d4r

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

:
: 大牛有什么想法？感觉建立一个hashmap就可以了？

p*22012-10-26 07:10

18 楼

list?
跟hashmap比有啥好处吗？

【在 C***U 的大作中提到】

: 可不可以根据首字母尾字母长度构建array? 然后每个位置对应一个linked list?

w*o2012-10-26 07:10

19 楼

来一个不recursive的：
Node findDeepestNode(Node root) {
Stack s = new Stack();
Stack d = new Stack();
int max = -1; Node x = null;
s.push(root); d.push(0);
while(!s.empty()) {
int dep = d.pop();
Node n = s.pop();
if(n.left == null && n.right == null) {
if(dep > max) {
max = dep;
x = n;
}
} else {
if(n.left != null) {s.push(n.left); d.push(dep + 1);}
if(n.right != null) {s.push(n.right); d.push(dep + 1);}
}
}

return x;
}

w*o2012-10-26 07:10

20 楼

第二题
可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
这样，任给一个abbr都能在O（1）返回是否是唯一的。

e*s2012-10-26 07:10

21 楼

我就不懂了，不就是BFS最后一个节点吗？
public static BTNode DeepestRightMostNode(BTNode root)
{
if (root == null)
return null;
Queue queue = new Queue();
queue.Enqueue(root);
BTNode temp = root;
while(queue.Count > 0)
{
temp = queue.Dequeue();
if(temp.Left != null)
queue.Enqueue(temp.Left);
if(temp.Right != null)
queue.Enqueue(temp.Right);
}
return temp;
}

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

: 来一个不recursive的：
: Node findDeepestNode(Node root) {
: Stack s = new Stack();
: Stack d = new Stack();
: int max = -1; Node x = null;
: s.push(root); d.push(0);
: while(!s.empty()) {
: int dep = d.pop();
: Node n = s.pop();
: if(n.left == null && n.right == null) {

e*s2012-10-26 07:10

22 楼

自己要设计Hash Function吗？请问是怎么设计的？

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

: 第二题
: 可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
: hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
: 这样，任给一个abbr都能在O（1）返回是否是唯一的。

d*x2012-10-26 07:10

23 楼

如果是英文词典，则只要建立两个 52 * 52 的 long long 数组即可，对于每一个长度
，用bitmap。
如果是比较大的字符集，则不用数组，用hashmap.

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

m*02012-10-26 07:10

24 楼

能具体说说这个hashcode的原理是什么？土人没看明白。谢谢！

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

g*e2012-10-26 07:10

25 楼

dfs自然也可以做。不过应该先访问right sub tree
很多时候dfs/recursive 可以写出看着很cool的code

【在 e***s 的大作中提到】

: 我就不懂了，不就是BFS最后一个节点吗？
: public static BTNode DeepestRightMostNode(BTNode root)
: {
: if (root == null)
: return null;
: Queue queue = new Queue();
: queue.Enqueue(root);
: BTNode temp = root;
: while(queue.Count > 0)
: {

w*o2012-10-26 07:10

26 楼

好，比我的要简洁。

【在 e***s 的大作中提到】