一亩三分地论坛

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

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

facebook 实习面经

[复制链接] |试试Instant~ |关注本帖
byq 发表于 2016-2-20 06:29:08 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
新鲜热乎的面经印度小哥
1. magic number like:
f(n) = f(n-1) + 2*f(n-3)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

follow up
f(n, k) = f(n - 1) + 2 * f(n - k)-google 1point3acres


2. K closest points to a given point (x, y). N is in millions and K is few hundreds.


没答好,估计挂了。。

. 1point 3acres 璁哄潧

补充内容 (2016-2-23 23:43):
谢谢大家看帖。。。二面已过。. from: 1point3acres.com/bbs

补充内容 (2016-3-4 13:00):. more info on 1point3acres.com
Phd 第三轮team match 重在交流,ML的组几乎都会问和组内项目相关的design问题,楼主有交流障碍,感觉不是很好,大家好好准备,轻松聊天就好。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zhihaosun 发表于 2016-8-4 11:21:23 | 显示全部楼层
第一题用dp还是不难,可以用rolling array达到O(k) 空间,第二题开一个size为k的max priorityQueue , 遍历所有点,先装pq,满了后,如果新的距离小于pq中最大距离,就pop掉装新的
回复 支持 1 反对 1

使用道具 举报

Jester_Z 发表于 2016-2-20 07:49:01 | 显示全部楼层
楼主会有好运的!!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
能不能问一下 第一题那个f(n,k)是什么意思 最后要求的是什么?

还有第二题n特别大的时候 感觉不管是heap还是quickselect 都需要遍历整个N 有什么好的思路吗~.鐣欏璁哄潧-涓浜-涓夊垎鍦

今天大米加完了=   =   明天补上
回复 支持 反对

使用道具 举报

 楼主| byq 发表于 2016-2-20 10:28:50 | 显示全部楼层
哎,估计挂了。FB效率和快,一般过了当天就说了。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n <=0) f(n) = 1
2. quick select做就行, 但是我时间不够,没有写完代码。。。。。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


补充内容 (2016-2-20 10:29):
返回f(n, k )的值,比如 f(100, 10)
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-21 00:57:05 | 显示全部楼层
byq 发表于 2016-2-20 10:28
哎,估计挂了。FB效率和快,一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n

谢谢楼主~! 祝好运~~~
回复 支持 反对

使用道具 举报

jasonsfk 发表于 2016-2-21 05:26:19 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

