一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2861|回复: 22
收起左侧

[算法题] 一道Amazon intern面试题有感

[复制链接] |试试Instant~ |关注本帖
sumingche 发表于 2014-3-1 08:38:18 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天帮一个师弟面下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 = 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);
                }
}



评分

3

查看全部评分

北美农民 发表于 2014-3-1 08:47:21 | 显示全部楼层
本帖最后由 北美农民 于 2014-2-28 19:52 编辑

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

使用道具 举报

 楼主| sumingche 发表于 2014-3-1 10:28:58 | 显示全部楼层

恩恩,就是个dfs啦,只是开始没看出来是dfs,我在旁边也没听到dfs的思路,只是看到题啦~
回复 支持 反对

使用道具 举报

头像被屏蔽
tli5 发表于 2014-3-1 20:59:45 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

shuiguo 发表于 2014-3-2 03:43:53 | 显示全部楼层
帮面amazon。。。。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-3-2 06:08:32 | 显示全部楼层
  1. import java.util.ArrayList;
  2. import java.util.Arrays;


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

回复 支持 反对

使用道具 举报

austurela 发表于 2014-3-2 06:10:32 | 显示全部楼层
BTW 帮助面试真的好吗?
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-2 06:15:52 | 显示全部楼层
austurela 发表于 2014-3-1 17:10
BTW 帮助面试真的好吗?

不太好啊,挺掉rp的
回复 支持 反对

使用道具 举报

austurela 发表于 2014-3-2 06:19:06 | 显示全部楼层
sumingche 发表于 2014-3-2 06:15
不太好啊,挺掉rp的

那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了?
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-2 06:21:14 | 显示全部楼层
austurela 发表于 2014-3-1 17:19
那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了?

我向祖国人民检讨~
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-2 06:22:09 | 显示全部楼层
austurela 发表于 2014-3-1 17:19
那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了?

准确说我不是替考,我是在旁边坐着,看着他来着~帮他搜搜资料什么的
回复 支持 反对

使用道具 举报

austurela 发表于 2014-3-2 06:27:27 | 显示全部楼层
本帖最后由 austurela 于 2014-3-2 06:30 编辑
sumingche 发表于 2014-3-2 06:22
准确说我不是替考,我是在旁边坐着,看着他来着~帮他搜搜资料什么的

I hope this could have been acceptable to Americans.
回复 支持 反对

使用道具 举报

vancexu 发表于 2014-3-3 06:36:38 | 显示全部楼层
请问这题是给了一个Langford pairing 比如2,3,1,2,1,3,
然后让你求n=3出现的位置吗?

还是给了n=3,
你写算法生成一个Langford pairing?
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-3 07:15:50 | 显示全部楼层
vancexu 发表于 2014-3-2 17:36
请问这题是给了一个Langford pairing 比如2,3,1,2,1,3,
然后让你求n=3出现的位置吗?

给你个n ,让你写出一个排列
回复 支持 反对

使用道具 举报

anikin0617 发表于 2014-3-29 15:11:37 | 显示全部楼层
北美农民 发表于 2014-3-1 08:47
这题完全acceptable嘛, amz想搞个高大上的名字唬人么。bitset也没啥, 自己弄一个a[n/32]的数组bit oper判 ...

想问一下,最后问什么要还原呢?就是最后两句话 bs.flip(i);  bs.flip(j); 小弟水平有限,希望兄弟不惜赐教
                                       
回复 支持 反对

使用道具 举报

cqx83 发表于 2014-3-29 16:23:39 | 显示全部楼层
实在没看出这题有用bitset的必要啊。。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2014-3-29 19:53:40 | 显示全部楼层

thanks for sharing
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-29 22:47:09 | 显示全部楼层
vancexu 发表于 2014-3-2 17:36
请问这题是给了一个Langford pairing 比如2,3,1,2,1,3,
然后让你求n=3出现的位置吗?

恩恩,题目是这个意思哈~
回复 支持 反对

使用道具 举报

anikin0617 发表于 2014-3-30 02:01:03 | 显示全部楼层
cqx83 发表于 2014-3-29 16:23
实在没看出这题有用bitset的必要啊。。

恩恩,我觉得就普通的数组就OK,小弟有一点不明白,最后为什么要回归还原呢。就是最后两句话 bs.flip(i);  bs.flip(j)
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-3-30 02:09:00 | 显示全部楼层
anikin0617 发表于 2014-3-29 02:11
想问一下,最后问什么要还原呢?就是最后两句话 bs.flip(i);  bs.flip(j); 小弟水平有限,希望兄弟不惜赐 ...

Sry cannot type Chinese.

This is for going backward and recover bits if we did not find solution. I think this is also the essence of DFS: trying a possible solution, go deeper and if no solution then we go backward and try another possible solution.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 21:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表