一亩三分地论坛

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

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

Facebook实习面经

[复制链接] |试试Instant~ |关注本帖
yixianpig 发表于 2016-2-28 10:37:14 | 显示全部楼层 |阅读模式

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

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

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

x
拿到offer,回馈地里~

1.20内推,约得2.11第一次电面
第一次电面的题目之前在面经里看过,就是那个task schedual
给了一串task,不同的task可能属于不同type。这些task要放到CPU里运行,运行同一种type是要考虑一个冷却时间。
举个栗子:thread是1,2,3,1不能改顺序, 冷却时间3,运行起来就是1, 2, 3, _, 1时间就是5.要返回总运行时间5
我是用hashmap,key是该task的数字,value是上次运行这个task的时间。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
follow up是如果可以改变顺序,最少要运行多少时间
小哥超级好!!!一直嘿嘿嘿的...


面完两个小时HR就回信让我约下次面试的时间,真的是FB的HR,效率名不虚传
我提供了未来两周的时间,结果HR给了我个12天后...我欲哭无泪,因为担心没坑了
所以给HR回了个邮件想商量电面时间能不能提早,HR给我秒回(效率啊!)说没事没事,你好好表现就行~
. From 1point 3acres bbs

第二次电面是2.23
不知道是不是因为看我简历上有个recommendation system?问了个关于推荐好友的
有个函数getFriendList(int id)可以调用,返回的是List<Integer>,是id这个用户的所有好友的id
问如何给用户推荐10个好友?. 1point3acres.com/bbs
我又用了hash系列产品,返回并记录这个用户所有好友的好友,记录时排除已经是这个用户的好友的那些结果,返回top10
这题我错了一个地方,忘记排除用户自己...!面试小哥还循循善诱,到他自己在那儿乐个不停,我都急死了没想出来这个bug  T.T  
另外就是小哥问我hashmap咋对value排序呢,我说做个新的comparator用来比value的值?或者用heap?他问那big O是多少?. 1point 3acres 璁哄潧
然后他要求用O(n)的time complexity做排序,刚开始我没想出来,他换话题说我上面写那个bug去了。说完bug又来追究这个问题. Waral 鍗氬鏈夋洿澶氭枃绔,
我突然想到priority queue可以,小哥特别满意的放过我了...

这时候还不到30分钟,他说时间多再来一题?我说行呀~我能说不行吗
他就开始自言自语hm...hm...this one? 我说ok!(其实我根本没看到题目...)他又自言自语hm...no...我=.=|||
题目很简单,print a singly linked list reversely但是我没听懂(是三哥),以为是reverse a singly linked list
我就说很简单啊,正要写,小哥就说等等!time complexity是什么?我说O(n) 啊
写一半他说我不想让你改变它们的指针,然后我就晕了...我说那要不我two pointers调换头尾的值?这样一直调换到中间. 1point 3acres 璁哄潧
他说我不想让你修改linked list,我就彻底晕了
然后问清楚原来是print就行,用recursion就一下写好了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
小哥说有个问题,如果很多人都在操作这个list,会有什么问题?我说concurrency, list中间加入有null值
就concurrency聊了一些,但是好像小哥不是很满意这个答案
然后他又说如果这是个很长的list?我说recursion占用stack的空间
他说那怎么办呢?我说 by installment?然后他终于放过我了...
-google 1point3acres

这时候都45分钟了,就让我提问题,我提了个,他又让我提一个问题,我看这都50分钟了,不是都准点挂电话吗?但是他说没事,我就又问了个. visit 1point3acres.com for more.
小哥原来在微软做过6年,然后来fb2年了


面完第三天中午收到HR的邮件intern offer~

评分

4

查看全部评分

本帖被以下淘专辑推荐:

DJ963 发表于 2016-2-28 11:08:41 | 显示全部楼层
首先恭喜楼主啦,想问楼主第一题follow up是如果可以改变顺序,最少要运行多少时间怎么做啊
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-2-28 11:37:40 | 显示全部楼层
DJ963 发表于 2016-2-28 11:08
首先恭喜楼主啦,想问楼主第一题follow up是如果可以改变顺序,最少要运行多少时间怎么做啊

