传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

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

facebook 实习面经

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

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

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

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

x
新鲜热乎的面经印度小哥
1. magic number like:
f(n) = f(n-1) + 2*f(n-3). visit 1point3acres.com for more.


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


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

. 鍥磋鎴戜滑@1point 3 acres
没答好,估计挂了。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧


补充内容 (2016-2-23 23:43):
谢谢大家看帖。。。二面已过。

补充内容 (2016-3-4 13:00):
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 | 显示全部楼层
楼主会有好运的!!. more info on 1point3acres.com
能不能问一下 第一题那个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
. Waral 鍗氬鏈夋洿澶氭枃绔,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. 1point 3acres 璁哄潧
哎,估计挂了。FB效率和快,一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n
. 1point3acres.com/bbs
谢谢楼主~! 祝好运~~~
回复 支持 反对

使用道具 举报

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. public int fun(int n, int k) {. 鍥磋鎴戜滑@1point 3 acres
  7.    return f(n - 1) + 2 * f(n-k);
  8. }

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

使用道具 举报

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

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

使用道具 举报

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

line 14 is 2 * f(n - k). From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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效率和快,一般过了当天就说了。。。. From 1point 3acres bbs
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个就行了吧  
当你选出来第k个的时候 比k小已经都在它前面了
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-23 02:23:29 | 显示全部楼层
Jester_Z 发表于 2016-2-23 02:00
quick select的话 只用调用一次 选出来第k个就行了吧  . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
当你选出来第k个的时候 比k小已经都在它前面了

嗯,如果顺序不重要的话是这样的,如果需要明确的指明closest,second closest... kth closest,还是需要k次select
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-2-23 04:25:46 | 显示全部楼层
iwofr 发表于 2016-2-22 11:23
嗯,如果顺序不重要的话是这样的,如果需要明确的指明closest,second closest... kth closest,还是需要 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
给这k个再排一次不就行了klogk
回复 支持 反对

使用道具 举报

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

使用道具 举报

头像被屏蔽
wk93210 发表于 2016-3-7 06:06:35 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
wk93210 发表于 2016-3-7 06:06:50 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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 | 显示全部楼层
第二题
  1. public class Solution {
  2.   int dist(Point p1, Point p2) {
  3.     int dx = p1.x - p2.x;
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.     int targetdist = dist(pivot, target);. 1point3acres.com/bbs
  10.     while (start < end) {
  11.       while (start < end && dist(arr[start], target) < targetdist) {
  12.         start++;. from: 1point3acres.com/bbs
  13.       }
  14.       arr[end] = arr[start]; // into end
  15.       while (start < end && dist(arr[end], target) > targetdist) {
  16.         end--;. 鍥磋鎴戜滑@1point 3 acres
  17.       }
  18.       arr[start] = arr[end]; // into start, end empty
  19.     }
  20.     arr[end] = pivot; // into end. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.     return end;
  22.   }
  23. . 1point 3acres 璁哄潧
  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);
  30.       if (mid < k) {
  31.         low = mid + 1;
  32.       } else if (mid > k) {
  33.         high = mid - 1;
  34.       }
  35.     } while (mid != k);
  36.     return Arrays.copyOfRange(arr, 0, k);
  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))
  42.       System.out.println(p);
  43.   }
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-26 21:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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