一亩三分地论坛

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

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

Amazon OA2 面经

  [复制链接] |试试Instant~ |关注本帖
subzero2 发表于 2016-9-16 08:25:14 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Amazon - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
OA2 由 Work simulation 和 3道 coding题组成

1. Work simulation
我的一个同学给了我一个cheat-sheet-oa2.pdf, 里面对work simulation介绍得很详细。我就只看了这个,觉得帮助很大。. visit 1point3acres.com for more.
虽然我不知道这个pdf的作者,但是为帮助大家,我把它上传到这个帖子的附件里面。不过我不知道这样子合不合适,如果不合适的话请跟我说。

2. 3道 coding
cheat-sheet-oa2.pdf 里面还有 coding部分的面经,可是我的 OA2 居!然!一!道!也!没!考! 我花了一天来看这十多道题目啊。
而且我发现这个PDF里面的解法里的一些code不够简洁,大家别太当做标准答案就好。
PDF里面的一些题目不算简单的,但是我遇到的3道题都太简单……

好了,说说这3道题:
第一道: 不记得了……
第二道:
(题目背景)一个组织发现了外星人,要给他们通信。我们的任务是给太空中的一些有可能有外星人的点发射信号。但是由于天线质量差(真是奇怪的理由),只能给太空中的 k 个点发射信号。现在又已知一个点P,它的坐标是(0,0),这个点周围最有可能有外星人。好了,给你N个点, 找到这个N个点中离原点P最近的k个。
(实质) 天呐,这不就是根据 x*x + y*y给一个数组排序么。

第三道:
(题目背景) 要给几十个城市供电。 在不同城市之间架设电网的花费不同。给你一个图,表示不同城市之间连接的花费。要你挑一些边,把所有城市连接起来并且总花费最小。
(实质) 最小生成树。 太直白了……
我用Kruskal + Union-Find敲的,原因是我忘记Prim算法了。。。我都有点惊讶,因为我有快四年没写过MST了,我居然还写出来了……
输出答案是你挑选的那些边。如果要过所有test case,记得输出的边需要按城市名字母顺序排序,现在大家可能不明白这是什么意思,大家可以先记着,到时看到题目就知道我在说啥了。
题目的描述并没有说要求你这样做,可是如果你不做,就过不了所有test case。真是坑 - _ -
. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
问个问题: 我收到了video,video是招聘流程的最后一步么?也就是我没有机会去西雅图onsite了?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

cheat-sheet-oa2.pdf

264.21 KB, 下载次数: 614, 下载积分: 大米 -1 升

本帖被以下淘专辑推荐:

hitman047 发表于 2016-9-20 03:10:29 | 显示全部楼层
如果你没有完成30分钟的问题,你自动拒绝?
回复 支持 1 反对 1

使用道具 举报

