一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 39749|回复: 73
收起左侧

地里2016年度所有Facebook面试题总结

    [复制链接] |试试Instant~ |关注本帖
qesss 发表于 2016-9-29 09:24:03 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Facebook - 内推 - HR筛选 技术电面 Onsite 校园招聘会 在线笔试 其他 |Other其他

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

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

x
要面FB了,在看面经,顺便把2016年度所有地里的FB面试题都总结了,dirty work,没什么技术含量。希望对大家有帮助。还没offer呢,攒攒人品。另外,好心人给我点货币,新人不知道咋弄货币呢,但是有时候看帖、下载需要。。。-google 1point3acres

=====

15. 3Sum

139. Word Break I/II

91. Decode Ways

209. Minimum Size Subarray Sum
  • Map store previous values ( O(N) )
  • 把第一题extend到2D。给一个matrix, all elements are positive,问有没有个sub rectangle加起来和等于target。return true/false。
  • Lz听到题目有点懵,认真调整心态,解决之。先写了个cumulative sum。把所有从0,0 到i,j的和算在新的matrix的i,j上。方便之后算head到tail的sub rectangle的和。这一步O(n^2)


350. Intersection of Two Arrays II
  • Sort, then find duplicates
    . 1point 3acres 璁哄潧

给一个字典包括很多字符串(e.g., abcd, dhfyf),然后给定一个字符串查看字典中是否包含这个字符串。字符串中可能包括*,*可以匹配任何字符。我用的Trie。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Task那道题,很多面经都提到过。就是比如给你一串task,再给一个cooldown,执行每个task需要时间1,两个相同task之间必须至少相距cooldown的时间,问执行所有task总共需要多少时间。比如执行如下task:12323,假设cooldown是3。总共需要的时间应该是 1 2 3 _ _ 2 3,也就是7个单位的时间。再比如 1242353,假设cool down是4,那总共时间就是 1 2 4 _ _ _ 2 3 5 _ _ _ 3,也就是13个单位的时间
  • 基于1,给出最优的排列,使得字符串最短。


自然string comparator。不知道的搜下。就是string 比较的时候考虑里面数字的大小,比如 abc9 < abc123 abc > ab9  因为char比digit重要。

117. Populating Next Right Pointers in Each Node II
  • salbring tree,不过没有next指针, 你要用原来的left,right指针
    . From 1point 3acres bbs
  • Level BFS
    . From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres
binary tree转换成doubly linked list
  • And revert it back (reverted to balanced tree): 109. Convert Sorted List to Binary Search Tree


75. Sort Colors

Print a binary tree by columns top to bottom.
.1point3acres缃
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]

list of sorted integer arrays,要求找所有的数的median. e.g. [1,3,6,7,9], [2,4, 8], [5], return 5

two sum + three sum + follow up

Best Time to Buy and Sell Stock, (I and II)
  • buy and sell stock,每天可以买一股,也可以都卖了,或者不买不卖。
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    • Find maximum, buy from earlier days, and sell on that day.


33. Search in Rotated Sorted Array

38.
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

218. The Skyline Problem (hard)

278. First Bad Version
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Min Queue, 跟Min Stack类似, 实现一个Queue, 然后O(1)复杂度获得这个Queue里最小的元素。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
interval [startTime, stoptime)   ----integral  time stamps
给这样的一串区间 I1, I2......In  
找出 一个 time stamp  出现在interval的次数最多。
startTime <= t< stopTime 代表这个数在区间里面出现过。
example:  [1,3),  [2, 7),   [4,  8),   [5, 9)
5和6各出现了三次, 所以答案返回5,6。  (Hard)

shortest continuous substring with all characters in input
  • 76. Minimum Window Substring


合并邮件列表(后来才知道也是个面经题)
Given 1 million email list:
list 1: a@a.com, b@b.com
list 2: b@b.com, c@c.com
list 3: e@e.com
list 4: a@a.com
...
Combine lists with identical emails, and output tuples:
(list 1, list 2, list 4) (a@a.com, b@b.com, c@c.com)
(list 3) (e@e.com)

79. Word Search

输出所有 root - leaf 的路径,递归做完了让迭代。
  • Iterative? BFS?


17. Letter Combinations of a Phone Number

28. Implement strStr()

398. Random Pick Index

37. Sudoku Solver

一个完全树。node有parent指针。
每个node的值为 0或 1
每个parent的值为两个子node的 “and” 结果
现在把一个leaf翻牌子(0变1或者1变0). visit 1point3acres.com for more.
把树修正一遍

200. Number of Islands

