May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4133|回复: 22
收起左侧

下午刚做的OA2

[复制链接] |试试Instant~ |关注本帖
joker8116 发表于 2016-9-24 11:21:21 | 显示全部楼层 |阅读模式

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

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

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

x
楼主是15号做的OA1 第二天早上给了OA2 拖到今天下午 刚做完首先说一下监考吧 楼主提前约好时间 然后快到点了就在电脑前等 结果一开始要装个applet死活装不上(楼主macbook). from: 1point3acres.com/bbs
来来回回弄了半个小时 还好有online help 还跟我说现在还没开始计时 我才放心 换了台电脑做的OA
然后考试开始以后监考一直都挺好的 先让我给他看一下室内 然后就都没有打断过我 我做完ws说上个厕所 回来以后她说再给她看一下室内 然后就接着做题了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

WS一开始的题好多 拿不太准 后来10几题开始 面经差不多都见过了 不过有一个题是给不同的task组合打分的 这道题组合出现的顺序变了 而且面经上可以打到6分 原题只有五分 六种组合
所以大家做的时候还是细心点 别直接照面经写. from: 1point3acres.com/bbs
最后test case那五个倒是没变

coding部分 现实两道老题很简单 window sum和kthclosest
值得提一下的是 kth这道题横纵坐标是给的double 不是int 但是compare的返回值好像只能int 楼主考前没想过这个问题 不过也不是啥大问题 就是给大家提个醒
最后一题是那个connections的题 一堆connections 都有一定的cost 找出其中能连接全部点且cost最小的组合
test case果然如前几天一个地里小伙伴说的一样 会给你一个连接不上全部点的input output要null 我一开始return new ArrayList<Connection>();还不对
coding部分楼主test case都过了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

之前看地里两个video都是longest palin,kth和connections
和楼主后两个题一样 所以也舔着脸求个好结果~
当然也希望上述能帮到大家. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
lzlmike 发表于 2016-9-24 11:42:37 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主最后一题都连不上的input和output是什么0.0, 最后一题你是prim写的还是union-find + kruskal? 我明天OA2,哈哈,对了还有那个要装的东西mac装不上?
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 11:45:38 | 显示全部楼层
关注一亩三分地微博:
Warald
lzlmike 发表于 2016-9-24 11:42
楼主最后一题都连不上的input和output是什么0.0, 最后一题你是prim写的还是union-find + kruskal? 我明天O ...

我也不知道为啥 我死活装不上 后来换了pc
那个题我使用kruskal+unionfind.鏈枃鍘熷垱鑷1point3acres璁哄潧
input可能会给你一个连不起来的组合 比如(A, B, 5), (C, D, 4);
这样即便是把这两个connection都选中 也还是不能吧所有点连起来.1point3acres缃
此时返回null
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-24 12:41:24 | 显示全部楼层
joker8116 发表于 2016-9-24 11:45
我也不知道为啥 我死活装不上 后来换了pc
那个题我使用kruskal+unionfind
input可能会给你一个连不起来 ...

那null的情况是不是就看最后result.size() < cityTotalCount - 1 : null : result ?这样, 我用prim写了下,好难写,感觉到时候半个小时怕写不完。。。对了,他会让你打草稿的么,比如用A4纸之类的
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 13:29:26 | 显示全部楼层
对 我是把node放在set里了 最后看set的size
不能用纸 本来是要记一个什么id号 但是她说不能用纸 也不用记那个号
回复 支持 反对

使用道具 举报

sqrl 发表于 2016-9-24 14:10:57 | 显示全部楼层
楼主WS和Coding都做了多久呀?
回复 支持 反对

使用道具 举报

