GG Phone面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

GG Phone面经

GG Phone面经# JobHunting - 待字闺中

C*m2015-01-20 08:01

1 楼

前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.
第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;
第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束.
分享给大家,希望有所帮助.

h*c2015-01-20 08:01

2 楼

deep copy drama
A {
B& b
}
B {
A& a
}

s*k2015-01-20 08:01

3 楼

Phone or onsite?

O(

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

: 前两天面了GG, 刚收到feedback说通过. 下面是面经:
: 白人小伙, 一上来什么都没说,直接开题.
: 第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
: match的字符串.
: 给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
: 达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
: 好说的从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;
: 第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
: Space O(n); 一是直接对List拆分deep拷贝然后再恢复原list Time O(n) + Space O(
: 1)。

y*e2015-01-20 08:01

4 楼

第一题应该怎么做啊？ lz请明示。。。

g*s2015-01-20 08:01

5 楼

楼主拿到offer没。你工作经验几年。

r*72015-01-20 08:01

6 楼

为什么就两轮。。。
deep copy linked list，如果只有next指针，为什么要hashmap？存一个prev就行了啊

O(

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

y*e2015-01-20 08:01

7 楼

我觉得是那个有random pointer的linked list。。。。如果只有next pointer，没啥
考点啊。。

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

: 为什么就两轮。。。
: deep copy linked list，如果只有next指针，为什么要hashmap？存一个prev就行了啊
:
: O(

C*m2015-01-20 08:01

8 楼

电面对有random pointer的那道题

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

: 我觉得是那个有random pointer的linked list。。。。如果只有next pointer，没啥
: 考点啊。。

C*m2015-01-20 08:01

9 楼

phone

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

: Phone or onsite?
:
: O(

C*m2015-01-20 08:01

10 楼

here is mine...
(1) build a trie
(2) locate the first node in the trie corresponding to the last character of
the user input string
(3) print out the user input + all the paths in the subtree of this node
e.g.,
a
b c l
d e f
user input: ab
the find b first,
print out
a + all paths(bd, be)
--> abd abe

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

: 第一题应该怎么做啊？ lz请明示。。。

j*32015-01-20 08:01

11 楼

赞啊，这个不是发bb面经那个么？

C*m2015-01-20 08:01

12 楼

New grads还没毕业

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

: 楼主拿到offer没。你工作经验几年。

C*m2015-01-20 08:01

13 楼

是呀别人肉哈

【在 j**********3 的大作中提到】

: 赞啊，这个不是发bb面经那个么？

l*82015-01-20 08:01

14 楼

这里的path是到叶子节点，还是到每一个节点都是一条path

of

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

: here is mine...
: (1) build a trie
: (2) locate the first node in the trie corresponding to the last character of
: the user input string
: (3) print out the user input + all the paths in the subtree of this node
: e.g.,
: a
: b c l
: d e f
: user input: ab

l*82015-01-20 08:01

15 楼

能否具体说下第二道题，random pointer是什么？

O(

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

C*m2015-01-20 08:01

16 楼

到子树的叶节点

【在 l*****8 的大作中提到】

: 这里的path是到叶子节点，还是到每一个节点都是一条path
:
: of

C*m2015-01-20 08:01

17 楼

除了正常的next, 另外加的random pointer 随机指向任意一个节点或者是null
比如
c a null a
| | | |
a --> b -- > c-- > d

【在 l*****8 的大作中提到】

: 能否具体说下第二道题，random pointer是什么？
:
: O(

l*82015-01-20 08:01