HuaZhe 发表于 2016-9-21 03:34:42 | 显示全部楼层
第三题大概这样可以吗???谢谢楼主了!
  1. public class solution {. From 1point 3acres bbs
  2.         public static void main (String[] args) {
  3.                 Connection[] citys = new Connection[10];
  4.                 citys[0] = new Connection("A","B",6);
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.                 citys[1] = new Connection("A","D",1);
  6.                 citys[2] = new Connection("A","E",5); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.                 citys[3] = new Connection("B","C",3);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.                 citys[4] = new Connection("B","D",5);
  9.                 citys[5] = new Connection("C","D",6);
  10.                 citys[6] = new Connection("C","F",6);
  11.                 citys[7] = new Connection("D","F",4);
  12.                 citys[8] = new Connection("D","E",5);
    . 1point 3acres 璁哄潧
  13.                 citys[9] = new Connection("E","F",2);
  14.                 ArrayList<Connection> list = new ArrayList<Connection> ();
  15.                 for (Connection temp : citys) {
  16.                         list.add(temp);
  17.                 }
  18.                
  19.                 for (Connection temp : findPath(list)){. 鍥磋鎴戜滑@1point 3 acres
  20.                         temp.printConnection();
  21.                 }
  22.                
  23.         }
  24.        
  25.         public static List<Connection> findPath (List<Connection> list) {
  26.                 ArrayList<Connection> result = new ArrayList<Connection> ();
  27.                 ArrayList<String> cityTree = new ArrayList<String> ();        //to Maintain the cities have been traversed.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  28.                 while (!list.isEmpty()) {
  29.                         //find the minimum cost to the city from cityTree among the result.
  30.                         Connection temp = findMin(list, cityTree);
  31.                         if (temp == null) {// we finished
  32.                                 break;
  33.                         }
  34.                         list.remove(temp);        //remove the current minimum cost from grand set
  35.                         cityTree.add(temp.city1);
  36.                         cityTree.add(temp.city2);
  37.                         result.add(temp);
  38.                 }. From 1point 3acres bbs
  39.                 //override compare make it alphabet order
  40.                 Comparator<Connection> cmp = new Comparator<Connection>(){
  41.                         public int compare(Connection c1, Connection c2) {
  42.                                 if (c1.city1.equals(c2.city1)) {
  43.                                         return c1.city2.compareTo(c2.city2);
  44.                                 }
  45.                                 return c1.city1.compareTo(c2.city1);
  46.                         }};
  47.                 result.sort(cmp);
  48.                
  49.                 return result;
  50.         }
  51.        
  52.         //find the minimum cost between the city we traversed and we did not traverse.
  53.         public static Connection findMin(List<Connection> list, ArrayList<String> cityTree) {
  54.                 Connection result = null;
  55.                 int minCost = Integer.MAX_VALUE;        //minimum cost. more info on 1point3acres.com
  56.                
  57.                 for (Connection con : list) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58.                         if (con.cost <= minCost) {
  59.                                 //if none of the city we traversed. 1point 3acres 璁哄潧
  60.                                 //or the connection is connected to either city from cityTree.
  61.                                 if ((cityTree.contains(con.city1) && !cityTree.contains(con.city2)) ||
  62.                                                 cityTree.contains(con.city2) && !cityTree.contains(con.city1)) {
  63.                                         minCost = con.cost;
  64.                                         result = con;. from: 1point3acres.com/bbs
  65.                                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  66.                                 if (cityTree.isEmpty()) {
  67.                                         minCost = con.cost;
  68.                                         result = con;
  69.                                 }
  70.                         }
  71.                 }
  72.                
  73.                 return result;
  74.         }
  75.        
  76. .1point3acres缃
  77. }
复制代码


  1. public class Connection {
  2.         String city1;
  3.         String city2;. 1point3acres.com/bbs
  4.         int cost;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.         Connection (String city1, String city2, int cost) {
  6.                 this.city1 = city1;
    . 1point3acres.com/bbs
  7.                 this.city2 = city2;
  8.                 this.cost = cost;
  9.         }. 1point 3acres 璁哄潧
  10.         . From 1point 3acres bbs
  11.         public void printConnection () {
  12.                 System.out.println("{ " + this.city1 + " , " + this.city2 + "} " + this.cost);.1point3acres缃
  13.         }
  14. }
复制代码
回复 支持 2 反对 0

使用道具 举报

hitman047 发表于 2016-9-16 11:12:56 | 显示全部楼层
什么是第3问题的输入和输出?
回复 支持 0 反对 1

使用道具 举报

xwjjjw 发表于 2016-10-3 11:14:56 | 显示全部楼层
lpx1989 发表于 2016-10-3 10:20
对,我就是这个意思,我想的方法,就是额外定义了个hashset用来数unique城市的数目用。
不知道这样是不 ...
. visit 1point3acres.com for more.
我觉得你get到point了。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
先说一点,union find处理数字比字符串要方便。说说我的做法,用个map把城市名和从0开始的编号对应起来,然后开一个数组来记录每个城市union后的根节点编号,每次union后都更新对应城市的根节点编号和对一个用来数有效connection的计数器加一。这样就能处理你的问题了。
希望能解决你的问题!
回复 支持 1 反对 0

使用道具 举报

