今天Google电面的一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

今天Google电面的一道题

今天Google电面的一道题# JobHunting - 待字闺中

n*i2015-01-26 08:01

1 楼

今天参加google的电面，我想了一下出什么题，突然一个念头闪过，出了下面这个题
Add a key (integer type) into a circular doubly linked list so that the list
maintains a sorted order. The head has the smallest value.
我原本觉得不算难，但是在面的过程中渐渐发现不trivial，有点对那个candidate不好
意思，本来想给个不太难的。大家能想到所有要考虑的情况吗？
还有觉得这个电面难度如何？

w*o2015-01-26 08:01

2 楼

我目前只能做到O(n)
當然, 如果能用額外空間, 比如BST來做index的話, 可以做O(lgN)

n*i2015-01-26 08:01

3 楼

不要考虑复杂度，就是把代码写对，各种情况考虑到。

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

: 我目前只能做到O(n)
: 當然, 如果能用額外空間, 比如BST來做index的話, 可以做O(lgN)

n*i2015-01-26 08:01

4 楼

看来这道题做phone interview有点难。

l*a2015-01-26 08:01

5 楼

1)这道题的出现频率不低，不过远远不够google onsite的难度吧
2)这题要考虑很多情况吗？你的circular DDL不是已经sorted了吗
0/1 item算是特殊情况
然后比较是否在current.val<=target<=current.next.val之间，if yes, then
insert,
otherwise, current=current.next until current.next==head
then insert and update head

list

【在 n***i 的大作中提到】

: 今天参加google的电面，我想了一下出什么题，突然一个念头闪过，出了下面这个题
: Add a key (integer type) into a circular doubly linked list so that the list
: maintains a sorted order. The head has the smallest value.
: 我原本觉得不算难，但是在面的过程中渐渐发现不trivial，有点对那个candidate不好
: 意思，本来想给个不太难的。大家能想到所有要考虑的情况吗？
: 还有觉得这个电面难度如何？

y*e2015-01-26 08:01

6 楼

circular list可以连在任何一个node上吧，ending condition应该是这个node有没有
visit过吧，不需要一个hashmap track吗? 不过我想了一下，觉得insert应该比delete
a node好写

r*72015-01-26 08:01

7 楼

为啥需要hashmap track呢？最多存一个start来track，而且像楼上说的，其实不用，
能插入的位置是唯一的啊

delete

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

: circular list可以连在任何一个node上吧，ending condition应该是这个node有没有
: visit过吧，不需要一个hashmap track吗? 不过我想了一下，觉得insert应该比delete
: a node好写

l*a2015-01-26 08:01

8 楼

circular list应该是个环吧，不是的话另说了

delete

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

y*e2015-01-26 08:01

9 楼

俺的意思是list的末端是只能连去head,还是可以连去list的任何一个node? 如果是可
以连在任何一个node,
curr在move的过程中是不是需要track，如果已经visit过说明入环了也就是走到底了。

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

: circular list应该是个环吧，不是的话另说了
:
: delete

l*82015-01-26 08:01

10 楼

没看出tricky的点在哪里。。。corner case处理一下，找到插入的位置，狠狠插入就
可以了

list

【在 n***i 的大作中提到】

l*a2015-01-26 08:01

11 楼

显然是tail.next=head吧

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

: 俺的意思是list的末端是只能连去head,还是可以连去list的任何一个node? 如果是可
: 以连在任何一个node,
: curr在move的过程中是不是需要track，如果已经visit过说明入环了也就是走到底了。

y*e2015-01-26 08:01

12 楼

汗。。是circular list啊，没仔细读题。。。
没想出太多的tricky point，回家写写

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

: 显然是tail.next=head吧

n*i2015-01-26 08:01

13 楼

这题有以下几个点
如果 head 是 null，要create 一个node 然后return它作为head。这个node如果prev
和 next 都连到自己，那么 1 item的情况可以被general case 所包括
general case 里面：
先看看要加的key是否大于等于 tail 的key，如果是的话，加入的key应该在tail 和
head 之间。tail 通过 head->prev 得到
如果要加的key比tail小，那么就
curr = head;
while(curr->key < keyToInsert) {
curr = curr -> next;
}
然后while loop停下来，新node要加在 curr 和 curr->prev 之间。
如果curr = head, head还要被update成新加的new node
最后return head
--------
如果整个过程没有任何问题我觉得这个candidate还是很牛的

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

: 1)这道题的出现频率不低，不过远远不够google onsite的难度吧
: 2)这题要考虑很多情况吗？你的circular DDL不是已经sorted了吗
: 0/1 item算是特殊情况
: 然后比较是否在current.val<=target<=current.next.val之间，if yes, then
: insert,
: otherwise, current=current.next until current.next==head
: then insert and update head
:
: list

l*a2015-01-26 08:01

14 楼

你说的这些不都是链表的基本case吗？

prev

【在 n***i 的大作中提到】

: 这题有以下几个点
: 如果 head 是 null，要create 一个node 然后return它作为head。这个node如果prev
: 和 next 都连到自己，那么 1 item的情况可以被general case 所包括
: general case 里面：
: 先看看要加的key是否大于等于 tail 的key，如果是的话，加入的key应该在tail 和
: head 之间。tail 通过 head->prev 得到
: 如果要加的key比tail小，那么就
: curr = head;
: while(curr->key < keyToInsert) {
: curr = curr -> next;

n*i2015-01-26 08:01

15 楼

是可以这么说，但是考虑到双链表加环链表让题目的复杂性提高了，我认为能够把这
些情况都考虑到是很不容易的了。你属于我说的牛的candidate了：）

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

: 你说的这些不都是链表的基本case吗？
:
: prev

l*82015-01-26 08:01

16 楼

猜测lz是google资深员工，不了解现在刷题的变态。。。

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

: 你说的这些不都是链表的基本case吗？
:
: prev

n*i2015-01-26 08:01

17 楼

比如说，有人就忘了head有可能变，新节点可能大于tail，等等

【在 n***i 的大作中提到】

: 是可以这么说，但是考虑到双链表加环链表让题目的复杂性提高了，我认为能够把这
: 些情况都考虑到是很不容易的了。你属于我说的牛的candidate了：）