BST to increasing array
  • Recursive, iterative
  • 173. Binary Search Tree Iterator
    . 1point3acres.com/bbs
BST iterator
Iterator for a list of BSTs (heap contain each BST’s iterator)

128. Longest Consecutive Sequence

22. Generate Parentheses

238. Product of Array Except Self
. 1point 3acres 璁哄潧
191. Number of 1 Bits
. Waral 鍗氬鏈夋洿澶氭枃绔,
给2D平面上的N个点,求离原点最近的K个点
.鏈枃鍘熷垱鑷1point3acres璁哄潧
33.
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
. 1point3acres.com/bbs
39. Combination Sum
. 1point3acres.com/bbs
125. Valid Palindrome
214. Shortest Palindrome
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
98. Validate Binary Search Tree

Longest Arithmetic Progression)

10. Regular Expression Matching

211. Add and Search Word
. 鍥磋鎴戜滑@1point 3 acres
138. Copy List with Random Pointer

71. Simplify Path

Maximal square:

314. Binary Tree Vertical Order Traversal

198. House Robber

53. Maximum Subarray

-google 1point3acres
152. Maximum Product Subarray

32. Longest Valid Parentheses

277. Find the Celebrity
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
56. Merge Intervals
  • Variant: 一串start time - end time,格式是Apr 2010 - Mar 2011这种,要求计算出这些时间的总跨度,重叠的跨度不重复计算。举例:["Apr 2010 - Dec 2010", "Aug 2010 - Dec 2010", "Jan 2011 - Mar 2011"]


57. Insert Interval

206. Reverse Linked List

implement circular array
  • Circular buffer


Check big/small endian

第一题:binary tree,给定一个value,return bin tree里面下一个比value大的值
第二题:binary tree的node加一个ptr next,point到inorder traversal的下一个node,比上一个简单

297. Serialize and Deserialize Binary Tree

Given a list of number, there is only one peak or one drop. Find the maximum drop.
Exps:
1 -> 2 -> 3 -> 9 -> 3 -> 0 = 9;
10 -> 4 -> 3 -> 8 = 7 ;

224. Basic Calculator

43. Multiply Strings

282. Expression Add Operators

顺时针的print binary tree boundary, 就是从根开始,先打右边界,再打叶子,最后打左边界。

310. Minimum Height Trees

不用“/”,“%”运算符实现division,说了可以用binary search

273. Integer to English Words

111. Minimum Depth of Binary Tree
. visit 1point3acres.com for more.
找两个字符串中长度为N以上的共同子串
. 鍥磋鎴戜滑@1point 3 acres
117. Populating Next Right Pointers in Each Node I / II

29. Divide Two Integers

一个数组内要是存在至少三个升序的数(array[x] < array[y] < array[z], x < y < z)就返回true

161. One Edit Distance
. 1point 3acres 璁哄潧
print max depth path of a binary tree

151. Reverse Words in a String
. From 1point 3acres bbs
261. Graph Valid Tree
  • any connected graph without simple cycles is a tree.

-google 1point3acres
给一个linkedlist,里面的element都排序好了,但是是一个blackbox,有三个function可以调用。pop()随机pop出最前面或最后面的element,peek()随机偷看最前面或最后面的element,isEmpty()回传linkedlist是不是空了。问设计一个资料结构,list或是array都可以,把linkedlist里面所有的element都拿出来,并保持他们的排序。followup是如果不能用peek()该怎么做。
  • My thinking: if I got element A, and next element B is smaller than A, then A is from the tail of the list; otherwise, A is from the head of the list.


133. Clone Graph

Erase duplicate in an unsorted array

几何算法问题。如果给你一堆的矩形, 求重合矩形重合最多的坐标位置。我上过一个算法课,大概思路就是做一个二维的meeting room II

给定N个2D坐标(可以设想为餐厅的位置),要求输入任意坐标,可以返回方圆d距离内的所有餐厅

65. Valid Number

253. Meeting Rooms II
  • 求最多interval的时间点,返回任意一个就行。




补充内容 (2016-9-30 07:30):
一夜暴富了。。。谢谢大家。我昨天又做了一些修改,删去重复,合并了一些。另外一些难题的还写了写代码。可是帖子不能编辑啊?太菜了。

PS,刚刚面了FB第一轮,iterator for merging K sorted arrays

评分

92

查看全部评分

本帖被以下淘专辑推荐:

 楼主| qesss 发表于 2016-9-29 14:19:09 | 显示全部楼层
xu8431 发表于 2016-9-29 14:17
哈哈哈,谢谢楼主。
怎么连序号都是乱的,请问这序号是怎么编的?是按照时间顺序吗?

