推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

脸书面经

[复制链接] |试试Instant~ |关注本帖
gbwta 发表于 2017-7-31 00:32:05 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
一共三轮
第一轮: 第一题给两个排好序的没重复array要求返回两个array中共有的element。followup是有重复怎么做。前面的都用的两个指针的方法时间复杂度是o(n),面试官说有没有比这个更优化的做法,我只是简单说说用二分法,两个array都做二分,面试官说按照这个思路想对的但是没有让继续说思路就换下一题了。第二题是把一个树转换成双向的list,面经题。
第二轮:一老头,不做题也不问简历,纯behavioral。第一个问题是你每天的动力是什么,他特意说是技术方面的动力。然后问了最喜欢的课是什么,最不喜欢的课是什么,讲一个和队友有冲突的故事,讲一个和队友配合很好的故事,最喜欢的教授是谁,最不喜欢的教授是谁。
第三轮: 就一道题,设计一个数据结构实现get(key), put(key, value), delete(key)和getLast()来存放k-v对。这个getLast返回的是上一次操作的k-v对,但是删除的操作不算,因为删除的k-v已经不在数据结构里了。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

mchzh 发表于 2017-7-31 01:04:25 | 显示全部楼层
楼主没有系统设计?
回复 支持 反对

使用道具 举报

sterne 发表于 2017-7-31 02:42:24 | 显示全部楼层
同好奇楼主为什么只有三轮 而且没有系统设计。第一题树转双向list 是可以用一个新的ListNode还是必须在原来的TreeNode上进行转换?第三题应该用Map<K, V> + Stack<K> 就行了吧。 第二轮最难
回复 支持 反对

使用道具 举报

vlpckznet 发表于 2017-7-31 02:53:27 | 显示全部楼层
想问下楼主是明年春季毕业吗?
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-7-31 02:56:19 | 显示全部楼层
这是 onsite 么,面之前有没有提design ?
回复 支持 反对

使用道具 举报

熟狗脸 发表于 2017-7-31 03:20:02 来自手机 | 显示全部楼层
这经历很奇葩
回复 支持 反对

使用道具 举报

jingshihao 发表于 2017-7-31 03:30:40 | 显示全部楼层
第三轮是LRU的变形吗?
回复 支持 反对

使用道具 举报

jingshihao 发表于 2017-7-31 03:30:24 | 显示全部楼层
第三轮是LRU的变形吗?
回复 支持 反对

使用道具 举报

jingshihao 发表于 2017-7-31 03:32:01 | 显示全部楼层
第三轮是LRU的变形吗?
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-31 09:07:08 | 显示全部楼层
如果我不停的call getLast会发生什么?返回同一个k-v对,还是按照操作历史,依次返回?
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:01:16 | 显示全部楼层
forteller 发表于 2017-7-31 09:07
如果我不停的call getLast会发生什么?返回同一个k-v对,还是按照操作历史,依次返回?

返回同一个
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:01:46 | 显示全部楼层
mchzh 发表于 2017-7-31 01:04
楼主没有系统设计?

没有,是new grad
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:02:23 | 显示全部楼层
sterne 发表于 2017-7-31 02:42
同好奇楼主为什么只有三轮 而且没有系统设计。第一题树转双向list 是可以用一个新的ListNode还是必须在原来 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
原来的树转换就好
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:02:53 | 显示全部楼层
jingshihao 发表于 2017-7-31 03:30. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第三轮是LRU的变形吗?

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷很像,可以这样说
回复 支持 反对

使用道具 举报

胤小宣 发表于 2017-7-31 13:11:38 | 显示全部楼层
第一题两个一起二分的思路楼主能稍微讲讲吗
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-7-31 13:18:26 | 显示全部楼层
gbwta 发表于 2017-7-31 13:01 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
没有,是new grad

fb很少发new grad,楼主怎么拿到new grad机会的
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:24:49 | 显示全部楼层
胤小宣 发表于 2017-7-31 13:11
第一题两个一起二分的思路楼主能稍微讲讲吗

面试官要求比o(n)复杂度还好我只能说用二分,至于具体我感觉应该比较麻烦吧,看有没有大神给解答一下
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:25:18 | 显示全部楼层
mchzh 发表于 2017-7-31 13:18. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
fb很少发new grad,楼主怎么拿到new grad机会的

内推时机赶巧有坑吧
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-7-31 13:40:34 | 显示全部楼层
gbwta 发表于 2017-7-31 13:25
内推时机赶巧有坑吧

运气不错,onsite的behavior question这轮楼主怎么准备的?
回复 支持 反对

使用道具 举报

chris612ku 发表于 2017-7-31 17:46:31 | 显示全部楼层
第一题followup的二分思维应该是下面这个code的概念吧?(大致上写了一下,欢迎批评指教)
最坏的情况还是O(nums1.size()+nums2.size()), e.g nums1=[1,2,3,4,5,6,7], nums2=[1,2,3,4,5,6,7], 还是两个都要traverse完
最好的情况可以是O(log(nums1.size()) or O(log(nums2.size()) => 看数组的分配, e.g nums1=[1,1,1,1,1,1], nums2=[1,2,3,4,5]
.1point3acres缃
vector<int> find_duplicate(vector<int> nums1, vector<int> nums2){
   
    int len1 = nums1.size(), len2 = nums2.size();
    if(len1 == 0 || len2 == 0) // sanity check
        return {};
   
    vector<int> output; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    int left1 = 0, left2 = 0, right1 = len1-1, right2 = len2-1;
   
    while(left1 <= right1 && left2 <= right2){
        if(nums1[left1] == nums2[left2]){
            output.push_back(nums1[left1]);
            left1 = find_next(nums1,left1);
            left2 = find_next(nums2,left2);. more info on 1point3acres.com
        }else if(nums1[left1] < nums2[left2]){
            left1 = find_next(nums1,left1);. 1point 3acres 璁哄潧
        }else{
            left2 = find_next(nums2,left2);
        }
    }
   
    return output;. 1point 3acres 璁哄潧
    . visit 1point3acres.com for more.
}

int find_next(vector<int> nums, int left){
. more info on 1point3acres.com   
-google 1point3acres    int right = 1;. 1point3acres.com/bbs
    while(left+right < nums.size() && nums[left+right] == nums[left]){
        right *= 2;
    }
   
    right = left+right;
    if(right >= nums.size()){
        if(nums[left] == nums[nums.size()-1]){
            return nums.size();
        }else{
            right = nums.size()-1;
        }
    }
   
    int mid;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴    while(left < right){
        mid = left + (right-left)/2 + 1;
        if(nums[left] == nums[mid]){. Waral 鍗氬鏈夋洿澶氭枃绔,
            left = mid;
        }else{
            right = mid-1;. From 1point 3acres bbs
        }
    }
   
    return left+1;
}

补充内容 (2017-7-31 17:48):
我想这题的Runtime应该还是要回答O(nums1.size()+nums2.size()),只是这样做Binary Search可以多少优化一点
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 23:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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