亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2070|回复: 24
收起左侧

脸书面经

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

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

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

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

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.1point3acres缃
楼主没有系统设计?
. From 1point 3acres bbs
没有,是new grad
回复 支持 反对

使用道具 举报

 楼主| gbwta 发表于 2017-7-31 13:02:23 | 显示全部楼层
sterne 发表于 2017-7-31 02:42.1point3acres缃
同好奇楼主为什么只有三轮 而且没有系统设计。第一题树转双向list 是可以用一个新的ListNode还是必须在原来 ...

原来的树转换就好
回复 支持 反对

使用道具 举报

 楼主| 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]

vector<int> find_duplicate(vector<int> nums1, vector<int> nums2){. visit 1point3acres.com for more.
   
    int len1 = nums1.size(), len2 = nums2.size();
    if(len1 == 0 || len2 == 0) // sanity check. 鍥磋鎴戜滑@1point 3 acres
        return {};. From 1point 3acres bbs
   
    vector<int> output;
    int left1 = 0, left2 = 0, right1 = len1-1, right2 = len2-1;
   
    while(left1 <= right1 && left2 <= right2){
-google 1point3acres        if(nums1[left1] == nums2[left2]){
            output.push_back(nums1[left1]);
            left1 = find_next(nums1,left1);
            left2 = find_next(nums2,left2);
        }else if(nums1[left1] < nums2[left2]){
            left1 = find_next(nums1,left1);
        }else{. 鍥磋鎴戜滑@1point 3 acres
            left2 = find_next(nums2,left2);
        }
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   
    return output;
   
}

int find_next(vector<int> nums, int left){-google 1point3acres
   
. 1point 3acres 璁哄潧    int right = 1;
    while(left+right < nums.size() && nums[left+right] == nums[left]){
        right *= 2;
    }-google 1point3acres
   
    right = left+right;. visit 1point3acres.com for more.
    if(right >= nums.size()){
.1point3acres缃        if(nums[left] == nums[nums.size()-1]){
            return nums.size();.1point3acres缃
        }else{
            right = nums.size()-1;
        }
    }
    -google 1point3acres
    int mid;
    while(left < right){
        mid = left + (right-left)/2 + 1;
        if(nums[left] == nums[mid]){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            left = mid;
        }else{. from: 1point3acres.com/bbs
            right = mid-1;
        }
    }
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    return left+1;
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2017-7-31 17:48):
我想这题的Runtime应该还是要回答O(nums1.size()+nums2.size()),只是这样做Binary Search可以多少优化一点
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-19 17:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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