一亩三分地论坛

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

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

facebook面经

[复制链接] |试试Instant~ |关注本帖
beiyouyangxi 发表于 2014-11-20 03:28:37 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass

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

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

x
首先感谢帮我内推的哥们,谢谢你让我顺利拿到电话面试。
其他的就不废话了,电话打进来了。一哥们先介绍了一下他做的东西,做API的。然后说了2min,给我说今天一共45分钟,首先会问5-10分钟简历,然后30分钟左右的coding,最后的时间提问。
1. 一来就是一道简单题,翻转链表
// Reverse a Singly Linked List
// Example Input: A -> B -> C. from: 1point3acres.com/bbs
// Example Output: C -> B -> A
他先让说思路,然后问时间和空间复杂度,然后写代码。说思路说了半天,这种list的题,就是画图,英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部分,所以很快就写完了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
2.第二题直接copy 题目,感觉跟leetcode上面的interval那题很相似,简单一点点。.1point3acres缃
// Given a array of pairs where each pair contains the start and end time of a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False

同样的思路+复杂度。 同样是变种题,还变简单了,很快写完。(主要是考比较器的override吧)

3. follow up第二题
// determine the minimum number of meeting rooms needed to hold all the meetings.
// Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5)). more info on 1point3acres.com
// Output: 2

我看表还剩下10分钟,然后想了3min钟,面试官就说没时间了,要不你说说思路。然后说了一下思路,面试官说OK。让我提问题。瞎问了一个问题。面试官还特别详细的解答了。他说超了一点时,不过没关系。 然后互相感谢了一下,客套了一下。就再见了。 第二天HR说下一轮Onsite了。
. more info on 1point3acres.com
最后求大家祝福,希望能onsite好运~~ 祝大家都能拿到心仪的offer~

评分

2

查看全部评分

alex2013 发表于 2014-11-23 12:59:57 | 显示全部楼层
kongweihan 发表于 2014-11-23 12:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
应该也是greedy algorithm。搜了一下,思路是:从没有room开始,每次在不得已的情况下增加room,每个room ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
看到别人一个更简略的办法,应该是对的:. visit 1point3acres.com for more.
按start 或者 end 时间从小到大排序, 从0 到n-1遍历一遍,初始化roomNum为0, 遇到start点,房间个数+1, 遇到end点 房间个数-1, 这个过程中房间个数的最大值就是需要的最少房间个数。
回复 支持 3 反对 0

使用道具 举报

lch04 发表于 2015-3-29 11:27:35 | 显示全部楼层
public static int minimumRooms(List<Interval> intervals) {. 鍥磋鎴戜滑@1point 3 acres
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (Interval interval : intervals) {
            list.add(interval.begin);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            list.add(-interval.end);
        }
        Collections.sort(list, new IntegerComparator());
        int cur = 0, max = 0;
        for (Integer num : list) {
            if (num >= 0) {
                ++cur;
            } else {
                --cur;
            }
            max = Math.max(cur, max);
        }
        return max;
    }

    static class IntegerComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
. more info on 1point3acres.com            return Math.abs(o1) - Math.abs(o2);
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }

    static class Interval {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int begin;
        int end;
        Interval(int begin, int end) {
            this.begin = begin;.鐣欏璁哄潧-涓浜-涓夊垎鍦
            this.end = end;
        }. 1point3acres.com/bbs
    }
回复 支持 1 反对 0

使用道具 举报

tyr034 发表于 2014-11-20 13:21:43 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

alex2013 发表于 2014-11-23 03:24:41 | 显示全部楼层
想问下LZ那个follow up是什么个思路呢?
回复 支持 反对

使用道具 举报

kongweihan 发表于 2014-11-23 12:36:23 | 显示全部楼层
alex2013 发表于 2014-11-23 03:24
想问下LZ那个follow up是什么个思路呢?

应该也是greedy algorithm。搜了一下,思路是:从没有room开始,每次在不得已的情况下增加room,每个room只存储安排在这个room的最后一个meeting的结束时间,具体解法是:

1. 按照开始时间排列所有meeting,新建一个room,把第一个meeting的结束时间存在里面(类似于roomFinishTime .add(finishTime[0]))
2. 开始循环,每次循环安排一个meeting。如果当前meeting的时间与已经存在的某个room是兼容的(其开始时间大于某个room的最后一个meeting的结束时间),就安排给它,如果都不兼容,就新增一个room,每次都要更新room的最后一个meeting的结束时间
3. 所有meeting全部安排完后,已有room的数量就是所求的结果

证明:. 鍥磋鎴戜滑@1point 3 acres
原则上讲,一个时间点有可能同时存在x个会议,所以在这个时间点上至少需要x个room。所有时间点上的这个x值里的最大值就是所求的room数量的可能的最小值。每次循环中,如果一个meeting与已有的所有room都不兼容,说明这个meeting的开始的时间点上,至少有room数量那么多个meeting,那我们就不得不新增一个room。而这个算法自始至终都只在这个情况下才增加room,所以最后的结果是最优的。
.1point3acres缃
写得比较简略,欢迎讨论!
回复 支持 反对

使用道具 举报

wksora 发表于 2014-12-23 17:17:36 | 显示全部楼层
用一个根据开始时间排序的List,用一个存放前一个meeting结束前正在运行的优先队列,按结束时间早的优先,用一个变量存当前总共需要的meeting room数量,用一个变量存当前free的meeting room数量。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后就是遍历List,每次把结束时间在当前开始时间前的room从优先队列里面弹出来,每弹出一个就freeroom++,直到优先队列为空或者优先队列的堆顶时间在当前开始时间之后
然后如果freeroom>0就push当前结束时间到优先队列,freeroom--,如果freeroom==0就让totalroom++,然后push当前结束时间到优先队列。直到压入最后一个会议安排。
totalroom为所求答案。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
纯greedy,未证明。
回复 支持 反对

