l**n
发帖数: 88 | 1 职位为: financial software developer
1. You have a revolver gun with one bullet in six chambers. I first shoot
the gun on my head and it did not fire. Then it is your turn. Do you choose
to spin the cylinder then shoot on your head on directly shoot on your head.
why?
2. find whether there is a loop in a linked list. Do you have other ways
instead of using a quick pointer and a slow pointer?
3. Why people usually do binary search instead of triple search (divide the
array into three parts each time |
c***g
发帖数: 472 | 2 第三题怎么解释?
choose
head.
the
【在 l**n 的大作中提到】
: 职位为: financial software developer
: 1. You have a revolver gun with one bullet in six chambers. I first shoot
: the gun on my head and it did not fire. Then it is your turn. Do you choose
: to spin the cylinder then shoot on your head on directly shoot on your head.
: why?
: 2. find whether there is a loop in a linked list. Do you have other ways
: instead of using a quick pointer and a slow pointer?
: 3. Why people usually do binary search instead of triple search (divide the
: array into three parts each time
|
c**********e
发帖数: 2007 | 3 For binary search, after 2 steps (checking two points), the remaining
interval (or array length, etc) is 1/4 of the original one. But for
triple search, after 1 step (checking 2 points), the remaining interval
(or array length, etc) is 1/3 of the original one.
For an example, if an array a[1000] is sorted. You want to find
some i such that a[i]=35. For binary search, after first checking
a[500], then checking either a[250] or a[750], i is narrowed down
to a subarray of 250 integers. But for tri
【在 c***g 的大作中提到】
: 第三题怎么解释?
:
: choose
: head.
: the
|
m******9
发帖数: 968 | 4 第3题我是想，用binary search，每次比较可以筛除掉1/2
但是triple search，每次比较只能筛除掉1/3
所以，还是binary search要好一些 |
l******4
发帖数: 729 | 5 第三题，我是这样想的。
分得越多，比较的次数越多，越傻。
binary, 比较4次，除掉3/4
triple, 比较4次，除掉2/3
你要是分成n/2段search，就成了linear search
第6题，什么答案？ 数组行吗？ |
s*****i
发帖数: 355 | 6 没人对第一题感兴趣？三个门猜山羊的变种?
choose
head.
the
【在 l**n 的大作中提到】
: 职位为: financial software developer
: 1. You have a revolver gun with one bullet in six chambers. I first shoot
: the gun on my head and it did not fire. Then it is your turn. Do you choose
: to spin the cylinder then shoot on your head on directly shoot on your head.
: why?
: 2. find whether there is a loop in a linked list. Do you have other ways
: instead of using a quick pointer and a slow pointer?
: 3. Why people usually do binary search instead of triple search (divide the
: array into three parts each time
|
P**********0
发帖数: 412 | |
s*****i
发帖数: 355 | 8 简单点的，保存一下每次访问过的节点，前提是不能有重复的值。
一个链表里面的值全部相等，有loop，用单指针怎么查?
【在 P**********0 的大作中提到】
: 弱弱的问，第二题怎么答？
|
f****4
发帖数: 1359 | 9 第一题
spin（不spin，死的机会是1/5;spin 死的机会是1/6）
3个门的题目，开了一个门之后，另2个们赢的机会 50%:50%
没必要换啊？
有错请指出
第5
pointer size
x86体系的虚拟内存一般都是4G,也就是2的32次方,32位的指针可以覆盖所有的虚拟内存区域,所以一般是 4个字节 |
r****o
发帖数: 1950 | 10 可以保存每次访问过的节点的地址吗?
【在 s*****i 的大作中提到】
: 简单点的，保存一下每次访问过的节点，前提是不能有重复的值。
: 一个链表里面的值全部相等，有loop，用单指针怎么查?
|
|
|
r**u
发帖数: 1567 | 11 2. hash the address of each node, 如果conflict就比较address。
3. binary search每次比较一次，需要log2（n）层比较。total: log2(n)
如果是triple search每次比较2此，需要log3(n)层比较。total: 2*log3(n) = 2 * log2(n)/log2（3）> log2(n)。
也就是都是O(logn)，但是前面的constant不一样，binary该是最小的。
6. 经常变化就需要快速查询，修改，hash或者array啥的都合理吧。
【在 s*****i 的大作中提到】
: 简单点的，保存一下每次访问过的节点，前提是不能有重复的值。
: 一个链表里面的值全部相等，有loop，用单指针怎么查?
|
o*******7
发帖数: 13 | 12 3个门要换
【在 f****4 的大作中提到】
: 第一题
: spin（不spin，死的机会是1/5;spin 死的机会是1/6）
: 3个门的题目，开了一个门之后，另2个们赢的机会 50%:50%
: 没必要换啊？
: 有错请指出
: 第5
: pointer size
: x86体系的虚拟内存一般都是4G,也就是2的32次方,32位的指针可以覆盖所有的虚拟内存区域,所以一般是 4个字节
|
r****o
发帖数: 1950 | 13 我觉得3个门换不换是要看主持人是不是故意的，还是随机的打开了一扇有养的门吧。
如果是故意的就要换，随机的则不换。
另外，那这个手枪要spin吗？是不是也要看第一个人是不是知道枪里有没有子弹先?
【在 o*******7 的大作中提到】
: 3个门要换
|
o*******7
发帖数: 13 | 14 试一下解这个题...
bool check_loop (node* head) {
if !(head && head->next) return false;
node* stored=head->next;
node* p=head->next;
head->next=NULL;
while (p->next) p=p->next;
head->next=stored;
return (head==p);
}
【在 s*****i 的大作中提到】
: 简单点的，保存一下每次访问过的节点，前提是不能有重复的值。
: 一个链表里面的值全部相等，有loop，用单指针怎么查?
|
o*******7
发帖数: 13 | 15 不可能是随机的。如果真的是随机的，主持人就有可能打开有羊的门。这个游戏就没法
玩了。
【在 r****o 的大作中提到】
: 我觉得3个门换不换是要看主持人是不是故意的，还是随机的打开了一扇有养的门吧。
: 如果是故意的就要换，随机的则不换。
: 另外，那这个手枪要spin吗？是不是也要看第一个人是不是知道枪里有没有子弹先?
|
r****o
发帖数: 1950 | 16 没看明白，
这里p是不是就是NULL了？
如果有loop的话，这里会不会一直循环?
【在 o*******7 的大作中提到】
: 试一下解这个题...
: bool check_loop (node* head) {
: if !(head && head->next) return false;
: node* stored=head->next;
: node* p=head->next;
: head->next=NULL;
: while (p->next) p=p->next;
: head->next=stored;
: return (head==p);
: }
|
C*******n
发帖数: 40 | 17 Loop 不一定是从head 开始吧？
为什么不用hash table, 检查是否下一个node是以前出现过的？
【在 o*******7 的大作中提到】
: 试一下解这个题...
: bool check_loop (node* head) {
: if !(head && head->next) return false;
: node* stored=head->next;
: node* p=head->next;
: head->next=NULL;
: while (p->next) p=p->next;
: head->next=stored;
: return (head==p);
: }
|
o*******7
发帖数: 13 | 18 说的对
【在 C*******n 的大作中提到】
: Loop 不一定是从head 开始吧？
: 为什么不用hash table, 检查是否下一个node是以前出现过的？
|
