一道Amazon intern面试题有感

今天帮一个师弟面下amazon intern, 看以前的经验帖子，觉得amazon intern面试题应该都很简单的，无非就是leetcode的难度，还考一些基本题，所以信心满满。
后来发现出来一道langford pairing的题目
http://en.wikipedia.org/wiki/Langford_pairing
a Langford pairing for n = 3 is given by the sequence 2,3,1,2,1,3.
让你实现这个算法，DFS暴力搜索，其实代码不太难写，只是我开始没听到解法，压根就不知道这个题怎么解，当然他也不可能上来就告诉你这个题是Langford_pairing，
等着你去google 搜答案，感觉amazon intern面试题的难度增加啦，回头网上搜了一个代码，简单改了改发现居然能用Bitset类去写，好强大，下面贴下代码


import java.util.*;
        public class LangfordPairing {
                public static  void langford(int N) {
                        if(N == 0) {
                                System.out.println(" no result ");
                                System.exit(0);
                        }
                        BitSet bs = new BitSet();
                        bs.set(N * 2);
                        int[] a=new int[2 * N];
                        put(bs, N, a);
                        if(bs.nextClearBit(0) >= 0) {
                                System.out.println(" no result ");
                        }
                }
                public  static void put(BitSet bs, int n, int[] arr) {
                       
                        if (n == 0) {
                               
                                System.out.println(Arrays.toString(arr));
                                System.exit(0);
                                //return;
                       
                        }
                        for (int i = -1, L = bs.length() - n - 1;
                                        (i = bs.nextClearBit(i + 1)) < L ;) {


                                final int j = i + n + 1;
                                if (!bs.get(j)) {
                                        arr[i] = n;
                                        arr[j] = n;
                                        bs.flip(i);
                                        bs.flip(j);
                                        put(bs, n - 1, arr);
                                        bs.flip(i);
                                        bs.flip(j);
                                }
                        }
                }
                public static void main(String[] args) {
               
                        //langford(9);
                        langford(4);
                }
}

Longford Pairing 既然是一种permutation, 自然就是考虑用DFS, 在DFS的过程中，每次尝试加入一个新的数字到solution中时, 都要check是否满足Longford Pairing的feature, 所以这道题的思路也是一种backtracking的想法。注意需要一个List<List<Integer>>保存结果。

1. public class LongfordSequence {
   
2.         public List<List<Integer>> gernerateSequence(int n) {
   
3.                 List<List<Integer>> result = new ArrayList<List<Integer>>();
   
4.                 int[] count = new int[n + 1];
   
5.                 gernerateHelper(result, new ArrayList<Integer>(), count);
   
6.                 return result;
   
7.         }
   
8. 
   
9.         private void gernerateHelper(List<List<Integer>> result, List<Integer> solution, int[] count) {
   
10.                 if (solution.size() == 2 * (count.length - 1)) {
    
11.                         result.add(new ArrayList<Integer>(solution));
    
12.                         return;
    
13.                 }
    
14. 
    
15.                 for (int i = 1; i <= count.length - 1; i++) {
    
16.                         if (count[i] == 0) {
    
17.                                 solution.add(i);
    
18.                                 count[i] = 1;
    
19.                                 gernerateHelper(result, solution, count);
    
20.                                 solution.remove(solution.size() - 1);
    
21.                                 count[i] = 0;
    
22.                         } else if (count[i] == 1) {
    
23.                                 int size = solution.size();
    
24.                                 if (size - i - 1 >= 0 && solution.get(size - i - 1) == i) {
    
25.                                         solution.add(i);
    
26.                                         count[i] = 2;
    
27.                                         gernerateHelper(result, solution, count);
    
28.                                         solution.remove(solution.size() - 1);
    
29.                                         count[i] = 1;
    
30.                                 }
    
31.                         }
    
32.                 }
    
33.         }
    
34. }

复制代码

这题完全acceptable嘛， amz想搞个高大上的名字唬人么。bitset也没啥， 自己弄一个a[n/32]的数组bit oper判断就行了。

北美农民 发表于 2014-2-28 19:47
这题完全acceptable嘛， amz想搞个高大上的名字唬人么。bitset也没啥， 自己弄一个a[n/32]的数组bit oper判 ...

恩恩，就是个dfs啦，只是开始没看出来是dfs，我在旁边也没听到dfs的思路，只是看到题啦~

帮面amazon。。。。

1. import java.util.ArrayList;
   
2. import java.util.Arrays;
   
3. 
   
4. 
   
5. public class LangfordPairing {
   
6.         public ArrayList<int[]> langford(int n){
   
7.                 ArrayList<int[]> returnVal = new ArrayList<int[]>();
   
8.                 int[] record = new int[2 * n];
   
9.                 lanfordHelper(returnVal, record, n);
   
10.                 return returnVal;
    
11.         }
    
12.        
    
13.         private void lanfordHelper(ArrayList<int[]> returnVal, int[] record, int downNum){
    
14.                 // Edge case
    
15.                 if(downNum < 0)        return;
    
16.                 // Base
    
17.                 if(downNum == 0){
    
18.                         returnVal.add(Arrays.copyOf(record, record.length));
    
19.                         return;
    
20.                 }
    
21.                 //Normal
    
22.                 for(int i = 0; i <= record.length - downNum - 2; i++){
    
23.                         if(record[i] == 0 && record[i + downNum + 1] == 0){
    
24.                                 record[i] = downNum;
    
25.                                 record[i + downNum + 1] = downNum;
    
26.                                 lanfordHelper(returnVal, record, downNum - 1);
    
27.                                 record[i] = 0;
    
28.                                 record[i + downNum + 1] = 0;
    
29.                         }
    
30.                 }
    
31.         }
    
32. }
    

复制代码

BTW 帮助面试真的好吗?

austurela 发表于 2014-3-1 17:10
BTW 帮助面试真的好吗?

不太好啊，挺掉rp的

sumingche 发表于 2014-3-2 06:15
不太好啊，挺掉rp的

那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了？

austurela 发表于 2014-3-1 17:19
那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了？

我向祖国人民检讨~