一亩三分地论坛

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

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

Facebook Intern电面

[复制链接] |试试Instant~ |关注本帖
yhfyhf 发表于 2015-12-29 08:03:03 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完Facebook Intern电面,跪惨了。题目是Find first k common elements in n sorted arrays. 完全没思路,磕磕绊绊写完后代码我自己都觉得恶心,一定各种bug,面试官还象征性的说"ok,对了"。。

就这样吧 :(

评分

1

查看全部评分

mjq04 发表于 2016-1-3 05:35:54 | 显示全部楼层
  1. //Find first k common elements in n sorted arrays
  2. public class ArrayPointers {
  3.     public static void main(String[] args) {
  4.         int[][] arr = new int[][] {{1, 5, 10, 20}, {6, 7, 20, 30}, {3, 4, 15, 20, 30}}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         ArrayPointers instance = new ArrayPointers();
  6.         int ret = instance.firstKCommonElements(arr, 0);
  7.         System.out.print(ret);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.     }
  9.     private int firstKCommonElements (int[][] arrays, int k) {. more info on 1point3acres.com
  10.         int n = arrays.length;
  11.         int[] pointers = new int[n];. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.         for (int i = 0; i < n; i++) {
  13.             pointers[i] = 0;
  14.         }
  15.         for (int i = 0; i < n; i++) {
  16.             while (pointers[i] < arrays[i].length) {
  17.                 int num = arrays[i][pointers[i]];//不能在index变了之后,再用index
  18.                 if (hasKCommonElements(arrays, pointers, i, k)) {
  19.                     return num;
  20.                 }
  21.             }
  22.         }
  23.         return 0;
  24.     }
  25.     private boolean hasKCommonElements(int[][] arrays, int[] pointers, int idx, int k) {
  26.         int cnt = 1;. 1point3acres.com/bbs
  27.         int num = arrays[idx][pointers[idx]];
  28.         pointers[idx]++;
  29.         for (int i = idx; i < pointers.length; i++) {
  30.             while (pointers[i] < arrays[i].length && arrays[i][pointers[i]] <= num) {
  31.                 if (arrays[i][pointers[i]] == num) {.1point3acres缃
  32.                     cnt++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.                 }
  34.                 pointers[i]++;
  35.             }
  36.         }
  37.         return cnt == k;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  38.     }
  39. }
复制代码
回复 支持 2 反对 0

使用道具 举报

DJ963 发表于 2015-12-29 13:50:29 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-29 13:33
暴力解法很简单啊,跟找common prefix差不多。
既然是common,我就取k里面的第1个array,
然后for loop ...

暴力破解确实很简单,就像是楼下说的,hashmap轻松搞定,但是如果用hashmap,面试官肯定又会问,如果数组特别大怎么办,用hashmap的缺点是啥,会造成什么问题。。。。等等~想想都蛋碎,最后还是像你说的,免不了优化,换个算法继续干
回复 支持 1 反对 0

使用道具 举报

leixiang5 发表于 2015-12-29 12:16:05 | 显示全部楼层
好可惜。楼主没把握机会。。加油!
回复 支持 0 反对 1

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-29 12:53:35 | 显示全部楼层
leixiang5 发表于 2015-12-29 12:16
好可惜。楼主没把握机会。。加油!

你有什么好的解法么?-google 1point3acres
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-12-29 13:17:12 | 显示全部楼层
如果输入的是List<ListNode> 代表数组的话(n个listNode,每个listNode代表的是所在数组的头结点),用优先队列会很好做,先把每个数组的第一个元素放到优先队列中,开始对优先队列进行操作,每次抛出一个最小值,然后把最小值.next 放进优先队列中, 然后用一个count记录出现的次数,每次抛出最小值时,如果跟之前的一样就更新count 不一样count就归0,并且查看一下count是多少,如果正好是k就说明之前的元素出现了k次 那么返回就好了,不是的话就继续来

补充内容 (2015-12-29 13:18):
随便瞎逼逼的,求大神轻喷

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-29 13:17:50 | 显示全部楼层
DJ963 发表于 2015-12-29 13:17
如果输入的是List 代表数组的话(n个listNode,每个listNode代表的是所在数组的头结点),用优先队列会很好 ...

题目是array...
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-12-29 13:22:24 | 显示全部楼层

其实我有点不大明白 k common elements 是啥意思呢 ? 是第一个重复次数为k的元素 还是 那些是重复元素中的第k个
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-29 13:24:09 | 显示全部楼层
DJ963 发表于 2015-12-29 13:22
其实我有点不大明白 k common elements 是啥意思呢 ? 是第一个重复次数为k的元素 还是 那些是重复元素中 ...
. 1point 3acres 璁哄潧
我觉的,就是相同的元素?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如k是2,
2个arrays, {1,2,3,6,7}, {1,2,5,7}
我觉的返回值应该是,1,2?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2015-12-29 13:27:22 | 显示全部楼层
DJ963 发表于 2015-12-29 13:17
如果输入的是List 代表数组的话(n个listNode,每个listNode代表的是所在数组的头结点),用优先队列会很好 ...

不是链表。。。
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2015-12-29 13:27:52 | 显示全部楼层
DJ963 发表于 2015-12-29 13:22
其实我有点不大明白 k common elements 是啥意思呢 ? 是第一个重复次数为k的元素 还是 那些是重复元素中 ...

第一个重复次数为k的元素。数组都是有序的。
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-12-29 13:28:41 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-29 13:24. Waral 鍗氬鏈夋洿澶氭枃绔,
我觉的,就是相同的元素?
比如k是2,
2个arrays, {1,2,3,6,7}, {1,2,5,7}

嗯,如果这样的话 第一个的重复次数为2的元素就是1了。 其实我感觉如果是数组的话也还好,不过那就得用一个index数组来维护每个数组当先走到的index,然后还是按我刚才说的用优先队列做,每次往优先队列中放完元素的话,再去更新index数组中对应数组的index,你感觉呢? 不过这个方法感觉好蠢~不知道还有什么其他的好方法
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-29 13:33:15 | 显示全部楼层
DJ963 发表于 2015-12-29 13:28
嗯,如果这样的话 第一个的重复次数为2的元素就是1了。 其实我感觉如果是数组的话也还好,不过那就得用一 ...

暴力解法很简单啊,跟找common prefix差不多。. 鍥磋鎴戜滑@1point 3 acres
既然是common,我就取k里面的第1个array,
然后for loop编列array的每个index, 每编列一个index,然后看其他k-1的array相同的index是不是和第1个array的相同index数相同,如果相同,就继续index++。 -google 1point3acres
但是这肯定不是optimal solution吧? 如果facebook问,这么做肯定要follow up,让你优化。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-29 13:35:29 | 显示全部楼层
Array的话好像没啥太好办法,遍历一遍,用一个HashMap记录一下每个数出现的次数?直至有一个数的次数是K。。
或者优化一下,遍历第一个array,对其中的每一个元素,在剩下的所有array里面进行二分查找,获得总得出现次数。每次二分查找都可以为下一次二分查找缩小范围。。
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-12-29 13:47:07 | 显示全部楼层
小A要当码农 发表于 2015-12-29 13:35
Array的话好像没啥太好办法,遍历一遍,用一个HashMap记录一下每个数出现的次数?直至有一个数的次数是K。 ...

如果这样的话,假如现在在第一个数组里我们找到了一个3,然后想在剩下的n-1个数组中,每个都进行二分查找,剩下的数组中,有的只有一个3,有的好几个3,那么简单的二分查找就比较蛋疼了,每次二分查找个人感觉不大能为下一次二分查找缩小范围吧,因为那么数组只是在水平方向上是递增的,垂直的应该不是吧
回复 支持 反对

使用道具 举报

dangertrip 发表于 2015-12-29 14:14:03 | 显示全部楼层
DJ963 发表于 2015-12-29 13:17
如果输入的是List 代表数组的话(n个listNode,每个listNode代表的是所在数组的头结点),用优先队列会很好 ...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴题目不是说了sorted嘛,这不应该相当于求n个array merge?每次拿最小的头,如果和前一个一样,计数器+1(初始值1),判断到k了就输出当前结果?维护一个最小堆,每次操作lgn,最差是数组长度*lgn? 有没有更好解法?
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-12-29 14:24:11 | 显示全部楼层
dangertrip 发表于 2015-12-29 14:14
题目不是说了sorted嘛,这不应该相当于求n个array merge?每次拿最小的头,如果和前一个一样,计数器+1( ...

这个方法我之前也想到了,但是总是感觉他会问 如果数组的长度过长,怎么办~也就是堆存不下这么大的数组,该怎么解决呢
回复 支持 反对

使用道具 举报

dangertrip 发表于 2015-12-29 14:31:25 | 显示全部楼层
DJ963 发表于 2015-12-29 14:24
这个方法我之前也想到了,但是总是感觉他会问 如果数组的长度过长,怎么办~也就是堆存不下这么大的数组, ...

堆只需要n的大小啊…只维护第一个数,取一个删一个
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-29 15:01:13 | 显示全部楼层
DJ963 发表于 2015-12-29 13:47
如果这样的话,假如现在在第一个数组里我们找到了一个3,然后想在剩下的n-1个数组中,每个都进行二分查找 ...

还需要用一个HashMap来存每一个Array的下次二分起点
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-29 15:01:53 | 显示全部楼层
dangertrip 发表于 2015-12-29 14:31
堆只需要n的大小啊…只维护第一个数,取一个删一个

. From 1point 3acres bbs那你怎么知道删了一个以后,接下来去哪个数组取呢?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-29 15:16:37 | 显示全部楼层
小A要当码农 发表于 2015-12-29 13:35
Array的话好像没啥太好办法,遍历一遍,用一个HashMap记录一下每个数出现的次数?直至有一个数的次数是K。 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
first k elements,应该是连续的吧?还是随意顺序.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实,我也不是很懂,题目具体是啥样。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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