一亩三分地论坛

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

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

Facebook第二轮电面面经 刚刚结束 求大米~!

[复制链接] |试试Instant~ |关注本帖
北航小涵 发表于 2015-3-21 03:56:17 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Other

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

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

x
刚刚结束的第二轮facebook电话面试。还没结果呢所以结果就先选的other~求大米~~求offer~~~. from: 1point3acres.com/bbs
居然做了三个题目。。
小哥迟到了5分钟打过来,那五分钟真是内心煎熬啊。。。
真的非常感谢地里朋友,所以赶紧发面经了。

1. flood fill。感谢地里面经:here and here and here
就上面题目的各种变种,题目是有一个矩阵
1代表已经染色,0代表没有染色。
完成一个函数,
输入:矩阵a,整数x, 整数y
输出:
返回一个矩阵,为以(x,y)点(0-based)为开始点的染色结果,将其周围区域染色,直到遇到已经染色的位置或边界为止。
若(x, y)已经染色则直接返回。注意:只能向上下左右四个方向染色。
输入样例:. 1point 3acres 璁哄潧
111111
111001
100110.鏈枃鍘熷垱鑷1point3acres璁哄潧
2
. more info on 1point3acres.com
1
输出样例:
111111
111001
111110

基本就是我在这里楼下贴的程序一样。注意处理边界条件。我用的DFS。代码如下:
  1. public class Solution {
  2.     private row = 0;
  3.     private col = 0;
  4.    
  5.     public void fillBlack(int[][] a, int x, int y) {
  6.         if (a == null || x == null || y == null) {
  7.             return;
  8.         }
  9.         
  10.         row = a.length;
  11.         col = a[0].length;
  12.         dfs(a, x, y);
  13.     }
  14.    
  15.     public void dfs(int[][] a, int i, int j) {
  16.         if (i < 0 || i >= row || j < 0 || j >= col || a[i][j] != 0) {
  17.             return;
  18.         }
  19.         a[i][j] = 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.         dfs(a, i - 1, j);
  21.         dfs(a, i + 1, j);. 1point 3acres 璁哄潧
  22.         dfs(a, i, j + 1);
  23.         dfs(a, i, j - 1);
  24.      
  25.     }
  26.    
  27.    
  28. }
复制代码
2. lintcode原题,merge two sorted array II. 连接请点击这里
我们从后往前走即可。注意如果B数组提前结束,那么A剩下的就是在原地,所以不用再变了~要求in-place
代码如下:
  1. public class Solution {. more info on 1point3acres.com
  2.     public void mergeSortedArray(int[] a, int m, int[] b, int n) {
  3.         if (a == null || b == null) {
  4.             return;
  5.         }
  6.         
  7.         int pos = m + n - 1;
  8.         int i = m - 1;
  9.         int j = n - 1;
  10.         while (i >= 0 && j >=0) {
  11.             if (a[i] >= b[j]) {
  12.                 a[pos] = a[i];
  13.                 i--;
  14.             } else {
  15.                 a[pos] = b[j];
  16.                 j--;
  17.             }
  18.             pos--;
  19.         }
  20.         
  21.         if (i < 0) {
  22.             while (pos >= 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                 a[pos] = b[j];
  24.                 j--;
  25.                 pos--;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.             }
  27.         }
  28.     }     . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29. }  
复制代码
3. 感谢面经~这是二叉树经典题目 BST转换成循环双向链表。leetcode类似题目请点击这里:Flatten Binary Tree to Linked List
其实我在面经贴:这里下面给出了自己的代码了。
具体思路是:
1. 拿出根节点。. From 1point 3acres bbs
2. 递归处理left, 找到左边最后一个节点,并且连接root到这个节点上。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3. 递归处理right, 找到右边最前面的节点,并且连接root到这个节点上。
4. return。

最后还需要处理一下头连接到尾巴的双向循环,补上就行,不贴code了。
  1. public class SolutionConvert {
  2.     public void solve(TreeNode root) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         if (root == null) {
  4.             return;. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         }
  6.         convertToDoubleLinkedList(root);           
  7.     }
  8.    
  9.     public void convertToDoubleLinkedList(TreeNode root) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.         if (root == null) {
  11.             return;
  12.         }
  13.         if (root.left != null) {
  14.             TreeNode left = root.left;
  15.             convertToDoubleLinkedList(left);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.             while (left.right != null) {
  17.                 left = left.right;
  18.             }-google 1point3acres
  19.             left.right = root;
  20.             root.left = left;
  21.         }
  22.         if (root.right != null) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.             TreeNode right = root.right;
  24.             convertToDoubleLinkedList(right);
  25.             while (right.left != null) {
  26.                 right = right.left;
  27.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.             right.left = root;
  29.             root.right = right;
  30.         }
  31.     }
  32.    
  33.     public void test(String[] args) {
  34.         TreeNode a = new TreeNode("10");
  35.         TreeNode b = new TreeNode("12"); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.         TreeNode c = new TreeNode("15");. 鍥磋鎴戜滑@1point 3 acres
  37.         TreeNode d = new TreeNode("25");
  38.         TreeNode e = new TreeNode("30");
  39.         TreeNode f = new TreeNode("36");
  40.         a.left = b;
  41.         a.right = c;
  42.         b.left = d;
  43.         b.right = e;
  44.         c.left = f;
  45.         solve(a);
  46.         while (a.left != null) {
  47.             a = a.left;
  48.         }
  49.         while (a != null) {
  50.             System.out.print(a.val + " ");
  51.             a = a.right;. visit 1point3acres.com for more.
  52.         }      
  53.     }-google 1point3acres
  54. }