使用道具 举报

犬座 发表于 2014-12-25 02:52:20 | 显示全部楼层
meeting room:
  1. bool pairLess_first(const double& a, const double& b) {
  2.   return a <= b;
  3. }

  4. /* return ture if the x is of the from m.0 */
  5. bool isEnd(double x) {
  6.   double intpart;
  7.   return modf(x, &intpart) == 0.0;
  8. }
  9. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10. int minMeetingRoom(vector<pair<int, int> >& list) {
  11.   int len = list.size();
  12.   vector<double> dlist(2 * len, 0);. 1point 3acres 璁哄潧
  13.   
  14.   for(int i = 0; i < len; ++i) {
  15.     dlist[2 * i] = 1.0 * list[i].first + 0.1;
  16.     dlist[2 * i + 1] = 1.0 * list[i].second;
  17.   }

  18.   // sort pairs based on starting time. 1point3acres.com/bbs
  19.   sort(dlist.begin(), dlist.end(), pairLess_first);

  20.   int room = 0;
  21.   int minroom = 0;
  22.   for(int i = 0; i < 2 * len; ++i) {. From 1point 3acres bbs
  23.     minroom = max(minroom, isEnd(dlist[i]) ? --room : ++room);-google 1point3acres
  24.   }

  25.   return minroom;
  26. }
复制代码
回复 支持 反对

使用道具 举报

迷彩的瓜皮帽 发表于 2014-12-25 05:19:45 | 显示全部楼层
  1. public class MinMeetingRooms {
  2.         public static int canAttend(Interval[] arr) {
  3.                 if (arr == null || arr.length <= 1) {
  4.                         return 1;
  5.                 }
  6.                 Arrays.sort(arr, new Comparator<Interval>() {
  7.                         @Override
  8.                         public int compare(Interval o1, Interval o2) {
  9.                                 return o1.start - o2.start;. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                         }
  11.                 });
  12.                 int num = 0;.1point3acres缃
  13.                 boolean[] checker = new boolean[arr.length];
  14.                 for (int i = 0; i < arr.length; i++) {
  15.                         if (!checker[i]) {
  16.                                 num++;
  17.                                 checker[i] = true;
  18.                                 int end = arr[i].end;
  19.                                 for (int j = i + 1; j < arr.length; j++) {
  20.                                         if (!checker[j] && arr[j].start >= end) {
  21.                                                 checker[j] = true;
  22.                                                 end = arr[j].end;
  23.                                         }
  24.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.                         }
  26.                 }
  27.                 return num;. 1point3acres.com/bbs
  28.         }. more info on 1point3acres.com
  29. }
复制代码
求指点,我这个方法对么
回复 支持 反对

使用道具 举报

mj2009 发表于 2014-12-25 08:03:02 | 显示全部楼层
alex2013 发表于 2014-11-23 12:59
看到别人一个更简略的办法,应该是对的:
按start 或者 end 时间从小到大排序, 从0 到n-1遍历一遍,初 ...

对,这个方法简单有效。每次碰到conflict的时候就加一个room。
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-1-26 06:49:51 | 显示全部楼层
alex2013 发表于 2014-11-23 12:59
看到别人一个更简略的办法,应该是对的:
按start 或者 end 时间从小到大排序, 从0 到n-1遍历一遍,初 ...

也在思考这道题,目前想到的也是O(N2)的解法,感觉应该是有ON的,能发下你的这个解法的详细链接吗
回复 支持 反对

使用道具 举报

alex2013 发表于 2015-1-26 09:36:50 | 显示全部楼层
YY大帝 发表于 2015-1-26 06:49
也在思考这道题,目前想到的也是O(N2)的解法,感觉应该是有ON的,能发下你的这个解法的详细链接吗

没有详细版本,也是在某个帖子里面看到别人这么说的。不过用两个queue,一个存start一个存end,是可以实现的。
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-2-12 16:24:46 | 显示全部楼层
首先按照开始时间排序,定义一个priority_queue,使得堆顶是当前堆里面meeting结束最早的时间点, 定义一个roomNumber, 然后从头开始,
如果queue是空的,push当前会议结束时间到堆里,roomNumber++;
如果当前会议开始时间晚于堆顶会议结束时间,将堆顶时间取出,更新,并重新push
如果当前会议开始时间早于堆顶会议结束时间,将当前会议结束时间push, roomNumber++;
return roomNumber;
时间复杂度,nlogn吧
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-2-12 17:45:21 来自手机 | 显示全部楼层
crazybadboy 发表于 2015-2-12 16:24
首先按照开始时间排序,定义一个priority_queue,使得堆顶是当前堆里面meeting结束最早的时间点, 定义一个 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求大神指点一二
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2015-3-22 01:01:49 | 显示全部楼层
alex2013 发表于 2014-11-23 12:59. 鍥磋鎴戜滑@1point 3 acres
看到别人一个更简略的办法,应该是对的:
按start 或者 end 时间从小到大排序, 从0 到n-1遍历一遍,初 ...

就像一个袋子,放东西,取东西,放最多的时候就是你需要的最大空间。
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-10-23 11:13:46 | 显示全部楼层
crazybadboy 发表于 2015-2-12 16:24. From 1point 3acres bbs
首先按照开始时间排序,定义一个priority_queue,使得堆顶是当前堆里面meeting结束最早的时间点, 定义一个 ...

这个解释很赞啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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