一亩三分地论坛

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

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

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

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

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

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

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

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

鏉ユ簮涓浜.涓夊垎鍦拌鍧. =====

15. 3Sum

139. Word Break I/II
. From 1point 3acres bbs
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


给一个字典包括很多字符串(e.g., abcd, dhfyf),然后给定一个字符串查看字典中是否包含这个字符串。字符串中可能包括*,*可以匹配任何字符。我用的Trie。
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指针

  • Level BFS
    . 1point 3acres 璁哄潧

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.

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. Count and Say

sparse vector dot multiplication
  • 这道题我当时并没有准备到,但是正因为如此,我认为我跟面试官的交流给我加分了不少。面试官首先问我每个vector很大,并不能在内存中存下,该怎么办,我说只需要存下非零的元素和他们的下标就行,然后询问面试官是否可以用预处理后的这两个vector非零元素的index和value作为输入,面试官同意后快速写完O(M*N)的代码,M和N分别是两个vector的长度。面试官说这两个输入如果是根据下标排序好的话应该怎么办,我说可以遍历长度较短的那一个,然后用二分搜索的方法在另一个vector中找index相同的元素,相乘加入到结果中,这样的话复杂度就是O(M*logN)。这时,面试官又问是否可以同时利用两个输入都是排序好这一个特性,我在这个地方有点卡住,但是在白板上写出一个test case,试着用可视化的方法帮助我来进行思考,同时面试官给了一些提醒,最后写出了O(M + N)的双指针方法
  • 然后问如果有一个向量比另一个长很多怎么办,遍历短的,对长的二分查找。
  • 两个vector相乘
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鍥磋鎴戜滑@1point 3 acres
211. Add and Search Word

239. Sliding Window Maximum

282. Expression Add Operators

158. Read N Characters Given Read4 II - Call multiple times

49. Group Anagrams - use counting sort

linked list 反序输出 - 1) reverse the list; 2) recursion

问题一:flatten an array?

285. Inorder Successor in BST

283. Move Zeroes
  • Minimizing “writes”


5. Longest Palindromic Substring
62. Unique Paths I/II

moving all the nonzeros to the front of a list。

Prettify JSON:  输入[1,2,3, {"id": 1, "name": "wang", "tag":[1,"home",2], "price":234}]

Smallest subarray with sum greater than a given value:

flatten nested array

215. Kth Largest Element in an Array

114. Flatten Binary Tree to Linked List
  • Linked list needs to be formed as a cycle

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
301. Remove Invalid Parentheses (hard)
  • Maintain counter and go from left to right, remove when necessary, then counter must be > 0, then remove “(“ from right hand side
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

218. The Skyline Problem (hard)

278. First Bad Version

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)
. 1point 3acres 璁哄潧
79. Word Search

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

.1point3acres缃
17. Letter Combinations of a Phone Number

28. Implement strStr()

398. Random Pick Index
. from: 1point3acres.com/bbs
37. Sudoku Solver

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

BST to increasing array
  • Recursive, iterative
  • 173. Binary Search Tree Iterator

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
. visit 1point3acres.com for more.
191. Number of 1 Bits

给2D平面上的N个点,求离原点最近的K个点

33. Search in Rotated Sorted Array
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
找出两个给出两个string, leetcode, codyabc和一个数字k = 3,问两个string里面存不存在连续的common substring大于等于k.比如这个例子,两个string都有cod,所以返回true。楼主用dp建了一个m*n的table秒了,然后写test case,发现有个小corner case,改了,pass
  • Longest common substring

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给定一个数列,比如1234,将它match到字母上,1是A,2是B等等,那么1234可以是
ABCD
但是还可以是12是L,所以1234也可以写作
LCD 或者
AWD

给出N个序列,比如2个序列A,B,没个序列包含若干的区间,比如
A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]
Merge them all:  [1,6], [8, 20].

