【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 7851|回复: 43
收起左侧

Facebook Menlo Part University Day

[复制链接] |试试Instant~
我的人缘0
alfredaria 发表于 2016-10-28 05:53:41 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩

2016(10-12月) 码农类General 硕士 全职@Facebook - 内推 - Onsite  | Pass | fresh grad应届毕业生

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

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

x

University Day前电面,一位国人phd姐姐给了一道LC273。Integer to Words.
一周后收到HR约Onsite的邮件,说干脆把我扔到 10/20 Menlo Park 的 University Day吧。听说只是3轮时心里好开心。  以下Onsite 题目:

第一轮 一年多工作经验的印度小哥,不苟言笑。

1. Find all cells that are furthest to knights: (X is wall, O is space, K is Knight)(multiple knights)
O O O
O X O
K X O
return [(2,2)]
Corner case:
(1). [O], return all O’s
(2). [K X O O] should return all [(0,2), (0,3)] because they are all on the other side
Asked: Why BFS is more efficient than DFS
. From 1point 3acres bbs
2. Task execution with k period cooldown (keep order), all tasks take 1 time period. e.g.
[1,1,2,1] with k = 2, time consumption is 7 (1 _ _ 1 2 _ 1)
Optimize storage, you don't need to store all task numbers.
提议用LinkedHashMap,要说明至少一种implementation 方式,并且每次执行task都检查最早的element,如果执行记录远久直接移除。只有15分钟所以写了pseudo code。

第二轮 一年多工作经验的ABC(非常nice,做完题闲聊了20分钟):

3. Flatten linked list
Struct{
  int val;
  Struct next, child;
}
e.g.
3 -> 4 -> 5
        |
        6 -> 7
        |
        8 -> 9
return 3 -> 4 -> 6 -> 8 -> 9 -> 7 -> 5
. 留学申请论坛-一亩三分地
4. Total hamming distance of all numbers in array. The array contains all 64 bits integers,
   and two integers respectively having 0 and 1 at one digit contributes 1 hamming distance.
   E.g. 11011 : 10011 has Hamming distance 1, and 11111 : 01100 has 3.
   
   Follow up: Do better than O(n^2) brute force.

第三轮 五年多工作经验的国人

5.1. Behavior interview. 没有问why facebook,但问我以前的team project, intern project和分工。.1point3acres网

5.2. Move non-zeros to the left side in array, return the count of non-zero integers, don't care about the rest of the array which are not used, require minimum number of writes. Order of integers does not matter.

[size=14.666666666666666px]e.g.[1,0,2,0,4,0,5,7] -> [1,7,2,5,4,x,x,x] and return 5. # writes is 2.

周三收到HR电话给offer details。

评分

参与人数 5大米 +52 收起 理由
bych0223 + 3 感谢分享!
ShalynChin + 3 恭喜!
knight0clk + 3 感谢分享!
qr719830 + 3 感谢分享!
nunuh89 + 40

查看全部评分


上一篇:GoDaddy新鲜OA
下一篇:来一发 Yelp 电面面筋 10/21
我的人缘0
spiritrhy 发表于 2016-10-29 06:29:40 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
xpli521 发表于 2016-10-28 07:59
同问怎么做better than O(N^2) ? 是要把所有的integer建Trie,然后再比较吗? 这样应该会better than(n^2)  ...

