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

zhiqiang四月 27, 2007 计算机科学

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

输入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，看看这两个网站上的题目就可以了。

关于, , »
  • Perfect Shuffle的算法 珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。 一年前，我们讨论过一个算法问题，perfect shuffle，...
  • 帽子游戏二 这个题目听说是MSRA的面试题。 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
  • 图同构问题属于P？ 更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。 提交论文到arxiv不需要审阅...
  • 2008年10月EMC笔试 今天下午去EMC笔试了。笔试题目分四部分：求职意向3题，专业基础知识和智力题25道，编程题3道，英语作文。全英文题目和作答。虽然前面关于操作系...
  • 编程的核心是数据结构，而不是算法 Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: 你无法断定程序会在什么地方耗费运...
  • 网易笔试题 笔试多了，便会发现题目大同小异，很多笔试考的时候就是考经验和见世面。下面收集一些。 Fibonacci数列中，一个Fibonacci数如果与它之前的Fibonacci数均...
  • 素数筛法的复杂度 Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的...
  • WorldQuant的笔试题 今年找工作并且常在水木混的人对WorldQuant这个公司应该不陌生，因为它在各求职版周期性发帖，标题是“美国著名对冲基金！   超百万收入！...
  • 理论计算机初步：算法和计算模型 下面是wikipedia上算法的定义： 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算...
  • 有序矩阵的中位数算法 给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
20条留言 -> 跳到留言表格
  • 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 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.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]
                              (Required)
                              (Required, not published)

                                B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
                              «
                              »
                              guest | 注册 | 管理 | English | 繁體 | https

                              阅微堂

                              zhiqiang's personal blog
                              Loading...
                              Loading...
                              Loading...