m******9
发帖数: 968 | 1 我做的真是稀烂，题目：
question 1： 给定一个singly linked list，删除指定的一个node
函数的signature是：deleteNode(Node* head, Node* remove);
head不是指代任意的node，就是指整个list的header
remove是要删除的node。
要求： 不可以用Node* previousNode 这样的变量。
question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
匹。
条件：
1. 每次最多只能挑出5匹马进行race
2. 不能计时，只能知道赛马的相对速度 （order）
就这样，答案是最少赛7次
尤其是，第一题怎么写呀？ |
s*********g
发帖数: 849 | 2 7 Races
Very interesting problem. well First race 5 sets of 5 horses. This
eliminates 2 horses from each race i. e numbers 4 and 5 of each set (as
stated above the fastest 3 in one set could possibly be the fastest 3 in
all 25 horses)Now we have 15 horses. Now we have 5 sets of 3 horses
each.
The 6th race will be between the fastest horses from the first 5 races.
The fastest horse in this race is the fastest of all 25.
Horses coming in 4th and 5th get there sets of 3 from the first 5 races
elimi
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
r*****e
发帖数: 264 | 3 I can give the idea on the first one:
If it is not the tail, copy the content of the next node to this node,
delete the next node. -- O(1)
If it is the tail, have to traverse the list until you reach the previous
node. -- O(n)
Special case: head removal.
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
p*****n
发帖数: 368 | 4 如果head==remove，是一种情况
否则每次move on之前先check一下是否next==remove
如果是就把next->next的指针copy过来
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
r*****e
发帖数: 264 | 5 One the second one, do the horses perform consistently?
If yes, 7 is the answer; if no, it is actually PageRank scheme (are you
interviewed by Google?) or RoundRobin tournament.
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
s*****r
发帖数: 773 | 6 第一题以前提到的solution应该是把后面的node copy到前一个, 然后释放最后一个?
不能直接从head开始找,找到到这个node了删掉么
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
S******A
发帖数: 1002 | 7 第一题应该是要求O(1)
pNext = remove->next;
remove->data=pNext->data;
remove->next = pNext->next;
delete pNext;
然后考虑remove == pHead
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
s*******s
发帖数: 1568 | 8 bloomberg?
1) memcopy remove's next node to current mem space of remove.
2) 7
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
n******h
发帖数: 50 | 9 第一题 即使不用previousnode指被删的前一个node，也至少要用一个tempnode来指向
要最终要free的node。总要有个临时变量的。 |
r*****e
发帖数: 264 | 10 Remove == tail is also a special case, since there is no data in the next
node.
【在 S******A 的大作中提到】
: 第一题应该是要求O(1)
: pNext = remove->next;
: remove->data=pNext->data;
: remove->next = pNext->next;
: delete pNext;
: 然后考虑remove == pHead
:
: 3
|
|
|
p*****n
发帖数: 368 | 11 你这不对，没保证remove的前一个node还能找到remove->next
【在 S******A 的大作中提到】
: 第一题应该是要求O(1)
: pNext = remove->next;
: remove->data=pNext->data;
: remove->next = pNext->next;
: delete pNext;
: 然后考虑remove == pHead
:
: 3
|
p*****n
发帖数: 368 | 12
这个是不知道head的情况
【在 s*****r 的大作中提到】
: 第一题以前提到的solution应该是把后面的node copy到前一个, 然后释放最后一个?
: 不能直接从head开始找,找到到这个node了删掉么
:
: 3
|
H*M
发帖数: 1268 | 13 本版就讨论过很多次了
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
m******9
发帖数: 968 | 14 cool, 我想这是他想要的答案，他想要的应该就是copy的方法
我当时给他的方法是笨办法。
【在 r*****e 的大作中提到】
: I can give the idea on the first one:
: If it is not the tail, copy the content of the next node to this node,
: delete the next node. -- O(1)
: If it is the tail, have to traverse the list until you reach the previous
: node. -- O(n)
: Special case: head removal.
:
: 3
|
m******9
发帖数: 968 | 15 删除以后，需要重新把list连接起来。 所以需要处理preNode, currentNode,
nextNode.
不过楼上给的答案好帮，怪我以前没复习到位，没想到copy的方法，
【在 s*****r 的大作中提到】
: 第一题以前提到的solution应该是把后面的node copy到前一个, 然后释放最后一个?
: 不能直接从head开始找,找到到这个node了删掉么
:
: 3
|
m*****f
发帖数: 1243 | 16 comfort 这题很老了
【在 m******9 的大作中提到】
: 删除以后，需要重新把list连接起来。 所以需要处理preNode, currentNode,
: nextNode.
: 不过楼上给的答案好帮，怪我以前没复习到位，没想到copy的方法，
|
a****m
发帖数: 83 | 17 马先分五组比赛:
五场下来选出每组头三名
a1 a2 a3
b1 b2 b3
c1 c2 c3
d1 d2 d3
e1 e2 e3
第六场比赛: a1 b1 c1 d1 e1 比
后两名整组淘汰, 比如d和e组, 第三名(假定是c1)淘汰组内其他马 (c2 c3)
剩下a1 b1
第七场比赛:
a2 a3 b2 b3 c1.
选出最快的, 加a1 b1 就是最快的三匹. |
n*******s
发帖数: 482 | 18 must be 2sigma. The recuiter's question, not 2 sigma's. |
m******9
发帖数: 968 | 19 这个公司是akamai，一家网络公司，大家干兴趣的话，也去投递把 |
H*M
发帖数: 1268 | 20 谢谢
请问你是在他们网站投的吗？
【在 m******9 的大作中提到】
: 这个公司是akamai，一家网络公司，大家干兴趣的话，也去投递把
|
|
|
m*****f
发帖数: 1243 | 21 类似第一题的另外一题, 你没做过的话就看看吧
A single LL, aside from the "next" pointer, each node has a pointer points
to a random member of the list. Copy the LL.
异曲同工之妙
【在 m******9 的大作中提到】
: 这个公司是akamai，一家网络公司，大家干兴趣的话，也去投递把
|
c*****o
发帖数: 178 | 22 第六场b1不一定是第二名，a2，a3都可能比b1快，这里只能确定a1是第一。
第七场才能比出第二名和第三名。
【在 a****m 的大作中提到】
: 马先分五组比赛:
: 五场下来选出每组头三名
: a1 a2 a3
: b1 b2 b3
: c1 c2 c3
: d1 d2 d3
: e1 e2 e3
: 第六场比赛: a1 b1 c1 d1 e1 比
: 后两名整组淘汰, 比如d和e组, 第三名(假定是c1)淘汰组内其他马 (c2 c3)
: 剩下a1 b1
|
m******9
发帖数: 968 | 23 没错，我就是他们网站直接投的，不过要抓紧投，他们正面的火热，
【在 H*M 的大作中提到】
: 谢谢
: 请问你是在他们网站投的吗？
|
m******9
发帖数: 968 | 24 got it,多谢提醒
【在 m*****f 的大作中提到】
: 类似第一题的另外一题, 你没做过的话就看看吧
: A single LL, aside from the "next" pointer, each node has a pointer points
: to a random member of the list. Copy the LL.
: 异曲同工之妙
|
H*****L
发帖数: 5705 | 25 晕...你不需要remove的前一个node
你需要O(1)
head是用来处理remove=head/tail的特殊情况的
【在 p*****n 的大作中提到】
: 你这不对，没保证remove的前一个node还能找到remove->next
|
H*M
发帖数: 1268 | 26 呵呵
谢谢
刚一下投了他家8份。
不知道多久能收到feedback呢？
【在 m******9 的大作中提到】
: 没错，我就是他们网站直接投的，不过要抓紧投，他们正面的火热，
|
f****b
发帖数: 486 | 27 牛，你这是彻底把投简历灌水化了，知道为啥有人每天能投那么多了
【在 H*M 的大作中提到】
: 呵呵
: 谢谢
: 刚一下投了他家8份。
: 不知道多久能收到feedback呢？
|
h**k
发帖数: 3368 | 28 第7场改成a2,a3,b1,b2,c1然后取前两名就对了。
【在 a****m 的大作中提到】
: 马先分五组比赛:
: 五场下来选出每组头三名
: a1 a2 a3
: b1 b2 b3
: c1 c2 c3
: d1 d2 d3
: e1 e2 e3
: 第六场比赛: a1 b1 c1 d1 e1 比
: 后两名整组淘汰, 比如d和e组, 第三名(假定是c1)淘汰组内其他马 (c2 c3)
: 剩下a1 b1
|
m******9
发帖数: 968 | 29 我不是很明白的是，怎么做到O(1)？
我知道，只是单纯的delete，就是将remove->next中的内容bit copy到remove里面，然后再删除remove->next, 这个步骤是O(1)的。
不过如果在处理special case时，也需要确认remove是不是就一定在list之中，也有可能remove压根不在list之中，这个确认需要O(n)
但是如果就assume，remove就已经在list之中了，那就是O(1)
【在 H*****L 的大作中提到】
: 晕...你不需要remove的前一个node
: 你需要O(1)
: head是用来处理remove=head/tail的特殊情况的
|
m******9
发帖数: 968 | 30 是1个星期左右回复的，
【在 H*M 的大作中提到】
: 呵呵
: 谢谢
: 刚一下投了他家8份。
: 不知道多久能收到feedback呢？
|
|
|
c*****y
发帖数: 90 | 31 你的方法是对的。但我有个问题：题目给了head和removenode，那么除开head=
removenode的情况
外，你都要traverse the list until you find the removenode。是不是可以就用
currentnode.next和removenode比较，如果相等，则找到了，currentnode的下一个就是
removenode，这样再进行处理？我的意思是：是不是tail并非一个特例，和其他情况同
样处理。
previous
【在 r*****e 的大作中提到】
: I can give the idea on the first one:
: If it is not the tail, copy the content of the next node to this node,
: delete the next node. -- O(1)
: If it is the tail, have to traverse the list until you reach the previous
: node. -- O(n)
: Special case: head removal.
:
: 3
|
f****b
发帖数: 486 | 32 removenode只要不是tail，都不用traverse就可以O(1)删除
就是
【在 c*****y 的大作中提到】
: 你的方法是对的。但我有个问题：题目给了head和removenode，那么除开head=
: removenode的情况
: 外，你都要traverse the list until you find the removenode。是不是可以就用
: currentnode.next和removenode比较，如果相等，则找到了，currentnode的下一个就是
: removenode，这样再进行处理？我的意思是：是不是tail并非一个特例，和其他情况同
: 样处理。
:
: previous
|
r*****e
发帖数: 264 | 33 where is the trap?
【在 m*****f 的大作中提到】
: 类似第一题的另外一题, 你没做过的话就看看吧
: A single LL, aside from the "next" pointer, each node has a pointer points
: to a random member of the list. Copy the LL.
: 异曲同工之妙
|
r*****e
发帖数: 264 | |
c*****y
发帖数: 90 | 35 谢谢。看来我对题目的理解有误，我以为先要找到那个removenode，再进行下下一步操
作。如果题目
就是removenode已经指给你了，那就不要traverse就可以O(1)删除了。
【在 f****b 的大作中提到】
: removenode只要不是tail，都不用traverse就可以O(1)删除
:
: 就是
|
m******r
发帖数: 61 | 36 太难了
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
c*******d
发帖数: 255 | 37 25匹马那题：
1.分组赛：任意分成5组，每组5匹，进行比赛，并记下名次
2.快马赛：每组的第一名挑出来进行比赛，记下名次
3.最终赛：快马赛第一名的组的2，3名，第2名组的第1，2名，第3名组的第1名再比一次
快马赛的第一名总体排名第一
最终赛的第1，2名总体排名分别为2，3
这样一共赛7场
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
h********0
发帖数: 440 | 38 directly free(deleteNode) after changing pointers.
【在 n******h 的大作中提到】
: 第一题 即使不用previousnode指被删的前一个node，也至少要用一个tempnode来指向
: 要最终要free的node。总要有个临时变量的。
|
n******h
发帖数: 50 | 39 after changing the pointer (moving forward I suppose you mean), you lose the
address of the node to delete. How can you not use another temp pointer?
【在 h********0 的大作中提到】
: directly free(deleteNode) after changing pointers.
|
g***3
发帖数: 2304 | |
|
|
s********l
发帖数: 648 | 41 ft, 第二道题我也面过, 同样稀烂
3
【在 m******9 的大作中提到】
: 我做的真是稀烂，题目：
: question 1： 给定一个singly linked list，删除指定的一个node
: 函数的signature是：deleteNode(Node* head, Node* remove);
: head不是指代任意的node，就是指整个list的header
: remove是要删除的node。
: 要求： 不可以用Node* previousNode 这样的变量。
: question 2: 25 horse puzzle， 给定25个马，问题：用最少多少次可以找出最快的3
: 匹。
: 条件：
: 1. 每次最多只能挑出5匹马进行race
|
