一亩三分地论坛

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

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

facebook 新鲜电面

[复制链接] |试试Instant~ |关注本帖
kemeng1314 发表于 2016-5-17 03:00:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
上周四面的fb,面试官人非常nice,在讨论的过程中我感觉就像大家在聊天,分享自己的经验和感悟。题目我认为是之前merge matrix的变种,Given k sorted lists of O(n) integers each, implement an iterator that will yield all elements in sorted order。大体讨论了几种思路。转换为 linkedlist 做正常的merge,但较好的思路是直接用iterator来实现大类的next,hasnext和constructor。希望大家可以贡献想法看看这种思路怎么继续做下去。面完我所想到的还是新建一个wrapper class, 类似于代替了linklist里面每次指向下一个node。由于是要sort order,肯定需要维护一个k size 的queue。今天周一一早收到hr的follow up,去总部参加onsite。这是第一次,希望能好好把我机会,多听听大家对fb onsite还有什么建议。本人面的就是new grad,求好运,加油

评分

1

查看全部评分

ykwwind 发表于 2016-5-18 08:22:48 | 显示全部楼层
wrapper存第一个element, 再存一个iterator.
每次最小的踢出去,iterator还有的话,改下element, 存回去...
回复 支持 1 反对 0

使用道具 举报

lookbackinanger 发表于 2016-5-17 03:21:24 | 显示全部楼层
恭喜恭喜,请问下内推后大约多久给的电面啊?
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-17 03:27:37 | 显示全部楼层
lookbackinanger 发表于 2016-5-17 03:21
恭喜恭喜,请问下内推后大约多久给的电面啊?

大概一周多吧
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-17 03:33:19 | 显示全部楼层
楼主 问一下 为什么是维护k size的queue,而不是维护k size的heap呢。 祝楼主 好运
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-17 03:37:47 | 显示全部楼层
adiggo 发表于 2016-5-17 03:33
楼主 问一下 为什么是维护k size的queue,而不是维护k size的heap呢。 祝楼主 好运

说错了,不好意思,就是k size的heap
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-17 20:42:14 | 显示全部楼层
  1. class KSortedListIterator {
  2. . Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         private ArrayList<Integer> list= new ArrayList<Integer>();
  4.         Iterator iterator = list.iterator();

  5.         public KSortedListIterator(ArrayList<ArrayList<Integer>> lists) {. visit 1point3acres.com for more.
  6.                 this.list = mergeKSortedLists(lists);
  7.       iterator=list.iterator();
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.         }

  9.         public boolean hasNext() {. more info on 1point3acres.com
  10.                 return iterator.hasNext();
  11.         }
  12. . Waral 鍗氬鏈夋洿澶氭枃绔,
  13.         public int next() {
  14.                 return iterator.next();
  15.         }. Waral 鍗氬鏈夋洿澶氭枃绔,

  16. }
复制代码


这样?
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-17 22:56:50 | 显示全部楼层

恩,merge之后的list只要是sorted,直接用它的iterator就行了,核心就是merge k lists了,你用的什么思路呢
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-17 23:21:18 | 显示全部楼层
kemeng1314 发表于 2016-5-17 22:56
恩,merge之后的list只要是sorted,直接用它的iterator就行了,核心就是merge k lists了,你用的什么思路 ...

如果面试官要求的是merge k linked list的话 那就可以leetcode上的照搬了 如果是arraylist就比较麻烦了
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-17 23:29:10 | 显示全部楼层
给的是sorted list of integer,http://blog.csdn.net/github_34333284/article/details/51345092。 如果是Linked List 就是leetcode原题。
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-18 00:15:39 | 显示全部楼层
wtcupup 发表于 2016-5-17 23:21
如果面试官要求的是merge k linked list的话 那就可以leetcode上的照搬了 如果是arraylist就比较麻烦了
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给的输入是arraylist。确实和linkedlist差别比较大
回复 支持 反对

使用道具 举报

