一亩三分地论坛

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

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

Amazon OA2

[复制链接] |试试Instant~ |关注本帖
mgnhjkl 发表于 2016-11-27 15:03:27 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚结束的Amazon OA2,WS都是面经历出现的题目,可以参考http://wdxtub.com/interview/14520850399861.html
coding抽到的题目是Longest Palindromic Substring,Rectangle Overlap和Order Dependency。(做coding的时候室友做饭把烟雾警报弄响了,我真是报了火警
建议大家在做coding的时候不要照抄答案,最好自己实现一遍看看答案有什么错的或者可以改进的地方(我看到有个兄弟做k nearest points的时候照抄把comparator里的double强转成int,默哀。。)
我自己发现的改进是很多答案里MST的union find都是用set实现的,但是这样合并union的时间复杂度就是O(V2)了,虽然理论上E最多是V2,不影响总体的时间复杂度,但是还是感觉不好。。
我写了一个版本是树形的union find,结合path compression,欢迎讨论
  1. import java.util.*;
  2. public class MinimumSpanningTree {
  3.         public static List<Connection> findPath(List<Connection> paths){
  4.                 List<Connection> res = new ArrayList<Connection>();
  5.                 Map<String, Integer> idMap = new HashMap<String, Integer>();
  6.                 int idCount = 0;
  7.                 for (Connection path : paths){
  8.                         if (!idMap.containsKey(path.node1)){
  9.                                 idMap.put(path.node1, idCount);-google 1point3acres
  10.                                 idCount ++;. From 1point 3acres bbs
  11.                         }
  12.                         if (!idMap.containsKey(path.node2)){
  13.                                 idMap.put(path.node2, idCount);
  14.                                 idCount ++;
  15.                         }
  16.                 }
  17.                 int[] unions = new int[idCount];
  18.                 for (int i = 0; i < unions.length; i ++){
  19.                         unions[i] = i;. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                 }. 1point 3acres 璁哄潧
  21.                
  22.                 paths.sort(new Comparator<Connection>(){
  23.                         public int compare(Connection c1, Connection c2){
  24.                                 return c1.cost - c2.cost;
  25.                         }
    . 1point 3acres 璁哄潧
  26.                 });
  27.                
  28.                 int unionCount = idCount;
  29.                 for (Connection path: paths){
  30.                         int id1 = idMap.get(path.node1);
  31.                         int id2 = idMap.get(path.node2);
  32.                         int leadId1 = find(unions, id1);
  33.                         int leadId2 = find(unions, id2);
  34.                         if (leadId1 == leadId2){
  35.                                 continue;
  36.                         } else {
  37.                                 unions[leadId2] = leadId1;
  38.                                 res.add(path);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.                                 unionCount --;
  40.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  41.                 }
  42.                 res.sort(new Comparator<Connection>(){
  43.                         public int compare(Connection c1, Connection c2){
  44.                                 if (!c1.node1.equals(c2.node1)){
  45.                                         return c1.node1.compareTo(c2.node1);
  46.                                 }
  47.                                 return c1.node2.compareTo(c2.node2);
  48.                         }
  49.                 });
  50.                 System.out.println(unionCount);
  51.                 return res;
  52.         }
  53.         public static void main (String[] args) {
  54.         Connection[] citys = new Connection[7];
  55.         citys[0] = new Connection("A","E",1);
  56.         citys[1] = new Connection("C","D",2);
  57.         citys[2] = new Connection("A","B",3);
  58.         citys[3] = new Connection("B","E",4);
  59.         citys[4] = new Connection("B","C",5);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  60.         citys[5] = new Connection("E","C",6);
  61.         citys[6] = new Connection("E","D",7);. From 1point 3acres bbs
  62. //        citys[7] = new Connection("D","F",4);
  63. //        citys[8] = new Connection("D","E",5);
  64. //        citys[9] = new Connection("E","F",2);. visit 1point3acres.com for more.
  65.         ArrayList<Connection> list = new ArrayList<Connection> ();.1point3acres缃
  66.         for (Connection temp : citys) {
  67.                 list.add(temp);
  68.         }
  69. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  70.         for (Connection temp : findPath(list)){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  71.                 temp.printConnection();
  72.         }

  73. }
  74.        
  75.         public static int find(int[] unions, int id){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  76.                 while (unions[id] != id){
  77.                         unions[id] = unions[unions[id]];
  78.                         id = unions[id];
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  79.                 }
  80.                 return id;
  81.         }
  82. }
  83. class Connection{
  84.         String node1;. 1point3acres.com/bbs
  85.         String node2;
  86.         int cost;
  87.         public Connection(String n1, String n2, int cost){
  88.                 node1 = n1;
  89.                 node2 = n2;
  90.                 this.cost = cost;
  91.         }
  92.         public void printConnection() {
  93.                 System.out.println(node1 + " " + node2 + " " + cost);
  94.                 .1point3acres缃
  95.         }
  96. }
复制代码

补充内容 (2016-11-27 15:06):.1point3acres缃
50行写错了。。应该是判断unionCount != 1的时候返回null,图不联通。我调试的时候就输出了一下没写判断

本帖被以下淘专辑推荐:

yutingguo1990 发表于 2016-11-27 23:07:37 | 显示全部楼层
求问 oa的时候也要把test写进去吗
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-27 23:17:48 | 显示全部楼层
yutingguo1990 发表于 2016-11-27 23:07
求问 oa的时候也要把test写进去吗

不用的,我是按照wiki的例子写了个测试,看一下对不对
回复 支持 反对

使用道具 举报

wujingzhishui 发表于 2016-11-27 23:20:11 | 显示全部楼层
楼主order dependency除了拿string做key还有别的坑么?比如dependency是空返回null还是empty list。最后输出的时候, 是输出原来order还是根据order name 重新写一个dependency?
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-27 23:23:24 | 显示全部楼层
wujingzhishui 发表于 2016-11-27 23:20
楼主order dependency除了拿string做key还有别的坑么?比如dependency是空返回null还是empty list。最后输 ...

没有坑,我估计test case是随机抽选的吧,我不管是empty list还是null都是全过。最后是根据order name重建的Order对象
回复 支持 反对

使用道具 举报

手抓饼 发表于 2016-11-27 23:39:38 | 显示全部楼层
楼主你Longest Palindromic Substring用的是哪种算法?
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-27 23:41:26 | 显示全部楼层
手抓饼 发表于 2016-11-27 23:39. 鍥磋鎴戜滑@1point 3 acres
楼主你Longest Palindromic Substring用的是哪种算法?

智商不足,直接用的O(n2)的
回复 支持 反对

使用道具 举报

手抓饼 发表于 2016-11-27 23:43:36 | 显示全部楼层
mgnhjkl 发表于 2016-11-27 23:41
智商不足,直接用的O(n2)的

保佑楼主offer. more info on 1point3acres.com
有结果出来喊一吓哈
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-27 23:45:01 | 显示全部楼层
手抓饼 发表于 2016-11-27 23:43
保佑楼主offer
有结果出来喊一吓哈

好的,多谢
回复 支持 反对

使用道具 举报

DanielWang1204 发表于 7 天前 | 显示全部楼层
弱弱的问一句,kclosest那题,compare 函数,把double 强转成int 有问题吗……
回复 支持 反对

使用道具 举报

DanielWang1204 发表于 7 天前 | 显示全部楼层
哦,想起来了,根据结果的正负来返回对吧
回复 支持 反对

使用道具 举报

icezhou0784 发表于 5 天前 | 显示全部楼层
DanielWang1204 发表于 2016-11-28 07:54
弱弱的问一句,kclosest那题,compare 函数,把double 强转成int 有问题吗……
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哈喽,我还是没明白这个跟int 和 double 有什么关系?
回复 支持 反对

使用道具 举报

xuanyuanyi12 发表于 5 天前 | 显示全部楼层
DanielWang1204 发表于 2016-11-28 07:54
弱弱的问一句,kclosest那题,compare 函数,把double 强转成int 有问题吗……

当然有问题3.53 > 3.52转完后成3.5和3.5咋排
回复 支持 反对

使用道具 举报

northwest 发表于 5 天前 | 显示全部楼层
楼主有消息了更新一下啊 祝好运~
回复 支持 反对

使用道具 举报

Gaaralw 发表于 5 天前 | 显示全部楼层
求问,oa2的三道算法题之间能切换吗? 前两题和第三题能切换吗?
想知道就是如果有testcse没过,能不能先写完再回来调整代码?
谢谢lz
回复 支持 反对

使用道具 举报

northwest 发表于 5 天前 | 显示全部楼层
Gaaralw 发表于 2016-11-30 04:19
求问,oa2的三道算法题之间能切换吗? 前两题和第三题能切换吗?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
想知道就是如果有testcse没过,能不能先 ...
. 1point3acres.com/bbs
一二题可以 共享时间 第三题是单独的一个 section
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 5 天前 | 显示全部楼层
northwest 发表于 2016-11-30 02:53
楼主有消息了更新一下啊 祝好运~

昨天刚收到onsite
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 5 天前 | 显示全部楼层
Gaaralw 发表于 2016-11-30 04:19
求问,oa2的三道算法题之间能切换吗? 前两题和第三题能切换吗?.1point3acres缃
想知道就是如果有testcse没过,能不能先 ...

只有前两题能切换,第三题是提交了前两题之后才给的
回复 支持 反对

使用道具 举报

northwest 发表于 5 天前 | 显示全部楼层
-google 1point3acres
加油加油!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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