近期论坛无法登录的解决方案


一亩三分地论坛

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

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

facebook 新鲜电面

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

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

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

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

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
楼主 问一下 为什么是维护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. . From 1point 3acres bbs
  5.         public KSortedListIterator(ArrayList<ArrayList<Integer>> lists) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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.         public int next() {. 鍥磋鎴戜滑@1point 3 acres
  13.                 return iterator.next();
  14.         }

  15. }
复制代码


这样?
回复 支持 反对

使用道具 举报

 楼主| 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. 1point3acres.com/bbs
恩,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 | 显示全部楼层
是不是这样?. from: 1point3acres.com/bbs

  1. package heap;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  2. import java.util.*;

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

  74. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
回复 支持 反对

使用道具 举报

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 | 显示全部楼层

是的,思路很好,我也是类似的想法,无非就是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. 鍥磋鎴戜滑@1point 3 acres
恭喜楼主!请问楼主的onsite时间定好了么?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 21:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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