一亩三分地论坛

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

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

Facebook新鲜面经!!!

[复制链接] |试试Instant~ |关注本帖
zhenjieruan 发表于 2016-3-2 09:21:18 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 实习@Facebook - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚结束的一面,面试官是个非常nice的印度小哥,infrastructure组的,上来一听他做这个我那个激动啊,因为我喜欢distributed system的东西,于是就说我想去facebook就是因为他们infrastructure牛逼,然后就问项目,最近写了个简单的paxos,就和他扯了扯然后说了个优化(说自己写的。。其实是paper上看的。。。)然后他说cool,optimization makes sense。然后就做题,题目如下,楼主leetcode只刷了70道。。所以第一遍写完了有两个bug,他指出来以后都改好了。然后就第二题,他说不用写代码,说思路就好,follow up是,hashmap会不会有hole(有些col不存在)答不会,又问为什么DFS不行,扯了个理由。。。他说也对但是应该是因为blablabla(没听清。。。),然后就Q&A,问他觉得在Facebook工作如何,isn't that great?他大笑后就blabla说了一堆好的地方,然后就问了个technical的问题,问如果同一个file的copy在不同的datacenter被write他们是怎么merge这个file的,然后他blabla解释了,听了解释觉得我这个问题真是太初级了。。。不应该班门弄斧的。。。。。。最后问他有什么advice给我,他说没有没有,it's cool,就结束了,题目在下面,还有我面试时候写的码(求批判!!!这里先谢过了~)求二面求offer!!!
/*
高频题,hashmap+BFS,没要求写代码. From 1point 3acres bbs
Print a binary tree by columns top to bottom.

       1
    2     3
  4   5,6   7.鐣欏璁哄潧-涓浜-涓夊垎鍦
8   9

8 4 2 9 1 5 6 3 7
*/.鏈枃鍘熷垱鑷1point3acres璁哄潧

void printByCol(Node* root) {
}

/*
第一题
We're given a sorted array of integers: [-3, -1, 0, 1, 2]
We want to generate a sorted array of their squares: [0, 1, 1, 4, 9]
O(n) runtime complexity.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
0
我和他讨论算法的时候写的分析,以便code时候参照
pointer negative -> [-3,-1]. from: 1point3acres.com/bbs
pointer positive -> [1,2]
if positive pointer's value's square is greater than the negative pointer's value: we move
if they are equal, move both pointer

[-1, 2, 3]
[-1,-2,-3]
*/. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.1point3acres缃
vector<int> genSortedSquares(vector<int>& in) {
  int positive = in.size(), negative = in.size() - 1;
  vector<int> result;
  for (int i = 0; i < in.size(); ++i) {
    if (in[i] >= 0) {
      positive = i;
      negative = i-1;
      break;
    }
  }
  while (positive < in.size() && negative >= 0) {.1point3acres缃
    if (positive^2 < negative^2) {
      result.push_back(positive^2);
      positive++;. 1point 3acres 璁哄潧
    } else {
      result.push_back(negative^2);
      negative--;. visit 1point3acres.com for more.
    }
  }
  if (positive < in.size()) {
    for (int i = positive; i < in.size(); ++i) {
      result.psuh_back(positive^2);. 鍥磋鎴戜滑@1point 3 acres
      return result;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }
  } else if (negative > 0) {. from: 1point3acres.com/bbs
    for (int i = negative; i > 0; --i) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
      result.push_back(negative^2);
    }
  }
  return result;. 1point 3acres 璁哄潧
}

各位看官高兴的话给点米呗。还有真心code求打脸!
. 鍥磋鎴戜滑@1point 3 acres

评分

4

查看全部评分

zxl9171 发表于 2016-3-2 14:38:09 | 显示全部楼层
spwahaha 发表于 2016-3-2 10:03
这道题为什么不能用DFS?

因为题目要求是同一列中顺序由level的高低决定,如果dfs则不能保证这一顺序,只能保证左子树排在右子树前边。。。如果没有这个要求,dfs也行。
回复 支持 3 反对 0

使用道具 举报

jasonsfk 发表于 2016-3-3 05:01:48 | 显示全部楼层
第一题 扫一遍可以吗?
  1. public class Solution {
  2.         public int[] square(int[] nums) {
  3.                 if (nums == null || nums.length == 0) return new int[0];. visit 1point3acres.com for more.
  4.                 int left = 0, right = nums.length - 1, index = right;
  5.                 int[] res = new int[nums.length];
  6.                 while (left <= right) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.                         if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                                 nums[index--] = nums[left] * nums[left];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.                                 left++;
  10.                         }else if (Math.abs(nums[left]) < Math.abs(nums[right])) {. 1point3acres.com/bbs
  11.                                 nums[index--] = nums[right] * nums[right];
  12.                                 right--;-google 1point3acres
  13.                         }
  14.                 }
  15.                 return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.         }
  17. }
