n***i
发帖数: 777 | 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**********o
发帖数: 140 | 2 我目前只能做到O(n)
當然, 如果能用額外空間, 比如BST來做index的話, 可以做O(lgN) |
n***i
发帖数: 777 | 3 不要考虑复杂度，就是把代码写对，各种情况考虑到。
【在 w**********o 的大作中提到】
: 我目前只能做到O(n)
: 當然, 如果能用額外空間, 比如BST來做index的話, 可以做O(lgN)
|
n***i
发帖数: 777 | 4 看来这道题做phone interview有点难。 |
l*****a
发帖数: 14598 | 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*****e
发帖数: 712 | 6 circular list可以连在任何一个node上吧，ending condition应该是这个node有没有
visit过吧，不需要一个hashmap track吗? 不过我想了一下，觉得insert应该比delete
a node好写 |
r****7
发帖数: 2282 | 7 为啥需要hashmap track呢？最多存一个start来track，而且像楼上说的，其实不用，
能插入的位置是唯一的啊
delete
【在 y*****e 的大作中提到】
: circular list可以连在任何一个node上吧，ending condition应该是这个node有没有
: visit过吧，不需要一个hashmap track吗? 不过我想了一下，觉得insert应该比delete
: a node好写
|
l*****a
发帖数: 14598 | 8 circular list应该是个环吧，不是的话另说了
delete
【在 y*****e 的大作中提到】
: circular list可以连在任何一个node上吧，ending condition应该是这个node有没有
: visit过吧，不需要一个hashmap track吗? 不过我想了一下，觉得insert应该比delete
: a node好写
|
y*****e
发帖数: 712 | 9 俺的意思是list的末端是只能连去head,还是可以连去list的任何一个node? 如果是可
以连在任何一个node,
curr在move的过程中是不是需要track，如果已经visit过说明入环了也就是走到底了。
【在 l*****a 的大作中提到】
: circular list应该是个环吧，不是的话另说了
:
: delete
|
l*****8
发帖数: 1083 | 10 没看出tricky的点在哪里。。。corner case处理一下，找到插入的位置，狠狠插入就
可以了
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不好
: 意思，本来想给个不太难的。大家能想到所有要考虑的情况吗？
: 还有觉得这个电面难度如何？
|
|
|
l*****a
发帖数: 14598 | 11 显然是tail.next=head吧
【在 y*****e 的大作中提到】
: 俺的意思是list的末端是只能连去head,还是可以连去list的任何一个node? 如果是可
: 以连在任何一个node,
: curr在move的过程中是不是需要track，如果已经visit过说明入环了也就是走到底了。
|
y*****e
发帖数: 712 | 12 汗。。是circular list啊，没仔细读题。。。
没想出太多的tricky point， 回家写写
【在 l*****a 的大作中提到】
: 显然是tail.next=head吧
|
n***i
发帖数: 777 | 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*****a
发帖数: 14598 | 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***i
发帖数: 777 | 15 是可以这么说，但是考虑到 双链表加环链表 让题目的复杂性提高了，我认为能够把这
些情况都考虑到是很不容易的了。你属于我说的牛的candidate了 ：）
【在 l*****a 的大作中提到】
: 你说的这些不都是链表的基本case吗？
:
: prev
|
l*****8
发帖数: 1083 | 16 猜测lz是google资深员工，不了解现在刷题的变态。。。
【在 l*****a 的大作中提到】
: 你说的这些不都是链表的基本case吗？
:
: prev
|
n***i
发帖数: 777 | 17 比如说，有人就忘了head有可能变，新节点可能大于tail，等等
【在 n***i 的大作中提到】
: 是可以这么说，但是考虑到 双链表加环链表 让题目的复杂性提高了，我认为能够把这
: 些情况都考虑到是很不容易的了。你属于我说的牛的candidate了 ：）
|
l*****8
发帖数: 1083 | 18 这题在lc里的话，算medium难度偏容易的
【在 n***i 的大作中提到】
: 是可以这么说，但是考虑到 双链表加环链表 让题目的复杂性提高了，我认为能够把这
: 些情况都考虑到是很不容易的了。你属于我说的牛的candidate了 ：）
|
n***i
发帖数: 777 | 19 所以如果phone screen 用它的话还是挺难的，我在考虑是否把它弄简单一点
【在 l*****8 的大作中提到】
: 这题在lc里的话，算medium难度偏容易的
|
y*****e
发帖数: 712 | 20 如果是同胞的话就让他过了吧。。
【在 n***i 的大作中提到】
: 所以如果phone screen 用它的话还是挺难的，我在考虑是否把它弄简单一点
|
n***i
发帖数: 777 | 21 面了个印度人
【在 y*****e 的大作中提到】
: 如果是同胞的话就让他过了吧。。
|
l*****8
发帖数: 1083 | |
