Perfect Shuffle 的算法

作者: , 共 908 字

珍爱生命,远离政治。我们继续讨论算法。

2008/04/01 补充:此算法有重大缺陷。详情请见留言部分。

一年前,我们讨论过一个算法问题, perfect shuffle ,据称是个微软面试题:

输入\( a_1,a_2,\cdots,a_n,b_1,\cdots,b_n\) ,如何用\( O(n)\) 的时间,\( O(1)\) 的空间,将这个序列顺序改为\( a_1,b_1,\cdots,a_n,b_n\)

那一次讨论我们翻出了问题的来源,一篇长达 12 页的论文Computing the Cycles in the Perfect Shuffle Permutation,算法那是非常的复杂,我估计贴出来都没几个人仔细看。

这一次, Xie Xie (没错,又是他 :) )翻出了 Art of Computer Programming, Volume 3 上的一个难度为 40 分的 Merge Sort 习题:

已知数列\( x_1\leq x_2\leq \cdots x_M, x_{M+1}\leq x_{M+2}\leq\cdots\leq x_n\) ,设计算法使得在线性时间,常数空间实现归并,也就是将原数组排序。

而 Perfect Shuffle 问题是可以规约到这个 Merge Sort 问题的:

mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
     m <- max(x[1...2n])+1;
     x[i] <- x[i]+(2i-1)m,
     x[i+n] <- x[i+n] + 2im
     mergeSort(x[1...2n])
     x[i] <- x[i]%m

原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。

很好很强大。

Q. E. D.

类似文章:
一个面试题,号称是微软的
2007 年,我们讨论过一个算法问题, perfect shuffle ,据称是个微软面试题:
毛毛虫爬棍子,有三个变体:
相似度: 0.062
这个题目听说是 MSRA 的面试题。
最大回撤是一个重要的风险指标。对于对冲基金和数量化策略交易,这个指标比波动率还重要。
一个非常好的面试题。难度适中。
数学 » 头脑风暴
发信人: GGGGDDDDK (忠贾诩发动乱武,反华佗没法急救别人了), 信区: SanGuoSha
标   题: 据说此题是入职腾讯游戏策划部门一道题 zz
发信站: 水木社区 (Mon Sep 20 11:10:40 2010), 站内
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
珍爱生命,远离政治。今天我们讨论一个数学问题。