一亩三分地论坛

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

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

新鲜出炉的Amazon电面二面 新题目 我们来集思广益

[复制链接] |试试Instant~ |关注本帖
ethan1786 发表于 2014-6-27 04:44:25 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Amazon - 网上海投 - 技术电面 |Other

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

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

x
刚刚放下电话 本来45分钟到一个小时的面试硬是说了一个半小时

这次Amazon的电话二面 是一个烙印 人很nice 也一直在跟我交流 最后放下电话的时候因为没有时间写optimization了 说fair enough "This is what I am thinking should be the right direction." 然后他说他只是会把这次面试的结果传给 hire manager 所以他也不能说就接下来会怎么样 不过感觉他应该不会给我写的太差

题目是没见过的题目 google都搜不到。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
“You are working for a company responsible for rebuilding a long bridge. For construction, it wants to estimate the maximum weight that the bridge will have to support - using the past information. They have historical logs (from the toll sensors) with entry and exit time for each car that crossed the older bridge. To start with, they are interested in finding out the maximum number of cars that were present on the bridge at any instant of time. Can you write a method that will take that list of <Car, entry_time, exit_time> and return the maximum number of cars present at any instance of time?”
. 鍥磋鎴戜滑@1point 3 acres
class LogEntry {
String car;
DateTime entry;
DateTime exit;
}


For example:. 鍥磋鎴戜滑@1point 3 acres
Car A: 12:00 - 12:20
Car B: 12:10 - 12:15 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Car C: 12:16 - 12:30
Car D: 12:18 - 12:30


要return同一时间在桥上的最多car的number 所以是在这个case是3

我就不献丑了 希望听听大家的解法 我们可以讨论一下 也扩大了地里的题库. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2014-6-27 04:48):
这个是最开始的题目 后来假设log entry有无穷多 比如有几千万 时间跨度是一年 每个entry的时间精确到毫秒 求时间和空间最optimize的解法

