g*******y 发帖数: 1930 | 1 一道算法老题,josephus环,N个数的循环,从第一个数开始,逆时针每跳一次,count
++,当count==M的时候,删掉当前的数,count清零
例如,1 2 3 4 5 6 7, M=3,删除数的顺序就是 3 6 2 7 5 1 4
现在给定 N,M<=N, M=O(N),求一个算法找到删除数的顺序
没做过的同学拿来思考下还是不错的~
答案在42楼,还有个注释过的cpp |
a****n 发帖数: 1887 | |
g*******y 发帖数: 1930 | 3 所以我说是老题嘛
我是在CLRS上看的思考题
记得codejam08 第一轮也有个这个题目的变种
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : TopCoder原题
|
w*******h 发帖数: 60 | 4 def josring(N, M):
index = M-1
cntM = 0
pout = 1
ring = range(1,(N+1))
print ring[index]
ring[index] = -1
while (pout < N):
index = index + 1
if ring[index%N] != -1:
cntM = cntM + 1
if cntM%M == 0:
print ring[index%N]
ring[index%N] = -1
pout = pout + 1
if __name__ == "__main__":
josring(7,3)
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所以我说是老题嘛 : 我是在CLRS上看的思考题 : 记得codejam08 第一轮也有个这个题目的变种
|
a********a 发帖数: 219 | 5 你算法很强啊。topcoder和codejam都搞,很强了。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所以我说是老题嘛 : 我是在CLRS上看的思考题 : 记得codejam08 第一轮也有个这个题目的变种
|
g*******y 发帖数: 1930 | 6 这个是O(N^2)
想想能不能再优化
【在 w*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def josring(N, M): : index = M-1 : cntM = 0 : pout = 1 : ring = range(1,(N+1)) : : print ring[index] : ring[index] = -1 : : while (pout < N):
|
g*******y 发帖数: 1930 | 7 没有,我很少做topcoder的题,codejam也就9月份的时候做了练了三个星期,呵呵,当
时水平不行,只是想碰碰运气,看能不能靠这个加点分好拿个google的面试,呵呵。
不过因为水平不够,加上发挥也不怎么好,最后只进到第二轮就挂了,不过还是拿到了
个google的面试,毕竟是google自己家的比赛,所以可能还是有点用。
所以我觉得这也是一条路,如果你觉得你算法coding比较强的,不妨早准备多练练
codejam的题,看一些程序竞赛的资料,9月份参赛如果能进个什么第三轮或者决赛,肯
定拿个google onsite没问题的,哪怕就进个第二轮,也可能能够拿个电面。其实预赛
和第一轮都不难,多练习的话,至少进第二轮没什么问题的。
【在 a********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你算法很强啊。topcoder和codejam都搞,很强了。
|
m*****f 发帖数: 1243 | 8 topcoder的门槛其实很低的, 除非是红名
不过可以当成一个练习面试的工具
【在 a********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你算法很强啊。topcoder和codejam都搞,很强了。
|
a********1 发帖数: 750 | 9 topcoder挺好的啊,而且可以看别人的代码。。。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有,我很少做topcoder的题,codejam也就9月份的时候做了练了三个星期,呵呵,当 : 时水平不行,只是想碰碰运气,看能不能靠这个加点分好拿个google的面试,呵呵。 : 不过因为水平不够,加上发挥也不怎么好,最后只进到第二轮就挂了,不过还是拿到了 : 个google的面试,毕竟是google自己家的比赛,所以可能还是有点用。 : 所以我觉得这也是一条路,如果你觉得你算法coding比较强的,不妨早准备多练练 : codejam的题,看一些程序竞赛的资料,9月份参赛如果能进个什么第三轮或者决赛,肯 : 定拿个google onsite没问题的,哪怕就进个第二轮,也可能能够拿个电面。其实预赛 : 和第一轮都不难,多练习的话,至少进第二轮没什么问题的。
|
a****n 发帖数: 1887 | 10 topcoder比较平民化, 据说大公司面试的难度相当于 SRM div I,第一题
而且都有官方的题解
不过我只做过些练习题。。。 |
|
|
a********1 发帖数: 750 | 11 差不多吧,不过topcoder时间内code 3道还是有点难的
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : topcoder比较平民化, 据说大公司面试的难度相当于 SRM div I,第一题 : 而且都有官方的题解 : 不过我只做过些练习题。。。
|
a****n 发帖数: 1887 | 12 我是说topcoder single round match比较容易参与,codejam 好像就是多轮比赛
至于难度, 我没做过codejam, 不知道 |
a********a 发帖数: 219 | 13 不是有点难吧?能做出三道题的谁还在这里混?
【在 a********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 差不多吧,不过topcoder时间内code 3道还是有点难的
|
g*******y 发帖数: 1930 | 14 1 2 3 4 5 6 7, M=3
指针从左往右走(循环的)
指针指到1的时候,count=1
指针指到2的时候,count=2
指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零
指针指到4的时候,count=1
指针指到5的时候,count=2
指针指到6的时候,count=3=M,第二个删除的是6
指针指到7的时候,count=1
指针指到1的时候,count=2
指针指到2的时候,count=3=M,第三个删除的是2
指针指到4的时候,count=1
指针指到5的时候,count=2
指针指到7的时候,count=3=M,第四个删除的是7
。。。。。。
M
写个code出来,要求O(NlogN)
count
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道算法老题,josephus环,N个数的循环,从第一个数开始,逆时针每跳一次,count : ++,当count==M的时候,删掉当前的数,count清零 : 例如,1 2 3 4 5 6 7, M=3,删除数的顺序就是 3 6 2 7 5 1 4 : 现在给定 N,M<=N, M=O(N),求一个算法找到删除数的顺序 : 没做过的同学拿来思考下还是不错的~ : 答案在42楼,还有个注释过的cpp
|
H*M 发帖数: 1268 | 15 谢谢解释啊.不好意思了都.. :>
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1 2 3 4 5 6 7, M=3 : 指针从左往右走(循环的) : 指针指到1的时候,count=1 : 指针指到2的时候,count=2 : 指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零 : 指针指到4的时候,count=1 : 指针指到5的时候,count=2 : 指针指到6的时候,count=3=M,第二个删除的是6 : 指针指到7的时候,count=1 : 指针指到1的时候,count=2
|
c****p 发帖数: 32 | 16 一个简单方法是把原来的int[]变成circular linked list,每次删除一个node后,下
一个node成为head,然后delete head->next->next直到最后,但是这样space是O(n)...
或者用bitmap来记录删掉的,但是time就成了...呃,这个time complexity是O(n2)??
或者...这个删除的顺序能用数学公司总结吗?我折腾了半天也推不出一个genenral
formula
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1 2 3 4 5 6 7, M=3 : 指针从左往右走(循环的) : 指针指到1的时候,count=1 : 指针指到2的时候,count=2 : 指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零 : 指针指到4的时候,count=1 : 指针指到5的时候,count=2 : 指针指到6的时候,count=3=M,第二个删除的是6 : 指针指到7的时候,count=1 : 指针指到1的时候,count=2
|
H*M 发帖数: 1268 | 17 最后谁survive有个数学公式的。
...
??
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个简单方法是把原来的int[]变成circular linked list,每次删除一个node后,下 : 一个node成为head,然后delete head->next->next直到最后,但是这样space是O(n)... : 或者用bitmap来记录删掉的,但是time就成了...呃,这个time complexity是O(n2)?? : 或者...这个删除的顺序能用数学公司总结吗?我折腾了半天也推不出一个genenral : formula
|
g*******y 发帖数: 1930 | 18 我发现这个题要写出来还是有点难度。。。
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢解释啊.不好意思了都.. :>
|
g*******y 发帖数: 1930 | 19 这个题目不在于考推导一个数学公式,或者我变一下题目,m不是固定的值,m等于每次
删去的那个数的值
提示一下,用树来做搜索。
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后谁survive有个数学公式的。 : : ... : ??
|
w********p 发帖数: 948 | 20 过年了。 我偷偷懒,等答案。
你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。 |
|
|
c****p 发帖数: 32 | 21 ...败了,我去topcoder翻答案算了。
没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移
直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法
,复杂度应该是O(N*M)吧。用tree就不用判断了??
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目不在于考推导一个数学公式,或者我变一下题目,m不是固定的值,m等于每次 : 删去的那个数的值 : 提示一下,用树来做搜索。
|
a********a 发帖数: 219 | 22 你的思想跑偏了。
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ...败了,我去topcoder翻答案算了。 : 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移 : 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法 : ,复杂度应该是O(N*M)吧。用tree就不用判断了??
|
g*******y 发帖数: 1930 | 23 常规的搜索是一个一个的往下找,找到第M个
而用树的搜索,找下一个要打印的数,可以提高到O(logN)
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ...败了,我去topcoder翻答案算了。 : 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移 : 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法 : ,复杂度应该是O(N*M)吧。用tree就不用判断了??
|
g*******y 发帖数: 1930 | 24 呵呵,新年的开头就想想题目多好啊~
要是没人发答案的话,我一会儿晚上来贴吧
我的面试还没schedule具体的时间,一直在等消息
【在 w********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 过年了。 我偷偷懒,等答案。 : 你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。
|
a********a 发帖数: 219 | 25 第二轮就是onsite了吧?还有好多轮么?
【在 w********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 过年了。 我偷偷懒,等答案。 : 你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。
|
c****p 发帖数: 32 | 26 “找下一个要打印的数”?这又回到我开始问的问题:是否有算法可以直接算出“下一
个”,而无需比较该数已经被删除?
post一个我用linked list实现的土法:D
void RingDelete(int* values, unsigned int size, int M)
{
if (size==0) return;
printf("step: %d\n", M);
struct Node
{
int value;
Node* next;
};
Node head;
head.next = NULL;
Node* pLastNode = NULL;
// costruct a circular linked list
for(int i=0; i
{
Node* pNode = new Node();
pNode->value=values[i];
if (i==0)
{
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 常规的搜索是一个一个的往下找,找到第M个 : 而用树的搜索,找下一个要打印的数,可以提高到O(logN)
|
h***r 发帖数: 726 | 27 当是抛砖引玉了
red-black tree储存所有的数字。
删除的数就从tree中也删掉。
下次要删除的数字需要在red-black tree中search.
en, 需要augment tree for order information to make sure search the ith
element can be done in o(logn)
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 常规的搜索是一个一个的往下找,找到第M个 : 而用树的搜索,找下一个要打印的数,可以提高到O(logN)
|
g*******y 发帖数: 1930 | 28 嗯,差不多是这个思路了。不过不需要非得是红黑树。
呵呵,其实这个就是CLRS上面augment data structure那部分后面的思考题
【在 h***r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当是抛砖引玉了 : red-black tree储存所有的数字。 : 删除的数就从tree中也删掉。 : 下次要删除的数字需要在red-black tree中search. : en, 需要augment tree for order information to make sure search the ith : element can be done in o(logn)
|
m*****f 发帖数: 1243 | 29 survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人)
原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后谁survive有个数学公式的。 : : ... : ??
|
H*M 发帖数: 1268 | 30 或者AVL tree?总之any balanced tree..
先build好这个augmented的tree,
第一个去死的是order(M),删除掉
然后第二个去死的是,剩下来的order(M+M-1),删除
第三个去死的是,剩下来的order(M+M+M-1-1),删除
其实要做个module,如果大于这个tree里面的元素个数的话。
我的天,这个用tree的方法真比那个推公式什么的清晰多了
sigh...
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯,差不多是这个思路了。不过不需要非得是红黑树。 : 呵呵,其实这个就是CLRS上面augment data structure那部分后面的思考题
|
|
|
H*M 发帖数: 1268 | 31 对了,我有个问题
如果,面试中要用augmented red black tree/avl TREE咋办啊
难道还写个RB tree/AVL tree不成
我RB tree insert/delete那些function都没记,太多了
应该怎么弄呢?assume有个现成的?
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 或者AVL tree?总之any balanced tree.. : 先build好这个augmented的tree, : 第一个去死的是order(M),删除掉 : 然后第二个去死的是,剩下来的order(M+M-1),删除 : 第三个去死的是,剩下来的order(M+M+M-1-1),删除 : 其实要做个module,如果大于这个tree里面的元素个数的话。 : 我的天,这个用tree的方法真比那个推公式什么的清晰多了 : sigh...
|
H*M 发帖数: 1268 | 32 这formula啥意思?
【在 m*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人) : 原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个
|
g*******y 发帖数: 1930 | 33 这个题不需要用RBT,AVL
想想heap是怎么用数组实现树结构的
我感觉面试不太可能让code实现RBT,AVL,有些太刁难人了。
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对了,我有个问题 : 如果,面试中要用augmented red black tree/avl TREE咋办啊 : 难道还写个RB tree/AVL tree不成 : 我RB tree insert/delete那些function都没记,太多了 : 应该怎么弄呢?assume有个现成的?
|
m*****f 发帖数: 1243 | 34 面试的时候实现Red Black Tree太难了吧, 也没那么多时间写啊
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题不需要用RBT,AVL : 想想heap是怎么用数组实现树结构的 : 我感觉面试不太可能让code实现RBT,AVL,有些太刁难人了。
|
H*M 发帖数: 1268 | 35 那一般关于augmented data structure的题,就只能嘴上说说了
反正我不记哪些RBTree的functions.
【在 m*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试的时候实现Red Black Tree太难了吧, 也没那么多时间写啊
|
a********a 发帖数: 219 | 36 现在的面试都到红黑树这么难的东西了?
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那一般关于augmented data structure的题,就只能嘴上说说了 : 反正我不记哪些RBTree的functions.
|
H*M 发帖数: 1268 | 37 大概就是用吧,和一些特性
不是 augmented data structures被烤果好几回了
【在 a********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在的面试都到红黑树这么难的东西了?
|
m*****f 发帖数: 1243 | 38 我觉得没, 我所听说的几个面试也就是问问linklist, queue stack之类的东西
如果被问到红黑树, 可能是因为表现的实在太强了
【在 a********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在的面试都到红黑树这么难的东西了?
|
g*******y 发帖数: 1930 | 39 这个公式貌似是找最后一个数?
【在 m*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人) : 原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个
|
H*M 发帖数: 1268 | 40 这个跟wiki上递推公式有点像,
不过没看懂。。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个公式貌似是找最后一个数?
|
|
|
g*******y 发帖数: 1930 | 41 是这样的
m=3:
1 2 3 4 5最后survive的那个是第4个数
考虑1 2 3 4 5 6:
第一个删除的是3,删除3后:
1 2 4 5 6,从4开始接着往后面计数/删,因为是循环的,相当于 4 5 6 1 2,从头开
始计数/删;
又因为删了一个,所以现在只剩5个数了,这样问题就递归到5个数的情况了
不过这个公式是找最后一个数,我这个题是让你打印所有删除的数的顺序,嘿嘿,如果你还是用这个思路做,貌似还是O(N^2)的
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个跟wiki上递推公式有点像, : 不过没看懂。。
|
g*******y 发帖数: 1930 | 42 贴答案了:
思路是:
(以n=16举例,array[16]={1,2,...,16})
array的每个位置(index)写成二进制就是0000 ... 1111
可以构造一棵树,根节点统计总共还有多少个数剩下没有删。根下面,往左边走,代表bit=0,往右边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix:
比如,根的左孩子的右孩子,prefix就是01,那么该节点就用来统计array中所有包含01前缀的位置中,还有多少个数剩下还没有删。
这样,我们还可以很简便的用数组来表示这个树,只需要规定root = 1, 左孩子=root<<1, 右孩子=左孩子+1(就像书上实现heap那样)。
这个数据结构写出来后,剩下的工作就好办了。
贴一个程序:
https://webfiles.uci.edu/siyangx/public/Josephus.cpp |
a********a 发帖数: 219 | 43 你这个太强大了。现在面试太可怕了。
表bit=0,往右
边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix:
含01前缀的位
置中,还有多少个数剩下还没有删。
root<<1, 右孩
子=左孩子+1(就像书上实现heap那样)。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴答案了: : 思路是: : (以n=16举例,array[16]={1,2,...,16}) : array的每个位置(index)写成二进制就是0000 ... 1111 : 可以构造一棵树,根节点统计总共还有多少个数剩下没有删。根下面,往左边走,代表bit=0,往右边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix: : 比如,根的左孩子的右孩子,prefix就是01,那么该节点就用来统计array中所有包含01前缀的位置中,还有多少个数剩下还没有删。 : 这样,我们还可以很简便的用数组来表示这个树,只需要规定root = 1, 左孩子=root<<1, 右孩子=左孩子+1(就像书上实现heap那样)。 : 这个数据结构写出来后,剩下的工作就好办了。 : 贴一个程序: : https://webfiles.uci.edu/siyangx/public/Josephus.cpp
|
m*****f 发帖数: 1243 | 44 对, 最后一个数
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个公式貌似是找最后一个数?
|
s*****r 发帖数: 773 | 45 请问topcoder算法题目的连接是哪个?
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ...败了,我去topcoder翻答案算了。 : 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移 : 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法 : ,复杂度应该是O(N*M)吧。用tree就不用判断了??
|