聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2260|回复: 18
收起左侧

Amazon OA2

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

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

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

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

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;. visit 1point3acres for more.
  7.                 for (Connection path : paths){
  8.                         if (!idMap.containsKey(path.node1)){
  9.                                 idMap.put(path.node1, idCount);
  10.                                 idCount ++;
  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;
  20.                 }
  21.                
  22.                 paths.sort(new Comparator<Connection>(){
  23.                         public int compare(Connection c1, Connection c2){. 1point3acres
  24.                                 return c1.cost - c2.cost;
  25.                         }
  26.                 });
  27.                
  28.                 int unionCount = idCount;. From 1point 3acres bbs
  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){. more info on 1point3acres
  35.                                 continue;
  36.                         } else {
  37.                                 unions[leadId2] = leadId1;. 牛人云集,一亩三分地
  38.                                 res.add(path);
  39.                                 unionCount --;
  40.                         }
  41.                 }. from: 1point3acres
  42.                 res.sort(new Comparator<Connection>(){
  43.                         public int compare(Connection c1, Connection c2){. 牛人云集,一亩三分地
  44.                                 if (!c1.node1.equals(c2.node1)){. 1point3acres
  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];. 围观我们@1point 3 acres
  55.         citys[0] = new Connection("A","E",1);.1point3acres网
  56.         citys[1] = new Connection("C","D",2);
  57.         citys[2] = new Connection("A","B",3);
  58.         citys[3] = new Connection("B","E",4);. more info on 1point3acres
  59.         citys[4] = new Connection("B","C",5);-google 1point3acres
  60.         citys[5] = new Connection("E","C",6);
  61.         citys[6] = new Connection("E","D",7);
  62. //        citys[7] = new Connection("D","F",4);
  63. //        citys[8] = new Connection("D","E",5);
  64. //        citys[9] = new Connection("E","F",2);
  65.         ArrayList<Connection> list = new ArrayList<Connection> ();
  66.         for (Connection temp : citys) {
  67.                 list.add(temp);
  68.         }. 留学申请论坛-一亩三分地

  69.         for (Connection temp : findPath(list)){
  70.                 temp.printConnection();. 1point3acres
  71.         }. 围观我们@1point 3 acres

  72. }
  73.        
  74.         public static int find(int[] unions, int id){
  75.                 while (unions[id] != id){
  76.                         unions[id] = unions[unions[id]];
  77.                         id = unions[id];. from: 1point3acres
  78.                 }
  79.                 return id;
  80.         }
  81. }
  82. class Connection{. 留学申请论坛-一亩三分地
  83.         String node1;
  84.         String node2;
  85.         int cost;. from: 1point3acres
  86.         public Connection(String n1, String n2, int cost){
  87.                 node1 = n1;
  88.                 node2 = n2;. 1point3acres
  89.                 this.cost = cost;
  90.         }. Waral 博客有更多文章,
  91.         public void printConnection() {-google 1point3acres
  92.                 System.out.println(node1 + " " + node2 + " " + cost);
  93.                
  94.         }. From 1point 3acres bbs
  95. }
复制代码

补充内容 (2016-11-27 15:06):
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对象
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-27 23:41:26 | 显示全部楼层
手抓饼 发表于 2016-11-27 23:39
楼主你Longest Palindromic Substring用的是哪种算法?

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

使用道具 举报

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

好的,多谢
回复 支持 反对

使用道具 举报

DanielWang1204 发表于 2016-11-28 07:54:12 | 显示全部楼层
弱弱的问一句,kclosest那题,compare 函数,把double 强转成int 有问题吗……
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

DanielWang1204 发表于 2016-11-28 08:10:30 | 显示全部楼层
哦,想起来了,根据结果的正负来返回对吧
回复 支持 反对

使用道具 举报

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

哈喽,我还是没明白这个跟int 和 double 有什么关系?
回复 支持 反对

使用道具 举报

xuanyuanyi12 发表于 2016-11-30 02:48:40 | 显示全部楼层
DanielWang1204 发表于 2016-11-28 07:54
弱弱的问一句,kclosest那题,compare 函数,把double 强转成int 有问题吗……
. 1point 3acres 论坛
当然有问题3.53 > 3.52转完后成3.5和3.5咋排
回复 支持 反对

使用道具 举报

northwest 发表于 2016-11-30 02:53:20 | 显示全部楼层
楼主有消息了更新一下啊 祝好运~
回复 支持 反对

使用道具 举报

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

使用道具 举报

northwest 发表于 2016-11-30 04:23:22 | 显示全部楼层
Gaaralw 发表于 2016-11-30 04:19
求问,oa2的三道算法题之间能切换吗? 前两题和第三题能切换吗?.本文原创自1point3acres论坛
想知道就是如果有testcse没过,能不能先 ...

一二题可以 共享时间 第三题是单独的一个 section
回复 支持 反对

使用道具 举报

 楼主| mgnhjkl 发表于 2016-11-30 04:24:00 | 显示全部楼层
northwest 发表于 2016-11-30 02:53. 一亩-三分-地,独家发布
楼主有消息了更新一下啊 祝好运~

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

使用道具 举报

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

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

使用道具 举报

northwest 发表于 2016-11-30 04:26:51 | 显示全部楼层

加油加油!
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-21 11:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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