补充内容 (2014-6-27 04:52):
来打脸了 刚找到了在careercup的一个讨论 (http://www.careercup.com/question?id=13817668)不过里面没有特别好的解法 所以还要看大家讨论了

补充内容 (2014-6-28 04:28):
Update: Amazon很惊讶的跪了 明明问题都做出来了而且跟interviewer都聊得很好 不知道为什么 不过还好接到google的电话 打算给我安排on-site的面试 算是给了点安慰 这两天拜上帝不管用啊 是不是应该拜春哥?

评分

3

查看全部评分

本帖被以下淘专辑推荐:

tianyangche 发表于 2014-6-27 13:59:07 | 显示全部楼层
感觉和之前看到过的一道fb面经很像。
我的想法是可以把这道题的start 和 end看成一个interval[s, e],然后把这一堆拆开,进行排序。也就是说如果你有n辆车,那么总共有2n个起始点,把这2n个数进行排序。这些数都有个标识,标识是start还是end。排序的时候如果[12:00, 12:10], [12:10, 12:20],这样的话要把第一辆车的结束时间放在第二辆车的开始时间之前。然后对排好序的数组进行扫描。每遇到一个开始点,加1,遇到一个结束点,减1。扫描过程中记录最大值。
如果log特别大就不知道该怎么办了。听听大牛们怎么说。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

readman 发表于 2014-6-27 15:45:00 | 显示全部楼层
区间树``````
. more info on 1point3acres.com
补充内容 (2014-6-27 15:47):
普林斯顿课上有提到哦
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-27 21:37:13 | 显示全部楼层
readman 发表于 2014-6-27 15:45. more info on 1point3acres.com
区间树``````

补充内容 (2014-6-27 15:47):

赞区间树! 刚才google了一下区间树 发现中文很多都把区间树和线段树放在一起了 貌似应该是不一样的 stackoverflow上有这样的解释:
  • Segment tree stores intervals, and optimized for "which of these intervals contains a given point" queries.
  • Interval tree stores intervals as well, but optimized for "which of these intervals overlap with a given interval" queries. It can also be used for point queries - similar to segment tree.
  • Range tree stores points, and optimized for "which points fall within a given interval" queries.
  • Binary indexed tree stores items-count per index, and optimized for "how many items are there between index m and n" queries.

Performance / Space consumption for one dimension:

  • Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space
  • Interval tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
  • Range tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
  • Binary Indexed tree - O(n logn) preprocessing time, O(logn) query time, O(n) space

(k is the number of reported results).

All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:

  • Segment tree - interval can be added/deleted in O(logn) time (see here)
  • Interval tree - interval can be added/deleted in O(logn) time
  • Range tree - new points can be added/deleted in O(logn) time (see here)
  • Binary Indexed tree - the items-count per index can be increased in O(logn) time

Higher dimensions (d>1):

  • Segment tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space
  • Interval tree - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space
  • Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space
  • Binary Indexed tree - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space

. 1point3acres.com/bbs
. from: 1point3acres.com/bbs
这样的话 最优的时间复杂度是 O(NlogN) 空间复杂度是O(N) 貌似到极限了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

readman 发表于 2014-6-27 22:57:08 | 显示全部楼层
ethan1786 发表于 2014-6-27 21:37
赞区间树! 刚才google了一下区间树 发现中文很多都把区间树和线段树放在一起了 貌似应该是不一样的 stac ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不过电面问这个你怎么答??? 自己写一个?
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 01:30:06 | 显示全部楼层
readman 发表于 2014-6-27 22:57. Waral 鍗氬鏈夋洿澶氭枃绔,
不过电面问这个你怎么答??? 自己写一个?
. 1point3acres.com/bbs
我电面讲到最优解的时候已经没时间了 所以后面基本就是全描述 如果有时间的话应该是自己写吧 我的办法不是用区间树 我提了一下用树 他直接否决了 所以我用数组做的

假设所有log已经按entry time排序了 这样把所有entry time拿出来 成为一个长度n的数组 再建另外一个长度为n的数组A 数组每一项的值为1 代表在那个时间点车的数量是+1 这样是O(logN) 然后把exist time loop拿出来 在entry time的数组里找 entryTime[i-1] < exitTime <=entryTime的i 如果entryTime[n-1] < exitTime return n-1 然后A -- 思路是在两辆车entry的间隔有车离开的话 对找max car number 没有意义 只是在新的车进来的时候需要考虑 这里用binary search 所以时间复杂度是O(NlogN) 然后对A做 A += A[i-1] 就得到对应时间点所有车得数量 是 O(N) 最后再loop一遍就是O(N) 这样加起来的时间是O(NlogN) 空间是2N  

补充内容 (2014-6-28 01:31):
自动变斜体是为什么。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xuanyue 发表于 2014-6-28 06:54:26 | 显示全部楼层
感觉careercup上讨论的和你的不一样,你这道题只要求maxium number就行了。而career cup上是返回给定时间的车辆数目。. 鍥磋鎴戜滑@1point 3 acres
我感觉二楼的解法已经够了。简单而且算上排序的时间复杂度也是O(nlogn),O(n).但是因为需要排序所以不适合大数据集
另外想问下用区间树该怎么做?
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 09:47:05 | 显示全部楼层
ethan1786 发表于 2014-6-28 01:30
我电面讲到最优解的时候已经没时间了 所以后面基本就是全描述 如果有时间的话应该是自己写吧 我的办法不 ...

那无限多个log也用数组么....
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 20:04:01 | 显示全部楼层
readman 发表于 2014-6-28 09:47
那无限多个log也用数组么....

数组和树对这道题的本质是一样的吧 因为都是静态数据 至少面试的烙印觉得数组更好
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 20:10:17 | 显示全部楼层
ethan1786 发表于 2014-6-28 20:04
数组和树对这道题的本质是一样的吧 因为都是静态数据 至少面试的烙印觉得数组更好

我觉得树可以把节点分布在不同的主机上...数组嘛.......
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 20:29:26 | 显示全部楼层
readman 发表于 2014-6-28 20:10
我觉得树可以把节点分布在不同的主机上...数组嘛.......

恩恩 是啊 问题在于我那个时候还没听说过区间树啊。。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 20:46:37 | 显示全部楼层
ethan1786 发表于 2014-6-28 20:29
恩恩 是啊 问题在于我那个时候还没听说过区间树啊。。。

没事...结果怎么样?? 还有 这个是什么职位?
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 20:55:40 | 显示全部楼层
readman 发表于 2014-6-28 20:46
没事...结果怎么样?? 还有 这个是什么职位?

结果跪了。。。莫名其妙的 不知道哪儿出了问题 头疼。。。 这个是SDE 在amazon kindle组
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 21:09:37 | 显示全部楼层
ethan1786 发表于 2014-6-28 20:55
结果跪了。。。莫名其妙的 不知道哪儿出了问题 头疼。。。 这个是SDE 在amazon kindle组

patpat kindle哇..我最爱啊......
继续加油哈..没问题的
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 21:22:07 | 显示全部楼层
readman 发表于 2014-6-28 21:09
patpat kindle哇..我最爱啊......
继续加油哈..没问题的

哎 面试完了以后自信满满的 结果受到了打击 这个组现在在开始做fire phone 真的是我比较喜欢的组 结果还是跟Amazon有缘无分啊 继续刷CC150 和leetcode 准备下一个面试 可惜找朋友内推了好多公司现在都还没有消息 和现在的manager实在不合 走是早晚得事儿 面试大公司又屡受打击 我本来只想当一个快乐单纯的小码农的。。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 21:28:53 | 显示全部楼层
ethan1786 发表于 2014-6-28 21:22
哎 面试完了以后自信满满的 结果受到了打击 这个组现在在开始做fire phone 真的是我比较喜欢的组 结果还 ...
. 1point3acres.com/bbs
- = 你有工作啊....赞一个.. 有就好..有就有后盾..等拿到卡再换工作把
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-28 21:34:31 | 显示全部楼层
readman 发表于 2014-6-28 21:28
- = 你有工作啊....赞一个.. 有就好..有就有后盾..等拿到卡再换工作把

如果不是干不下去了 何至于换工作呢 女朋友也劝我说最好留下来好好干 只是manager实在是太阴了 当面聊天特别nice的跟你说干得不错 转身就在review里写觉得我不符合他要求 说不定哪天就被踢出来
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-28 23:33:31 | 显示全部楼层
ethan1786 发表于 2014-6-28 21:34
如果不是干不下去了 何至于换工作呢 女朋友也劝我说最好留下来好好干 只是manager实在是太阴了 当面聊天 ...

这...这种人在哪国都有的......其实也没什么好的办法哎...
回复 支持 反对

使用道具 举报

 楼主| ethan1786 发表于 2014-6-29 01:04:21 | 显示全部楼层
readman 发表于 2014-6-28 23:33
这...这种人在哪国都有的......其实也没什么好的办法哎...

哎 是啊 也怪我年轻气盛 很多时候做事儿不到位自己都没有注意 以后要慢慢学着了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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