ryanlr 发表于 2016-5-18 02:52:35 | 显示全部楼层
是不是这样?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. package heap;

  2. import java.util.*;. 鍥磋鎴戜滑@1point 3 acres

  3. class Wrapper{
  4.         public ArrayList<Integer> list; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         public int index;
  6.        
  7.         public Wrapper(ArrayList<Integer> list, int index){
  8.                 this.list = list;
  9.                 this.index= index;. more info on 1point3acres.com
  10.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11. }

  12. public class MergeKList {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.         PriorityQueue<Wrapper> queue;
  14.        
  15.         public MergeKList(ArrayList<ArrayList<Integer>> lists){
  16.                 queue = new PriorityQueue<Wrapper>(new Comparator<Wrapper>(){
  17.                         public int compare(Wrapper w1, Wrapper w2){
  18.                                 return w1.list.get(w1.index) - w2.list.get(w2.index);
  19.                         }
  20.                 });
  21.                
  22.                 for(ArrayList<Integer> list: lists){
  23.                         Wrapper w = new Wrapper(list, 0);
  24.                         queue.offer(w);. 1point 3acres 璁哄潧
  25.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.         }
  27.        
  28.         public boolean hasNext(){                . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  29.                 if(!queue.isEmpty())
  30.                         return true;
  31.                
  32.                 return false;
  33.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  34.         .1point3acres缃
  35.         public Integer next(){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                
  37.                 Wrapper w = queue.poll();
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.                
  39.                 ArrayList<Integer> list = w.list;
  40.                 int index = w.index;
  41.                
  42.                 if(index < list.size()-1){
  43.                         w.index = index+1;
  44.                         queue.offer(w);
  45.                 }
  46.                
  47.                 return list.get(index);
  48.         }
  49.        
  50.         public static void main(String[] args) {
  51.                
  52.                 ArrayList<Integer> l1 = new ArrayList<Integer>();
  53.                 ArrayList<Integer> l2 = new ArrayList<Integer>();
  54.                 ArrayList<Integer> l3 = new ArrayList<Integer>();.1point3acres缃
  55.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  56.                 l1.add(2);
  57.                 l1.add(4);
  58.                 l1.add(6);
  59.                 l2.add(1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  60.                 l2.add(3);
  61.                 l3.add(5);
  62.                
  63.                 ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
  64.                 lists.add(l1);
  65.                 lists.add(l2);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  66.                 lists.add(l3);
  67.                
  68.                 MergeKList mk = new MergeKList(lists);
  69.                 while(mk.hasNext()){. more info on 1point3acres.com
  70.                         System.out.println(mk.next());. from: 1point3acres.com/bbs
  71.                 }
  72.         }

  73. }
复制代码
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-5-18 06:43:47 | 显示全部楼层
如果只是需要输出结果或者可以用array/linked list来存的话,应该是没区别的呀。能不能解释一下区别在哪里啊,谢谢!
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-18 08:09:45 | 显示全部楼层
sheepmiemies 发表于 2016-5-18 06:43
如果只是需要输出结果或者可以用array/linked list来存的话,应该是没区别的呀。能不能解释一下区别在哪里 ...

我认为array/arraylist来存是类似的,他们和linkedlist的区别就是merge的时候如果你没有用wrapper class额外存什么信息,当你pop出最小元素后,指针无法向后移动。而linkedlist都是有next属性的,方便向后取数。
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-18 08:11:03 | 显示全部楼层
ryanlr 发表于 2016-5-18 02:52
. 1point 3acres 璁哄潧是不是这样?

.1point3acres缃是的,思路很好,我也是类似的想法,无非就是wrapper里面没有存arraylist,而是存了arraylist的index。谢谢你的代码!
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-5-18 08:50:10 | 显示全部楼层
kemeng1314 发表于 2016-5-18 08:09
我认为array/arraylist来存是类似的,他们和linkedlist的区别就是merge的时候如果你没有用wrapper class ...

soga,语言不同,我不太熟java,c++的STL可以用iterator是一样的
回复 支持 反对

使用道具 举报

cheeroh 发表于 2016-5-20 05:43:09 | 显示全部楼层
楼主是ms 还是phd new grad啊?
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-20 07:09:13 | 显示全部楼层
cheeroh 发表于 2016-5-20 05:43. 1point 3acres 璁哄潧
楼主是ms 还是phd new grad啊?

ms fresh grad
回复 支持 反对

使用道具 举报

chijuzipi 发表于 2016-5-20 11:40:02 | 显示全部楼层
恭喜楼主!请问楼主的onsite时间定好了么?
回复 支持 反对

使用道具 举报

 楼主| kemeng1314 发表于 2016-5-20 11:50:26 | 显示全部楼层
chijuzipi 发表于 2016-5-20 11:40. Waral 鍗氬鏈夋洿澶氭枃绔,
恭喜楼主!请问楼主的onsite时间定好了么?

定好啦,5.31号11:00到3:00差不多吧。三~四轮
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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