【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2777|回复: 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分钟,只做了这一题。.鏈枃鍘熷垱鑷1point3acres璁哄潧
华人面试官。不求过,只愿能帮到大家。

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

孤笑客 发表于 2015-10-16 06:32:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
做一个大小为M的heap,然后每个list查阅最前面的N个数字就好了?log(M) * M * N?
reversed sorted 的话,每个list跑两个距离为M的指针,然后从倒数第M个位置开始,做同样的事情?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-16 07:50:52 | 显示全部楼层
关注一亩三分地微博:
Warald
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 | 显示全部楼层
只能说,好多朋友乱回答。。。
.1point3acres缃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. . from: 1point3acres.com/bbs
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);
  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()) {
  13.                     found = true;
  14.                     queue.poll();
  15.                     queue.offer(input.get(i).poll());
  16.                 }. 鍥磋鎴戜滑@1point 3 acres
  17.             }
  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
4->3->2
6->5. 鍥磋鎴戜滑@1point 3 acres
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 的话, ...
. from: 1point3acres.com/bbs
为什么只查阅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-7-22 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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