ymsfdwingswww 发表于 2016-9-24 14:17:06 | 显示全部楼层
谢谢楼主分享!最后一题我用了两次PriorityQueue一次是排耗费一次是排名称,但是感觉做得很繁琐,楼主有什么建议吗
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-24 14:52:59 | 显示全部楼层
楼主,我这样写可以的么0.0 : union and find + kruskal

  1. public class Connections {
  2.         private Map<String, String> uf;
  3.         public List<Connection> mst (List<Connection> city) {
  4.                 if (city == null || city.isEmpty()) {
  5.                         return null;
  6.                 }
  7.                
  8.                 Collections.sort(city, new Comparator<Connection> () {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                         @Override
  10.                         public int compare (Connection c1, Connection c2) {
  11.                                 return c1._cost - c2._cost;
  12.                         }
  13.                 });
  14.                 List<Connection> result = new ArrayList<>();
  15.                 uf = new HashMap<>();
  16.                 int total = total(city);
  17.                 int index = 0;
  18.                 while (index < city.size() && result.size() < total - 1) {
  19.                         Connection cur = city.get(index++);
  20.                         String city1 = cur._city1;
  21.                         String city2 = cur._city2;
  22.                         if (connected(city1, city2)) {
  23.                                 continue;
  24.                         }
  25.                         union(city1, city2);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                         result.add(cur);
  27.                 }
  28.                 return result.size() == total - 1 ? result : null;
  29.         }
  30.        
  31.         private boolean connected (String s1, String s2) {
  32.                 return findRoot(s1).equals(findRoot(s2));
  33.         }
  34.        
  35.         private void union (String s1, String s2) {
  36.                 uf.put(findRoot(s1), findRoot(s2));
  37.         }
  38.        
  39.         private String findRoot (String s) {
  40.                 while (!s.equals(uf.get(s))) {
  41.                         s = uf.get(s);. From 1point 3acres bbs
  42.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  43.                 return s;
  44.         }
  45.        
  46.         private int total (List<Connection> city) {
  47.                 for (Connection c : city) {
  48.                         uf.put(c._city1, c._city1);
    .1point3acres缃
  49.                         uf.put(c._city2, c._city2);
  50.                 }
  51.                 return uf.size();. more info on 1point3acres.com
  52.         }. 1point3acres.com/bbs
  53. }
复制代码
回复 支持 反对

使用道具 举报

bbmbill 发表于 2016-9-24 22:11:01 | 显示全部楼层
楼主Kth closest那题是用的Priority Queue直接写的?
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:23:46 | 显示全部楼层
bbmbill 发表于 2016-9-24 22:11
楼主Kth closest那题是用的Priority Queue直接写的?

是的 记得import就好
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:26:21 | 显示全部楼层
sqrl 发表于 2016-9-24 14:10
楼主WS和Coding都做了多久呀?
.1point3acres缃
WS做的很放松 做了大概六七十分钟
coding第一部分 二三十 第二部分10分钟
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:27:30 | 显示全部楼层
ymsfdwingswww 发表于 2016-9-24 14:17
谢谢楼主分享!最后一题我用了两次PriorityQueue一次是排耗费一次是排名称,但是感觉做得很繁琐,楼主有什 ...

我也是两次 好像没事 没有说超时之类的
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:30:10 | 显示全部楼层
lzlmike 发表于 2016-9-24 14:52
楼主,我这样写可以的么0.0 : union and find + kruskal

应该可以的 你试试写几个 testcase. From 1point 3acres bbs
另外最后返回结果要排序 要不然有的case过不了
先按第一个城市名排 第一个一样再按第二个排
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-25 06:50:58 | 显示全部楼层
joker8116 发表于 2016-9-24 23:30
应该可以的 你试试写几个 testcase. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
另外最后返回结果要排序 要不然有的case过不了
先按第一个城市名排  ...

楼主,我刚做完OA2,前2提都是简单题,都有,考的就是connection,哈哈哈,对了,楼主可以吧我发的那个代码回复,删掉么0.0,我怕等会查到这。。谢啦
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-25 08:35:33 | 显示全部楼层
lzlmike 发表于 2016-9-25 06:50
楼主,我刚做完OA2,前2提都是简单题,都有,考的就是connection,哈哈哈,对了,楼主可以吧我发的那个代码 ...

我不会删啊 快教我~!
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-25 08:43:08 | 显示全部楼层
joker8116 发表于 2016-9-25 08:35
我不会删啊 快教我~!

0.0,版主也删不了啊,哈哈哈,亚马逊应该不会知道这个吧0.0,我主要怕以后的人看到这个代码不要写一样的就好, 我也不知道怎么删,哈哈,
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-10-4 10:10:21 | 显示全部楼层
楼主我看到connection这个题是哪个啊,我看到一个资源http://www.jianshu.com/p/807fc0ec0bc3 没看到这个题
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-10-4 12:04:40 | 显示全部楼层
gaocan1992 发表于 2016-10-4 10:10
楼主我看到connection这个题是哪个啊,我看到一个资源http://www.jianshu.com/p/807fc0ec0bc3 没看到这个题

33 好吓人 还有这种网站。。
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-10-4 12:18:38 | 显示全部楼层
joker8116 发表于 2016-10-3 20:04
33 好吓人 还有这种网站。。

哦豁,就是新题MST啊,神奇的网站
回复 支持 反对

使用道具 举报

纳格兰的风 发表于 2016-11-14 14:17:39 | 显示全部楼层
LZ你好,想问下import PriorityQueue的问题,我有个朋友做OA2的时候说import java.util.*了还是不能用,不知道你是import java.util.*还是单独import java.util.priorityqueue这样?还是她一紧张弄错了什么东西……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 09:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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