一亩三分地论坛

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

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

FB 第二轮面经

[复制链接] |试试Instant~ |关注本帖
lsycody 发表于 2015-3-10 06:10:12 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other

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

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

x
原本上周四的改到了今天,mobile组的白人应该,再次庆幸没碰到阿三……-google 1point3acres
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
先是介绍了自己做的project,我一开始有点紧张,自己都感觉讲的不大清楚…=。=
然后开始做题
1. 给定matrix,只有0和1,求1的连通size,连通只算上下左右,不算对角线。比如:
0 1 0 0 1
1 1 1 0 0
1 0 0 0 1. visit 1point3acres.com for more.
0 0 0 0 1                   返回 5, 1, 2
反正不难,DFS的时候check那个点有没有被访问过就好了。不过过程中有点小问题,reference有点没处理好。后来想改,甚至说了不需要reference了,可以直接返回int值,不需要这么麻烦了。但是面试官说算了,时间不多了,他知道了。
2. 简单题,翻转linklist。

做完题大概过了40分钟。最后问问题聊high了,又问我为什么要来FB。话唠模式开启,讲完之后他说it's inspiring……受宠若惊
挂电话时一共55分钟。.1point3acres缃

总体感觉,面试官还是挺nice的。整个面试过程中,基本都是我自己在说话,自言自语,他稍微附和几句,最后聊的也蛮开心的,感觉像是托福口语高分的节奏。。。

Anyway,求下一轮,应该就是onsite了…求offer……求脱离待业狗身份!!!!
最后祝大家好运!

评分

2

查看全部评分

 楼主| lsycody 发表于 2015-3-28 11:05:38 | 显示全部楼层
sanguine 发表于 2015-3-27 20:32
为什么是矩阵的大小?你每次都需要check旁边的是否为1,然后下次你又两个for循环再继续check这个点,应该 ...

