一亩三分地论坛

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

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

下午刚做的OA2

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

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

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

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

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

WS一开始的题好多 拿不太准 后来10几题开始 面经差不多都见过了 不过有一个题是给不同的task组合打分的 这道题组合出现的顺序变了 而且面经上可以打到6分 原题只有五分 六种组合
所以大家做的时候还是细心点 别直接照面经写. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最后test case那五个倒是没变

coding部分 现实两道老题很简单 window sum和kthclosest. more info on 1point3acres.com
值得提一下的是 kth这道题横纵坐标是给的double 不是int 但是compare的返回值好像只能int 楼主考前没想过这个问题 不过也不是啥大问题 就是给大家提个醒. 1point3acres.com/bbs
最后一题是那个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. visit 1point3acres.com for more.
楼主最后一题都连不上的input和output是什么0.0, 最后一题你是prim写的还是union-find + kruskal? 我明天O ...
. 1point3acres.com/bbs
我也不知道为啥 我死活装不上 后来换了pc. more info on 1point3acres.com
那个题我使用kruskal+unionfind
input可能会给你一个连不起来的组合 比如(A, B, 5), (C, D, 4);
这样即便是把这两个connection都选中 也还是不能吧所有点连起来
此时返回null
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 13:29:26 | 显示全部楼层
对 我是把node放在set里了 最后看set的size
不能用纸 本来是要记一个什么id号 但是她说不能用纸 也不用记那个号
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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.1point3acres缃
  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.                         }.1point3acres缃
  25.                         union(city1, city2);. more info on 1point3acres.com
  26.                         result.add(cur);. Waral 鍗氬鏈夋洿澶氭枃绔,
  27.                 }. 1point3acres.com/bbs
  28.                 return result.size() == total - 1 ? result : null;. 鍥磋鎴戜滑@1point 3 acres
  29.         }
  30.        
  31.         private boolean connected (String s1, String s2) {
  32.                 return findRoot(s1).equals(findRoot(s2));
  33.         }
  34.         . Waral 鍗氬鏈夋洿澶氭枃绔,
  35.         private void union (String s1, String s2) {. From 1point 3acres bbs
  36.                 uf.put(findRoot(s1), findRoot(s2));.1point3acres缃
  37.         }
  38.        
  39.         private String findRoot (String s) {
  40.                 while (!s.equals(uf.get(s))) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  41.                         s = uf.get(s);
  42.                 }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  43.                 return s;
  44.         }
  45.         . more info on 1point3acres.com
  46.         private int total (List<Connection> city) {
  47.                 for (Connection c : city) {. more info on 1point3acres.com
  48.                         uf.put(c._city1, c._city1);
  49.                         uf.put(c._city2, c._city2);
  50.                 }
  51.                 return uf.size();
  52.         }
  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都做了多久呀?

WS做的很放松 做了大概六七十分钟
coding第一部分 二三十 第二部分10分钟
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:27:30 | 显示全部楼层
ymsfdwingswww 发表于 2016-9-24 14:17
谢谢楼主分享!最后一题我用了两次PriorityQueue一次是排耗费一次是排名称,但是感觉做得很繁琐,楼主有什 ...
. From 1point 3acres bbs
我也是两次 好像没事 没有说超时之类的
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 23:30:10 | 显示全部楼层
lzlmike 发表于 2016-9-24 14:52. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主,我这样写可以的么0.0 : union and find + kruskal

应该可以的 你试试写几个 testcase
另外最后返回结果要排序 要不然有的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. 1point3acres.com/bbs
楼主,我刚做完OA2,前2提都是简单题,都有,考的就是connection,哈哈哈,对了,楼主可以吧我发的那个代码 ...

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

使用道具 举报

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

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这样?还是她一紧张弄错了什么东西……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-24 22:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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