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

刚刚放下电话 本来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 th

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

04:52):
来打脸了 刚找到了在careercup的一个讨论 （）不过里面没有特别好的解法 所以还要看大家讨论了

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

readman 发表于 2014-6-27 15:45
区间树``````

补充内容 (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
  

这样的话 最优的时间复杂度是 O(NlogN) 空间复杂度是O(N) 貌似到极限了

readman 发表于 2014-6-27 22:57
不过电面问这个你怎么答??? 自己写一个?

我电面讲到最优解的时候已经没时间了 所以后面基本就是全描述 如果有时间的话应该是自己写吧 我的办法不是用区间树 我提了一下用树 他直接否决了 所以我用数组做的

假设所有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[i] -- 思路是在两辆车entry的间隔有车离开的话 对找max car number 没有意义 只是在新的车进来的时候需要考虑 这里用binary search 所以时间复杂度是O(NlogN) 然后对A做 A[i] += A[i-1] 就得到对应时间点所有车得数量 是 O(N) 最后再loop一遍就是O(N) 这样加起来的时间是O(NlogN) 空间是2N  

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

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

区间树``````

补充内容 (2014-6-27 15:47):
普林斯顿课上有提到哦

ethan1786 发表于 2014-6-27 21:37
赞区间树！ 刚才google了一下区间树 发现中文很多都把区间树和线段树放在一起了 貌似应该是不一样的 stac ...

不过电面问这个你怎么答??? 自己写一个?

感觉careercup上讨论的和你的不一样，你这道题只要求maxium number就行了。而career cup上是返回给定时间的车辆数目。
我感觉二楼的解法已经够了。简单而且算上排序的时间复杂度也是O(nlogn),O(n).但是因为需要排序所以不适合大数据集
另外想问下用区间树该怎么做？

lz大牛啊

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

那无限多个log也用数组么....

readman 发表于 2014-6-28 09:47
那无限多个log也用数组么....

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