是按我搜索时候的顺序,也就是回帖顺序,但是你就当最前面的就越新就好了。
回复 支持 1 反对 0

使用道具 举报

 楼主| qesss 发表于 2016-9-29 12:09:14 | 显示全部楼层
Badger96 发表于 2016-9-29 12:00
interval [startTime, stopTime)   ----interval  time stamps
给这样的一串区间 I1, I2......In  
找 ...

恩,原帖有讨论,我就不找原帖了。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
总结如下:就是meeting rooms II,维护一个堆,堆里记录现在各个meeting room的结束时间。处理下一个interval时,首先把堆里已经结束的(在这个新的interval开始的时候)meeting rooms出堆,这样相当于堆里维护的一直都是overlapping的meeting rooms (intervals),每一个meeting room出堆,都更新结果:目前overlapping的meeting room (intervals)数就是堆的size(包含这个正在出堆的,要加1),对应这个overlapping size的时间段是上一个处理的interval的开始时间,到出堆这个interval的结束时间。最后再把新的interval入堆。
回复 支持 1 反对 0

使用道具 举报

dc_726 发表于 2016-9-29 09:28:37 | 显示全部楼层
非常感谢!lz加油!
回复 支持 反对

使用道具 举报

liuzxiao 发表于 2016-9-29 09:37:22 | 显示全部楼层
万分感激!!!最后突击一遍!
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-9-29 10:07:40 | 显示全部楼层
楼主好人一生平安
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-29 10:28:22 | 显示全部楼层
这...厉害~....谢谢楼主!!!
回复 支持 反对

使用道具 举报

luckylady 发表于 2016-9-29 10:47:55 | 显示全部楼层
谢谢楼主 楼主是电面还是onsite 电面的话一起刷题啊
回复 支持 反对

使用道具 举报

thewayofwin 发表于 2016-9-29 10:48:23 | 显示全部楼层
点赞,字数字数字数
回复 支持 反对

使用道具 举报

sterne 发表于 2016-9-29 10:48:35 | 显示全部楼层
非常有用,感谢楼主!
回复 支持 反对

使用道具 举报

 楼主| qesss 发表于 2016-9-29 10:49:00 | 显示全部楼层
gaocan1992 发表于 2016-9-29 09:58
弱弱的问一下,这是不就是lc的fb tag里的80多道,看上去感觉像

我猜有很多leetcode里没有的。但是我也不确定。这样看方便点而已。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Badger96 发表于 2016-9-29 11:24:30 | 显示全部楼层
大部分是tag里的,有个别只存在于面经,比如timestamp那题。顺便请教下有人知道那题该怎么做吗
回复 支持 反对

使用道具 举报

 楼主| qesss 发表于 2016-9-29 11:56:15 | 显示全部楼层
Badger96 发表于 2016-9-29 11:24
大部分是tag里的,有个别只存在于面经,比如timestamp那题。顺便请教下有人知道那题该怎么做吗

哪个timestamp?
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-9-29 12:00:22 | 显示全部楼层

interval [startTime, stopTime)   ----interval  time stamps
给这样的一串区间 I1, I2......In  
找出 一个 time stamp  出现在interval的次数最多。
startTime <= t< stopTime 代表这个数在区间里面出现过。. 鍥磋鎴戜滑@1point 3 acres
example:  [1,3),  [2, 7),   [4,  8),   [5, 9)
5和6各出现了三次, 所以答案返回5,6。
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-9-29 12:37:05 | 显示全部楼层
qesss 发表于 2016-9-29 12:09
恩,原帖有讨论,我就不找原帖了。

总结如下:就是meeting rooms II,维护一个堆,堆里记录现在各个me ...

谢谢楼主啊,才发现这题也可以用meeting rooms的方法做,不过最后应该还得扫一遍heap里的数来取得overlap最多次的值
回复 支持 反对

使用道具 举报

zengm321 发表于 2016-9-29 13:07:25 | 显示全部楼层
感谢楼主,FB的题比狗家的人性多了。
回复 支持 反对

使用道具 举报

Seraph_Roy 发表于 2016-9-29 13:31:36 | 显示全部楼层
感谢分享!!!马克一下……
回复 支持 反对

使用道具 举报

xu8431 发表于 2016-9-29 14:17:29 | 显示全部楼层
哈哈哈,谢谢楼主。
怎么连序号都是乱的,请问这序号是怎么编的?是按照时间顺序吗?
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-9-29 14:19:06 | 显示全部楼层
mark 學習下
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-17 02:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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