那就是说,一个单元格,最多被周围四个递归check过。
如果一个单元格被访问过了,下次再碰到就不会再递归下去了。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lch04 发表于 2015-3-29 06:19:43 | 显示全部楼层
public ListNode reverse(ListNode head) {
        // write your code here
        if (head == null) {
            return head;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴        return helper(head, null);
    }
    private ListNode helper(ListNode cur, ListNode prev) {
        if (cur == null) {. 1point3acres.com/bbs
            return prev;
        }
        ListNode next = cur.next;. From 1point 3acres bbs
        cur.next = prev;
        return helper(next, cur);
    }
回复 支持 1 反对 0

使用道具 举报

北航小涵 发表于 2015-3-10 09:52:31 | 显示全部楼层
沾喜气!LZ上次面完第一轮多久给的回复》?
回复 支持 反对

使用道具 举报

 楼主| lsycody 发表于 2015-3-10 10:02:44 | 显示全部楼层
北航小涵 发表于 2015-3-9 19:52
沾喜气!LZ上次面完第一轮多久给的回复》?

第一轮…周五面的,周一给的答复
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-10 10:16:43 | 显示全部楼层
lsycody 发表于 2015-3-9 21:02. Waral 鍗氬鏈夋洿澶氭枃绔,
第一轮…周五面的,周一给的答复

我好奇怪啊 上周四面的 现在都没有信儿呢。。。。是不是挂了
回复 支持 反对

使用道具 举报

 楼主| lsycody 发表于 2015-3-10 10:25:26 | 显示全部楼层
北航小涵 发表于 2015-3-9 20:16. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我好奇怪啊 上周四面的 现在都没有信儿呢。。。。是不是挂了

你面的怎么样呢?再等等看咯
我当时一面不大好,感觉还是看RP的,面试官有好有坏
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-10 10:39:39 | 显示全部楼层
lsycody 发表于 2015-3-9 21:25
你面的怎么样呢?再等等看咯
我当时一面不大好,感觉还是看RP的,面试官有好有坏

我感觉还行啊。。。。。。。。。但是这么久会不会很奇怪。。。
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-10 10:40:28 | 显示全部楼层
lsycody 发表于 2015-3-9 21:25
你面的怎么样呢?再等等看咯
我当时一面不大好,感觉还是看RP的,面试官有好有坏

既然看人品的话。。。那么我就静静地。。等吧。
回复 支持 反对

使用道具 举报

sunnyiez 发表于 2015-3-12 00:19:26 | 显示全部楼层
  1. <font face="Verdana">ListNode * reverse (ListNode * prev, ListNode * curr)
  2. {
  3.         if (curr == NULL) return prev;
  4.         ListNode * new_head = reverse (curr, curr->next);
  5.         curr->next = prev;
  6.         return new_head;
  7. }

  8. // usage
  9. // ListNode * new_head = reverse (NULL, head);</font>
复制代码
My implementation on reversing single linked list.
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-3-12 16:40:50 | 显示全部楼层
哎,FB据说要求很高,下周有点面,看了这么多都没信心了
回复 支持 反对

使用道具 举报

Tiffanyyny 发表于 2015-3-22 07:38:52 | 显示全部楼层
请问第一题DFS的时间复杂度是多少呢?
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-3-28 06:56:50 | 显示全部楼层
同问=。=时间复杂度应该是多少==
回复 支持 反对

使用道具 举报

 楼主| lsycody 发表于 2015-3-28 08:22:38 | 显示全部楼层
Tiffanyyny 发表于 2015-3-21 17:38
请问第一题DFS的时间复杂度是多少呢?

诶怎么之前没看见……就是你的矩阵大小
回复 支持 反对

使用道具 举报

 楼主| lsycody 发表于 2015-3-28 08:22:48 | 显示全部楼层
sanguine 发表于 2015-3-27 16:56. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
同问=。=时间复杂度应该是多少==

同上,字数字数字数
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-3-28 10:32:33 | 显示全部楼层
lsycody 发表于 2015-3-27 19:22. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
同上,字数字数字数

为什么是矩阵的大小?你每次都需要check旁边的是否为1,然后下次你又两个for循环再继续check这个点,应该不止O(mn)吧=。=

不太懂DFS和递归的time complexity
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-3-28 11:29:57 | 显示全部楼层
sanguine 发表于 2015-3-28 10:32
.鐣欏璁哄潧-涓浜-涓夊垎鍦为什么是矩阵的大小?你每次都需要check旁边的是否为1,然后下次你又两个for循环再继续check这个点,应该 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
代码:
  1. #include<iostream>. 1point 3acres 璁哄潧
  2. #include<cstdio>
  3. #include<string>
  4. #include<string.h>
  5. #include<cstring>
  6. #include<algorithm>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. using namespace std;
  8. const int maxn = 105;. From 1point 3acres bbs
  9. bool matrix[maxn][maxn];
  10. int m, n;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11. bool visit[maxn][maxn];
  12. const int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};. 1point3acres.com/bbs
  13. int valid(int x,int y){
  14.         return x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] == 1 && visit[x][y] == 0;
  15. }
  16. int dfs(int x,int y){
  17.         for(int i = 0; i < 8; ++i){
  18.                 int tmpx = x + dir[i][0];
  19.                 int tmpy = y + dir[i][1];
  20.                 if(valid(tmpx, tmpy)){
  21.                         visit[tmpx][tmpy] = 1;
  22.                         dfs(tmpx, tmpy);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.                 }
  24.         }. 鍥磋鎴戜滑@1point 3 acres
  25.         return 0;
  26. }
  27. int main(){
  28.         while((scanf("%d%d",&m,&n))!=EOF){
  29.                 if(m == 0){
  30.                         break;. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.                 }
  32.                 int cnt = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  33.                 memset(matrix, 0, sizeof(matrix));. 1point 3acres 璁哄潧
  34.                 memset(visit, 0, sizeof(visit));
  35.                 int i = 0, j = 0;. 1point 3acres 璁哄潧
  36.                 char mark;
  37.                 for(i = 0; i < m; ++i){
  38.                         for(j = 0; j < n; ++j){
  39.                                 cin >> mark;. From 1point 3acres bbs
  40.                                 switch(mark){
  41.                                         case('*'):
  42.                                                 matrix[i][j] = 0;
  43.                                                 break;
  44.                                         case('@'):
  45.                                                 matrix[i][j] = 1;. visit 1point3acres.com for more.
  46.                                                 break;
  47.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  48.                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  49.                 }
  50.                 for(i = 0; i < m; ++i){
  51.                         for(j = 0; j < n; ++j){
  52.                                 if(!visit[i][j] && matrix[i][j] == 1){. more info on 1point3acres.com
  53.                                         ++cnt;
  54.                                         dfs(i, j);
  55.                                 }
  56.                         }. more info on 1point3acres.com
  57.                 }
  58.                 printf("%d\n",cnt);
  59.         }
  60.         return 0;
  61. }       
复制代码
每次dfs之前都要check一下这个点是否被visit过,即每个点最多被visit一次;
每次dfs最多向旁边看8个点,所以复杂度上限是8*m*n,也就是 O(m*n)啦~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sanguine 发表于 2015-3-28 12:39:23 | 显示全部楼层
lsycody 发表于 2015-3-27 22:05
那就是说,一个单元格,最多被周围四个递归check过。
如果一个单元格被访问过了,下次再碰到就不会再递 ...

懂了!!!太感谢!
回复 支持 反对

使用道具 举报

lch04 发表于 2015-3-29 06:08:57 | 显示全部楼层
public static int connected(int[][] matrix, int a, int b) {
        if (a < 0 || a >= row || b < 0 || b >= col || matrix[a][b] != 1) {
            return 0;
        }. From 1point 3acres bbs
        matrix[a][b] = 2;
        return 1 + connected(matrix, a - 1, b) + connected(matrix, a, b - 1)
                + connected(matrix, a + 1, b) + connected(matrix, a, b + 1);
    }
回复 支持 反对

使用道具 举报

haungge0385 发表于 2015-4-9 22:51:39 | 显示全部楼层
minglotus 发表于 2015-3-28 11:29
代码:每次dfs之前都要check一下这个点是否被visit过,即每个点最多被visit一次;-google 1point3acres
每次dfs最多向旁边看8 ...

请问fb面试要自己考虑输入输出的吗?还是像leetcode一样不用管?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 01:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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