亚马逊intern面经

wait4it 发表于 2015-12-28 11:20
同学你还是先复习下这些容器的基本概念把

你priority q不用sort全部？
你别骗我，priority就是implements comparator，不sort全部，你怎么知道哪个数大。
数组是,1,3,5,6,7,8,9。如果,维护第3大的，你也要全sort数啊。你还是了解一下comparator是怎么工作的吧。

xiaozhuxiaozhu 发表于 2015-12-28 11:29
你priority q不用sort全部？
你别骗我，priority就是implements comparator，不sort全部，你怎么知道哪 ...

PQ用的是Binary Heap实现的。。。你可以上网看些教程或公开课了解下。。。

xiaozhuxiaozhu 发表于 2015-12-28 11:29
你priority q不用sort全部？
你别骗我，priority就是implements comparator，不sort全部，你怎么知道哪 ...

重点不是comparator  先看看heap比较好

xiaozhuxiaozhu 发表于 2015-12-28 11:29
你priority q不用sort全部？
你别骗我，priority就是implements comparator，不sort全部，你怎么知道哪 ...

其实很多面试都会问你优先队列 map 哈希表之类的工作原理，我建议你面试之前这些都先复习复习，可能时间长了有点忘了把。

kth largest number 是leetcode那道吗？似乎是可以用快排的思想，做到average o(n)

caffery24 发表于 2015-12-29 13:36
kth largest number 是leetcode那道吗？似乎是可以用快排的思想，做到average o(n)

好像是可以，但是我当时没有想到，他也没问我更快的方法。所以我就这么做了，就是最后一个follow up给的不是数组，是一个很长很长的list， 然后给你他的iterator， 然后跟你说一般容器塞不下这么不长的。问你怎么求

请问楼主 两个数字标记找2nd怎么做的？

zealot5209 发表于 2015-12-29 14:26
请问楼主 两个数字标记找2nd怎么做的？

一个int是最大，另外个为第二大，然后扫一遍，如果比最大大，那么最大更新，第二大更新成之前的最大，如果比第二大大，更新第二大。

wait4it 发表于 2015-12-29 23:52
一个int是最大，另外个为第二大，然后扫一遍，如果比最大大，那么最大更新，第二大更新成之前的最大，如 ...

感谢楼主的耐心解答~！ 另外请问quick select用在array和用在list会不一样吗？

zealot5209 发表于 2015-12-30 11:22
感谢楼主的耐心解答~！ 另外请问quick select用在array和用在list会不一样吗？

我觉得用list的花，quick select你不知道list的位置，不能跟vector一样直接调用index，我感觉是这样