每位0的个数和1的个数相乘 求和
public static int hammingDistanceSum(int[] nums, int k) {
          int len = nums.length;
                int[] countOfOnes = new int[32];//统计每位的1的个数总和. 一亩-三分-地,独家发布
                for (int i = 0; i < len; i++) {
                        for (int j = 0; j < 32; j++) {
                                countOfOnes[j] += (nums >> j) & 1;//64大小的话,这里会挪过了. 1point 3acres 论坛
                        }
                }. 1point3acres
                int sum = 0;
                for (int count: countOfOnes) {
                        sum += count * (len - count);//0的个数 X 1的个数
                }. from: 1point3acres
                return sum;
    }  
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-30 09:11:51 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
whitney94 发表于 2016-10-30 06:11
多谢楼主分享!能问一下楼主第一轮第二题task with k cooldown的那个followup,怎么用linkedhashmap啊,为 ...
-google 1point3acres
这个题时间是O(N) (N为tasks总数)。如果只用一个unordered_map<int,int> lastTime来记录一个task最后一次执行的时间的话那么最差空间就是O(N)。但是随着时间推移,当一个task最后一次执行时间早于currentTime - k的时候就没有必要保存了,因为从currentTime 起反正cool down时间都已经过了,所以其实保存lastTime中最新的k个就足够了。这样空间消耗就从O(N)降到了O(min(N,k))。但是unordered_map是没有顺序概念的,所以在C++中就再配合使用一个list<int> prevTasks来按时间顺序记录最近执行过的k个task ids.注意list是node based container,所以再删除第一个元素时的操作pop_front()是O(1)的,这个很重要,保持整体算法时间还是O(N)的。
我对Java不熟,估计linkedhaskmap在Java中是类似的意思。
  1. int TimeConsumption(vector<int>& tasks, int k) {. 围观我们@1point 3 acres
  2.   if (k <= 0) return tasks.size(); // no cool down needed
  3.   // store info only within last k time stamps
  4.   unordered_map<int,int> lastTime; // task id->last executed time stamp
  5.   list<int> prevTasks; // previous task ids ordered in time
  6.   int curTime = 1; // current time stamp
  7.   
  8.   for (int t : tasks) {. 一亩-三分-地,独家发布
  9.     // remove oldest task if older than curTime - k  
  10.     if (!prevTasks.empty() && lastTime[*prevTasks.begin()] < curTime - k)
  11.     { lastTime.erase(*prevTasks.begin()); prevTasks.pop_front(); }
  12.    
  13.     // t is not executed within last k time stamps
  14.     if (!lastTime.count(t)) {
  15.         lastTime[t] = curTime++;
  16.         prevTasks.push_back(t);.留学论坛-一亩-三分地
  17.     }
  18.     // t is executed within last k time stamps
  19.     else {. 围观我们@1point 3 acres
  20.         lastTime[t] += (k+1);
  21.         curTime = lastTime[t];
  22.     }.1point3acres网
  23.   }
  24.   return curTime;
  25. }
复制代码

补充内容 (2016-10-30 09:20):
Sorry. 以上算法在else case "// t is executed within last k time stamps"时没有将task t从list中移到尾端。我在下面补上正确的算法
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-30 09:42:50 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
更正25层算法:当当前task need cool down时,需要将当前task从list移到尾部,所以需要在unordered_map中有list::iterator的位置。将lastTime改为从task到pair(last time, list::iterator)。
. Waral 博客有更多文章,
  1. int TimeConsumption(vector<int>& tasks, int k) {
  2.   if (k <= 0) return tasks.size(); // no cool down needed
  3.   // store info only within last k time stamps
  4.   // task id->(last executed time stamp, list position)
  5.   unordered_map<int,pair<int,list<int>::iterator>> lastTime;
  6.   list<int> prevTasks; // previous task ids ordered in time . Waral 博客有更多文章,
  7.   int curTime = 0; // current time stamp
  8.   
  9.   for (int t : tasks) {
  10.     curTime++;. 一亩-三分-地,独家发布
  11.    
  12.     // remove oldest task if older than curTime - k  
  13.     if (!prevTasks.empty() && lastTime[*prevTasks.begin()].first < curTime - k).本文原创自1point3acres论坛
  14.     { lastTime.erase(*prevTasks.begin()); prevTasks.pop_front(); }
  15.     . 留学申请论坛-一亩三分地
  16.     // if executed within last k time stamps
  17.     if (lastTime.count(t)) {
  18.       prevTasks.erase(lastTime[t].second);
  19.       curTime = lastTime[t].first + k + 1; // need cool down. Waral 博客有更多文章,
  20.     }
  21.     // make most recently executed task. From 1point 3acres bbs
  22.     prevTasks.push_back(t);
  23.     lastTime[t] = make_pair(curTime, --prevTasks.end());
  24.   }. 1point3acres
  25.   return curTime;
  26. }
复制代码
回复

使用道具 举报

我的人缘0
 楼主| alfredaria 发表于 2016-10-28 07:23:59 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
pawprinter 发表于 2016-10-28 07:08
请问lz有更好的解法嘛,求指导

我当时问能否改原来的matrix,答曰可以,所以就不需要额外空间了吧。我的做法是用两个ArrayList队列维护前后两层的节点。耗尽所有节点时,返回最后一层节点,期间每个合法节点都填成'X'。  但这样做最后就需要测一次如果依然存在'O',就返回这些'O'的集合。

Pseudo code:. 留学申请论坛-一亩三分地
定义ans
维护 q1 q2
向q1加入所有knights节点,将这些节点的值设为'X‘.本文原创自1point3acres论坛
while q1 非空:
    对q1中每个节点n:
       对n的每个合法邻居m(边界内、值为'O'):.1point3acres网
          将m放入q2,并设值为'X’
    if q2为空,ans = q1 跳出while循环
    else q1 = q2.本文原创自1point3acres论坛
if matrix 还有'O'节点,返回全部'O'的节点
else 返回 ans

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
hrl1991 发表于 2016-10-28 06:24:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (69)
 
 
2% (2)  踩
恭喜!楼主什么时候onsite的?有要reference吗?
回复