balance parentheses in a string
例子:
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"
Note: balance的意思就是把原来string里unpaired的括号变成paired的形式。如果有多个可能的结果, 比如上述最后一种情况,我们就只需要输出一个对的结果即可,所以这点简化了题目的难度。感受: 遍历string, 用一个stack存储每个open parenthesis的index,也就是'('的index, 每当遇到closed parenthesis就执行一次pop操作。
注意两种unbalanced的情况:
1. 出现多余的')':
    对应情况就是stack为空,但遇到了一个')'。
2. 出现多余的'(':
    对应情况就是遍历结束,stack未空
. 鍥磋鎴戜滑@1point 3 acres
get binary tree's next node in inorder
class Node {Node left, Node right, Node parent}
Node getNext (Node current) {}

给一个tree,每个node 有很多children,
找到所有最深的nodes 的common  ancestor,
  • 比如只有一个点最深,那返回他自己。
  • Similar to 236. Lowest Common Ancestor of a Binary Tree


78. Subsets
90. Subsets II

341. Flatten Nested List Iterator

102. Binary Tree Level Order Traversal

给三个funtions: is_low(), is_mid(), is_high(). 让给一个数组排序, low的放在最前面, mid的放在中间, high的放在最后面.
  • Color sort: think about when there are K colors


39. Combination Sum

125. Valid Palindrome
214. Shortest Palindrome

98. Validate Binary Search Tree

Longest Arithmetic Progression)

10. Regular Expression Matching

211. Add and Search Word

138. Copy List with Random Pointer

71. Simplify Path

Maximal square:

314. Binary Tree Vertical Order Traversal
. 1point 3acres 璁哄潧
198. House Robber

53. Maximum Subarray

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,比上一个简单
-google 1point3acres
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 ;
-google 1point3acres
224. Basic Calculator

43. Multiply Strings

282. Expression Add Operators
.鏈枃鍘熷垱鑷1point3acres璁哄潧
顺时针的print binary tree boundary, 就是从根开始,先打右边界,再打叶子,最后打左边界。
. from: 1point3acres.com/bbs
310. Minimum Height Trees

. 鍥磋鎴戜滑@1point 3 acres
不用“/”,“%”运算符实现division,说了可以用binary search

273. Integer to English Words

. visit 1point3acres.com for more.
111. Minimum Depth of Binary Tree
. from: 1point3acres.com/bbs
找两个字符串中长度为N以上的共同子串

117. Populating Next Right Pointers in Each Node I / II

29. Divide Two Integers

. 鍥磋鎴戜滑@1point 3 acres
一个数组内要是存在至少三个升序的数(array[x] < array[y] < array[z], x < y < z)就返回true

161. One Edit Distance
.鏈枃鍘熷垱鑷1point3acres璁哄潧
print max depth path of a binary tree

151. Reverse Words in a String

261. Graph Valid Tree
  • any connected graph without simple cycles is a tree.


给一个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.

.1point3acres缃
133. Clone Graph

Erase duplicate in an unsorted array
. Waral 鍗氬鏈夋洿澶氭枃绔,
几何算法问题。如果给你一堆的矩形, 求重合矩形重合最多的坐标位置。我上过一个算法课,大概思路就是做一个二维的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

评分

73

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 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.1point3acres缃
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 | 显示全部楼层
万分感激!!!最后突击一遍!
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-29 09:58:14 | 显示全部楼层
弱弱的问一下,这是不就是lc的fb tag里的80多道,看上去感觉像
回复 支持 反对

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
弱弱的问一下,这是不就是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那题。顺便请教下有人知道那题该怎么做吗
. visit 1point3acres.com for more.
哪个timestamp?
回复 支持 反对

使用道具 举报

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

interval [startTime, stopTime)   ----interval  time stamps 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给这样的一串区间 I1, I2......In  
找出 一个 time stamp  出现在interval的次数最多。
startTime <= t< stopTime 代表这个数在区间里面出现过。
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 ...
. 1point 3acres 璁哄潧
谢谢楼主啊,才发现这题也可以用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 學習下
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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