推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2803|回复: 19
收起左侧

Google电面 - 10/15/2015

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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缃
  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.                 }
  12.                 else if (queue.peek() < input.get(i).peek()) {. more info on 1point3acres.com
  13.                     found = true;
  14.                     queue.poll();
  15.                     queue.offer(input.get(i).poll());
  16.                 }
  17.             }. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.             if (!found) break;
  19.         }
  20.         while (!queue.isEmpty()) result.add(queue.poll());
  21.         return result;
  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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1->0.鏈枃鍘熷垱鑷1point3acres璁哄潧
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
做一个大小为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啦。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-17 16:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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