媒体从业人员 VS 狗# Joke - 肚皮舞运动
S*I
1 楼
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，总是先遇见leftchild,
再遇见right child，假设输入没有问题。要求返回root。需要keep track of root,
最后用了一个hashset + 一个hashmap
说说怎么设计card class和deck class，各有哪些函数，什么时候static什么时候private，什么时候有返回，什么情况不返回
4. 如果要死就死这个geek手里了
一开始问了一堆behaivior question，比较tough
一道joseph problem题，但他说每次是1-based index 死，经典题目是0-based
，所以我code （单向circular链表）的里有一个bug。脑子已经不太转了，他说是当k
= 1的时候。 最后在最前面加上 if k ==1, return n...
这人看起来就是个geek中的geek，我刚写完他就说有一个bug。他说他见过一个最好的解法，用一个circular buffer，什么每次走到k的位置就不放在最后面。。。没明白这解法有什么好的
回来后想来想去最后一个人可能是bar raiser。。。求祝福和包子安慰。。
☆─────────────────────────────────────☆
icn9 (icn) 于 (Wed Apr 6 14:30:59 2011, 美东) 提到:
谢谢分享，能问一下是什么组吗
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:31:40 2011, 美东) 提到:
pm你了
☆─────────────────────────────────────☆
icn9 (icn) 于 (Wed Apr 6 14:39:23 2011, 美东) 提到:
bar raiser可能就是challenge candidate的，让人觉得比较tough,祝一举拿下offer!
☆─────────────────────────────────────☆
godmode (godmode) 于 (Wed Apr 6 14:41:29 2011, 美东) 提到:
bless
你的题目我感觉比看到的其他a面筋要难一点
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 6 14:42:53 2011, 美东) 提到:
bless早日拿到offer
人还是很看背景的
,
候private，什么时候有返回，什么情况不返回
k
的解法，用一个circular buffer，什么每次走到k的位置就不放在最后面。。。没明白
这解法有什么好的
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:47:58 2011, 美东) 提到:
我觉得题目本身不算难，我看版上的难题都没问道。。。
但是他们就题目本身引申的东西我都没准备过，比如算sqrt float的精确度和时间复杂
度关系，还有paint fill的method stack，也可能是大家发面经的时候没提到这部分，
我从没仔细想过，其实也是自己平时太粗心了
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 14:56:39 2011, 美东) 提到:
what is paint fill and what is method stack?
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:01:55 2011, 美东) 提到:
让我想起了quake3里面那个神奇的inverse sqrt算法，呵呵
牛顿方法里复杂度和精度的关系，不看真的不容易想到。
http://en.citizendium.org/wiki/Newton's_method#Computation
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:05:21 2011, 美东) 提到:
重新再学习一下
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can
be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
☆─────────────────────────────────────☆
godmode (godmode) 于 (Wed Apr 6 15:26:59 2011, 美东) 提到:
我觉得跟其他人发的amazon的coding题比起来，你的更麻烦些，当然我比较菜了...
相比g和f，当然这些题还是比较常见或者可以马上有idea的.
ps,据我所知bar raiser不光是challenge candidate,如果丫不让人过的话其他人都过
了也没用,恶心阿
祝你能拿到offer :)
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:33:01 2011, 美东) 提到:
是阿，所以回来越想越难过
谢谢你的祝福：）
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:33:39 2011, 美东) 提到:
我是用binary search弄的。。。。回头仔细研究一下你这个解法
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:35:05 2011, 美东) 提到:
一个bitmap/matrix，往里填色，见career cup
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:38:22 2011, 美东) 提到:
用newton's method，收敛快很多
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 6 16:36:01 2011, 美东) 提到:
这个bt的解法依赖于0x5f3759df这个神奇的初值
不是一般的思路能够想到的。。
☆─────────────────────────────────────☆
nowheresep (nowheresep) 于 (Wed Apr 6 17:14:15 2011, 美东) 提到:
bless~~~~~~~~~~~~
☆─────────────────────────────────────☆
ilove (小虾) 于 (Wed Apr 6 17:30:23 2011, 美东) 提到:
big bless.
楼主能不能展开说说重建二叉树的那题呢？ ＜PARENT， CHILD＞是数值还是指针呢？
不是很明白题目的意思拉 能不能举个例子啊 谢谢
☆─────────────────────────────────────☆
Hond (云卷云舒) 于 (Wed Apr 6 18:07:47 2011, 美东) 提到:
bless mm.
祝拿OFFER~
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 21:24:08 2011, 美东) 提到:
比如输入是{(A,B),(A,C),(B,D),(B,F),(H,A),....}
树应该是这样的, 最后返回root
H
/
A
/ \
B C
/ \
D F
？
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 21:35:18 2011, 美东) 提到:
what is the complexity requirement?
i think O(NlgN) is easy to come up with.
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 21:36:14 2011, 美东) 提到:
oh, actually if we do hash map, O(N) is enough.
☆─────────────────────────────────────☆
ilove (小虾) 于 (Wed Apr 6 23:37:12 2011, 美东) 提到:
how to code it in O(n) ? assume you have hash map ?
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 23:49:05 2011, 美东) 提到:
对，时间空间都是O(n)
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 23:50:47 2011, 美东) 提到:
今天和老板说了面试的经历，他说我毕业后如果想留下可以stay as long as I want..
. 还可以给我弄H1B，感动了。。
☆─────────────────────────────────────☆
cmhero2008 (dada) 于 (Wed Apr 6 23:59:57 2011, 美东) 提到:
good luck
☆─────────────────────────────────────☆
ilove (小虾) 于 (Thu Apr 7 00:17:58 2011, 美东) 提到:
我能想的方法是先找到根节点， 然后用类似于先根的递归去做了。 还有找到ROOT的节
电应该扫描两遍吗？ 有没有什么更好的方法？ 楼主如何解的？
..
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Thu Apr 7 12:00:58 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
☆─────────────────────────────────────☆
madmonk (madmonk) 于 (Sun Apr 10 19:00:19 2011, 美东) 提到:
for joseph's problem, just googled this page: http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3521
There are n persons numbered from 0 to n - 1 standing in a circle. The
person number k, counting from the person number 0, is executed. After that
the person number k of the remaining persons is executed, counting from the
person after the last executed one. The process continues until only one
person is left. This person is a survivor. The problem is, given n and k
detect the survivor's number in the original circle.
Of course, all of you know the way to solve this problem. The solution is
very short, all you need is one cycle:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
I do not understand this solution at all, and I tested n=5 and k=1, it runs
and returns 4, but I manually get the right answer should be 2 as follows:
init:
0 1 2 3 4
0 2 3 4 1 is killed, counting from 2
0 2 4 3 is killed, counting from 4
2 4 0 is killed counting from 2,
2 4 killed
Did I miss something?
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Mon Apr 11 23:06:38 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:09:55 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:21:22 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:46:45 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:55:56 2011, 美东) 提到:
for joseph's problem, just googled this page:
http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3521
There are n persons numbered from 0 to n - 1 standing in a circle. The
person number k, counting from the person number 0, is executed. After that
the person number k of the remaining persons is executed, counting from the
person after the last executed one. The process continues until only one
person is left. This person is a survivor. The problem is, given n and k
detect the survivor's number in the original circle.
Of course, all of you know the way to solve this problem. The solution is
very short, all you need is one cycle:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
I do not understand this solution at all, and I tested n=5 and k=1, it runs
and returns 4, but I manually get the right answer should be 2 as follows:
init:
0 1 2 3 4
0 2 3 4 1 is killed, counting from 2
0 2 4 3 is killed, counting from 4
2 4 0 is killed counting from 2,
2 4 killed
Did I miss something?
For 0 based i.e k = 0, 1, 2... inti: 0 1 2 3 4
r := 0;
for i from 1 to n do
r := (r + k + 1) mod i;
return r;
For 1 based i.e k = 1, 2... inti: 1 2 3 4 5
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r + 1;
☆─────────────────────────────────────☆
lh2006 (lh) 于 (Tue Apr 12 13:05:43 2011, 美东) 提到:
bless !
☆─────────────────────────────────────☆
madmonk (madmonk) 于 (Tue Apr 12 17:39:30 2011, 美东) 提到:
thanks, I figured the k base out afterwards, but still no idea when this
loop works and how to prove it is correct.
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，总是先遇见leftchild,
再遇见right child，假设输入没有问题。要求返回root。需要keep track of root,
最后用了一个hashset + 一个hashmap
说说怎么设计card class和deck class，各有哪些函数，什么时候static什么时候private，什么时候有返回，什么情况不返回
4. 如果要死就死这个geek手里了
一开始问了一堆behaivior question，比较tough
一道joseph problem题，但他说每次是1-based index 死，经典题目是0-based
，所以我code （单向circular链表）的里有一个bug。脑子已经不太转了，他说是当k
= 1的时候。 最后在最前面加上 if k ==1, return n...
这人看起来就是个geek中的geek，我刚写完他就说有一个bug。他说他见过一个最好的解法，用一个circular buffer，什么每次走到k的位置就不放在最后面。。。没明白这解法有什么好的
回来后想来想去最后一个人可能是bar raiser。。。求祝福和包子安慰。。
☆─────────────────────────────────────☆
icn9 (icn) 于 (Wed Apr 6 14:30:59 2011, 美东) 提到:
谢谢分享，能问一下是什么组吗
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:31:40 2011, 美东) 提到:
pm你了
☆─────────────────────────────────────☆
icn9 (icn) 于 (Wed Apr 6 14:39:23 2011, 美东) 提到:
bar raiser可能就是challenge candidate的，让人觉得比较tough,祝一举拿下offer!
☆─────────────────────────────────────☆
godmode (godmode) 于 (Wed Apr 6 14:41:29 2011, 美东) 提到:
bless
你的题目我感觉比看到的其他a面筋要难一点
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 6 14:42:53 2011, 美东) 提到:
bless早日拿到offer
人还是很看背景的
,
候private，什么时候有返回，什么情况不返回
k
的解法，用一个circular buffer，什么每次走到k的位置就不放在最后面。。。没明白
这解法有什么好的
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:47:58 2011, 美东) 提到:
我觉得题目本身不算难，我看版上的难题都没问道。。。
但是他们就题目本身引申的东西我都没准备过，比如算sqrt float的精确度和时间复杂
度关系，还有paint fill的method stack，也可能是大家发面经的时候没提到这部分，
我从没仔细想过，其实也是自己平时太粗心了
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 14:56:39 2011, 美东) 提到:
what is paint fill and what is method stack?
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:01:55 2011, 美东) 提到:
让我想起了quake3里面那个神奇的inverse sqrt算法，呵呵
牛顿方法里复杂度和精度的关系，不看真的不容易想到。
http://en.citizendium.org/wiki/Newton's_method#Computation
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:05:21 2011, 美东) 提到:
重新再学习一下
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can
be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
☆─────────────────────────────────────☆
godmode (godmode) 于 (Wed Apr 6 15:26:59 2011, 美东) 提到:
我觉得跟其他人发的amazon的coding题比起来，你的更麻烦些，当然我比较菜了...
相比g和f，当然这些题还是比较常见或者可以马上有idea的.
ps,据我所知bar raiser不光是challenge candidate,如果丫不让人过的话其他人都过
了也没用,恶心阿
祝你能拿到offer :)
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:33:01 2011, 美东) 提到:
是阿，所以回来越想越难过
谢谢你的祝福：）
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:33:39 2011, 美东) 提到:
我是用binary search弄的。。。。回头仔细研究一下你这个解法
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 15:35:05 2011, 美东) 提到:
一个bitmap/matrix，往里填色，见career cup
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Wed Apr 6 15:38:22 2011, 美东) 提到:
用newton's method，收敛快很多
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 6 16:36:01 2011, 美东) 提到:
这个bt的解法依赖于0x5f3759df这个神奇的初值
不是一般的思路能够想到的。。
☆─────────────────────────────────────☆
nowheresep (nowheresep) 于 (Wed Apr 6 17:14:15 2011, 美东) 提到:
bless~~~~~~~~~~~~
☆─────────────────────────────────────☆
ilove (小虾) 于 (Wed Apr 6 17:30:23 2011, 美东) 提到:
big bless.
楼主能不能展开说说重建二叉树的那题呢？ ＜PARENT， CHILD＞是数值还是指针呢？
不是很明白题目的意思拉 能不能举个例子啊 谢谢
☆─────────────────────────────────────☆
Hond (云卷云舒) 于 (Wed Apr 6 18:07:47 2011, 美东) 提到:
bless mm.
祝拿OFFER~
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 21:24:08 2011, 美东) 提到:
比如输入是{(A,B),(A,C),(B,D),(B,F),(H,A),....}
树应该是这样的, 最后返回root
H
/
A
/ \
B C
/ \
D F
？
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 21:35:18 2011, 美东) 提到:
what is the complexity requirement?
i think O(NlgN) is easy to come up with.
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Wed Apr 6 21:36:14 2011, 美东) 提到:
oh, actually if we do hash map, O(N) is enough.
☆─────────────────────────────────────☆
ilove (小虾) 于 (Wed Apr 6 23:37:12 2011, 美东) 提到:
how to code it in O(n) ? assume you have hash map ?
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 23:49:05 2011, 美东) 提到:
对，时间空间都是O(n)
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 23:50:47 2011, 美东) 提到:
今天和老板说了面试的经历，他说我毕业后如果想留下可以stay as long as I want..
. 还可以给我弄H1B，感动了。。
☆─────────────────────────────────────☆
cmhero2008 (dada) 于 (Wed Apr 6 23:59:57 2011, 美东) 提到:
good luck
☆─────────────────────────────────────☆
ilove (小虾) 于 (Thu Apr 7 00:17:58 2011, 美东) 提到:
我能想的方法是先找到根节点， 然后用类似于先根的递归去做了。 还有找到ROOT的节
电应该扫描两遍吗？ 有没有什么更好的方法？ 楼主如何解的？
..
☆─────────────────────────────────────☆
happymermaid (娆) 于 (Thu Apr 7 12:00:58 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
☆─────────────────────────────────────☆
madmonk (madmonk) 于 (Sun Apr 10 19:00:19 2011, 美东) 提到:
for joseph's problem, just googled this page: http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3521
There are n persons numbered from 0 to n - 1 standing in a circle. The
person number k, counting from the person number 0, is executed. After that
the person number k of the remaining persons is executed, counting from the
person after the last executed one. The process continues until only one
person is left. This person is a survivor. The problem is, given n and k
detect the survivor's number in the original circle.
Of course, all of you know the way to solve this problem. The solution is
very short, all you need is one cycle:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
I do not understand this solution at all, and I tested n=5 and k=1, it runs
and returns 4, but I manually get the right answer should be 2 as follows:
init:
0 1 2 3 4
0 2 3 4 1 is killed, counting from 2
0 2 4 3 is killed, counting from 4
2 4 0 is killed counting from 2,
2 4 killed
Did I miss something?
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Mon Apr 11 23:06:38 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:09:55 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:21:22 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:46:45 2011, 美东) 提到:
我是先遍历的同时，用一个hashset记录已经创建的TreeNode，用于deserialize；另一
个hashmap记录parent,child信息，key存child,value存parent。
最后比较hashset和hashMap的keyset，hashmap应该少一个节点，就是root节点，原因
是二叉数root没有parent
=========================
这个hashset应该是hashmp吧， key是A,B or H..., value是建立的TreeNode. 不然怎
么trace相应的值已经建了TreeNode? i.e （A, TreeNode(A)）pair. 如果用hashset，
是 值存放ＴｒｅｅNode（A）是一个ｐｏｉｎｔｏｒ ｏｒ ｒｅｆｅｒｅｎｃｅ，
以后无法Ｔｒａｃｅ ｂａｃｋ！
☆─────────────────────────────────────☆
mikeyi (mike) 于 (Tue Apr 12 00:55:56 2011, 美东) 提到:
for joseph's problem, just googled this page:
http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3521
There are n persons numbered from 0 to n - 1 standing in a circle. The
person number k, counting from the person number 0, is executed. After that
the person number k of the remaining persons is executed, counting from the
person after the last executed one. The process continues until only one
person is left. This person is a survivor. The problem is, given n and k
detect the survivor's number in the original circle.
Of course, all of you know the way to solve this problem. The solution is
very short, all you need is one cycle:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
I do not understand this solution at all, and I tested n=5 and k=1, it runs
and returns 4, but I manually get the right answer should be 2 as follows:
init:
0 1 2 3 4
0 2 3 4 1 is killed, counting from 2
0 2 4 3 is killed, counting from 4
2 4 0 is killed counting from 2,
2 4 killed
Did I miss something?
For 0 based i.e k = 0, 1, 2... inti: 0 1 2 3 4
r := 0;
for i from 1 to n do
r := (r + k + 1) mod i;
return r;
For 1 based i.e k = 1, 2... inti: 1 2 3 4 5
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r + 1;
☆─────────────────────────────────────☆
lh2006 (lh) 于 (Tue Apr 12 13:05:43 2011, 美东) 提到:
bless !
☆─────────────────────────────────────☆
madmonk (madmonk) 于 (Tue Apr 12 17:39:30 2011, 美东) 提到:
thanks, I figured the k base out afterwards, but still no idea when this
loop works and how to prove it is correct.