找到出现最多次的task是解题关键~
回复 支持 反对

使用道具 举报

DJ963 发表于 2016-2-28 11:41:57 | 显示全部楼层
yixianpig 发表于 2016-2-28 11:37
找到出现最多次的task是解题关键~

我也是这么想的,把所有的task根据频率排序然后怎么弄啊
回复 支持 反对

使用道具 举报

sherry0419 发表于 2016-2-29 09:22:32 | 显示全部楼层
求问LZ当时说的concurrency和list中间有null的意思是?以及by installment指的是?
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-2-29 11:35:47 | 显示全部楼层
和楼上同问~
concurrency和list中间有null的意思是?
by installment指的是?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

beer 发表于 2016-2-29 11:54:04 | 显示全部楼层
楼主,priority queue怎么做到O(n)呢?感觉应该是O(nlogn)啊
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-2-29 22:58:25 | 显示全部楼层
DJ963 发表于 2016-2-28 11:41
我也是这么想的,把所有的task根据频率排序然后怎么弄啊

不需要管排序,只输出所需时间就行~
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-2-29 23:00:59 | 显示全部楼层
sherry0419 发表于 2016-2-29 09:22
求问LZ当时说的concurrency和list中间有null的意思是?以及by installment指的是?

concurrency和list中间有null都不用管...不是面试官想要的答案,我想歪了~by installment就是说一段一段的走recursion,比如先走最后100个list node的recursion并打印,然后在倒数第200至倒数第101个这样。不要一次走到底。你有想到更好的办法不?求分享~
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-2-29 23:13:02 | 显示全部楼层
beer 发表于 2016-2-29 11:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主,priority queue怎么做到O(n)呢?感觉应该是O(nlogn)啊

查了下API,说的是Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size)。wikipedia说priorityqueue如果是用heap建的就是logn,如果是binary tree就是nlogn。你觉得有什么好办法可以O(n)嘛?求分享~~
回复 支持 反对

使用道具 举报

sherry0419 发表于 2016-2-29 23:45:57 | 显示全部楼层
yixianpig 发表于 2016-2-29 23:00
concurrency和list中间有null都不用管...不是面试官想要的答案,我想歪了~by installment就是说一段一段 ...

我觉得很多人在操作这个题说不定是问synchronization和进程锁?

LZ的第一题如果可以改变顺序是怎么做的啊?
回复 支持 反对

使用道具 举报

sherry0419 发表于 2016-2-29 23:46:04 | 显示全部楼层
yixianpig 发表于 2016-2-29 23:00. Waral 鍗氬鏈夋洿澶氭枃绔,
concurrency和list中间有null都不用管...不是面试官想要的答案,我想歪了~by installment就是说一段一段 ...

我觉得很多人在操作这个题说不定是问synchronization和进程锁?

LZ的第一题如果可以改变顺序是怎么做的啊?
回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-1 00:15:50 | 显示全部楼层
sherry0419 发表于 2016-2-29 23:46
我觉得很多人在操作这个题说不定是问synchronization和进程锁?

LZ的第一题如果可以改变顺序是怎么做 ...
-google 1point3acres
涨姿势!我当时说concurrency想的就是synchronization这个思路T.T,但是没说出这个词还有进程锁。我也不确定他是不是要问这个,因为他问了下what do you mean by concurrency,我就说多人操作的话不安全。他就没接下去问了,就说如果这是一个很长的list啥的。我个人觉得是不是看考官引导的方向?
. 1point3acres.com/bbs
第一题不用输出顺序的,就问了下所需时间哈~我想如果要输出顺序应该也不是很难吧?主要是把每种task按照出现次数排序一下,然后一个一个放,该放空位(冷却)就放空位,就好?
回复 支持 反对

使用道具 举报