tianrenz 发表于 2016-9-16 08:32:51 | 显示全部楼层
请问楼主oa2交了多久后拿到的video?
回复 支持 反对

使用道具 举报

 楼主| subzero2 发表于 2016-9-16 08:47:09 | 显示全部楼层
tianrenz 发表于 2016-9-16 08:32
请问楼主oa2交了多久后拿到的video?

一个星期
回复 支持 反对

使用道具 举报

tianrenz 发表于 2016-9-16 08:49:39 | 显示全部楼层

喔喔 cool 楼主加油 从去年来看拿到video的一般都是比较厉害的 祝offer
回复 支持 反对

使用道具 举报

sadfcbasy 发表于 2016-9-16 11:14:09 | 显示全部楼层
求交流!私楼主消息了
回复 支持 反对

使用道具 举报

 楼主| subzero2 发表于 2016-9-16 11:14:31 | 显示全部楼层
hitman047 发表于 2016-9-16 11:12
什么是第3问题的输入和输出?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
输入:
("Acity","Bcity",1}
("Acity","Ccity",2}
("Bcity","Ccity",3}

输出:
("Acity","Bcity",1}
("Acity","Ccity",2}
回复 支持 反对

使用道具 举报

hitman047 发表于 2016-9-16 12:05:56 | 显示全部楼层
我在网上发现了这个问题。它是一样的第三个问题吗?

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴"In a city there are N houses, each of which is in need of a water supply. It costs w[i] dollars to build a well at house i, and it costs c[i][j] to build a pipe in between houses i and j. A house can receive water if either there is a well built there or there is some path of pipes to a house with a well. Design an algorithm to find the minimum amount of money needed to supply every house with water."
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-16 12:35:40 | 显示全部楼层
楼主,没大米了,资料求发email,我27的OA2due,多谢多谢! 祝楼主早拿offer!!!
lzlli@ucdavis.edu
回复 支持 反对

使用道具 举报

jellyld 发表于 2016-9-17 00:34:43 | 显示全部楼层
恭喜楼主,昨天刚做完OA2,然后收到邮件让做一个survey,一开始让填一个TEST LOGIN ID, 楼主知道这是什么吗,登录用的邮箱名?还是OA2开始的时候让记得那一长串数字?
回复 支持 反对

使用道具 举报

qiangwan 发表于 2016-9-17 03:12:25 | 显示全部楼层
请问你的题目是什么呀
回复 支持 反对

使用道具 举报

qiangwan 发表于 2016-9-17 03:12:44 | 显示全部楼层
jellyld 发表于 2016-9-17 00:34. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
恭喜楼主,昨天刚做完OA2,然后收到邮件让做一个survey,一开始让填一个TEST LOGIN ID, 楼主知道这是什么吗 ...

.鐣欏璁哄潧-涓浜-涓夊垎鍦请问你的题目是什么呀
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-9-17 03:32:44 | 显示全部楼层
现在居然还有video....第三题有点厉害
回复 支持 反对

使用道具 举报

Roisterer 发表于 2016-9-17 06:49:18 | 显示全部楼层
楼主用的是这样的么: 用两个集合 一个 reached 一个 unreached, 每次找到reached到unreached cost最小的边 然后把这条边加入结果中 直到unreached为空
回复 支持 反对

使用道具 举报

joker8116 发表于 2016-9-17 08:01:49 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

joker8116 发表于 2016-9-17 08:03:04 | 显示全部楼层
恭喜楼主啊 video基本就稳了
想请问一下楼主 第一题是不是longest palindrome?感觉kthnearestpoints 和 palindrome 总是一起出现
回复 支持 反对

使用道具 举报

jellyld 发表于 2016-9-17 09:15:47 | 显示全部楼层
请问楼主收到关于下一轮的通知了吗?

补充内容 (2016-9-17 09:16):.鐣欏璁哄潧-涓浜-涓夊垎鍦
没注意到楼主说video,无视这个留言吧
回复 支持 反对

使用道具 举报

lcx813 发表于 2016-9-18 23:43:50 | 显示全部楼层
请问楼主,第三题给的图是怎么表示的呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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