一亩三分地论坛

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

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

FB 11/04电面一轮

[复制链接] |试试Instant~ |关注本帖
roosterxie 发表于 2015-11-6 05:30:09 | 显示全部楼层 |阅读模式

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

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

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

x
面试官 台湾人 david 靠(kao)-google 1point3acres
1 strstr
2 meet room II 变种 求最多interval的时间点,返回任意一个就行。

写题写得慢,两题写完40分钟了 后面5分钟扯扯结束
. 1point 3acres 璁哄潧
求过一轮

评分

1

查看全部评分

 楼主| roosterxie 发表于 2015-11-6 05:33:45 | 显示全部楼层
好像发面试官名字不大好。。不会二次编辑帖子。。。有高手求指导。。。
回复 支持 反对

使用道具 举报

cherylshang 发表于 2015-11-6 05:54:36 | 显示全部楼层
LZ找人内推完 多久收到HR联系的啊?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-6 06:11:23 | 显示全部楼层
楼主牛人啊。。fb现在有面试的简历都很厉害。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-6 07:27:53 | 显示全部楼层
roosterxie 发表于 2015-11-6 05:33
好像发面试官名字不大好。。不会二次编辑帖子。。。有高手求指导。。。

楼主第二题可以说得详细一点嘛?谢啦
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-6 10:07:37 | 显示全部楼层
cherylshang 发表于 2015-11-6 05:54
LZ找人内推完 多久收到HR联系的啊?
. Waral 鍗氬鏈夋洿澶氭枃绔,
两周。。。。。。。。(打点为了8个字)
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-6 10:10:35 | 显示全部楼层
小A要当码农 发表于 2015-11-6 07:27
楼主第二题可以说得详细一点嘛?谢啦

meet room ii
原题:Given [[0, 30],[5, 10],[15, 20]],
          return 2.  
现在是return 5 因为时间点5的时候有两个interval在同时进行
当然 5 6 7 8 9 10 15 16 17 18 19 20 这些都行 return其中一个就行了
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 04:16:16 | 显示全部楼层
roosterxie 发表于 2015-11-6 10:10
meet room ii . 鍥磋鎴戜滑@1point 3 acres
原题:Given [[0, 30],[5, 10],[15, 20]],
          return 2.  

什么思路比较好,我想的比较暴力一些,用个hashmap 统计 从 最小的start到最大的end中所有的可能,不知道有没有更优的
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-7 06:55:19 | 显示全部楼层
难度略高啊。。。楼主strstr那题有要求用KMP么?
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 10:15:20 | 显示全部楼层
public static int max(Interval[] intervals) {
                // O(n*k) time space o(max-min)
                HashMap<Integer, Integer> map = new HashMap<>();. more info on 1point3acres.com
                for (int i = 0; i < intervals.length; i++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        Interval cur = intervals[i];
                        for (int j = cur.start; j <= cur.end; j++) {
                                if (map.containsKey(j)) {
                                        map.put(j, map.get(j) + 1);
                                } else {
                                        map.put(j, 1);
                                }
                        }
                }
                int max = 1;
                for (int key : map.keySet()) {
                        max = Math.max(max, map.get(key));
                }. From 1point 3acres bbs
                for (int key : map.keySet()) {
                        if (map.get(key) == max) {
                                return key;
                        }
                }
                return 0;
        }
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-7 13:04:45 | 显示全部楼层
oio14644 发表于 2015-11-7 10:15
public static int max(Interval[] intervals) {
                // O(n*k) time space o(max-min). more info on 1point3acres.com
                HashMap map = ne ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
The Space Complexity is too high?
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-8 10:59:18 来自手机 | 显示全部楼层
stonezms 发表于 2015-11-7 06:55
难度略高啊。。。楼主strstr那题有要求用KMP么?

没有要求。
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-8 18:49:05 | 显示全部楼层
小A要当码农 发表于 2015-11-7 13:04
The Space Complexity is too high?

怎么优化?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-9 00:25:16 | 显示全部楼层
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-9 07:51:33 | 显示全部楼层
小A要当码农 发表于 2015-11-9 00:25
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=109379&extra=page%3D1%26filter%3Dsort ...

能具体一点吗? 指的到底是哪个? 谢谢
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-9 11:12:32 | 显示全部楼层
oio14644 发表于 2015-11-9 07:51. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
能具体一点吗? 指的到底是哪个? 谢谢

Sorry. 15楼
回复 支持 反对

使用道具 举报

mooc 发表于 2015-12-8 13:05:41 | 显示全部楼层
lz strstr这道题要求runtime是多少的算法?
回复 支持 反对

使用道具 举报

xuweineo 发表于 2015-12-11 07:06:04 | 显示全部楼层
oio14644 发表于 2015-11-6 15:16
什么思路比较好,我想的比较暴力一些,用个hashmap 统计 从 最小的start到最大的end中所有的可能,不知道 ...

直接用meeting room II的代码,只不过把寸end time的容器变成priority_queue, 最后返回这个queue的front就好了。
  1. class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. private:
  3.     static bool compare(Interval &i1, Interval &i2){
  4.         return i1.start < i2.start;
  5.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. public:-google 1point3acres
  7.     int minMeetingRooms(vector<Interval>& intervals) {
  8.         std::sort(intervals.begin(), intervals.end(), compare);
  9.         std::priority_queue<int, vector<int>, std::greater<int>> endTimeOfRooms;
  10.         for(auto it : intervals){
  11.             if(!endTimeOfRooms.empty() && endTimeOfRooms.top() <= it.start){
  12.                 endTimeOfRooms.pop();
  13.                 endTimeOfRooms.push(it.end);
  14.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.             else . 1point3acres.com/bbs
  16.                 endTimeOfRooms.push(it.end);
  17.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         return endTimeOfRooms.top();
  19.     }
  20. };
复制代码
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-12-10 18:11):. visit 1point3acres.com for more.
我的基本思路就是看每个room最后的结束时间,最先结束的那个room,在结束时,其余别的room一定是被占用的 - 因为按照定义他是最先结束的。所以在这一瞬间,所有的room都在开会。
如果有问题,欢迎指正
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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