一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2274|回复: 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分 原题只有五分 六种组合. 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都过了
. 鍥磋鎴戜滑@1point 3 acres
之前看地里两个video都是longest palin,kth和connections. visit 1point3acres.com for more.
和楼主后两个题一样 所以也舔着脸求个好结果~
当然也希望上述能帮到大家
lzlmike 发表于 2016-9-24 11:42:37 | 显示全部楼层
楼主最后一题都连不上的input和output是什么0.0, 最后一题你是prim写的还是union-find + kruskal? 我明天OA2,哈哈,对了还有那个要装的东西mac装不上?
回复 支持 反对

使用道具 举报

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

我也不知道为啥 我死活装不上 后来换了pc. From 1point 3acres bbs
那个题我使用kruskal+unionfind. Waral 鍗氬鏈夋洿澶氭枃绔,
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
input可能会给你一个连不起来 ...
. 鍥磋鎴戜滑@1point 3 acres
那null的情况是不是就看最后result.size() < cityTotalCount - 1 : null : result ?这样, 我用prim写了下,好难写,感觉到时候半个小时怕写不完。。。对了,他会让你打草稿的么,比如用A4纸之类的
回复 支持 反对

使用道具 举报

 楼主| joker8116 发表于 2016-9-24 13:29:26 | 显示全部楼层
对 我是把node放在set里了 最后看set的size. more info on 1point3acres.com
不能用纸 本来是要记一个什么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.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.                 });
  14.                 List<Connection> result = new ArrayList<>();
  15.                 uf = new HashMap<>();. 鍥磋鎴戜滑@1point 3 acres
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.                         String city2 = cur._city2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.                         if (connected(city1, city2)) {
  23.                                 continue;.1point3acres缃
  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) {
    . more info on 1point3acres.com
  36.                 uf.put(findRoot(s1), findRoot(s2));. from: 1point3acres.com/bbs
  37.         }
  38.        
  39.         private String findRoot (String s) {
  40.                 while (!s.equals(uf.get(s))) {. 1point 3acres 璁哄潧
  41.                         s = uf.get(s);
  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);
  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一次是排耗费一次是排名称,但是感觉做得很繁琐,楼主有什 ...

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

使用道具 举报

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

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

使用道具 举报

lzlmike 发表于 2016-9-25 06:50:58 | 显示全部楼层
joker8116 发表于 2016-9-24 23:30
应该可以的 你试试写几个 testcase. 1point3acres.com/bbs
另外最后返回结果要排序 要不然有的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 好吓人 还有这种网站。。
. From 1point 3acres bbs
哦豁,就是新题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, 2016-12-10 07:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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