一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 5570|回复: 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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
wrapper存第一个element, 再存一个iterator.
每次最小的踢出去,iterator还有的话,改下element, 存回去...
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| 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. 1point3acres.com/bbs
楼主 问一下 为什么是维护k size的queue,而不是维护k size的heap呢。 祝楼主 好运

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

使用道具 举报

wtcupup 发表于 2016-5-17 20:42:14 | 显示全部楼层
  1. class KSortedListIterator {.鐣欏璁哄潧-涓浜-涓夊垎鍦

  2.         private ArrayList<Integer> list= new ArrayList<Integer>();
  3.         Iterator iterator = list.iterator();
  4. -google 1point3acres
  5.         public KSortedListIterator(ArrayList<ArrayList<Integer>> lists) {
  6.                 this.list = mergeKSortedLists(lists);. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.       iterator=list.iterator();. 鍥磋鎴戜滑@1point 3 acres
  8.         }
  9. . 鍥磋鎴戜滑@1point 3 acres
  10.         public boolean hasNext() {
  11.                 return iterator.hasNext();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  13.         public int next() {. 1point3acres.com/bbs
  14.                 return iterator.next();
  15.         }

  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.*;

  3. class Wrapper{
  4.         public ArrayList<Integer> list;
  5.         public int index;
  6.        
  7.         public Wrapper(ArrayList<Integer> list, int index){. 鍥磋鎴戜滑@1point 3 acres
  8.                 this.list = list;
  9.                 this.index= index;
  10.         }
  11. }

  12. public class MergeKList {
  13.         PriorityQueue<Wrapper> queue;
  14.        
  15.         public MergeKList(ArrayList<ArrayList<Integer>> lists){. 1point 3acres 璁哄潧
  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);. 鍥磋鎴戜滑@1point 3 acres
  24.                         queue.offer(w);
  25.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.         }
  27.         . more info on 1point3acres.com
  28.         public boolean hasNext(){                鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.                 if(!queue.isEmpty())
  30.                         return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                
  32.                 return false;
  33.         }
  34.        
  35.         public Integer next(){
  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) {. more info on 1point3acres.com
  51.                
  52.                 ArrayList<Integer> l1 = new ArrayList<Integer>();
  53.                 ArrayList<Integer> l2 = new ArrayList<Integer>();
  54.                 ArrayList<Integer> l3 = new ArrayList<Integer>();
  55.                
  56.                 l1.add(2);
  57.                 l1.add(4);
  58.                 l1.add(6);
  59.                 l2.add(1);
  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);. 鍥磋鎴戜滑@1point 3 acres
  66.                 lists.add(l3);
  67.                
  68.                 MergeKList mk = new MergeKList(lists);
  69.                 while(mk.hasNext()){
  70.                         System.out.println(mk.next());
  71.                 }
  72.         }-google 1point3acres

  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. from: 1point3acres.com/bbs
是不是这样?

.鏈枃鍘熷垱鑷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
楼主是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
恭喜楼主!请问楼主的onsite时间定好了么?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
定好啦,5.31号11:00到3:00差不多吧。三~四轮
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-1 08:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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