vivian88 发表于 2016-3-1 03:56:42 | 显示全部楼层
恭喜楼主~谁能找到第一题原来的面经的链接呢?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-1 17:49:52 | 显示全部楼层
lz能写下第1题么? 非常感谢。
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-3-2 02:24:33 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-1 17:49
lz能写下第1题么? 非常感谢。

.鏈枃鍘熷垱鑷1point3acres璁哄潧我写了一下。。可以参考一下。。

/**. more info on 1point3acres.com
     * Use the map to store the next position
     * */
    //O(n) O(n)
    public int taskSchedule(int[] nums, int interval) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ret = 0;. more info on 1point3acres.com

        //the value is the next position where this task can be implemented
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums) || map.get(nums) <= ret) {
                ret++;
            } else {
                ret = map.get(nums);
            }
            map.put(nums, ret + interval + 1);. visit 1point3acres.com for more.
        }
        return ret;
    }
. From 1point 3acres bbs
    /** 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
     * Follow up:
     * Find the task that appears for the most time
     * Use a map to count the number of the times the task appears  then get the maximum count
     * the result is decided by the maximum count and the number of tasks with maximum count
     *
     * two conditions:
     * 1.  5 4 _ _ _ 5 4 _ _ _ 5 4 _ _ _ 5 4  the rest tasks cannot fill the empty slots
     *     5 4 3 2 _ 5 4 3 2 _ 5 4 _ _ _ 5 4
     *     the answer is (maxCount - 1) * (interval + 1) + CountOfMax
     * 1. 5 4 _ _ _ 5 4 _ _ _ 5 4 _ _ _ 5 4  the rest tasks cannot fill the empty slots
     *    5 4 3 2 1 6 5 4 3 2 1 6 5 4 6 _ _ 5 4
     *    the answer is the length of the nums
     *    the task which does not have max count first fills the empty slots and then just insert any valid place. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
     * */. 1point3acres.com/bbs

    //O(n) O(n)
    public int taskScheduleUnorder(int[] nums, int interval) {
        if (nums == null || nums.length == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
            return 0;
        }
        int max = 0;
        int countOfMax = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int task : nums) {
            map.put(task, map.containsKey(task) ? map.get(task) + 1 : 1);
            if (max == map.get(task)) {
                countOfMax++;
            } else if (max < map.get(task)) {
                max = Math.max(max, map.get(task));. more info on 1point3acres.com
                countOfMax = 1;
            }
        }


        return Math.max(nums.length, (max - 1) * (interval + 1) + countOfMax);. 鍥磋鎴戜滑@1point 3 acres
    }

评分

3

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-2 02:26:19 | 显示全部楼层
woshixuyoudan 发表于 2016-3-2 02:24
我写了一下。。可以参考一下。。

/**

和我想的差不多,你的follow up不错,我也是贪心做的,他们说,还有用priorityqueue能减time complexity???我没找到解法啊
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-3-2 04:48:46 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-2 02:26
和我想的差不多,你的follow up不错,我也是贪心做的,他们说,还有用priorityqueue能减time complexity? ...

我觉得不会吧..  priorityqueue的search什么的都是O(nlogn)     上面的解法是O(n)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| yixianpig 发表于 2016-3-2 05:03:30 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-2 02:26. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
和我想的差不多,你的follow up不错,我也是贪心做的,他们说,还有用priorityqueue能减time complexity? ...

很好奇pq怎么实现优化,我没想出来...
回复 支持 反对

使用道具 举报

BrilliantBean 发表于 2016-3-4 00:57:13 | 显示全部楼层
woshixuyoudan 发表于 2016-3-2 02:24
我写了一下。。可以参考一下。。

/**

第二问是不是有点儿问题呢,因为你举的例子的话
1. 5 4 _ _ _ 5 4 _ _ _ 5 4 _ _ _ 5 4  the rest tasks cannot fill the empty slots
*    5 4 3 2 1 6 5 4 3 2 1 6 5 4 6 _ _ 5 4 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这结果不应该是19吗,怎么会是17呢,
求楼主解答
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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