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 的大作中提到】
: 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 的大作中提到】
: 所以我说是老题嘛
: 我是在CLRS上看的思考题
: 记得codejam08 第一轮也有个这个题目的变种
|
a********a
发帖数: 219 | 5 你算法很强啊。topcoder和codejam都搞，很强了。
【在 g*******y 的大作中提到】
: 所以我说是老题嘛
: 我是在CLRS上看的思考题
: 记得codejam08 第一轮也有个这个题目的变种
|
g*******y
发帖数: 1930 | 6 这个是O(N^2)
想想能不能再优化
【在 w*******h 的大作中提到】
: 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 的大作中提到】
: 你算法很强啊。topcoder和codejam都搞，很强了。
|
m*****f
发帖数: 1243 | 8 topcoder的门槛其实很低的， 除非是红名
不过可以当成一个练习面试的工具
【在 a********a 的大作中提到】
: 你算法很强啊。topcoder和codejam都搞，很强了。
|
a********1
发帖数: 750 | 9 topcoder挺好的啊，而且可以看别人的代码。。。
【在 g*******y 的大作中提到】
: 没有，我很少做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 的大作中提到】
: topcoder比较平民化， 据说大公司面试的难度相当于 SRM div I,第一题
: 而且都有官方的题解
: 不过我只做过些练习题。。。
|
a****n
发帖数: 1887 | 12 我是说topcoder single round match比较容易参与，codejam 好像就是多轮比赛
至于难度， 我没做过codejam, 不知道 |
a********a
发帖数: 219 | 13 不是有点难吧？能做出三道题的谁还在这里混？
【在 a********1 的大作中提到】
: 差不多吧，不过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 的大作中提到】
: 一道算法老题，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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 一个简单方法是把原来的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 的大作中提到】
: 谢谢解释啊.不好意思了都.. :>
|
g*******y
发帖数: 1930 | 19 这个题目不在于考推导一个数学公式，或者我变一下题目，m不是固定的值，m等于每次
删去的那个数的值
提示一下，用树来做搜索。
【在 H*M 的大作中提到】
: 最后谁survive有个数学公式的。
:
: ...
: ？？
|
w********p
发帖数: 948 | 20 过年了。 我偷偷懒，等答案。
你的GOOGLE面试怎么样了？ 我只闯到第二轮。那天头发昏，加上确实很没准备充分。 |
|
|
c****p
发帖数: 32 | 21 ...败了，我去topcoder翻答案算了。
没想明白。关键问题是对每个i%M，都要判断是否已经被删除了，否则就往后一个个移
直到碰到还没被删掉的为止，也就是CLRS里面hash table collision的第二种处理方法
，复杂度应该是O(N*M）吧。用tree就不用判断了？？
【在 g*******y 的大作中提到】
: 这个题目不在于考推导一个数学公式，或者我变一下题目，m不是固定的值，m等于每次
: 删去的那个数的值
: 提示一下，用树来做搜索。
|
a********a
发帖数: 219 | 22 你的思想跑偏了。
【在 c****p 的大作中提到】
: ...败了，我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M，都要判断是否已经被删除了，否则就往后一个个移
: 直到碰到还没被删掉的为止，也就是CLRS里面hash table collision的第二种处理方法
: ，复杂度应该是O(N*M）吧。用tree就不用判断了？？
|
g*******y
发帖数: 1930 | 23 常规的搜索是一个一个的往下找，找到第M个
而用树的搜索，找下一个要打印的数，可以提高到O(logN)
【在 c****p 的大作中提到】
: ...败了，我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M，都要判断是否已经被删除了，否则就往后一个个移
: 直到碰到还没被删掉的为止，也就是CLRS里面hash table collision的第二种处理方法
: ，复杂度应该是O(N*M）吧。用tree就不用判断了？？
|
g*******y
发帖数: 1930 | 24 呵呵，新年的开头就想想题目多好啊～
要是没人发答案的话，我一会儿晚上来贴吧
我的面试还没schedule具体的时间，一直在等消息
【在 w********p 的大作中提到】
: 过年了。 我偷偷懒，等答案。
: 你的GOOGLE面试怎么样了？ 我只闯到第二轮。那天头发昏，加上确实很没准备充分。
|
a********a
发帖数: 219 | 25 第二轮就是onsite了吧？还有好多轮么？
【在 w********p 的大作中提到】
: 过年了。 我偷偷懒，等答案。
: 你的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 的大作中提到】
: 常规的搜索是一个一个的往下找，找到第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 的大作中提到】
: 常规的搜索是一个一个的往下找，找到第M个
: 而用树的搜索，找下一个要打印的数，可以提高到O(logN)
|
g*******y
发帖数: 1930 | 28 嗯，差不多是这个思路了。不过不需要非得是红黑树。
呵呵，其实这个就是CLRS上面augment data structure那部分后面的思考题
【在 h***r 的大作中提到】
: 当是抛砖引玉了
: 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 的大作中提到】
: 最后谁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 的大作中提到】
: 嗯，差不多是这个思路了。不过不需要非得是红黑树。
: 呵呵，其实这个就是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 的大作中提到】
: 或者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 的大作中提到】
: 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 的大作中提到】
: 对了，我有个问题
: 如果，面试中要用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 的大作中提到】
: 这个题不需要用RBT,AVL
: 想想heap是怎么用数组实现树结构的
: 我感觉面试不太可能让code实现RBT,AVL，有些太刁难人了。
|
H*M
发帖数: 1268 | 35 那一般关于augmented data structure的题，就只能嘴上说说了
反正我不记哪些RBTree的functions.
【在 m*****f 的大作中提到】
: 面试的时候实现Red Black Tree太难了吧， 也没那么多时间写啊
|
a********a
发帖数: 219 | 36 现在的面试都到红黑树这么难的东西了？
【在 H*M 的大作中提到】
: 那一般关于augmented data structure的题，就只能嘴上说说了
: 反正我不记哪些RBTree的functions.
|
H*M
发帖数: 1268 | 37 大概就是用吧，和一些特性
不是 augmented data structures被烤果好几回了
【在 a********a 的大作中提到】
: 现在的面试都到红黑树这么难的东西了？
|
m*****f
发帖数: 1243 | 38 我觉得没, 我所听说的几个面试也就是问问linklist, queue stack之类的东西
如果被问到红黑树, 可能是因为表现的实在太强了
【在 a********a 的大作中提到】
: 现在的面试都到红黑树这么难的东西了？
|
g*******y
发帖数: 1930 | 39 这个公式貌似是找最后一个数？
【在 m*****f 的大作中提到】
: survive 那个是 F(n,k) = (F(n-1, k) + k)%n （n个人， 隔k个杀一人)
: 原理就是多杀一个人， 就往安全的地方退k步， 这样不死我死前面那个
|
H*M
发帖数: 1268 | 40 这个跟wiki上递推公式有点像，
不过没看懂。。
【在 g*******y 的大作中提到】
: 这个公式貌似是找最后一个数？
|
|
|
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 的大作中提到】
: 这个跟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 的大作中提到】
: 贴答案了：
: 思路是：
: (以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 的大作中提到】
: 这个公式貌似是找最后一个数？
|
s*****r
发帖数: 773 | 45 请问topcoder算法题目的连接是哪个?
【在 c****p 的大作中提到】
: ...败了，我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M，都要判断是否已经被删除了，否则就往后一个个移
: 直到碰到还没被删掉的为止，也就是CLRS里面hash table collision的第二种处理方法
: ，复杂度应该是O(N*M）吧。用tree就不用判断了？？
|