复制代码
求赏大米~~求拿offer~~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴







补充内容 (2015-3-22 07:23):
第一轮面经在这里:http://www.1point3acres.com/bbs/thread-122243-1-1.html

补充内容 (2015-3-26 06:13):
最终收到offer,详情点击:http://www.1point3acres.com/bbs/thread-126300-1-1.html

评分

13

查看全部评分

 楼主| 北航小涵 发表于 2015-3-21 04:07:33 | 显示全部楼层
突然发现自己第一题code没有返回值啊。。ORZ。。。希望面试官没有发现。。。。直接在原地改了。。
回复 支持 反对

使用道具 举报

siren01 发表于 2015-3-21 04:08:29 | 显示全部楼层
Good luck,是Seattle的不?
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-21 04:09:01 | 显示全部楼层
siren01 发表于 2015-3-20 15:08. 1point3acres.com/bbs
Good luck,是Seattle的不?

是的 字数字数 求offer。。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-21 04:28:50 | 显示全部楼层
Lz 一面二面之间隔了多少时间啊?
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-21 04:38:09 | 显示全部楼层
seabiscuit119 发表于 2015-3-20 15:28
Lz 一面二面之间隔了多少时间啊?

上上周四 算起来刚好两周零一天吧。。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-21 05:19:58 | 显示全部楼层
北航小涵 发表于 2015-3-21 04:38. 1point 3acres 璁哄潧
上上周四 算起来刚好两周零一天吧。。

感觉f家的电面难度差异好大啊。。有的特别难,有的又是leetcode题目。
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-21 05:26:59 | 显示全部楼层
seabiscuit119 发表于 2015-3-20 16:19
感觉f家的电面难度差异好大啊。。有的特别难,有的又是leetcode题目。

如果默认都没做过的情况下还是,。。。难度差不多的其实。。。
回复 支持 反对

使用道具 举报

zhuol 发表于 2015-3-21 05:58:10 | 显示全部楼层
顶一个!祝onsite+offer
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-3-21 15:55:40 | 显示全部楼层
这个基本上offer了吧,恭喜楼主
回复 支持 反对

使用道具 举报

Tiffanyyny 发表于 2015-3-22 10:36:23 | 显示全部楼层
请问第一题这种题型的时间空间复杂度是多少啊?网上有的说是O(m*n),但我觉得内层循环做DFS的耗时不算吗?
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-22 12:49:53 | 显示全部楼层
Tiffanyyny 发表于 2015-3-21 21:36
请问第一题这种题型的时间空间复杂度是多少啊?网上有的说是O(m*n),但我觉得内层循环做DFS的耗时不算吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是O(m*n)因为最多每个点只遍历一次 整个图就结束了。如果是类似于你要递归进入一个点 从这个点开始要找好多,找多次比如k次,那么 则是O(m*n*4^k).
回复 支持 反对

使用道具 举报

timpark4 发表于 2015-3-23 00:41:02 | 显示全部楼层
lz 是什么时候投的Facebook?  
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-23 01:44:01 | 显示全部楼层
timpark4 发表于 2015-3-22 11:41. 1point3acres.com/bbs
lz 是什么时候投的Facebook?

2月3号 学校招聘会
回复 支持 反对

使用道具 举报

liusicong999 发表于 2015-3-23 23:23:14 | 显示全部楼层

LZ是在加拿大的学校招聘会吗?
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-24 01:43:22 | 显示全部楼层
liusicong999 发表于 2015-3-23 10:23
LZ是在加拿大的学校招聘会吗?

是的 自数字数字数
回复 支持 反对

使用道具 举报

peace 发表于 2015-3-24 06:34:15 | 显示全部楼层
北航小涵 发表于 2015-3-24 01:43
是的 自数字数字数

小涵你电面的时候是一边写代码一边讲思路,还是先讲完思路再闷头写代码啊
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-24 07:24:24 | 显示全部楼层
peace 发表于 2015-3-23 17:34
小涵你电面的时候是一边写代码一边讲思路,还是先讲完思路再闷头写代码啊

先讨论 说清楚 再门头写~因为我无法一心二用。。。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-29 02:59:26 | 显示全部楼层
恭喜lz拿到这样好的offer!! 实力很强! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我也做了一下convert bt to circular list这题,和lz的代码不太一样,对自己没信心,不知lz能帮忙看一下吗?

public class bt_circular_list{. visit 1point3acres.com for more.
        private static TreeNode tail = null;
        public static TreeNode convert(TreeNode root){
                TreeNode head = root;
                helper(root);
                while(head.left != null){
                        head = head.left;
                }. from: 1point3acres.com/bbs
                head.left = tail;.1point3acres缃
                tail.right = head;
                return head;
        }
       
        public static void helper(TreeNode root) {
                if(root == null)
                        return;
                helper(root.left);
                if(tail != null){
. From 1point 3acres bbs                        tail.right = root;
                        root.left = tail;
                }
                tail = root;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                helper(root.right);
        }
}
回复 支持 反对

使用道具 举报

 楼主| 北航小涵 发表于 2015-3-30 09:21:19 | 显示全部楼层
yuxrose 发表于 2015-3-28 13:59. more info on 1point3acres.com
恭喜lz拿到这样好的offer!! 实力很强!
我也做了一下convert bt to circular list这题,和lz的代码不太一 ...

答体看了下貌似 对的 你可以跑一下试试看~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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