使用道具 举报

我的人缘0
 楼主| alfredaria 发表于 2016-10-28 06:27:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
hrl1991 发表于 2016-10-28 06:24
恭喜!楼主什么时候onsite的?有要reference吗?

有的,要一个manager 和一个professor,但是周二给的,所以貌似HR不用先特地联系他们再做决定
回复

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-28 06:33:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (73)
 
 
3% (3)  踩
问下lz 第一题是说找最远的么?也就是说如果到不了,距离是INF?
我想法就是开一个board,全部初始化为INF,然后BFS更新距离,最后输出最远的那几个?
求细节

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| alfredaria 发表于 2016-10-28 07:02:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
pawprinter 发表于 2016-10-28 06:33
问下lz 第一题是说找最远的么?也就是说如果到不了,距离是INF?. more info on 1point3acres
我想法就是开一个board,全部初始化为INF ...
. from: 1point3acres
可以这样做
回复

使用道具 举报

我的人缘0
bbsbbstry 发表于 2016-10-28 07:04:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (117)
 
 
7% (10)  踩
第四题直接异或再数1就是constant吧?还是我理解错题了?为什么会涉及O(n^2) ?
回复

使用道具 举报

我的人缘0
hrl1991 发表于 2016-10-28 07:05:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (69)
 
 
2% (2)  踩
alfredaria 发表于 2016-10-28 06:27.1point3acres网
有的,要一个manager 和一个professor,但是周二给的,所以貌似HR不用先特地联系他们再做决定

谢谢回复! 你是用pending offer催的吗? 我也被要了ref 但是一个礼拜过去了都还没消息呢

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-28 07:08:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (73)
 
 
3% (3)  踩

请问lz有更好的解法嘛,求指导
回复

使用道具 举报

我的人缘0
jacksterling 发表于 2016-10-28 07:14:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (702)
 
 
13% (107)  踩
楼主拿offer的速度好快啊!!!!
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-28 07:36:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (347)
 
 
38% (215)  踩
求问第四题如何better than O(N^2) ?
回复

使用道具 举报

我的人缘0
xpli521 发表于 2016-10-28 07:59:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
同问怎么做better than O(N^2) ? 是要把所有的integer建Trie,然后再比较吗? 这样应该会better than(n^2) ..
回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-10-28 09:26:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
xpli521 发表于 2016-10-28 07:59
同问怎么做better than O(N^2) ? 是要把所有的integer建Trie,然后再比较吗? 这样应该会better than(n^2)  ...

hamming distance就是l1-norm,按位做,然后把64位distance加起来就行了
回复

使用道具 举报

我的人缘0
spiritrhy 发表于 2016-10-28 13:58:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
楼主是在职跳槽吗,要manager的ref,我刚工作一年,只有现在的manager。。。无法弄啊
回复

使用道具 举报

我的人缘0
 楼主| alfredaria 发表于 2016-10-29 01:21:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
spiritrhy 发表于 2016-10-28 13:58
楼主是在职跳槽吗,要manager的ref,我刚工作一年,只有现在的manager。。。无法弄啊

我是new grad。。给的是以前实习的manager。
回复

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-29 01:25:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (73)
 
 
3% (3)  踩
alfredaria 发表于 2016-10-28 07:23
我当时问能否改原来的matrix,答曰可以,所以就不需要额外空间了吧。我的做法是用两个ArrayList队列维护 ...

谢谢lz 字数子数组
回复

使用道具 举报

我的人缘0
jfree811 发表于 2016-10-29 08:04:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
alfredaria 发表于 2016-10-28 07:23
我当时问能否改原来的matrix,答曰可以,所以就不需要额外空间了吧。我的做法是用两个ArrayList队列维护 ...

求教楼主一个情况呀
O X O O
O X O O
K X K O
像这个情况的话 应该输出哪些点最远呢? 因为被分成两个部分 (0, 0)点对于(2, 2)的knight距离是无限远。楼主的算法好像对于这个情况会输出 (0, 0) (0,2)(0,3)?
回复

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-29 08:31:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (73)
 
 
3% (3)  踩
jfree811 发表于 2016-10-29 08:04. 牛人云集,一亩三分地
求教楼主一个情况呀
O X O O
O X O O

应该是输出(0, 3)吧,我觉得是输出到任意一个knight的最短距离最大的点
回复

使用道具 举报

我的人缘0
jfree811 发表于 2016-10-29 08:55:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
pawprinter 发表于 2016-10-29 08:31. visit 1point3acres for more.
应该是输出(0, 3)吧,我觉得是输出到任意一个knight的最短距离最大的点
. 牛人云集,一亩三分地
这道题应该是LC叁药企 应该是所有的Knight
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-22 23:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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