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
https://leetcode.com/problems/read-n-characters-given-read4
int read4(char *buf);
struct Solution {
/*@param buf Destination buffer
* @param n Maximum number of characters to read
* @return The number of characters read*/
int read(char *buf, int n) {
if(buf==NULL or n<=0) return 0; //
int count=0, cur=INT_MIN;
while(n>count && (cur==4 || cur==INT_MIN))
cur=min(read4(buf+count), n-count), count+=cur;
return count;
}
};上面的方法能通过OJ但是直接读到buf里面有overflow的风险.下面的代码好些:
int read(char *buf, int n) {
if(!buf or n<=0) return 0;
char t[4]={};
int r=0;
while(1){
int c=read4(t); // read to t
int d=min(c,n-r);
memcpy(buf+r, t, d), r+=d;
if(c<4) break;
if(r==n) break;
}
return r;
}注意: 当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.
https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times
http://bit.ly/2wXqQhO
因为要调用多次,这里又多了一些corner case:
第一次调用时,如果read4读出的多余字符我们要先将其暂存起来,这样第二次调用时先读取这些暂存的字符
第二次调用时,如果连暂存字符都没读完,那么这些暂存字符还得留给第三次调用时使用
所以,难点就在于怎么处理这个暂存字符.
int read4(char *buf);
class Solution {
vector<char> t; // tmp buffer
public:
int read(char *buf, int n) {
if(!buf or n<=0) return 0;
int r=0;
if(t.empty()){
t.resize(4);
while(1){
int c=read4(&t[0]);
if(c<4) t.erase(t.begin()+c, t.end()); // to have a clean buffer
int d=min(c, n-r);
memcpy(buf+r,&t[0],d), r+=d;
if(c<4 || r==n){
t.erase(t.begin(),t.begin()+d);
break;
}
}
return r;
}
int sz=t.size();
memcpy(buf, &t[0], r=min(sz,n)), t.erase(t.begin(), t.begin()+r);
if(n<=sz) return r;
else return r+read(buf+r, n-r);
}
};这里一定要有一个temp buffer, 我用一个vector来管理.
注意memcpy的参数是dest在先,每次memcpy之后就清temp buffer.
2017(7-9月) 码农类 博士 全职 Facebook - 内推 - 技术电面 Onsite |Passfresh grad应届毕业生
电面:利口二期三.
Onsite:
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
http://www.1point3acres.com/bbs/thread-292326-1-1.html
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 -> ABhttps://leetcode.com/problems/excel-sheet-column-title
这是(1-based index)26进制的转换问题. 注意shift by one的问题.
string convertToTitle(int n) {
int BASE=26;
string r;
while(n)
r=char('A'+(n-1)%BASE)+r, n=(n-1)/BASE;
return r;
}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 numberX 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 ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]https://leetcode.com/problems/remove-invalid-parentheses/
给定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)\) ???
这种要返回所有结果的,很可能就是DFS,但是这题BFS也可以做.
Remove一个char之后的新string是下一个节点.
http://massivealgorithms.blogspot.com/2015/11/leetcode-301-remove-invalid-parentheses.html
http://www.cnblogs.com/grandyang/p/4944875.html
https://leetcode.com/discuss/67842/share-my-java-bfs-solution
https://leetcode.com/discuss/67825/backtracking-trick-here-eliminate-duplicates-without-map
https://leetcode.com/discuss/67821/dfs-and-bfs-java-solutions
http://bookshadow.com/weblog/2015/11/05/leetcode-remove-invalid-parentheses/
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.
可能用到的两个子函数:
bool valid(const string& s){
int l=0;
for (char c: s){
if(c=='(') l++; else if(c==')') l--;
if(l<0) return false;
}
return l==0;
}还有这个是算需要删除多少left and right parentheses:
pair<int,int> calc_mistmatch(const string& s){
int left = 0, right = 0;
for (char c : s)
if(c=='(') left++; else if(c==')') left>0 ? left-- : right++;
return {left, right};
}44.4.1 Naive DFS (TLE)
Remove Invalid Parentheses
对每一个Parenthesis我们可以选择要还是不要.
struct Solution {
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> r;
string p;
dfs(r,p,s,0,0);
return vector<string>(r.begin(),r.end());;
}
void dfs(unordered_set<string>& r, string p, const string& s, int l, int h){
if(l<0) return;
if(h==s.size() && l==0){
if(r.empty() || r.begin()->size()<p.size()){ r.clear(), r.insert(p);}
else if(r.begin()->size() == p.size()) r.insert(p);
return;
}
for(int i=h; i<s.size(); ++i)
if(s[i]=='(') dfs(r,p+s[i],s,l+1,i+1), dfs(r,p,s,l,i+1);
else if(s[i]==')') dfs(r,p+s[i],s,l-1,i+1), dfs(r,p,s,l,i+1);
else p+=s[i], dfs(r,p,s,l,i+1);
}
};这个算法的复杂度是\(2^N\),效率很低,所以Time Limit Exceeded, Last executed input: “())((((((((((b))(”.
44.4.2 DFS + Pruning
为提高效率必须优化．DFS solution with optimizations:
struct Solution { // 64.18 %
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> res;
int left = 0, right = 0;
for (char c : s)
if(c=='(') left++; else if(c==')') left>0 ? left-- : right++;
dfs(s, 0, 0, left, right, "", res);
return vector<string>(res.begin(), res.end());
}
void dfs(string& s, int i, int cl, int l, int r, string p, unordered_set<string>&res) {
if(cl<0) return; // the parentheses is invalid
if (i == s.size()) { if (0 == l && 0 == r) res.insert(p); return; }
if ('(' == s[i]) {
if (l>0) dfs(s, i+1, cl, l-1, r, p, res); // remove (
dfs(s, i+1, cl+1, l, r, p+s[i], res);
} else if (')' == s[i]) {
if (r>0) dfs(s, i+1, cl, l, r-1, p, res); // remove )
dfs(s, i+1, cl-1, l, r, p+s[i], res);
} else dfs(s, i+1, cl, l, r, p+s[i], res);
}
};采用的方法为:
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,表明我们最后的结果一定是删除１个`(`,3个`)`.
虽然最后具体删除哪个不一定确定,这个仍然是一个重要的信息,要好好利用.
但不是说left>0的时候遇到'('就必须删除．
比如: `)()(`, left=1, right=1,如果看到left==1就删掉第一个'(',是错的.- Use count variable to validate the parentheses dynamically.
- Use while loop to avoid duplicate result in DFS, instead of using HashSet.(TODO)
还有一种方法,不是构建string,而是从原string删除多余的parentheseｓ:
vector<string> removeInvalidParentheses(string s) { // 63.43 %
int left = 0, right = 0;
for (char c : s)
if(c=='(') left++; else if(c==')') left>0 ? left-- : right++;
vector<string> r;
dfs(s, 0, left, right, r);
return r;
}
void dfs(string s, int begin, int left, int right, vector<string> &r) {
if(left == 0 && right == 0){
if(valid(s)) r.push_back(s);
return;
}
for(int i = begin; i < s.size(); i++) {
if(i>begin && s[i]==s[i-1]) continue;
if (right > 0 && s[i] == ')'){
string t = s; t.erase(i, 1);// Optimized a little bit here
dfs(t,i,left,right-1,r);
}else if(left > 0 && s[i] == '('){
string t = s; t.erase(i, 1);// Optimized a little bit here
dfs(t,i,left-1,right,r);
}
}
}或者:
void dfs(string s, int begin, int left, int right, vector<string> &r) {
if(left == 0 && right == 0){
if(valid(s)) r.push_back(s);
return;
}
for(int i = begin; i < s.size(); i++)
if(i>begin && s[i]==s[i-1]) continue;
else if (right > 0 && s[i] == ')')
dfs(s.substr(0,i)+s.substr(i+1),i,left,right-1,r);
else if(left > 0 && s[i] == '(')
dfs(s.substr(0,i)+s.substr(i+1),i,left-1,right,r);
}Duplicates arise from consecutive ‘(’ or ‘)’. We only get rid of the first one before going a level further.(http://bit.ly/2xmitNl)
http://en.cppreference.com/w/cpp/string/basic_string/erase
http://bit.ly/2xmbT9u
44.4.3 BFS
这题最直观,最样板化的解法来自BFS.
struct Solution { // 36%, 56 ms
vector<string> removeInvalidParentheses(string s) {
if(s.empty()) return {""};
unordered_set<string> r, visited;
queue<string> q;
q.push(s);
if(valid(s)) r.insert(s);
visited.insert(s);
while(!q.empty() && r.empty()){ // break if r is not empty
int count=q.size();
while(count--){
string t = q.front(); q.pop();
for(int i=0; i<t.size(); ++i)
if(t[i]=='(' || t[i]==')'){
string ns=t.substr(0,i)+t.substr(i+1);
if(valid(ns)) r.insert(ns);
if(!visited.count(ns))
q.push(ns), visited.insert(ns);
}
}
visited.clear();
}
return vector<string>(r.begin(), r.end());
}
bool valid(const string& s){
int l=0;
for(char c: s){
if(c=='(') ++l; else if(c==')') --l;
if(l<0) return false;
}
return l==0;
}
};利用需要remove的left, right数目,optimize BFS:
vector<string> removeInvalidParentheses(string s) { // 40%, 46 ms
if(s.empty()) return {""};
int left = 0, right = 0;
for (char c : s)
if(c=='(') left++; else if(c==')') left>0 ? left-- : right++;
unordered_set<string> rs, visited;
queue<pair<string,pair<int,int>>> q;
q.push({s,{left,right}});
if(valid(s)) rs.insert(s);
visited.insert(s);
while(!q.empty() && rs.empty()){ // break if r is not empty
int count=q.size();
while(count--){
auto f = q.front(); q.pop();
const string& t=f.first;
for(int i=0; i<t.size(); ++i){
int l=f.second.first, r=f.second.second;
if(t[i]=='(' || t[i]==')'){
if(t[i]=='(') l--; else if(t[i]==')') r--;
string ns=t.substr(0,i)+t.substr(i+1);
if(l==0 && r==0 && valid(ns)) rs.insert(ns);
if(!visited.count(ns))
q.push({ns,{l,r}}), visited.insert(ns);
}
}
}
visited.clear();
}
return vector<string>(rs.begin(), rs.end());
}但是好像在测试中并没有加速太多.
涉及到parentheses的还有好多道:
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.
https://leetcode.com/problems/valid-parentheses/
struct Solution {
bool isValid(string s) {
if (s.empty()) return true;
const map<char,char> m{{'(',')'}, {'{','}'}, {'[',']'}};
stack<char> stk;
for_each(s.begin(), s.end(), [&](const char c){
if (!stk.empty() && m.count(stk.top()) && m.at(stk.top())==c){
stk.pop();
}else{stk.push(c);}});
return stk.empty();
}
};44.6 Longest Path in N-ary Tree
http://www.1point3acres.com/bbs/thread-214515-1-1.html
http://www.cnblogs.com/EdwardLiu/p/6404104.html
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
http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
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
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
44.9 549. Binary Tree Longest Consecutive Sequence II
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/
array.html#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.
Example:
Input:
[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Output: 2
Explanation:
