一亩三分地论坛

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

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

Google电面 - 10/15/2015

[复制链接] |试试Instant~ |关注本帖
crimsonfaith91 发表于 2015-10-16 05:13:01 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 校园招聘会 - 技术电面 |Other其他

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

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

x
Biggest M elements from N sorted lists.Follow-up: Biggest M elements from N reversely-sorted lists.
Time and space complexity
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
以之前面Amazon的题相似,但因压力头脑一片空白卡了10-15分钟,只做了这一题。
华人面试官。不求过,只愿能帮到大家。

第一轮面试在这里: http://www.1point3acres.com/bbs/thread-142707-1-1.html

评分

2

查看全部评分

本帖被以下淘专辑推荐:

孤笑客 发表于 2015-10-16 06:32:57 | 显示全部楼层
做一个大小为M的heap,然后每个list查阅最前面的N个数字就好了?log(M) * M * N?.鐣欏璁哄潧-涓浜-涓夊垎鍦
reversed sorted 的话,每个list跑两个距离为M的指针,然后从倒数第M个位置开始,做同样的事情?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-16 07:50:52 | 显示全部楼层
List是single linked list么?还是就是array?就是array的话感觉就是n个List每个放个Pointer在最后一个index, 然后比较n个pointer对应数的大小,然后从后往前输出result, O(mn)time, O(1) space?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-20 12:08:26 | 显示全部楼层
reverse sorted list的话 如果是linkedlist 可以反转以后再按照正常顺序的解法做吗
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-10-21 10:42:50 | 显示全部楼层
sorry, LZ, it's school computer. I just want to ask when did you have interview with Amazon? Cause I didn't get feedback after sending information to them.
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-21 23:10:52 | 显示全部楼层
孤笑客,问题是找出N sorted lists的biggest M elements,lists长短不一,M elements有可能都在同一个lists,需要cover一些edge cases。你的意思应该是查阅每个list最后面的M个nodes吧?
其实可以这样做:combine N lists to a sorted list, and then access the last M nodes.
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-21 23:11:33 | 显示全部楼层
又见紫风铃 ,list是singly linked list。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-21 23:14:01 | 显示全部楼层
liyanjia92,可以,但不需要。直接用heap就行了 - 用一个counter记载目前 access 了多少个nodes,当counter = M时 terminate。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-21 23:16:46 | 显示全部楼层
caffery24,我是今年2月面的。其实也去了实习。当时A家面了smallest(或biggest,忘了) M elements from N sorted arrays。
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-10-22 10:48:44 | 显示全部楼层
crimsonfaith91 发表于 2015-10-21 23:16
caffery24,我是今年2月面的。其实也去了实习。当时A家面了smallest(或biggest,忘了) M elements from N ...

哦哦,我以为楼主面过了明年夏天的amazon
回复 支持 反对

使用道具 举报

jobseeking 发表于 2015-10-22 14:54:17 | 显示全部楼层
只能说,好多朋友乱回答。。。
1. for singly sorted list, you should use a priority queue (queue) to hold N head nodes from each list (using default comparator from small to large), and then do queue.poll() to get the largest one (largeNode) while queue.add(largeNode.next). So it is O(M * lgM) time and O(M) space. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. I don't think it is a good idea to merge all N lists into a final sorted list and then get the last M nodes (which are largest ones), since the time complexity will be O (# of nodes * 2). But it is the best idea in my head currently.
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-23 03:43:17 | 显示全部楼层
caffery24,去年亚马逊12月起才开始招intern。今年不确定。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-23 03:49:17 | 显示全部楼层
jobseeking,我面时尝试implement (1)(不需merge lists),但发现了一个edge case没cover所以卡了一段时间。感觉面试官当时也没发现。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
建议(2)是因为(2)建立在LeetCode's Merge k Sorted Lists 的答案基础上。面试时可以先提出(2)再优化。
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-10-25 03:07:19 | 显示全部楼层
first question: select M largest elements from N sorted linked lists
Every element has to be checked, either add them to the priority queue, or ignore if it's smaller than the smallest element in the queue.
Run time complexity: worst case: O(log(M) * number of total elements); best case: O (log(M) + number of total elements)
  1. public static List<Integer> selectMLargest(List<Queue<Integer>> input, int m) {
  2.         List<Integer> result = new ArrayList<Integer>();
  3.         Queue<Integer> queue = new PriorityQueue<Integer>(m);. 1point3acres.com/bbs
  4.         while (true) {
  5.             boolean found = false;
  6.             for (int i = 0; i < input.size(); i++) {
  7.                 if (input.get(i).isEmpty()) continue;
  8.                 if (queue.size() < m) {
  9.                     found = true;
  10.                     queue.offer(input.get(i).poll());
  11.                 }-google 1point3acres
  12.                 else if (queue.peek() < input.get(i).peek()) {
  13.                     found = true;
  14.                     queue.poll();
  15.                     queue.offer(input.get(i).poll());
  16.                 }
  17.             }
  18.             if (!found) break;
  19.         }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.         while (!queue.isEmpty()) result.add(queue.poll());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.         return result;. 鍥磋鎴戜滑@1point 3 acres
  22.     }
复制代码
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-10-25 03:36:22 | 显示全部楼层
follow up:
If we want to use priority queue, I think it's the same as the original one. You will still need to traverse all the elements in order to get the largest m from the priority queue.
Consider the 4 reversely sorted lists, when M is 3. from: 1point3acres.com/bbs
1->0
4->3->2
6->5
20->19->18

Alternatively, we don't use priority queue. We keep a counter. We just need to compare the current head elements from all lists, whichever is the largest, we go to it's next one until the counter hits m. Run time complexity O(M*N)
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2015-10-27 02:58:29 | 显示全部楼层
javaprogrammer, I think your algorithm for the first question works better. Rather than merging the lists, we can run through all lists and store the biggest M largest elements.
For follow-up, I think using a heap is better. What if N >> M? In this case, maintaining a counter for each head node and comparing them every time to find the current largest node is very time-consuming. Furthermore, you will also have to use a data structure to store the counters if N is very big.
回复 支持 反对

使用道具 举报

slaink 发表于 2015-10-29 00:41:08 | 显示全部楼层
楼主有消息了吗
回复 支持 反对

使用道具 举报

翔在天空 发表于 2015-10-30 13:32:36 | 显示全部楼层
孤笑客 发表于 2015-10-16 06:32. 1point 3acres 璁哄潧
做一个大小为M的heap,然后每个list查阅最前面的N个数字就好了?log(M) * M * N?
reversed sorted 的话, ...

为什么只查阅n个,你应该是m个吗
回复 支持 反对

使用道具 举报

翔在天空 发表于 2015-10-30 13:39:08 | 显示全部楼层
怎么构造heap呢,求指导
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-30 21:16:38 | 显示全部楼层
翔在天空 发表于 2015-10-30 13:32
为什么只查阅n个,你应该是m个吗
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
呃,笔误。
本意是利用相隔距离为M的双指针方式得到每一个list倒数第M个位置的pointer(长度不满M的话就还是初始pointer),然后做一个size M的minHeap去读这么N个list啦。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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