复制代码

评分

1

查看全部评分

回复 支持 0 反对 1

使用道具 举报

lyburke 发表于 2016-3-3 05:11:59 | 显示全部楼层

不是大神= =就是先声明一个和输入等长的结果array,然后用左右指针比较对应值的绝对值大小,绝对值较大的将其平方放入结果array末尾,就这样一步步从后往前放结果。。。这样不用考虑全正,全负还是有正有负
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-2 09:40:48 | 显示全部楼层
。。。第1题,是vertical level order traversal吧。。。亲
回复 支持 1 反对 0

使用道具 举报

wangmengcathy 发表于 2016-3-20 12:46:27 | 显示全部楼层
spwahaha 发表于 2016-3-3 00:22. visit 1point3acres.com for more.
我也举得可以用,而且应该比BFS好写吧,
但是楼主和面试官不是说BFS有问题还是什么的

用bfs可能是为了保证从上到下的输出顺序吧
回复 支持 1 反对 0

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-2 09:31:27 | 显示全部楼层
哦对了。。这代码跑不起来然后面试官说没关系,意思到了就好
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-2 09:36:42 | 显示全部楼层
第1题 啥意思?????. From 1point 3acres bbs
能给个代码,lz。祝你拿offer
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-2 09:49:31 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-2 09:40
。。。第1题,是vertical level order traversal吧。。。亲
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是啊,特别高频啊!解法难道不是hashmap+BFS吗?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

spwahaha 发表于 2016-3-2 10:03:55 | 显示全部楼层
zhenjieruan 发表于 2016-3-2 09:49
是啊,特别高频啊!解法难道不是hashmap+BFS吗?

这道题为什么不能用DFS?
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-2 10:07:18 | 显示全部楼层
spwahaha 发表于 2016-3-2 10:03
这道题为什么不能用DFS?

我其实也没想明白。。那个小哥的解释我也没听清。。。通话质量不好。。
回复 支持 反对

使用道具 举报

sherry0419 发表于 2016-3-2 10:08:44 | 显示全部楼层
楼主运气太好了都考的原题!肯定过了!
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-2 10:10:39 | 显示全部楼层
sherry0419 发表于 2016-3-2 10:08
楼主运气太好了都考的原题!肯定过了!

第一题其实没见过。。有链接吗?谢谢谢谢
回复 支持 反对

使用道具 举报

lyburke 发表于 2016-3-2 13:04:59 | 显示全部楼层
LZ考的第一题和我面的一样。。。可以写的更简洁一些
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-2 13:16:22 | 显示全部楼层
lyburke 发表于 2016-3-2 13:04. 1point3acres.com/bbs
LZ考的第一题和我面的一样。。。可以写的更简洁一些

嗯嗯,可以指点一下吗?谢谢
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-2 13:18:09 | 显示全部楼层
spwahaha 发表于 2016-3-2 10:03
这道题为什么不能用DFS?
-google 1point3acres
可以用啊。。。dfs。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-2 13:18:42 | 显示全部楼层
lyburke 发表于 2016-3-2 13:04
LZ考的第一题和我面的一样。。。可以写的更简洁一些

大神快指导。。
回复 支持 反对

使用道具 举报

sherry0419 发表于 2016-3-2 22:22:42 | 显示全部楼层
zhenjieruan 发表于 2016-3-2 13:16
嗯嗯,可以指点一下吗?谢谢
.1point3acres缃
用两个指针,从左右两边扫,类似merge sort,结果从后往前加,O(n)一遍就可以解决啦
回复 支持 反对

使用道具 举报

spwahaha 发表于 2016-3-3 00:22:21 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-2 13:18
可以用啊。。。dfs。。

我也举得可以用,而且应该比BFS好写吧,
但是楼主和面试官不是说BFS有问题还是什么的
回复 支持 反对

使用道具 举报

 楼主| zhenjieruan 发表于 2016-3-3 06:22:55 | 显示全部楼层
lyburke 发表于 2016-3-3 05:11
不是大神= =就是先声明一个和输入等长的结果array,然后用左右指针比较对应值的绝对值大小,绝对值较大的 ...

我的bug就是出在全正全负的处理上,其实只要initial value选的smart一点就可以处理了,我问他2pass可不可以他说可以我就直接这么写了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-3 07:45:23 | 显示全部楼层
lyburke 发表于 2016-3-3 05:11
不是大神= =就是先声明一个和输入等长的结果array,然后用左右指针比较对应值的绝对值大小,绝对值较大的 ...

大神,看不懂汉语,能写格code么。 +大米 10
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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