Chapter 44 Facebook 2016 Interview Questions Part 1

44.1 157. Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value of this API is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. The read function should return the number of characters read.

Note: The read function will only be called once for each test case


注意: 当data source里面没有character的时候, 这个返回的count可能会小于n.

The crux to solve this problem is to be clear when we can keep reading data, and when we must break.

There are two scenarios that we should break from the reading loop:
1. n==count which means we have read n chars into buffer
2. cur<4 which means there is no enough data from the source we are reading

Negate (1 or 2), and we get condition of the while loop.

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

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function may be called multiple times.

因为要调用多次,这里又多了一些corner case:

这里一定要有一个temp buffer, 我用一个vector来管理.

注意memcpy的参数是dest在先,每次memcpy之后就清temp buffer.

2017(7-9月) 码农类 博士 全职 Facebook - 内推 - 技术电面 Onsite |Passfresh grad应届毕业生
1. 利口而就起, 利口三菱要(需要remove括号的个数)
2. Read4K,一个能够调用一次,一个能够调用多次,还有怎么减少copy次??
3. Research,主要是自己的research,最后问了利口125
4. Design Instagram.
时间线:7/11 内推 -> 7/12 收到recruiter邮件 -> 7/31 电面 -> 8/17 onsite -> 8/28 送committee -> 8/30 第一轮 -> 8/31 offer

44.3 168. Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
26 -> Z
27 -> AA
28 -> AB

这是(1-based index)26进制的转换问题. 注意shift by one的问题.

One line solver:

Note the difference between this counting system and the normal base-10 system
consider the letter ‘A’ to have a value of 1, ‘B’->2 … ‘Z’->26
note that in the above notation, values are 1-based
here our Radix ® == 26 the final value of a number X Y Z = X * R^2 + Y * R + Z
this looks similar to base-10 decimal number but the biggest difference is that the numbers on every digit starts with 1, instead of 0., and the max on each digit goes up to R (Radix) instead of R-1 for example
Z== Radix
then next number is AA = R + 1 = Z+1
ZZ = R * R + R
next number is AAA = 1R^2 + 1 R + 1 = ZZ +1
so from the AAA notation to their sequence number (decimal) it’s easy, but the other way is a bit tricky due to the way % and / operates

类似题目: bit.html#convert-a-number-to-hexadecimal

44.4 301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).


"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

给定String,去除invalid括号,输出所有结果集.一开始想的是DFS + Backtracking,没有坚持下去.后来在Discuss里发现了jeantimex大神的BFS方法非常好,于是搬过来借鉴.方法是我们每次去掉一个“(”或者“)”,然后把新的string加入到Queue里,继续进行计算.要注意的是需要设置一个boolean foundResult,假如在这一层找到结果的话,我们就不再继续进行下面的for循环了.这里应该还可以继续剪枝一下,比如记录当前这个结果的长度len,当queue里剩下的string长度比这个len小的话,我们不进行验证isValid这一步.

Time Complexity - \(O(n * 2^n)\), Space Complexity - \(O(2^n)\) ???



We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter. The counter will increase when it is ‘(’ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(’ in the prefix.

还有这个是算需要删除多少left and right parentheses:

44.4.2 DFS + Pruning

为提高效率必须优化.DFS solution with optimizations:

1. Before starting DFS, calculate the total numbers of opening and closing parentheses that need to be removed in the final solution, then these two numbers could be used to speed up the DFS process.

比如: 对`)))(()`来说, left=1, right=3,表明我们最后的结果一定是删除1个`(`,3个`)`.
比如: `)()(`, left=1, right=1,如果看到left==1就删掉第一个'(',是错的.
  1. Use count variable to validate the parentheses dynamically.
  2. Use while loop to avoid duplicate result in DFS, instead of using HashSet.(TODO)



Duplicates arise from consecutive ‘(’ or ‘)’. We only get rid of the first one before going a level further.(

44.4.3 BFS


利用需要remove的left, right数目,optimize BFS:



44.5 20. Valid Parentheses

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ’]’, determine if the input string is valid.

The brackets must close in the correct order, () and ()[]{} are all valid but (] and ([)] are not.

44.6 Longest Path in N-ary Tree

2016(4-6月) 码农类 硕士 全职 Google - 猎头 - Onsite |Other其他
1. there are m piles of coins, each pile is consisted of coins with different values. you are allowed to take n coins home. However, you can only take coins from the top of each pile. What’s the maximum value you can obtain.
2. output all same sub-tree pairs..
3. output the intersection between two list, O(1) space
4. Remove duplicate characters in a string.
5. find longest consecutive path in tree, not necessary binary tree
6. given a list, the query will be a range, return the maximum number within this range, what if there are 1000 queries per second..
7. detect cycle in a graph.
lots of follow up questions. They do care about space complexity.

44.7 Longest Path in DAG

The longest path problem for a general graph is not as easy as the shortest path problem because the longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem is NP-Hard for a general graph. However, the longest path problem has a linear time solution for directed acyclic graphs. The idea is similar to linear time solution for shortest path in a directed acyclic graph., we use Tological Sorting.

44.8 298. Binary Tree Longest Consecutive Sequence

44.10 554. Brick Wall

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.


[[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]

Output: 2