jasonsfk 发表于 2016-2-21 05:31:40 | 显示全部楼层
LZ 第一题是这个意思吗?
  1. public int f(int n) {
  2.    if (n <= 0) return 1;
  3.    return f(n-1) + 2*f(n-3);
  4. }

  5. Follow up:
  6. . 1point3acres.com/bbs
  7. public int fun(int n, int k) {
  8.    return f(n - 1) + 2 * f(n-k);
  9. }

  10. private int f(int n) {
  11.    if (n <= 0) return 1;
  12.    return f(n-1) + 2*f(n-3);
  13. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| byq 发表于 2016-2-22 23:42:47 | 显示全部楼层
jasonsfk 发表于 2016-2-21 05:26
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点 ...

论坛好神奇。。。
回复 支持 反对

使用道具 举报

 楼主| byq 发表于 2016-2-22 23:45:21 | 显示全部楼层
jasonsfk 发表于 2016-2-21 05:31.1point3acres缃
LZ 第一题是这个意思吗?

line 14 is 2 * f(n - k)

补充内容 (2016-2-22 23:50):
我改错了,你的follow up 写的不太对, 1. 斐波那契数列不是和前两个相关么,2.magic number是和前一个和前三个相关,3followup是与前一个和前k个相关,空间复杂度分别O(1), O(1),O(k), 时间复杂度O(n)
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-23 00:19:11 | 显示全部楼层
byq 发表于 2016-2-20 10:28
哎,估计挂了。FB效率和快,一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n

2. quick select is O(n), k quick select is O(kn). quick sort is nlogn.
when n is a million and k is a 100, O(kn) = 100n and nlogn is 20n. quick sort is better.
Can make the change to quick select by select the Kth number first and recursively select the rest numbers in the left partitioned array but the code needs to be modified.
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-23 02:00:48 | 显示全部楼层
iwofr 发表于 2016-2-23 00:19
2. quick select is O(n), k quick select is O(kn). quick sort is nlogn.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
when n is a million and k  ...

quick select的话 只用调用一次 选出来第k个就行了吧  . from: 1point3acres.com/bbs
当你选出来第k个的时候 比k小已经都在它前面了
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-23 02:23:29 | 显示全部楼层
Jester_Z 发表于 2016-2-23 02:00
quick select的话 只用调用一次 选出来第k个就行了吧  
当你选出来第k个的时候 比k小已经都在它前面了
.1point3acres缃
嗯,如果顺序不重要的话是这样的,如果需要明确的指明closest,second closest... kth closest,还是需要k次select
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-2-23 04:25:46 | 显示全部楼层
iwofr 发表于 2016-2-22 11:23. From 1point 3acres bbs
嗯,如果顺序不重要的话是这样的,如果需要明确的指明closest,second closest... kth closest,还是需要 ...

给这k个再排一次不就行了klogk
回复 支持 反对

使用道具 举报

flyflyfly 发表于 2016-3-7 03:33:50 | 显示全部楼层
LZ, team match有结果了吗?
回复 支持 反对

使用道具 举报

wk93210 发表于 2016-3-7 06:06:35 | 显示全部楼层
AndrewFish 发表于 2016-2-23 04:25
给这k个再排一次不就行了klogk
. visit 1point3acres.com for more.
选k次不也是klogk,不都一样么。。。
回复 支持 反对

使用道具 举报

wk93210 发表于 2016-3-7 06:06:50 | 显示全部楼层
AndrewFish 发表于 2016-2-23 04:25
给这k个再排一次不就行了klogk
.鐣欏璁哄潧-涓浜-涓夊垎鍦
选k次不也是klogk,不都一样么。。。
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-3-7 08:16:57 | 显示全部楼层
wk93210 发表于 2016-3-6 15:06
选k次不也是klogk,不都一样么。。。

quick select 是kn
回复 支持 反对

使用道具 举报

wk93210 发表于 2016-3-7 14:05:56 | 显示全部楼层
AndrewFish 发表于 2016-3-7 08:16. 鍥磋鎴戜滑@1point 3 acres
quick select 是kn
.鐣欏璁哄潧-涓浜-涓夊垎鍦
- -下午脑子浆糊了。。。又犯傻了。。。
回复 支持 反对

使用道具 举报

 楼主| byq 发表于 2016-3-9 04:45:33 | 显示全部楼层
wk93210 发表于 2016-3-7 14:05
- -下午脑子浆糊了。。。又犯傻了。。。

是指面试么?没关系的,不要紧张,虽然我很紧张面试的时候。。。
回复 支持 反对

使用道具 举报

honeyBear142857 发表于 2016-3-22 02:47:09 | 显示全部楼层
请问楼主team match interview之后多久拿到offer的? team match interview 有没有问 phd期间相关的project?
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-12 16:43:40 | 显示全部楼层
第二题. From 1point 3acres bbs
  1. public class Solution {
  2.   int dist(Point p1, Point p2) {.1point3acres缃
  3.     int dx = p1.x - p2.x;. from: 1point3acres.com/bbs
  4.     int dy = p1.y - p2.y;
  5.     return dx * dx + dy * dy;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.   }

  7.   int qs(Point[] arr, Point target, int start, int end) {
  8.     Point pivot = arr[end]; // end out. 1point 3acres 璁哄潧
  9.     int targetdist = dist(pivot, target);
  10.     while (start < end) {
  11.       while (start < end && dist(arr[start], target) < targetdist) {. From 1point 3acres bbs
  12.         start++;
  13.       }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.       arr[end] = arr[start]; // into end
  15.       while (start < end && dist(arr[end], target) > targetdist) {
  16.         end--;
  17.       }
  18.       arr[start] = arr[end]; // into start, end empty
  19.     }
  20.     arr[end] = pivot; // into end
  21.     return end;
  22.   }
  23. .1point3acres缃
  24.   public Point[] kn(Point[] arr, Point target, int k) {
  25.     int mid = -1;
  26.     int low = 0;
  27.     int high = arr.length - 1;
  28.     do {
  29.       mid = qs(arr, target, low, high);.1point3acres缃
  30.       if (mid < k) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  31.         low = mid + 1;
  32.       } else if (mid > k) {. 鍥磋鎴戜滑@1point 3 acres
  33.         high = mid - 1;
  34.       }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.     } while (mid != k);
  36.     return Arrays.copyOfRange(arr, 0, k);-google 1point3acres
  37.   }

  38.   public static void main(String[] args) {
  39.     Solution s = new Solution();
  40.     for (Point p : s.kn(new Point[] {new Point(0, 0), new Point(1, 0), new Point(0, 1),
  41.         new Point(0, 2), new Point(2, 0), new Point(1, 2), new Point(2, 1)}, new Point(3, 0), 5)). more info on 1point3acres.com
  42.       System.out.println(p);
  43.   }
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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