一个算法面试题 & 面试题库

系列：面试题
查看该系列所有文章

一个面试题，号称是微软的

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

刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换

x -> 2x mod 2n+1

我做了两小时没做出来，上网一搜，最近这个题目很热，已经有人在讨论这个题目，还翻出了问题的发源地http://www.cs.uvic.ca/~jellis/perfect.html，一个完美洗牌的构造问题。此网页上一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation给出了完整的算法和证明。

不知道有没有人给出直接而简便的方法？

在搜索过程中发现两个很好的程序设计类面试题库（英文），共享一下，如果你想面试Microsoft，Google或者Goldman Sachs，看看这两个网站上的题目就可以了。

[tags]算法,面试,题库[/tags]

写于2007年四月 27日

关于, , »
31条留言 -> 跳到留言表格
  • At 2007.04.29 00:37, You XU said:

    我在Google 遇到类似的题目：

    用最小的内存做下题
    假设p(k) 可以将 k=1..n 映射成1..n 的一个排列， 如何将一维数组(x1, x2,..., xn) 排成 (x_p(1), x_p(2), ... , x_p(n))

    其实，此问题被称为 In Situ Permutation (Knuth, 1972) TAOCP 有比较详细的讲解，大约就是说这些置换可以成环，关键是找到置换群的生成元。 知道了这个，我当时很幸运的秒杀了这个题目 ...

    [Reply]
    • At 2007.04.29 01:20, zhiqiang said:

      你那个问题不要求运算时间么？不要求运算时间的话，都可以在O(1)空间内搞定。

      文章中的那个问题，似乎不是能够秒杀的。分治法可以在O(nlogn)时间，O(1)空间搞定，但线性时间就不容易了。你有什么好方法么？

      [Reply]
      • At 2011.09.02 15:12, zhanglistar said:

        牛啊 膜拜一个！

        [Reply]
      • At 2007.04.30 01:25, Xie Xie said:

        该置换问题的最坏情况下时间是O(nlogn)，呵呵。

        比如20个的情况：
        1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
        第1个是不需要动的；
        第2个需要和2对应的置换即第11个位置所在元素恰好是11对换，换完之后数组有变化了；
        第3个需要和3所对应的2对换，找法是先找到3对应的置换2，在位置2寻找，而位置2已经是11了，不是所需要的，再在位置11寻找，刚好是2，对换之；
        ...
        这就是Knuth给出的方法：）写成程序稍微麻烦点，呵呵，用白话描述一下更好懂。
        对于这种奇偶的问题，有其特殊性，应该可以在O(n)时间内完成，有空可以看看Sedgewick的Analysis of algorithms，里面有in situ permutation的一节，他证明了平均情况下是n logn。
        它的时间依赖于该置换中的cycles数，而你给的那个论文就是计算它的，呵呵：）发在IPL上，档次不低。
        回头有时间再想想......

        [Reply]
        • At 2007.05.26 15:50, szuxjq said:

          你说的20个的情况，是上一行变成下一行还是下一行变成上一行？看着犯晕了~~

          [Reply]
          • At 2007.12.09 11:06, you_801204 said:

            该置换问题的最坏情况下时间是O(nlogn)?错了。只需要O(n).

            [Reply]
          • At 2007.04.30 06:55, You XU said:

            那篇paper 我细心读了一下，他无非就是使用了超级复杂的数论定理想办法把每个循环群的生成元挑出了一个。只能听他说的有道理，我们这些凡人估计是想不出来的了⋯⋯
            PS: 论文中Section 3 第 (5) 式就是对cycle 数量的估计.

            [Reply]
            • At 2007.05.01 20:01, zhiqiang said:

              test latex frac{Large f(x)=int_{-infty}^x e^{-t^2}dt}{Large f(x)= int_{-infty}^x e^{-t^2}dt}

              [Reply]
              • At 2007.05.01 23:11, zhiqiang said:

                begin{eqnarray}a&=&b+c\<br /> &=&d+e\<br /> sum x+prod y&=&11<br /> end{eqnarray}

                [Reply]
              • At 2007.05.02 03:16, You+XU said:

                Test
                The total number of cycles is \sum_{d\|m, d \neq 1} \frac{\phi (d)}{r_d}
                where r_d is the order of 2 (mod d).

                [Reply]
                • At 2007.05.02 03:17, You+XU said:

                  真的非常好用的插件 我太喜欢了 :)
                  上面发的公式就是那篇文章中的主要结论, 对cycle 的数量估计

                  [Reply]
                  • At 2007.05.02 10:46, zhiqiang said:

                    问题难度不在于对cycle数量的估计，而在于从每个cycle抽出一个生成元。

                    我大致浏览了那篇论文，用到一些数论上的计算技巧。过程倒也挺natural的。

                    [Reply]
                  • At 2008.01.09 07:29, zfy0701 said:

                    这是我想到的一个解法

                    用m代表整个数组,p,q分别代表两个变量

                    第i次迭代（i从1开始）

                    对p,q赋值：
                    当i为奇数，p赋值为m[2n - 1 - [i/2] ],q赋值为m[ 2 + [i/2] ]（[x]为下取整）
                    i为偶数，p赋值为m[n - i/2 ],q赋值为m[ n + i/2 ]

                    然后m[i + 1]与变量p迭代，m[2n- i]与q迭代

                    重复迭代n-1次即可

                    时间O(N),空间O(1)的算法

                    [Reply]
                    • At 2008.01.09 07:33, zfy0701 said:

                      想法就是这样了，还没上机验证，应该不会错
                      全文在：http://blog.csdn.net/zfy0701/archive/2008/01/09/2031162.aspx

                      [Reply]
                      • At 2008.01.09 07:44, zfy0701 said:

                        不好意思，有错，献丑了

                        [Reply]
                      • At 2008.10.28 11:01, st said:

                        这题拿来面试？不会是让用链表实现吧？然后被人云亦云，就成这样了。 :-D

                        [Reply]
                        • At 2009.04.07 13:27, 世泉 said:

                          就题目本身而言，可以这么设定
                          将1...n...2n,的数字换成1,n+1,2,n+2,3,n+3,...,n,2n
                          所以，分两种情况
                          x=n+1,移动到(x-n)*2

                          但是上面的这个过程和你给出的
                          2x mod (2n+1）在有不一致的情况，我觉得很奇怪

                          [Reply]
                          • At 2010.05.26 13:07, zjs0388 said:

                            using System;
                            using System.Collections.Generic;
                            using System.Linq;
                            using System.Text;
                            using System.IO;

                            namespace ConsoleApplication1
                            {
                            class Program
                            {
                            static void Main(string[] args)
                            {
                            int[] arra = new int[4000000];
                            for (int i = 0; i < arra.Length; i++) arra[i] = i + 1;
                            ReArrange(arra);
                            }

                            #region Rearrange the array
                            ///
                            /// The Test
                            ///
                            public static bool ReArrange(int[] array)
                            {
                            List list = new List();
                            list = getGenerator(array.Length);
                            if (list == null) return false;
                            // Call the exchange Methods;
                            revert(array, list);
                            return true;
                            }
                            #endregion

                            #region Get the generator for a number
                            ///
                            /// Get the generator for a number,and the generator can generate all the numbers from 1 to 2*number
                            ///
                            /// The number which used to generator the all the numbers from 1 to 2*number
                            /// Return an list which constains all the generators.
                            private static List getGenerator(int number)
                            {
                            if (number % 2 != 0) return null;
                            List list = new List();
                            int[] array = new int[number];
                            int start = 1;
                            loop:
                            int index = start;
                            array[index] = 1;
                            do
                            {
                            index = index * 2 % (array.Length - 1);
                            array[index] = 1;
                            } while (index != start);
                            list.Add(index);
                            for (int j = start+2; j < array.Length / 2; j += 2)
                            {
                            if (array[j] != 1)
                            {
                            start = j;
                            goto loop;
                            }
                            }
                            return list;
                            }
                            #endregion

                            #region Rearrange the all the items in the array such that it satisfy a1,b1...an ,bn.
                            ///
                            /// Rearrange the all the items in the array such that it satisfy a1,b1...an ,bn
                            ///
                            /// The array which is used to rearrange.
                            /// a set contains all the generators.
                            /// This parameter represent exchange times.If conter
                            /// equals array.Length-2 ,it indicates that all the rearrange completed.
                            private static void revert(int[] array, List set)
                            {
                            int conter = 0;
                            int temp;
                            int index;
                            int next;
                            int dinsinction;
                            int M = array.Length - 1;
                            foreach (int generator in set)
                            {
                            temp = array[generator];
                            index = generator;
                            next = generator * 2;
                            do
                            {
                            if (index % 2 == 0) dinsinction = index>> 1;//如果是偶数，它的值被index/2的值代替
                            else dinsinction = (index + M) / 2;// 如果是奇数，它的值被(index + M) / 2处的值代替
                            array[index] = array[dinsinction];
                            index = dinsinction;
                            }
                            while (index != next);
                            array[next] = temp;
                            }
                            }
                            #endregion

                            }
                            }

                            [Reply]
                            • At 2010.06.06 13:27, 日月三才剑 said:

                              public class Merge {

                              /**
                              * @param args
                              */
                              public static void main(String[] args) {
                              // TODO Auto-generated method stub

                              // FileReader fr = new FileReader();
                              int[] A={0,1,2,3,4,5,6,7,8,9,10,11,12};

                              int n = 6;
                              int tmp1,tmp2;
                              // tmp2 = 0;
                              int x = 7;
                              tmp1=A[x];

                              for (int j=0;j<2*n-1;j++){
                              if (1<x&&x<=n){
                              tmp2 = A[2*x-1];
                              A[2*x-1]=tmp1;
                              tmp1 = tmp2;
                              x = 2*x-1;
                              continue;
                              }
                              if (n<x && x<2*n+1){
                              tmp2 = A[2*(x-n)];
                              A[2*(x-n)]=tmp1;
                              tmp1 = tmp2;
                              x = 2*(x-n);
                              continue;
                              }
                              }

                              for (int j=0;j<13; j++){
                              System.out.println(A[j]);
                              }
                              System.out.println(x);
                              System.out.println(tmp1);
                              }
                              }

                              [Reply]
                              • At 2010.06.06 13:30, 日月三才剑 said:

                                初始 x=7
                                {0 1 7 2 8 3 9 4 10 5 11 6 12} 2 7

                                初始 x=2
                                {0 1 7 2 8 3 9 4 10 5 11 6 12} 3 2

                                [Reply]
                                • At 2010.06.06 13:33, 日月三才剑 said:

                                  数据是 a1=1,a2=2,....; b1=7,b2=8,...
                                  添加个0是为了让数组从下标[1]开始运算，使程序简洁，便于理解，A[0]可以不输出。

                                  [Reply]
                                  • At 2010.11.21 13:13, andyjojo said:

                                    请大家给小弟这个解法提提意见。

                                    [Reply]
                                    • At 2010.11.21 14:11, zhiqiang said:

                                      请直接写思路，看代码太难看懂

                                      [Reply]
                                    • At 2010.11.21 13:15, andyjojo said:

                                      http://andyjojo.javaeye.com/admin/blogs/818508

                                      [Reply]
                                      • At 2010.11.22 16:32, andyjojo said:

                                        a1不用换
                                        a2和b1换(b1对应整个数组的第n个数)
                                        a3的位置在结果中应该是a2，那就要找a2在什么地方，a2在第二次是和b1换了，也就是说现在a2在b1的位置，所以a3和b1还即可
                                        假设已换完j-1位，及1到j-1位置上以和结果一致，需要换j位
                                        现假设处理j位时，其结果中需要的那个元素此时的位置是L(j)
                                        如果j是偶数，那么结果应该是b(j/2)，即和b(j/2)交换即可(对应整个数组的第n+j/2个数，即L(j)=n+j/2)
                                        如果j是奇数，那么结果应该是a((j+1)/2)，那就要找此时a((j+1)/2)所在的位置，肯定不在数组的(j+1)/2，因为在处理(j+1)/2时，已被替换到别的位置，而这个位置就是L((j+1)/2)
                                        这样就变成计算L((j+1)/2)，同理，如果(j+1)/2是偶数，L((j+1)/2)=n+((j+1)/2)/2，如果是奇数，L((j+1)/2)=L((((j+1)/2)+1)/2)

                                        即 while(j不是偶数) j = (j+1)/2
                                        j是偶数了并且n+j/2在该位置之后，那么拿该位置的元素与n+j/2调换即可。
                                        如果n+j/2在该位置之前，那就还要重复上面的过程。

                                        不知道说明白了没有，呵呵

                                        [Reply]
                                        • At 2010.11.23 10:07, zhiqiang said:

                                          我帮你写得更清晰些

                                          假设输入为x[1, 2, ..., 2n]，则算法直接将序列中每个数依次交换到该在的位置

                                          for j = 1; j < = 2n;  j++ {
    swap(x[j], x[L(j)]);
}

                                          这里的关键是如何计算L(j)。先计算一种辅助的L'(j)

                                          如果j为偶数，L'(j) = n+j/2;
                                          如果j为奇数，L'(j) = L'((j+1)/2);

                                          那么L(j)为不断将L'作用到j上，直到L(j)>=j。

                                          你上面那一大段实际是如何不递归地计算L(j)（因为直接递归或动态规划需要线性空间，是题目不允许的）。

                                          这个算法应该是对的，思路很简洁。我想唯一的问题在于所需要的时间。我正在试图确认计算L(j)所需的时间，如果你已经算出来了，也可以直接贴到这里。

                                          [Reply]
                                          • At 2010.11.23 12:18, andyjojo said:

                                            考虑x[0,1,2,...,2n-1],即k=j-1
                                            如果k是奇数（k二进制最后一位为1），L'(k) = n+(k-1)/2
                                            如果k是偶数（k二进制最后一位为0），L'(k) = L'(k/2)
                                            即把k的最后一位0删除，继续再计算，同理如果k/2末尾是0，继续计算k/2/2，直到末尾是1

                                            则L'(k) = n+(k/(k-k&(k-1))-1)/2（不一定最优）

                                            设k的二进制为ab...c100...0
                                            k-1 = ab...c011...1
                                            k&(k-1) = ab...c000...0
                                            k-k&(k-1) = 100...0
                                            k/(k-k&(k-1)) = abc1
                                            即把k末尾的所有0移除了。

                                            至于L'(k)的执行次数，应该是O(1)的，这一步还需要证明

                                            [Reply]
                                            • At 2010.11.23 12:22, zhiqiang said:

                                              L'(k)的计算即使不按照你用的那种按位计算也是线性的，这个可以严格证明。

                                              难点还是在于“那么L(j)为不断将L'作用到j上，直到L(j)>=j”这段复杂性的分析。

                                              [Reply]
                                        • At 2010.11.23 12:36, andyjojo said:

                                          那么L(j)为不断将L'作用到j上，直到L(j)>=j
                                          L'(j)比j小可能在于j的二进制末尾0太多了，而n到2n-1中二进制末尾0很多的应该是O(log n)
                                          这些数最多移动O(log n)次，所以存在一些运算不超过O(log n log n)，但是这个比O(n)小，所以不影响总复杂的。
                                          呵呵，还没有想到严格证明

                                          [Reply]
                                          • At 2010.12.26 10:28, 后知后觉 » 重排数列 said:

                                            [...] 出处在这里 分类: 待解决 标签: maths 评论 (0) Trackbacks (0) 发表评论 Trackback [...]

                                            [Reply]
                                            • At 2011.09.02 15:22, zhanglistar said:

                                              这个题目如果用链表来解决应该符合面试要求。
                                              把输入存储到链表中，肯定是O（n）的时间复杂度，然后设置两个指针，相差为n，那么交换两个指针的值就可以了

                                              [Reply]
                                              (Required)
                                              (Required, not published)

                                                B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?

                                              «
                                              »
                                              guest | 注册 | 管理

                                              阅微堂

                                              理工科背景的证券从业人员
                                              Loading...
                                              Loading...
                                              Loading...