发信人: hahadaxiong (hahadaxiong), 信区: JobHunting
标 题: 分享几个FGTP Internship 的面经，顺便求FG收留
发信站: BBS 未名空间站 (Sun Dec 21 01:45:28 2014, 美东)
PhD summer intern，都是11月面的
F第一轮
Q1：两个string s1, s2, 比较前n个的字符的大小，n可能比s1, s2的长度长
Q2：每个user都有很多email联系人,<user, list of email contacts>,把这些user分
组，一个组内的user 可以通过一些共同的Email account连起来，还有一些改进
F第二轮
聊了很多的research和以前的project
Q1：一个文件里存着代码和注释，注释在/××/中间，要求print所有line除了注释
G家
Interview 1
有一些set of names, 比如first name, middle name, last name,写个iterator打印
名字的组合
Interview 2
Longest Consecutive Sequence
Simplify path 变型。。具体要求不太记得了
Interview 3 （是国人大哥）
聊了以前的project，题目是Interleaving String的一个变种，也是用DP做
T
Q1:设计数据结构快速查找一个栈里是否有某个元素
Q2： Inverted index 的一个题目，具体什么要求不太记得了
P：
Q1：给一个Amazon s3Key.next() 这个api, 可以读取一块定长字符串，要求实现常见
的nextLine()函数，即打印下一行。
TP面完都是一个小时内受到据信，这效率。。。。
G，F现在都在pool里等match, F家效率很低啊，好不容易安排了个面试，还被临时取消
了。。求哪位大侠收留。多谢！
Tuesday, December 23, 2014
Thursday, December 18, 2014
google题
发信人: xiaoyouyi (yy), 信区: JobHunting
标 题: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 04:06:43 2014, 美东)
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
发信人: blaze (狂且), 信区: JobHunting
标 题: Re: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)
Just dp:
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重，可以是正的或者负的。
f(m, n) = 0
f(i, j) = min(
max(f(i+1, j) - w(i+1,j), 0),
max(f(i, j+1) - w(i, j+1), 0)
)
每个点计算当前点到目标的最 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情 况取最小作为当前点的最小能量要求即可。
发信人: CodeSwim (CodeSwim), 信区: JobHunting
标 题: GG面经
发信站: BBS 未名空间站 (Tue Jan 20 12:55:43 2015, 美东)
前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.
第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的 从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;
第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝 然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束.
标 题: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 04:06:43 2014, 美东)
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
发信人: blaze (狂且), 信区: JobHunting
标 题: Re: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)
Just dp:
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。
w是当前点上的权重，可以是正的或者负的。
f(m, n) = 0
f(i, j) = min(
max(f(i+1, j) - w(i+1,j), 0),
max(f(i, j+1) - w(i, j+1), 0)
)
每个点计算当前点到目标的最 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情 况取最小作为当前点的最小能量要求即可。
发信人: CodeSwim (CodeSwim), 信区: JobHunting
标 题: GG面经
发信站: BBS 未名空间站 (Tue Jan 20 12:55:43 2015, 美东)
前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.
第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的 从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;
第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝 然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束.
Wednesday, December 17, 2014
Missing Ranges
from here
Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]
[分析]
一遍线性扫描即可。
[注意事项]
1）针对一些特殊情况，询问面试官，比如说如果array是个空的，或者array包含区间内的所有元素，相应的返回值是什么
2）可以给出一些有意思的test case，另外就是不需要限制给出的范围是[0, 99]，用start和end表示就行。在面试的时候可以先提一下，写出[0, 99]的代码，然后在稍作修改，变成start和end的版本。
Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]
[分析]
一遍线性扫描即可。
[注意事项]
1）针对一些特殊情况，询问面试官，比如说如果array是个空的，或者array包含区间内的所有元素，相应的返回值是什么
2）可以给出一些有意思的test case，另外就是不需要限制给出的范围是[0, 99]，用start和end表示就行。在面试的时候可以先提一下，写出[0, 99]的代码，然后在稍作修改，变成start和end的版本。
public class Solution { public List<String> findMissingRanges(int[] vals, int start, int end) { List<String> ranges = new ArrayList<String>(); int prev = start - 1; for (int i=0; i<=vals.length; ++i) { int curr = (i==vals.length) ? end + 1 : vals[i]; if ( cur-prev>=2 ) { ranges.add(getRange(prev+1, curr-1)); } rev = curr; } return ranges; } private String getRange(int from, int to) { return (from==to) ? String.valueOf(from) : from + "->" to; } }
总结3
发信人: watercc (watercc), 信区: JobHunting
标 题: FB面经
发信站: BBS 未名空间站 (Tue Dec 16 22:58:13 2014, 美东)
电面1
1. Find successor in BST
2. Find minimum number in a rotated sorted array (当时这个题还没在
leetcode里，所以写得代码有些繁琐，估计因为这个要再电面一轮）
电面2
1. Insert a node into a sorted circular linked list ( all next element is
larger except for the last one), the given head can point to any node
1 -> 3 -> 5 ->7
^ |
| |
| _ _ _ _ |
如果node的值是2，则插入1和3之间；如果node的值是8或者0，插入7和1之间。
要考虑node值重复的情况，虽然结果一样，但要和面试官讨论新的节点插入的位置，可
能插入在最开始或最后，我不记得了。
例如插入3, 结果是1->3->3'->5->7或者1->3'->3->5->7
2. Clone graph(leetcode)
Onsite 因为NDA就不透露了，之后又两轮coding的加面
第一轮就是leetcode的anagram和decode way
第二轮
2. Design a data structure supporting two operations
1） void addWord(string)
2） bool search(string)
search(string) can search word and regular expression ( only consider “.”,
which means any one character)
例如
addWord("rat")
addWord("cat")
addWord("bat")
search("dat") -> false
search("bat") -> true
search(".at") -> true
search("r.t") -> true
要求比brute force效率高，我用的Trie,实现了Trie的insert和search。由于“.”，
search用了DFS
发信人: xxzbj (xxue), 信区: JobHunting
标 题: FB电面面经
发信站: BBS 未名空间站 (Wed Nov 26 15:31:42 2014, 美东)
投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
一个小时前的FB电面， 电面的是个老印，一共出了3个题。
1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.
都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
contiguous， 给了
个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
2) palindrome String
边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
3) decode ways.
边讲边写，做了7，8分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。
发信人: xxzbj (xxue), 信区: JobHunting
标 题: f家面经
发信站: BBS 未名空间站 (Thu Dec 18 20:11:19 2014, 美东)
fresh phd, 今天下午刚面完，攒人品发面经。 前2论感觉很好，后2轮感觉很差。
长期求内推啊！！！
电面面经在这里
http://www.mitbbs.com/article_t/JobHunting/32838067.html
1） 国人大哥，culture fit半小时, 花10分钟象征性做了一个非常简单的回文。感觉
大哥人很好。
2） 国人大哥，非常简单的题矩阵相乘，然后follow up,涉及到tree， hashmap,
arraylist，也都很简单。 代码也得也都很顺利，感觉大哥人很好。
3）老印，最长的括号子序列。题不难，感觉这轮做得很差，老印提醒了2次，代码改了
几次， 虽然写出来了，老印最后照了相，知道挂了。心情开始很差。
4）午饭，版上的好心推荐人。
5）白人，设计一个在线图片编辑系统，完全没有经验，只能按版上的partition,
backup, cache等瞎说。边引导边回答。当面给的feedback都还算positive。
真心感觉不难，但只怪自己表现太差，同学们加油啊！！
心里还是很郁闷。但也只能move on。
标 题: FB面经
发信站: BBS 未名空间站 (Tue Dec 16 22:58:13 2014, 美东)
电面1
1. Find successor in BST
2. Find minimum number in a rotated sorted array (当时这个题还没在
leetcode里，所以写得代码有些繁琐，估计因为这个要再电面一轮）
电面2
1. Insert a node into a sorted circular linked list ( all next element is
larger except for the last one), the given head can point to any node
1 -> 3 -> 5 ->7
^ |
| |
| _ _ _ _ |
如果node的值是2，则插入1和3之间；如果node的值是8或者0，插入7和1之间。
要考虑node值重复的情况，虽然结果一样，但要和面试官讨论新的节点插入的位置，可
能插入在最开始或最后，我不记得了。
例如插入3, 结果是1->3->3'->5->7或者1->3'->3->5->7
2. Clone graph(leetcode)
Onsite 因为NDA就不透露了，之后又两轮coding的加面
第一轮就是leetcode的anagram和decode way
第二轮
2. Design a data structure supporting two operations
1） void addWord(string)
2） bool search(string)
search(string) can search word and regular expression ( only consider “.”,
which means any one character)
例如
addWord("rat")
addWord("cat")
addWord("bat")
search("dat") -> false
search("bat") -> true
search(".at") -> true
search("r.t") -> true
要求比brute force效率高，我用的Trie,实现了Trie的insert和search。由于“.”，
search用了DFS
发信人: xxzbj (xxue), 信区: JobHunting
标 题: FB电面面经
发信站: BBS 未名空间站 (Wed Nov 26 15:31:42 2014, 美东)
投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
一个小时前的FB电面， 电面的是个老印，一共出了3个题。
1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.
都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
contiguous， 给了
个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
2) palindrome String
边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
3) decode ways.
边讲边写，做了7，8分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。
发信人: xxzbj (xxue), 信区: JobHunting
标 题: f家面经
发信站: BBS 未名空间站 (Thu Dec 18 20:11:19 2014, 美东)
fresh phd, 今天下午刚面完，攒人品发面经。 前2论感觉很好，后2轮感觉很差。
长期求内推啊！！！
电面面经在这里
http://www.mitbbs.com/article_t/JobHunting/32838067.html
1） 国人大哥，culture fit半小时, 花10分钟象征性做了一个非常简单的回文。感觉
大哥人很好。
2） 国人大哥，非常简单的题矩阵相乘，然后follow up,涉及到tree， hashmap,
arraylist，也都很简单。 代码也得也都很顺利，感觉大哥人很好。
3）老印，最长的括号子序列。题不难，感觉这轮做得很差，老印提醒了2次，代码改了
几次， 虽然写出来了，老印最后照了相，知道挂了。心情开始很差。
4）午饭，版上的好心推荐人。
5）白人，设计一个在线图片编辑系统，完全没有经验，只能按版上的partition,
backup, cache等瞎说。边引导边回答。当面给的feedback都还算positive。
真心感觉不难，但只怪自己表现太差，同学们加油啊！！
心里还是很郁闷。但也只能move on。
Tuesday, December 16, 2014
Intersection of Two Linked Lists
idea from leetcode solution:
Two pointer solution (O(n+m) running time, O(1) memory):
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA||!headB) return NULL;
ListNode *lastA=NULL, *lastB=NULL;
ListNode *pA=headA,*pB=headB;
while(true){
if(pA==pB)
return pA;
if(pA->next==NULL)
lastA=pA;
if(pB->next==NULL)
lastB=pB;
if(lastA&&lastB&&lastA!=lastB)
return NULL;
pA=pA->next;
pB=pB->next;
if(pA==NULL)
pA=headB;
else if(pB==NULL)
pB=headA;
}
}
//from anniekim, get the length of both list first.
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * cur = NULL;
int lenA = 0, lenB = 0;
cur = headA;
while (cur) {
++lenA;
cur = cur->next;
}
cur = headB;
while (cur) {
++lenB;
cur = cur->next;
}
if (lenA >= lenB) {
int diff = lenA - lenB;
while (diff > 0) {
headA = headA->next;
--diff;
}
while (headA && headB) {
if(headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
} else {
int diff = lenB - lenA;
while (diff > 0) {
headB = headB->next;
--diff;
}
while (headA && headB) {
if(headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
}
return NULL;
}
Two pointer solution (O(n+m) running time, O(1) memory):
- Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
- When pA reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when pB reaches the end of a list, redirect it the head of A.
- If at any point pA meets pB, then pA/pB is the intersection node.
- To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
- If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA||!headB) return NULL;
ListNode *lastA=NULL, *lastB=NULL;
ListNode *pA=headA,*pB=headB;
while(true){
if(pA==pB)
return pA;
if(pA->next==NULL)
lastA=pA;
if(pB->next==NULL)
lastB=pB;
if(lastA&&lastB&&lastA!=lastB)
return NULL;
pA=pA->next;
pB=pB->next;
if(pA==NULL)
pA=headB;
else if(pB==NULL)
pB=headA;
}
}
//from anniekim, get the length of both list first.
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * cur = NULL;
int lenA = 0, lenB = 0;
cur = headA;
while (cur) {
++lenA;
cur = cur->next;
}
cur = headB;
while (cur) {
++lenB;
cur = cur->next;
}
if (lenA >= lenB) {
int diff = lenA - lenB;
while (diff > 0) {
headA = headA->next;
--diff;
}
while (headA && headB) {
if(headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
} else {
int diff = lenB - lenA;
while (diff > 0) {
headB = headB->next;
--diff;
}
while (headA && headB) {
if(headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
}
return NULL;
}
Monday, December 15, 2014
Google onsite一题
Divide number and return result in form of a string. e.g 100/3 result should
be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5
/10 should be 0.5.
Answer:
想法大概是，每一个iteration保留被除数，商和余数。小数点以后把被除数放在
一个hashtable里
面，如果被除数出现过，就把上一次被除数到这一次被除数之间的商重复。
5/10 返回0.5。有的面经让返回0.5(0)。这里返回0.5(0)。
string get_decimal(int num, int den) {
string ret = to_string(num / den);
ret.push_back('.');
num %= den;
map<int,int> rems;
while(num != 0 && !rems.count(num)) {
rems[num] = (int)ret.size();
num *= 10;
ret.push_back(num / den + '0');
num %= den;
}
if (num != 0) {
ret.insert(ret.begin() + rems[num], '(');
ret += ")";
} else {
ret += "(0)";
}
return ret;
}
be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5
/10 should be 0.5.
Answer:
想法大概是，每一个iteration保留被除数，商和余数。小数点以后把被除数放在
一个hashtable里
面，如果被除数出现过，就把上一次被除数到这一次被除数之间的商重复。
5/10 返回0.5。有的面经让返回0.5(0)。这里返回0.5(0)。
string get_decimal(int num, int den) {
string ret = to_string(num / den);
ret.push_back('.');
num %= den;
map<int,int> rems;
while(num != 0 && !rems.count(num)) {
rems[num] = (int)ret.size();
num *= 10;
ret.push_back(num / den + '0');
num %= den;
}
if (num != 0) {
ret.insert(ret.begin() + rems[num], '(');
ret += ")";
} else {
ret += "(0)";
}
return ret;
}
System Design总结
发信人: flamingos (flamingos), 信区: JobHunting
标 题: 我的System Design总结
发信站: BBS 未名空间站 (Mon Sep 8 02:49:55 2014, 美东)
我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面
试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言
这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目
== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍
2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid
single point of failure
再强调一遍 非常好的资料！
3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想
结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)
== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了
4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看
5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的
6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看
7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic
8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498
9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb
10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems --
twitter的前员工讲述如何处理实时数据
10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等
你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题
最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论
== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?
标 题: 我的System Design总结
发信站: BBS 未名空间站 (Mon Sep 8 02:49:55 2014, 美东)
我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面
试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言
这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目
== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍
2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid
single point of failure
再强调一遍 非常好的资料！
3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想
结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)
== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了
4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看
5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的
6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看
7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic
8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498
9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb
10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems --
twitter的前员工讲述如何处理实时数据
10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等
你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题
最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论
== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?
电面
发信人: xxzbj (xxue), 信区: JobHunting
标 题: G电面面经
发信站: BBS 未名空间站 (Sun Dec 14 11:15:55 2014, 美东)
老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
电面, 希望下次不要碰到这么傻逼的人。
1.
给一个数组
有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
2.
有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。
还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
s += compute(i);
}
return s;
}
这样出错概率就是 np;
问： 如何改第二个函数，让他的出错概率小于p?
我的思路是，for 循环里,再加个循环，写了代码。 最后老印说work, 大多人都这么做
，好像他不满意。这个题怎么做？
3. 考多线程。
给个函数
long sum(int file_ID, int machine_ID){
//return the sum of the numbers in this file using this machine.
}
实现另一个函数，
input: N(N files from 1 to N)， enough machine for using
output; the total sum of these files.
long getAllSum(int N){
}
review:
1.第一题应该是扫一遍，更新min 和 mid，遇到大于mid的就返回
pseudo-code:
设ai是原数组
xi=min{aj|j<i}
yi=min{aj|exist ak<aj k<j<i}
For every i
If ai>y[i-1], done
Elif ai<x[i-1], xi = ai
Else
yi = ai
One pass while updating xi yi
runnable code: xi is the current min value, yi is the current middle value, left is the final min value.
int xi=aVec[0];
int yi=INT_MAX;
int left=xi;
for (int i=1;i<aVec.size();i++)
{
if(aVec[i]>yi){
cout<<left<<" "<<yi<<" "<<aVec[i]<<endl;
break;
}
else if(aVec[i]<=xi)
{xi=aVec[i];}
else
{yi=aVec[i];left=xi;}
}
注意上面aVec[i]<=xi必须要有“=”，否则会出错。因为没有等号的话，可能会进入最后一个else，这样yi和left就相等了。可以运行这个例子：
{82,14,72,14,19,14,78,36,6,23};
another idea for 1
O(n) space, O(n) time
从左到右update minValue, 对于A[i]比minValue大，说明A[i]有小的在左边, 记录在
一个boolean array里面
从右到左update maxValue, 对于A[i]比minValue小，说明A[i]有大的在右边
标 题: G电面面经
发信站: BBS 未名空间站 (Sun Dec 14 11:15:55 2014, 美东)
老印，三个题。电话晚打1个半小时，中间掉线6次，还把我挂了。投诉HR，再安排一次
电面, 希望下次不要碰到这么傻逼的人。
1.
给一个数组
有没有三个下标 i < j < k, 满足A[i] < A[j] < A[k]。
我用2个数组，dp做的。好像不太满意，有没有比较好的解法？
2.
有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。
还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
s += compute(i);
}
return s;
}
这样出错概率就是 np;
问： 如何改第二个函数，让他的出错概率小于p?
我的思路是，for 循环里,再加个循环，写了代码。 最后老印说work, 大多人都这么做
，好像他不满意。这个题怎么做？
3. 考多线程。
给个函数
long sum(int file_ID, int machine_ID){
//return the sum of the numbers in this file using this machine.
}
实现另一个函数，
input: N(N files from 1 to N)， enough machine for using
output; the total sum of these files.
long getAllSum(int N){
}
review:
1.第一题应该是扫一遍，更新min 和 mid，遇到大于mid的就返回
pseudo-code:
设ai是原数组
xi=min{aj|j<i}
yi=min{aj|exist ak<aj k<j<i}
For every i
If ai>y[i-1], done
Elif ai<x[i-1], xi = ai
Else
yi = ai
One pass while updating xi yi
runnable code: xi is the current min value, yi is the current middle value, left is the final min value.
int xi=aVec[0];
int yi=INT_MAX;
int left=xi;
for (int i=1;i<aVec.size();i++)
{
if(aVec[i]>yi){
cout<<left<<" "<<yi<<" "<<aVec[i]<<endl;
break;
}
else if(aVec[i]<=xi)
{xi=aVec[i];}
else
{yi=aVec[i];left=xi;}
}
注意上面aVec[i]<=xi必须要有“=”，否则会出错。因为没有等号的话，可能会进入最后一个else，这样yi和left就相等了。可以运行这个例子：
{82,14,72,14,19,14,78,36,6,23};
another idea for 1
O(n) space, O(n) time
从左到右update minValue, 对于A[i]比minValue大，说明A[i]有小的在左边, 记录在
一个boolean array里面
从右到左update maxValue, 对于A[i]比minValue小，说明A[i]有大的在右边
Saturday, December 13, 2014
Good面试总结
发信人: Mitan009 (aha), 信区: JobHunting
标 题: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Wed Dec 10 22:21:18 2014, 美东)
基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但是究竟现在去还是大公司里先办绿卡，积累几年经验再去，也是有些
纠结的，目前倾向于去其中一家startup，主要concern是hr说主要办Eb2，绿卡可能不
方便走EB1b，另外package也希望能谈高一些。
准备：周围同学有准备1，2天coding就上的，我主要是平时代码写得不多，coding要热
身一下。programming exposed和cc150看了一遍，没有动手写，leecode动手写了，半
年前过了一遍，找工作前又过了一遍。Research也简单准备了下，怎么说high level
idea, 我自己没怎么讲details, 感觉面试官都会问下potential应用之类的问题。
design看了下几篇文章，知道个大意，google的mapreduce, file system, big table,
fb的memcache, unicorn。其他看到过的觉得还不错的design资料，最后一个常见题目
汇总可以过过看，很有帮助:
http://blog.csdn.net/v_july_v/article/details/7382693
https://www.youtube.com/watch?v=-W9F__D3oY4
http://www.mitbbs.com/article_t/JobHunting/32741713.html
另外建议稍微准备下常见数据类的写法(包括generic programming), 我倒是没碰到其
他一些concurrency, database, NP-hard之类的题目.
如果说有什么经验教训的话，我个体采样样本感觉就是要找refer!
我的offer都是找refer投简历的，1家大公司免了phone interview. 2家startup面试的
时候面试官都超级热情, 相反两家电面就挂了的startup是自己网投的，可能是对比强
烈，明显感觉得出面试官语气比较冷淡, 谈话会让人略微不舒服，也可能是我自己修为
不够，
题目倒不难，没想到结果是据信(1家说不match,1家不给feedback)。
面试时，对不同的部分我的基本步骤是
1.coding:
(a) 先确保理解了题意，然后一边想一遍描述思路，coding前和面试官confirm，这时
候要是面试官有其他想法会和你交流，或者给你hint，从中你可以大概知道他们脑子里
预定的解法.
(b) coding
(c) test case (corner cases, negative&positive cases。。。): 一个是确保你自
己写对了，没有粗心之类的错误。另外有时也是一个考察点，这个看时间，大概说说其
实也可以，也有些面试官会直接说不用了，挺好的。
2.design: 其实这部分我没怎么准备，基本就是凭感觉和常识扯蛋，面试前很紧张这部
分，其实后来觉得这部分大多数面试可能都是表现不错，和面试官聊得很开心，可能是
对fresh要求不高吧。我自己给自己定的步骤如下
(a) 分析需求和给个要考虑问题的outline: 可以画画大概前端，后端之类的，然后数
据流啊啥的，这个时候我一般是针对问题本身，但是会提到scale的问题作为一点以后
讨论，不过有的时候scale小和大的方案会不同，所以中间会有一些back and forth.
(b) 根据outline预留的问题开始一个个讨论解决方案, 比如算法，数据结构，
tradeoff.
(c) 一般会有一个估算的问题，比如这个问题多少用户，数据多少字节，算法处理时间
...不确定的数据可以问他是否这个估计make sense.
(d) 根据前面的估算，小scale的时候一个机器就可以解决(不同的问题可能要考虑
cache, memory, disk, cpu)；大scale的时候怎么办？vertical/horizontal scaling,
数据怎么partition, load balancer, index server, backup for single-point
failure, consistency, sharding。。。。。知道什么说什么，可能是fresh, 面试官
倒是没大追根究底为难我.
(e) 只有一家公司让我最后编程实现一个核心的算法，不难，不过这时候时间不够了，
最后就是一个伪代码的思路.
3. 面试调适：要是以前没有面试经验的new grad, 第一次电面或onsite可能会紧张，
我自己挺紧张，不过多面几次就适应了. 另外, 我有两家公司onsite是所有面试都在下
午，要是前两轮太兴奋的话，到后来可能会比较疲劳，中间需要的话可以问面试官稍微
休息下，上个厕所，喝点饮料啥的。
面试伪面经：
公司A：
电面(华人马内基：needle in haystack, sqrt(double)：binary search, 因为是
double需要考虑精度，然后boundary细心些)
onsite:
1. 小印：edit distance简化版，用双指针iterate，中间让我做了几个小改进，比如
constant space(我偷懒，没有iterate到底); 数组里找数，binary search的经典题,
当时还剩10分钟，还要留5分钟问问题，小印让我只描述算法，当时犹豫了下要不要快
速写掉，
但是怕一急出bug; 应该最后没难为我.
2. 华人马内基: expression matching类的经典题, recursion和dp的方法各写一遍，
分析复杂度
3. 东欧人: design常见题
4. 老美: thesis research + 最后5分钟1题小编程...
公司B：免了电面
onsite: 这家一般是白板，但是那天拿了一台笔记本给我用，不过我怕新机器打字不习
惯，还是白板。
1. 华人：几何直线常见题，略微变形：没啥算法，数据结构用hashmap就可以了，直线
的表示我用了点斜式，面试官想让我用斜截式，省一个返回参数，其实一样，最后
output返回直线的时候，转换一下就好了。cache的设计: 我扯到了这是一个online问
题，解决hit，miss，很多heuristic, 常见的是LRU, 有一个所谓的理论保证, 然后实
现思路，数据结构，算法，没让我写.
2. 老美： design
3. 老美： 排列组合常见题，有略微变形，用recursion, backtracking就可以了
4. 不明国籍美女： thesis research，面试官超短裙。。hot。。
5. 前苏联加盟共和国： 常见题 binary search; sorting相关的题目，但是需要
linear time, 要么heap，伪代码实现了下，要么用那个NB的5个一堆的quick sort，后
一个我说了算法，没让我证明和实现. http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-
SelectMasterThm.pdf
公司C：
电面：华人校友 两道tree的问题；第二题没时间了，就描述了思路, 太久了，忘了题
了，记得不难.
onsite:
1. 华人：实际问题，没有什么算法，但是数据结构要想下，用到一个固定长度array的
循环查找更新；
2. 东欧人：实际问题，本质是给定会议起止时间，最多需要几个会议室的问题，然后
有一个扩展是海量数据，需要按照时间partition怎么办，因为一个会议可能跨越多个
partition，有个小trick, 需要不同partition间传递参数.
3. 老美： dp经典题目，不难；还有一个类似log hit的实际问题，描述思路，没让写
code.
4. 华人： design常见题
公司D:
电面：华人校友 recoverBinaryTree from preorder and inorder，需要在网上运行程
序，写test case时需要顺便实现tree的traversal.
onsite:
1. 老美： 一个简单的数据结构类，需要用generic programming
2. 老美： DP问题，就是直线上jump的经典问题，但是加了扩展，有速度，有限的加速
度，需要小心构造dp的表格，其实本质一样，然后描述下扩展到多维的情况。但是。。
。。面试官觉得dp太复杂。。。。然后我写了recursion，但是说这个要exponential，
然后就僵持了，我说你让我用recursion但是还要polynomial time，这个怎么可能，那
我肯定要存中间结果啊，那不就是dp么，中间略过我快崩溃的不知道多久时间，然后面
试官说你phd啊，本科的东西忘了呀，memorization, 我瞬间明白他要让我存中间输入
参数到输出结果的映射，说了下，宾主尽欢。。他说dp的dimension不好，用hashmap是
linear的结构，简单明了，我只好狗腿的附和。然后电脑上写个简单的code，test
3. 华人： thesis research， 问了一道图的遍历的题目，电脑上跑code
4. 老美： 给了个实际问题，其实最后转换下就是字典查找的问题，可以直接比较，
linear time，但是如果海量查询的话，还是先把字典建一个trie tree, 然后让我实现
trie tree的查找，不用construct.
公司E和F电面：
马内基: 电话聊天
越南人:类似tree traversal的问题，输出root到某个node的路径.
华人: 给一个file system, 让找到里面文件内容一样的所有文件，分开存储返回文件
路径，比如输出vector<vector<string>>, inner的vector里存同一个内容的所有文件
路径，给了几个辅助函数，isfile判断是否文件还是文件夹，readfile是一个读取文件
内容的函数. 我假设文件读出来的是string, 用了tree traversal+hashmap做的，不知
道是不是有其他方法.
发信人: Mitan009 (aha), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 01:58:59 2014, 美东)
上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree
发信人: goodluck0 (goodluck), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 02:21:34 2014, 美东)
公司B是google吧，这段时间google给不少PhD免了电面
发信人: Mitan009 (aha), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Mon Dec 15 23:28:09 2014, 美东)
不敢当，我只是fresh屌丝而已。。
常见题链接： http://www.mitbbs.com/article_t/JobHunting/32741713.html
我觉得版上几位大牛总结比较好，你搜搜system design之类的就有了
另外，我总觉得fresh和experience这一块的要求应该不太一样，fresh的感觉common
sense之类的对头，然后对scalability之类的问题有个大概的概念可能就差不多了
【 在 njusz (sz) 的大作中提到: 】
: 大牛能不能具体说说design的常见题和准备方法
标 题: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Wed Dec 10 22:21:18 2014, 美东)
基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但是究竟现在去还是大公司里先办绿卡，积累几年经验再去，也是有些
纠结的，目前倾向于去其中一家startup，主要concern是hr说主要办Eb2，绿卡可能不
方便走EB1b，另外package也希望能谈高一些。
准备：周围同学有准备1，2天coding就上的，我主要是平时代码写得不多，coding要热
身一下。programming exposed和cc150看了一遍，没有动手写，leecode动手写了，半
年前过了一遍，找工作前又过了一遍。Research也简单准备了下，怎么说high level
idea, 我自己没怎么讲details, 感觉面试官都会问下potential应用之类的问题。
design看了下几篇文章，知道个大意，google的mapreduce, file system, big table,
fb的memcache, unicorn。其他看到过的觉得还不错的design资料，最后一个常见题目
汇总可以过过看，很有帮助:
http://blog.csdn.net/v_july_v/article/details/7382693
https://www.youtube.com/watch?v=-W9F__D3oY4
http://www.mitbbs.com/article_t/JobHunting/32741713.html
另外建议稍微准备下常见数据类的写法(包括generic programming), 我倒是没碰到其
他一些concurrency, database, NP-hard之类的题目.
如果说有什么经验教训的话，我个体采样样本感觉就是要找refer!
我的offer都是找refer投简历的，1家大公司免了phone interview. 2家startup面试的
时候面试官都超级热情, 相反两家电面就挂了的startup是自己网投的，可能是对比强
烈，明显感觉得出面试官语气比较冷淡, 谈话会让人略微不舒服，也可能是我自己修为
不够，
题目倒不难，没想到结果是据信(1家说不match,1家不给feedback)。
面试时，对不同的部分我的基本步骤是
1.coding:
(a) 先确保理解了题意，然后一边想一遍描述思路，coding前和面试官confirm，这时
候要是面试官有其他想法会和你交流，或者给你hint，从中你可以大概知道他们脑子里
预定的解法.
(b) coding
(c) test case (corner cases, negative&positive cases。。。): 一个是确保你自
己写对了，没有粗心之类的错误。另外有时也是一个考察点，这个看时间，大概说说其
实也可以，也有些面试官会直接说不用了，挺好的。
2.design: 其实这部分我没怎么准备，基本就是凭感觉和常识扯蛋，面试前很紧张这部
分，其实后来觉得这部分大多数面试可能都是表现不错，和面试官聊得很开心，可能是
对fresh要求不高吧。我自己给自己定的步骤如下
(a) 分析需求和给个要考虑问题的outline: 可以画画大概前端，后端之类的，然后数
据流啊啥的，这个时候我一般是针对问题本身，但是会提到scale的问题作为一点以后
讨论，不过有的时候scale小和大的方案会不同，所以中间会有一些back and forth.
(b) 根据outline预留的问题开始一个个讨论解决方案, 比如算法，数据结构，
tradeoff.
(c) 一般会有一个估算的问题，比如这个问题多少用户，数据多少字节，算法处理时间
...不确定的数据可以问他是否这个估计make sense.
(d) 根据前面的估算，小scale的时候一个机器就可以解决(不同的问题可能要考虑
cache, memory, disk, cpu)；大scale的时候怎么办？vertical/horizontal scaling,
数据怎么partition, load balancer, index server, backup for single-point
failure, consistency, sharding。。。。。知道什么说什么，可能是fresh, 面试官
倒是没大追根究底为难我.
(e) 只有一家公司让我最后编程实现一个核心的算法，不难，不过这时候时间不够了，
最后就是一个伪代码的思路.
3. 面试调适：要是以前没有面试经验的new grad, 第一次电面或onsite可能会紧张，
我自己挺紧张，不过多面几次就适应了. 另外, 我有两家公司onsite是所有面试都在下
午，要是前两轮太兴奋的话，到后来可能会比较疲劳，中间需要的话可以问面试官稍微
休息下，上个厕所，喝点饮料啥的。
面试伪面经：
公司A：
电面(华人马内基：needle in haystack, sqrt(double)：binary search, 因为是
double需要考虑精度，然后boundary细心些)
onsite:
1. 小印：edit distance简化版，用双指针iterate，中间让我做了几个小改进，比如
constant space(我偷懒，没有iterate到底); 数组里找数，binary search的经典题,
当时还剩10分钟，还要留5分钟问问题，小印让我只描述算法，当时犹豫了下要不要快
速写掉，
但是怕一急出bug; 应该最后没难为我.
2. 华人马内基: expression matching类的经典题, recursion和dp的方法各写一遍，
分析复杂度
3. 东欧人: design常见题
4. 老美: thesis research + 最后5分钟1题小编程...
公司B：免了电面
onsite: 这家一般是白板，但是那天拿了一台笔记本给我用，不过我怕新机器打字不习
惯，还是白板。
1. 华人：几何直线常见题，略微变形：没啥算法，数据结构用hashmap就可以了，直线
的表示我用了点斜式，面试官想让我用斜截式，省一个返回参数，其实一样，最后
output返回直线的时候，转换一下就好了。cache的设计: 我扯到了这是一个online问
题，解决hit，miss，很多heuristic, 常见的是LRU, 有一个所谓的理论保证, 然后实
现思路，数据结构，算法，没让我写.
2. 老美： design
3. 老美： 排列组合常见题，有略微变形，用recursion, backtracking就可以了
4. 不明国籍美女： thesis research，面试官超短裙。。hot。。
5. 前苏联加盟共和国： 常见题 binary search; sorting相关的题目，但是需要
linear time, 要么heap，伪代码实现了下，要么用那个NB的5个一堆的quick sort，后
一个我说了算法，没让我证明和实现. http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-
SelectMasterThm.pdf
公司C：
电面：华人校友 两道tree的问题；第二题没时间了，就描述了思路, 太久了，忘了题
了，记得不难.
onsite:
1. 华人：实际问题，没有什么算法，但是数据结构要想下，用到一个固定长度array的
循环查找更新；
2. 东欧人：实际问题，本质是给定会议起止时间，最多需要几个会议室的问题，然后
有一个扩展是海量数据，需要按照时间partition怎么办，因为一个会议可能跨越多个
partition，有个小trick, 需要不同partition间传递参数.
3. 老美： dp经典题目，不难；还有一个类似log hit的实际问题，描述思路，没让写
code.
4. 华人： design常见题
公司D:
电面：华人校友 recoverBinaryTree from preorder and inorder，需要在网上运行程
序，写test case时需要顺便实现tree的traversal.
onsite:
1. 老美： 一个简单的数据结构类，需要用generic programming
2. 老美： DP问题，就是直线上jump的经典问题，但是加了扩展，有速度，有限的加速
度，需要小心构造dp的表格，其实本质一样，然后描述下扩展到多维的情况。但是。。
。。面试官觉得dp太复杂。。。。然后我写了recursion，但是说这个要exponential，
然后就僵持了，我说你让我用recursion但是还要polynomial time，这个怎么可能，那
我肯定要存中间结果啊，那不就是dp么，中间略过我快崩溃的不知道多久时间，然后面
试官说你phd啊，本科的东西忘了呀，memorization, 我瞬间明白他要让我存中间输入
参数到输出结果的映射，说了下，宾主尽欢。。他说dp的dimension不好，用hashmap是
linear的结构，简单明了，我只好狗腿的附和。然后电脑上写个简单的code，test
3. 华人： thesis research， 问了一道图的遍历的题目，电脑上跑code
4. 老美： 给了个实际问题，其实最后转换下就是字典查找的问题，可以直接比较，
linear time，但是如果海量查询的话，还是先把字典建一个trie tree, 然后让我实现
trie tree的查找，不用construct.
公司E和F电面：
马内基: 电话聊天
越南人:类似tree traversal的问题，输出root到某个node的路径.
华人: 给一个file system, 让找到里面文件内容一样的所有文件，分开存储返回文件
路径，比如输出vector<vector<string>>, inner的vector里存同一个内容的所有文件
路径，给了几个辅助函数，isfile判断是否文件还是文件夹，readfile是一个读取文件
内容的函数. 我假设文件读出来的是string, 用了tree traversal+hashmap做的，不知
道是不是有其他方法.
发信人: Mitan009 (aha), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 01:58:59 2014, 美东)
上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree
发信人: goodluck0 (goodluck), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 02:21:34 2014, 美东)
公司B是google吧，这段时间google给不少PhD免了电面
发信人: Mitan009 (aha), 信区: JobHunting
标 题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Mon Dec 15 23:28:09 2014, 美东)
不敢当，我只是fresh屌丝而已。。
常见题链接： http://www.mitbbs.com/article_t/JobHunting/32741713.html
我觉得版上几位大牛总结比较好，你搜搜system design之类的就有了
另外，我总觉得fresh和experience这一块的要求应该不太一样，fresh的感觉common
sense之类的对头，然后对scalability之类的问题有个大概的概念可能就差不多了
【 在 njusz (sz) 的大作中提到: 】
: 大牛能不能具体说说design的常见题和准备方法
Simple Coder: LintCode: Maximum Subarray III
Simple Coder: LintCode: Maximum Subarray III: Given an array of integers and a number k , find k non-overlapping subarrays which have the largest sum. The number in each subarray shoul...
Sunday, December 7, 2014
Populating Next Right Pointers in Each Node II
void connect(TreeLinkNode *root) {
TreeLinkNode * leftWall=root;
while(leftWall){
TreeLinkNode *across=leftWall;
TreeLinkNode *next=NULL;// the first node of next level
TreeLinkNode * pre = NULL; // previous node on the same level
while(across){
if (!next) next = across->left?across->left:across->right;
if(across->left){
if(pre) {pre->next=across->left;}
pre=across->left;
}
if(across->right){
if(pre) {pre->next=across->right;}
pre=across->right;
}
across=across->next;
}
leftWall=next;
}
}
TreeLinkNode * leftWall=root;
while(leftWall){
TreeLinkNode *across=leftWall;
TreeLinkNode *next=NULL;// the first node of next level
TreeLinkNode * pre = NULL; // previous node on the same level
while(across){
if (!next) next = across->left?across->left:across->right;
if(across->left){
if(pre) {pre->next=across->left;}
pre=across->left;
}
if(across->right){
if(pre) {pre->next=across->right;}
pre=across->right;
}
across=across->next;
}
leftWall=next;
}
}
Populating Next Right Pointers in Each Node
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
void connect(TreeLinkNode *root) {
TreeLinkNode * leftWall=root;
while(leftWall)
{
TreeLinkNode * across=leftWall;
while(across)
{
if(across->left)
across->left->next=across->right;
if(across->right&&across->next)
across->right->next=across->next->left;
across=across->next;
}
leftWall=leftWall->left;
}
}
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
void connect(TreeLinkNode *root) {
TreeLinkNode * leftWall=root;
while(leftWall)
{
TreeLinkNode * across=leftWall;
while(across)
{
if(across->left)
across->left->next=across->right;
if(across->right&&across->next)
across->right->next=across->next->left;
across=across->next;
}
leftWall=leftWall->left;
}
}
Saturday, December 6, 2014
fb电面面经 print interval
发信人: pdu (PigDuckUnited), 信区: JobHunting
标 题: fb电面面经
发信站: BBS 未名空间站 (Thu Oct 17 20:02:42 2013, 美东)
给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
例子：
user1:
login_time: 0
logout_time: 1
user2:
login_time: 0
logout_time: 2
user3:
login_time: 1
logout_time: 3
输出：
[0 - 2): 2
[2 - 3): 1
[3 - infinite): 0
0 - 1不用输出，因为时间点0有2个在线用户，时间点1也有2个在线用户，在线用户数
没有变，所以不用输出。在时间点2在线用户数变为1，所以输出0 - 2: 2
完成函数：
struct Log
{
float login_time;
float logout_time;
};
void online_user(vector<Log> &logs);
=====
刚开始是一些behavior question，后来就问了这一个题，算法2分钟就沟通好了，可是
后来代码写得很乱，到最后都还有bug
华人面试官，感觉人挺好的。可惜自己脑抽了，一紧张就出错，一出错更紧张，最后就
搞不定了
最后他建议在面fb之前，先找其他公司的面试，练练状态
这种情况挂了只能怪自己，不能埋怨同胞不留情。move on to next
-----
更新下：刚收到thank you letter @2013-10-29
发信人: pepero (迅哥儿，你忘了那...), 信区: JobHunting
标 题: Re: fb电面面经
发信站: BBS 未名空间站 (Sat Oct 19 09:24:04 2013, 美东)
void online_user(vector<Log> &logs){
if (logs.empty()) return;
map<float, int> table;
for (vector<Log>::const_iterator it = logs.begin();
it != logs.end(); ++it){
table[it->login_time]++;
table[it->logout_time]--;
}
float prev = table.begin()->first;
int num = table.begin()->second;
for (map<float, int>::const_iterator it = ++table.begin();
it!=table.end(); ++it) {
if (it->second!=0) {
cout << "[" << prev << " - " << it->first << ") : " << num <<
endl;
num += it->second;
prev = it->first;
}
}
cout << "[" << prev << " - " << "infinite) : 0 " << endl;
}
Permutation Sequence
string getPermutation(int n, int k) {
string num, res;
int total = 1;
for (int i = 1; i <= n; ++i)
{
num.push_back(i + '0');
total *= i;
}
k--;
while (n)
{
total /= n;
int i = k / total;
k %= total;
res.push_back(num[i]);
num.erase(i, 1);
n--;
}
return res;
}
string num, res;
int total = 1;
for (int i = 1; i <= n; ++i)
{
num.push_back(i + '0');
total *= i;
}
k--;
while (n)
{
total /= n;
int i = k / total;
k %= total;
res.push_back(num[i]);
num.erase(i, 1);
n--;
}
return res;
}
Friday, December 5, 2014
print factors
printFactors(int n)
input:32
output:
1 * 32
2 * 16
2 * 2 * 8
2 * 2 * 2 * 4
2 * 2 * 2 * 2 * 2
2 * 4 * 4
4 * 8
Answer:
vector<vector<int> > printFactors(int n) {
vector<vector<int> > results;
vector<int> result;
recur(n, 2, results, result);
return results;
}
void recur(int n, int start, vector<vector<int> > &results, vector<int> &result)
{
if (n == 1) {
results.push_back(result);
return;
}
for (int i = start; i <= n; ++i) {
if (n%i == 0) {
result.push_back(i);
recur(n/i, i, results, result);
result.pop_back();
}
}
}
input:32
output:
1 * 32
2 * 16
2 * 2 * 8
2 * 2 * 2 * 4
2 * 2 * 2 * 2 * 2
2 * 4 * 4
4 * 8
Answer:
vector<vector<int> > printFactors(int n) {
vector<vector<int> > results;
vector<int> result;
recur(n, 2, results, result);
return results;
}
void recur(int n, int start, vector<vector<int> > &results, vector<int> &result)
{
if (n == 1) {
results.push_back(result);
return;
}
for (int i = start; i <= n; ++i) {
if (n%i == 0) {
result.push_back(i);
recur(n/i, i, results, result);
result.pop_back();
}
}
}
Read4096 - Google Interview Question
Google Interview Question Software Engineer
Given API:
int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.
Answer:
int read(char* buf, int n){
int num_it = n / 4096;
int remain = n % 4096;
int total = 0;
while(num_it--){
int num_read = read4096(buf);
if(num_read == 0) break;
buf += num_read;
total += num_read;
}
if(total != n-remain) return total;
char readbuf[4096];
int num_read = read4096(readbuf);
int num_copy = min(num_read, remain);
copy(readbuf, readbuf + num_copy, buf);
total += num_copy;
return total;
}
Given API:
int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.
Answer:
int read(char* buf, int n){
int num_it = n / 4096;
int remain = n % 4096;
int total = 0;
while(num_it--){
int num_read = read4096(buf);
if(num_read == 0) break;
buf += num_read;
total += num_read;
}
if(total != n-remain) return total;
char readbuf[4096];
int num_read = read4096(readbuf);
int num_copy = min(num_read, remain);
copy(readbuf, readbuf + num_copy, buf);
total += num_copy;
return total;
}
Balanced Binary Tree
from codeganker
这道题是树操作的题目，还是老套路用递归。这道题是求解树是否平衡，还是有一些小技巧的。要判断树是否平衡，根据题目的定义，深度是必需的信息，所以我们 必须维护深度，另一方面我们又要返回是否为平衡树，那么对于左右子树深度差的判断也是必要的。这里我们用一个整数来做返回值，而0或者正数用来表示树的深 度，而-1则用来比较此树已经不平衡了，如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了，否则就利用返回的深度信息看看左右子树是不是 违反平衡条件，如果违反返回-1，否则返回左右子树深度大的加一作为自己的深度即可。算法的时间是一次树的遍历O(n)，空间是栈高度O(logn)。代 码如下：
bool isBalanced(TreeNode *root) {
return help(root)>=0;
}
int help(TreeNode*root){
if(!root) return 0;
int left=help(root->left);
int right=help(root->right);
if(left==-1||right==-1)
return -1;
return abs(left-right)>1?-1:max(left,right)+1;
}
这道题是树操作的题目，还是老套路用递归。这道题是求解树是否平衡，还是有一些小技巧的。要判断树是否平衡，根据题目的定义，深度是必需的信息，所以我们 必须维护深度，另一方面我们又要返回是否为平衡树，那么对于左右子树深度差的判断也是必要的。这里我们用一个整数来做返回值，而0或者正数用来表示树的深 度，而-1则用来比较此树已经不平衡了，如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了，否则就利用返回的深度信息看看左右子树是不是 违反平衡条件，如果违反返回-1，否则返回左右子树深度大的加一作为自己的深度即可。算法的时间是一次树的遍历O(n)，空间是栈高度O(logn)。代 码如下：
bool isBalanced(TreeNode *root) {
return help(root)>=0;
}
int help(TreeNode*root){
if(!root) return 0;
int left=help(root->left);
int right=help(root->right);
if(left==-1||right==-1)
return -1;
return abs(left-right)>1?-1:max(left,right)+1;
}
Thursday, December 4, 2014
Remove Duplicates from Sorted Array II
int removeDuplicates(int A[], int n) {
if(n==0) return 0;
int dup=0;
int len=1;
for(int i=1;i<n;i++){
if(A[i]==A[i-1]){
dup++;
if(dup<2)
A[len++]=A[i];
}
else{
A[len++]=A[i];
dup=0;
}
}
return len;
}
if(n==0) return 0;
int dup=0;
int len=1;
for(int i=1;i<n;i++){
if(A[i]==A[i-1]){
dup++;
if(dup<2)
A[len++]=A[i];
}
else{
A[len++]=A[i];
dup=0;
}
}
return len;
}
Remove Duplicates from Sorted Array
int removeDuplicates(int A[], int n) {
if(n==0)
return 0;
int len=1;
for(int i=1;i<n;i++)
{
if(A[i]!=A[i-1])
A[len++]=A[i];
}
return len;
}
if(n==0)
return 0;
int len=1;
for(int i=1;i<n;i++)
{
if(A[i]!=A[i-1])
A[len++]=A[i];
}
return len;
}
电面 - use trie
2014-10-25google 电面
Use the shorest unique prefix to represent each word in the array
input: ["zebra", "dog", "duck",”dot”]
output: {zebra: z, dog: dog, duck: du, dot:dot}
[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}
如果某个字符串是另外一个的前缀，那是没法表示的，所以就返回空
[bearcat, bear]
{bearcat: bearc, bear: ""}
{ab，abb，abbb}
{abbb:abbb;abb:"";ab:""}
Answer: use a trie(note that a trie is also called a prefix tree), for every char in the word increase the count of the corresponding node by one. Then for every word, find the first node that has the count of value 1.
class PrefixTreeNode{
public:
PrefixTreeNode(int c){
count=c;
for(int i=0;i<26;i++)
children[i]=NULL;
}
int count;
PrefixTreeNode*children[26];
};
class ShortestUniquePrefixTree{
public:
PrefixTreeNode*root;
ShortestUniquePrefixTree(){
root=new PrefixTreeNode(0);
}
void insert(string word){
PrefixTreeNode*tmp=root;
for(int i=0;i<word.length();i++){
if(tmp->children[word[i]-'a']!=NULL)
tmp->children[word[i]-'a']->
else
tmp->children[word[i]-'a']=new PrefixTreeNode(1);
tmp=tmp->children[word[i]-'a']
}
}
string getShortestUniquePrefix(string word){
PrefixTreeNode*tmp=root;
for(int i=0;i<word.length();i++){
if(tmp->children[word[i]-'a']=
else if(tmp->children[word[i]-'a']-
return word.substr(0,i+1);
else
tmp=tmp->children[word[i]-'a']
}
//if(tmp->count>1)
return "";
}
};
Use the shorest unique prefix to represent each word in the array
input: ["zebra", "dog", "duck",”dot”]
output: {zebra: z, dog: dog, duck: du, dot:dot}
[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}
如果某个字符串是另外一个的前缀，那是没法表示的，所以就返回空
[bearcat, bear]
{bearcat: bearc, bear: ""}
{ab，abb，abbb}
{abbb:abbb;abb:"";ab:""}
Answer: use a trie(note that a trie is also called a prefix tree), for every char in the word increase the count of the corresponding node by one. Then for every word, find the first node that has the count of value 1.
class PrefixTreeNode{
public:
PrefixTreeNode(int c){
count=c;
for(int i=0;i<26;i++)
children[i]=NULL;
}
int count;
PrefixTreeNode*children[26];
};
class ShortestUniquePrefixTree{
public:
PrefixTreeNode*root;
ShortestUniquePrefixTree(){
root=new PrefixTreeNode(0);
}
void insert(string word){
PrefixTreeNode*tmp=root;
for(int i=0;i<word.length();i++){
if(tmp->children[word[i]-'a']!=NULL)
tmp->children[word[i]-'a']->
else
tmp->children[word[i]-'a']=new PrefixTreeNode(1);
tmp=tmp->children[word[i]-'a']
}
}
string getShortestUniquePrefix(string word){
PrefixTreeNode*tmp=root;
for(int i=0;i<word.length();i++){
if(tmp->children[word[i]-'a']=
else if(tmp->children[word[i]-'a']-
return word.substr(0,i+1);
else
tmp=tmp->children[word[i]-'a']
}
//if(tmp->count>1)
return "";
}
};
Merge Sorted Array
void merge(int A[], int m, int B[], int n) {
int pos=m+n-1;
int i=m-1,j=n-1;
while(i>=0&&j>=0){
if(A[i]>B[j]){
A[pos--]=A[i--];
}
else{
A[pos--]=B[j--];
}
}
while(j>=0)
A[pos--]=B[j--];
}
int pos=m+n-1;
int i=m-1,j=n-1;
while(i>=0&&j>=0){
if(A[i]>B[j]){
A[pos--]=A[i--];
}
else{
A[pos--]=B[j--];
}
}
while(j>=0)
A[pos--]=B[j--];
}
zigzag print matrix - google interview question
zigzag打印矩阵
e.g.
input:
a b c
d e f
g h i
output:
adbceghfi
Answer: just simulate the move
1)start at i=1, j=1
2)move down once(i++) OR move right if you are at the bottom side
3)move in north east direction until you are reached top or right side
4)move right once if you are at top side OR move down once if you are at right side
5)move in south west direction until you are reached bottom or left side
6)go to step2 if you are still in the range
void print(vector<string>&matrix){
int row=matrix.size();
int col=matrix[0].length();
int i=0,j=0;
do{
cout<<matrix[i][j]<<" ";
if(i<row-1)
i++;
else if(j<col-1)
j++;
else//already finished printing
break;
//NE(north east) direction
while(i>0&&j<col-1){
cout<<matrix[i][j]<<" ";
i--;j++;
}
cout<<matrix[i][j]<<" ";
if(i==0&&j<col-1)
j++;
else
i++;
while(i<row-1&&j>0){//SW direction
cout<<matrix[i][j]<<" ";
i++;j--;
}
}while(i<=row-1&&j<=col-1);
cout<<endl;
}
e.g.
input:
a b c
d e f
g h i
output:
adbceghfi
Answer: just simulate the move
1)start at i=1, j=1
2)move down once(i++) OR move right if you are at the bottom side
3)move in north east direction until you are reached top or right side
4)move right once if you are at top side OR move down once if you are at right side
5)move in south west direction until you are reached bottom or left side
6)go to step2 if you are still in the range
void print(vector<string>&matrix){
int row=matrix.size();
int col=matrix[0].length();
int i=0,j=0;
do{
cout<<matrix[i][j]<<" ";
if(i<row-1)
i++;
else if(j<col-1)
j++;
else//already finished printing
break;
//NE(north east) direction
while(i>0&&j<col-1){
cout<<matrix[i][j]<<" ";
i--;j++;
}
cout<<matrix[i][j]<<" ";
if(i==0&&j<col-1)
j++;
else
i++;
while(i<row-1&&j>0){//SW direction
cout<<matrix[i][j]<<" ";
i++;j--;
}
}while(i<=row-1&&j<=col-1);
cout<<endl;
}
Count Inversions in an array - use merge sort
观察归并排序——合并数列(1，3，5)与(2，4)的时候：
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：
//从归并排序到数列的逆序数对
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) //a[i] 前面的数 a[j] 后面的数
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
//a[j]和前面每一个数都能组成逆序数对
g_nCount += m - i + 1;
}
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
void MergeSort(int a[], int n)
{
int *p = new int[n];
mergesort(a, 0, n - 1, p);
}
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：
//从归并排序到数列的逆序数对
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) //a[i] 前面的数 a[j] 后面的数
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
//a[j]和前面每一个数都能组成逆序数对
g_nCount += m - i + 1;
}
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
void MergeSort(int a[], int n)
{
int *p = new int[n];
mergesort(a, 0, n - 1, p);
}
Wednesday, December 3, 2014
Interview Question - use kmp
Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
Find the length of the shortest palindrome that you can create from S by applying the above transformation.
Answer:
Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.
prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.
int getPalindrome(string s) {
int n = s.size();
vector<int> p(2*n+1,0);
string current = s + '$';
for (int i = 0; i < n; i++) {
current += s[n - 1 - i];
}
p[0] = 0;
for (int i = 1; i < 2 * n + 1; i++) {
int j = p[i - 1];
while (j > 0 && current[j] != current[i])
j = p[j - 1];
j += current[i] == current[j];
p[i] = j;
}
return 2 *n - p[2 * n];//returns the length of the palindrome formed
}
Find the length of the shortest palindrome that you can create from S by applying the above transformation.
Answer:
Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.
prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.
int getPalindrome(string s) {
int n = s.size();
vector<int> p(2*n+1,0);
string current = s + '$';
for (int i = 0; i < n; i++) {
current += s[n - 1 - i];
}
p[0] = 0;
for (int i = 1; i < 2 * n + 1; i++) {
int j = p[i - 1];
while (j > 0 && current[j] != current[i])
j = p[j - 1];
j += current[i] == current[j];
p[i] = j;
}
return 2 *n - p[2 * n];//returns the length of the palindrome formed
}
Word Ladder
int ladderLength(string start, string end, unordered_set<string> &dict) {
int ret = 0;
if (start == end)
return ret;
unordered_set<string> added;
queue<string> que;
int lev1 = 1;
int lev2 = 0;
que.push(start);
added.insert(start);
while (!que.empty()) {
string s = que.front();
que.pop();
--lev1;
for (int i = 0; i < s.length(); ++i) {
char before=s[i];
for (int j = 0; j < 26; ++j) {
s[i] = 'a' + j;
if (s == end)
return ret + 2;
if (dict.find(s) != dict.end()
&& added.find(s) == added.end()) {
que.push(s);
added.insert(s);
++lev2;
}
}
s[i]=before;
}
if (lev1 == 0) {
++ret;
lev1 = lev2;
lev2 = 0;
}
}
return 0;
}
//another flavor, by annikim
int ladderLength(string start, string end, unordered_set<string> &dict) {
queue<pair<string,int>> que;
que.push(make_pair(start,1));
while(!que.empty()){
pair<string,int> front=que.front();que.pop();
string word=front.first;
for(int i=0;i<word.length();i++){
char before=word[i];
for(char c='a';c<='z';c++){
word[i]=c;
if(word==end) return front.second+1;
if(dict.find(word)!=dict.end()){
que.push(make_pair(word,front.second+1));
dict.erase(word);
}
}
word[i]=before;
}
}
return 0;
}
int ret = 0;
if (start == end)
return ret;
unordered_set<string> added;
queue<string> que;
int lev1 = 1;
int lev2 = 0;
que.push(start);
added.insert(start);
while (!que.empty()) {
string s = que.front();
que.pop();
--lev1;
for (int i = 0; i < s.length(); ++i) {
char before=s[i];
for (int j = 0; j < 26; ++j) {
s[i] = 'a' + j;
if (s == end)
return ret + 2;
if (dict.find(s) != dict.end()
&& added.find(s) == added.end()) {
que.push(s);
added.insert(s);
++lev2;
}
}
s[i]=before;
}
if (lev1 == 0) {
++ret;
lev1 = lev2;
lev2 = 0;
}
}
return 0;
}
//another flavor, by annikim
int ladderLength(string start, string end, unordered_set<string> &dict) {
queue<pair<string,int>> que;
que.push(make_pair(start,1));
while(!que.empty()){
pair<string,int> front=que.front();que.pop();
string word=front.first;
for(int i=0;i<word.length();i++){
char before=word[i];
for(char c='a';c<='z';c++){
word[i]=c;
if(word==end) return front.second+1;
if(dict.find(word)!=dict.end()){
que.push(make_pair(word,front.second+1));
dict.erase(word);
}
}
word[i]=before;
}
}
return 0;
}
Binary Tree Level Order Traversal
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > ret;
if (!root) return ret;
TreeNode*pointer=root;
queue<TreeNode*> aQueue;
aQueue.push(pointer);
vector<int> temp;
int curlevel=1,nextlevel=0;
while(!aQueue.empty())
{
curlevel--;
pointer=aQueue.front();
aQueue.pop();
temp.push_back(pointer->val);
if (pointer->left)
{aQueue.push(pointer->left); nextlevel++;}
if (pointer->right)
{aQueue.push(pointer->right); nextlevel++;}
if (curlevel==0)
{
ret.push_back(temp);
temp.clear();
curlevel=nextlevel;
nextlevel=0;
}
}
return ret;
}
//another flavor, using NULL mark, by anniekim
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (!node)
{
res.push_back(level);
level.clear();
if (q.empty()) break; // end
q.push(NULL);
}
else
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
//another flavor
vector<vector<int> > levelOrder(TreeNode *root) {
if (!root) return vector<vector<int> >();
TreeNode*pointer=root;
queue<TreeNode*> currentLevel, nextLevel;
currentLevel.push(pointer);
vector<vector<int> > ret;
while(!currentLevel.empty()||!nextLevel.empty())
{
vector<int> temp1,temp2;
while(!currentLevel.empty())
{
pointer=currentLevel.front();
currentLevel.pop();
temp1.push_back(pointer->val);
if (pointer->left)
nextLevel.push(pointer->left);
if (pointer->right)
nextLevel.push(pointer->right);
}
while(!nextLevel.empty())
{
pointer=nextLevel.front();
nextLevel.pop();
temp2.push_back(pointer->val);
if (pointer->left)
currentLevel.push(pointer->left);
if (pointer->right)
currentLevel.push(pointer->right);
}
ret.push_back(temp1);
if(temp2.size()>0)
ret.push_back(temp2);
}
return ret;
}
vector<vector<int> > ret;
if (!root) return ret;
TreeNode*pointer=root;
queue<TreeNode*> aQueue;
aQueue.push(pointer);
vector<int> temp;
int curlevel=1,nextlevel=0;
while(!aQueue.empty())
{
curlevel--;
pointer=aQueue.front();
aQueue.pop();
temp.push_back(pointer->val);
if (pointer->left)
{aQueue.push(pointer->left); nextlevel++;}
if (pointer->right)
{aQueue.push(pointer->right); nextlevel++;}
if (curlevel==0)
{
ret.push_back(temp);
temp.clear();
curlevel=nextlevel;
nextlevel=0;
}
}
return ret;
}
//another flavor, using NULL mark, by anniekim
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (!node)
{
res.push_back(level);
level.clear();
if (q.empty()) break; // end
q.push(NULL);
}
else
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
//another flavor
vector<vector<int> > levelOrder(TreeNode *root) {
if (!root) return vector<vector<int> >();
TreeNode*pointer=root;
queue<TreeNode*> currentLevel, nextLevel;
currentLevel.push(pointer);
vector<vector<int> > ret;
while(!currentLevel.empty()||!nextLevel.empty())
{
vector<int> temp1,temp2;
while(!currentLevel.empty())
{
pointer=currentLevel.front();
currentLevel.pop();
temp1.push_back(pointer->val);
if (pointer->left)
nextLevel.push(pointer->left);
if (pointer->right)
nextLevel.push(pointer->right);
}
while(!nextLevel.empty())
{
pointer=nextLevel.front();
nextLevel.pop();
temp2.push_back(pointer->val);
if (pointer->left)
currentLevel.push(pointer->left);
if (pointer->right)
currentLevel.push(pointer->right);
}
ret.push_back(temp1);
if(temp2.size()>0)
ret.push_back(temp2);
}
return ret;
}
Surrounded Regions
from codeganker
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的'O'是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法， 把所有边缘上的'O'都替换成另一个字符，比如'#'。接下来我们知道除去被我们换成'#'的那些顶点，剩下的所有'O'都应该被替换成'X'，而'#' 那些最终应该是还原成'O'，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法， 因为只有是'O'才会进行，而且会被替换成'#'，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所 以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度 优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是 n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
class Solution {
public:
void solve(vector<vector<char>> & board) {
if(board.size()<=1 || board[0].size()<=1)
return;
for(int i=0;i<board[0].size();i++)
{
fill(board,0,i);
fill(board,board.size()-1,i);
}
for(int i=0;i<board.size();i++)
{
fill(board,i,0);
fill(board,i,board[0].size()-1);
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='#')
board[i][j]='O';
}
}
}
void fill(vector<vector<char>> & board, int i, int j)
{
if(board[i][j]!='O')
return;
board[i][j] = '#';
queue<int> queue;
int code = i*board[0].size()+j;
const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue.push(code);
while(!queue.empty())
{
code = queue.front();queue.pop();
int row = code/board[0].size();
int col = code%board[0].size();
for(int i=0;i<4;i++){
int currow=row+dir[i][0];
int curcol=col+dir[i][1];
if(currow>=0&&currow<board.size()&&curcol>=0&&curcol<board[0].size()){
if(board[currow][curcol]=='O'){
board[currow][curcol]='#';
queue.push(currow*board[0].size()+curcol);
}
}
}
}
}
};
//another flavor, from anniekim
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solve(BOARDTYPE &board) {
if (board.empty() || board[0].empty()) return;
int N = board.size(), M = board[0].size();
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (i == 0 || j == 0 || i == N-1 || j == M-1)
bfs(board, i, j); // you may call dfs or bfs here!
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
}
void dfs(BOARDTYPE &board, int row, int col) {
int N = board.size(), M = board[0].size();
if (row < 0 || row >= N || col < 0 || col >= M) return;
if (board[row][col] != 'O') return;
board[row][col] = 'V';
dfs(board, row+1, col);
dfs(board, row-1, col);
dfs(board, row, col+1);
dfs(board, row, col-1);
}
void bfs(BOARDTYPE &board, int row, int col) {
if (board[row][col] != 'O') return;
int N = board.size(), M = board[0].size();
queue<pair<int, int>> q;
q.push(make_pair(row, col));
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
if (i < 0 || i >= N || j < 0 || j >= M) continue;
if (board[i][j] != 'O') continue;// important to recheck!
board[i][j] = 'V';
q.push(make_pair(i-1, j));
q.push(make_pair(i+1, j));
q.push(make_pair(i, j-1));
q.push(make_pair(i, j+1));
}
}
};
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的'O'是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法， 把所有边缘上的'O'都替换成另一个字符，比如'#'。接下来我们知道除去被我们换成'#'的那些顶点，剩下的所有'O'都应该被替换成'X'，而'#' 那些最终应该是还原成'O'，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法， 因为只有是'O'才会进行，而且会被替换成'#'，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所 以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度 优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是 n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
class Solution {
public:
void solve(vector<vector<char>> & board) {
if(board.size()<=1 || board[0].size()<=1)
return;
for(int i=0;i<board[0].size();i++)
{
fill(board,0,i);
fill(board,board.size()-1,i);
}
for(int i=0;i<board.size();i++)
{
fill(board,i,0);
fill(board,i,board[0].size()-1);
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='#')
board[i][j]='O';
}
}
}
void fill(vector<vector<char>> & board, int i, int j)
{
if(board[i][j]!='O')
return;
board[i][j] = '#';
queue<int> queue;
int code = i*board[0].size()+j;
const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue.push(code);
while(!queue.empty())
{
code = queue.front();queue.pop();
int row = code/board[0].size();
int col = code%board[0].size();
for(int i=0;i<4;i++){
int currow=row+dir[i][0];
int curcol=col+dir[i][1];
if(currow>=0&&currow<board.size()&&curcol>=0&&curcol<board[0].size()){
if(board[currow][curcol]=='O'){
board[currow][curcol]='#';
queue.push(currow*board[0].size()+curcol);
}
}
}
}
}
};
//another flavor, from anniekim
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solve(BOARDTYPE &board) {
if (board.empty() || board[0].empty()) return;
int N = board.size(), M = board[0].size();
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (i == 0 || j == 0 || i == N-1 || j == M-1)
bfs(board, i, j); // you may call dfs or bfs here!
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
}
void dfs(BOARDTYPE &board, int row, int col) {
int N = board.size(), M = board[0].size();
if (row < 0 || row >= N || col < 0 || col >= M) return;
if (board[row][col] != 'O') return;
board[row][col] = 'V';
dfs(board, row+1, col);
dfs(board, row-1, col);
dfs(board, row, col+1);
dfs(board, row, col-1);
}
void bfs(BOARDTYPE &board, int row, int col) {
if (board[row][col] != 'O') return;
int N = board.size(), M = board[0].size();
queue<pair<int, int>> q;
q.push(make_pair(row, col));
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
if (i < 0 || i >= N || j < 0 || j >= M) continue;
if (board[i][j] != 'O') continue;// important to recheck!
board[i][j] = 'V';
q.push(make_pair(i-1, j));
q.push(make_pair(i+1, j));
q.push(make_pair(i, j-1));
q.push(make_pair(i, j+1));
}
}
};
Tuesday, December 2, 2014
Hash table vs Binary search tree
from here
Hash table and binary search tree are two fundamental data structures in CS. When would you want to use one over another one? What is the difference? This is a common interview question that I had most frequently been asked.
Well, it is not easy to answer by one or two sentences. The main difference between hash table and trees is on two aspects: Implementation details and behaviors and performance under different circumstance.
Let me start with implementation. Hash table uses hash function to assign index to input data and put data into array under corresponding index. If the size of hash table is 100, hash function can generate 0~99 to input data and store them into hash table. Theoretically, time complexity of insertion and looking-up is constant time (O(1)).
Binary search tree is implemented as the rule that all left children’s values are less than root, while all right children’s value are greater than it. If the tree is balanced, it always takes O(log(n)) time to insert a new node or look up.O(log(n)) is not as fast as constant time but rather fast. n is the total number in tree and log(n) is usually depth of tree. Notice that I mentioned if it is balanced tree, however there are sophisticated algorithm (e.g., RB tree) to maintain tree balanced.
It seems we can prefer hash table over tree, but it is not always the case. Hash table has significant drawbacks:
1. As more data input comes, there is huge probability that collision shows up (hash function maps different data to same index). There are two ways to handle collision. First is linear probing that implement hash table as array of linked list. In this case, worst time for insertion or retrieve or deletion is O(n) that all input data are mapped to same index. Besides, hash table need more space than number of input data. Second way is open addressing. It would not consume more space than input data, but at worst case insertion and retrieve is still O(n), which is extremely slow than constant time.
2. You have to know approximate size of input data before initializing hash table. Otherwise you need to resize hash table which is a very time-consuming operation. For example, your hash table size is 100 and then you want to insert the 101st element. Not only the size of hash table is enlarged to 150, all element in hash table have to be rehashed. This insertion operation takes O(n).
3. The elements stored in hash table are unsorted. In certain circumstance, we want data to be stored with sorted order, like contacts in cell phone.
However, binary search tree performs well against hash table:
1. Binary search tree never meets collision, which means binary search tree can guarantee insertion, retrieve and deletion are implemented in O(log(n)), which is hugely fast than linear time. Besides, space needed by tree is exactly same as size of input data.
2. You do not need to know size of input in advance.
3. all elements in tree are sorted that in-order traverse takes O(n) time.
OK, let me make a summary.
If you know how many data to maintain, and have enough space to store hash table and do not need data to be sorted, hash table is always good choice. Because, hash table provides constant time operation for insertion, retrieve and deletion. On the other hand, if items will be consistently added, binary search tree’s O(log(n)) operation is acceptable, comparing with rehashing operation during running time.
Besides, If you actually do not know size of input items, but after inserting, most operations are item looking up, hash table is preferred due to constant retrieve time. However, if items are continuously added or removed, tree’s O(log(n)) insertion and deletion time are more suitable in this condition.
In a word, there is no one answer that hash table or tree is better. All we need to know is pros and cons of hash table and tree in different conditions. Best decision can be made with knowledge of benefits and trade-offs of these two structures.
Hash table and binary search tree are two fundamental data structures in CS. When would you want to use one over another one? What is the difference? This is a common interview question that I had most frequently been asked.
Well, it is not easy to answer by one or two sentences. The main difference between hash table and trees is on two aspects: Implementation details and behaviors and performance under different circumstance.
Let me start with implementation. Hash table uses hash function to assign index to input data and put data into array under corresponding index. If the size of hash table is 100, hash function can generate 0~99 to input data and store them into hash table. Theoretically, time complexity of insertion and looking-up is constant time (O(1)).
Binary search tree is implemented as the rule that all left children’s values are less than root, while all right children’s value are greater than it. If the tree is balanced, it always takes O(log(n)) time to insert a new node or look up.O(log(n)) is not as fast as constant time but rather fast. n is the total number in tree and log(n) is usually depth of tree. Notice that I mentioned if it is balanced tree, however there are sophisticated algorithm (e.g., RB tree) to maintain tree balanced.
It seems we can prefer hash table over tree, but it is not always the case. Hash table has significant drawbacks:
1. As more data input comes, there is huge probability that collision shows up (hash function maps different data to same index). There are two ways to handle collision. First is linear probing that implement hash table as array of linked list. In this case, worst time for insertion or retrieve or deletion is O(n) that all input data are mapped to same index. Besides, hash table need more space than number of input data. Second way is open addressing. It would not consume more space than input data, but at worst case insertion and retrieve is still O(n), which is extremely slow than constant time.
2. You have to know approximate size of input data before initializing hash table. Otherwise you need to resize hash table which is a very time-consuming operation. For example, your hash table size is 100 and then you want to insert the 101st element. Not only the size of hash table is enlarged to 150, all element in hash table have to be rehashed. This insertion operation takes O(n).
3. The elements stored in hash table are unsorted. In certain circumstance, we want data to be stored with sorted order, like contacts in cell phone.
However, binary search tree performs well against hash table:
1. Binary search tree never meets collision, which means binary search tree can guarantee insertion, retrieve and deletion are implemented in O(log(n)), which is hugely fast than linear time. Besides, space needed by tree is exactly same as size of input data.
2. You do not need to know size of input in advance.
3. all elements in tree are sorted that in-order traverse takes O(n) time.
OK, let me make a summary.
If you know how many data to maintain, and have enough space to store hash table and do not need data to be sorted, hash table is always good choice. Because, hash table provides constant time operation for insertion, retrieve and deletion. On the other hand, if items will be consistently added, binary search tree’s O(log(n)) operation is acceptable, comparing with rehashing operation during running time.
Besides, If you actually do not know size of input items, but after inserting, most operations are item looking up, hash table is preferred due to constant retrieve time. However, if items are continuously added or removed, tree’s O(log(n)) insertion and deletion time are more suitable in this condition.
In a word, there is no one answer that hash table or tree is better. All we need to know is pros and cons of hash table and tree in different conditions. Best decision can be made with knowledge of benefits and trade-offs of these two structures.
Longest Substring Without Repeating Characters
int lengthOfLongestSubstring(string s) {
int n=s.length();
int i=0,j=0,maxLen=0;
bool exist[256]={false};
while(j<n){
if(exist[s[j]]){
maxLen=max(maxLen,j-i);
while(s[i]!=s[j]){
exist[s[i]]=false;
i++;
}
i++;
j++;
}
else{
exist[s[j]]=true;
j++;
}
}
return max(maxLen,n-i);
}
//same idea, more concise
int lengthOfLongestSubstring(string s) {
bool exist[256]={false};
int res = 0;
int start = 0, end = 0, N = s.size();
while (end < N && start + res < N)
{
if (!exist[s[end]])
exist[s[end++]] = true;
else
exist[s[start++]] = false;
res = max(end - start, res);
}
return res;
}
int n=s.length();
int i=0,j=0,maxLen=0;
bool exist[256]={false};
while(j<n){
if(exist[s[j]]){
maxLen=max(maxLen,j-i);
while(s[i]!=s[j]){
exist[s[i]]=false;
i++;
}
i++;
j++;
}
else{
exist[s[j]]=true;
j++;
}
}
return max(maxLen,n-i);
}
//same idea, more concise
int lengthOfLongestSubstring(string s) {
bool exist[256]={false};
int res = 0;
int start = 0, end = 0, N = s.size();
while (end < N && start + res < N)
{
if (!exist[s[end]])
exist[s[end++]] = true;
else
exist[s[start++]] = false;
res = max(end - start, res);
}
return res;
}
Maximum Subarray
int maxSubArray(int A[], int n) {
vector<int > dp(n,0);
dp[0]=A[0];
int amax=A[0];
for(int i=1;i<n;i++){
dp[i]=A[i]+(dp[i-1]>0?dp[i-1]:0);
amax=max(dp[i],amax);
}
return amax;
}
//less space
int maxSubArray(int A[], int n) {
int mx,pre;
mx=pre=A[0];
for(int i=1;i<n;i++){
if(pre>0)
{pre+=A[i];}
else
pre=A[i];
if(pre>mx) mx=pre;
}
return mx;
}
vector<int > dp(n,0);
dp[0]=A[0];
int amax=A[0];
for(int i=1;i<n;i++){
dp[i]=A[i]+(dp[i-1]>0?dp[i-1]:0);
amax=max(dp[i],amax);
}
return amax;
}
//less space
int maxSubArray(int A[], int n) {
int mx,pre;
mx=pre=A[0];
for(int i=1;i<n;i++){
if(pre>0)
{pre+=A[i];}
else
pre=A[i];
if(pre>mx) mx=pre;
}
return mx;
}
Word Break II
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> res;
if (!wordBreakPossible(s, dict)) return res;
wordBreakRe(s, dict, 0, "", res);
return res;
}
void wordBreakRe(const string &s, const unordered_set<string> &dict,
int start, string sentence, vector<string> &res) {
if (start == s.size()) {
res.push_back(sentence);
return;
}
if (start != 0) sentence.push_back(' ');
for (int i = start; i < s.size(); ++i) {
string word = s.substr(start, i-start+1);
if (dict.find(word) == dict.end())
continue;
wordBreakRe(s, dict, i+1, sentence + word, res);
}
}
bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {
int N = s.size();
bool canBreak[N+1];
memset(canBreak, false, sizeof(canBreak));
canBreak[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = i-1; j >= 0; --j) {
if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
canBreak[i] = true;
break;
}
}
}
return canBreak[N];
}
};
//another flavor
class Solution {
public:
//From right to left, compute the start index such that the substring[start ,current] is in the dictionary. Then backtrace from the beginning.
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<list<int>> mark(s.length(),list<int>());
for(int stop=s.length();stop>=0;stop--){
if(stop<s.length()&&mark[stop].empty()) continue;
for(int start=stop-1;start>=0;start--){
if(dict.count(s.substr(start,stop-start)))
mark[start].push_back(stop);
}
}
vector<string> result;
collect(mark,0,s,"",result);
return result;
}
void collect(vector<list<int>>& mark, int ind, const string& s,
string path, vector<string>& result){
for(auto& stop:mark[ind]){
string sub =s.substr(ind,stop-ind);
string newpath=path+(ind==0?sub:" "+sub);
if(stop==s.length()) result.push_back(newpath);
else collect(mark,stop,s,newpath,result);
}
}
};
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> res;
if (!wordBreakPossible(s, dict)) return res;
wordBreakRe(s, dict, 0, "", res);
return res;
}
void wordBreakRe(const string &s, const unordered_set<string> &dict,
int start, string sentence, vector<string> &res) {
if (start == s.size()) {
res.push_back(sentence);
return;
}
if (start != 0) sentence.push_back(' ');
for (int i = start; i < s.size(); ++i) {
string word = s.substr(start, i-start+1);
if (dict.find(word) == dict.end())
continue;
wordBreakRe(s, dict, i+1, sentence + word, res);
}
}
bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {
int N = s.size();
bool canBreak[N+1];
memset(canBreak, false, sizeof(canBreak));
canBreak[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = i-1; j >= 0; --j) {
if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
canBreak[i] = true;
break;
}
}
}
return canBreak[N];
}
};
//another flavor
class Solution {
public:
//From right to left, compute the start index such that the substring[start ,current] is in the dictionary. Then backtrace from the beginning.
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<list<int>> mark(s.length(),list<int>());
for(int stop=s.length();stop>=0;stop--){
if(stop<s.length()&&mark[stop].empty()) continue;
for(int start=stop-1;start>=0;start--){
if(dict.count(s.substr(start,stop-start)))
mark[start].push_back(stop);
}
}
vector<string> result;
collect(mark,0,s,"",result);
return result;
}
void collect(vector<list<int>>& mark, int ind, const string& s,
string path, vector<string>& result){
for(auto& stop:mark[ind]){
string sub =s.substr(ind,stop-ind);
string newpath=path+(ind==0?sub:" "+sub);
if(stop==s.length()) result.push_back(newpath);
else collect(mark,stop,s,newpath,result);
}
}
};
Word Break
wordB[i] means whether the substring [0, i] is true.
bool wordBreak(string s, unordered_set<string> &dict) {
vector<bool> wordB(s.length() + 1, false);
wordB[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = i - 1; j >= 0; j--) {
if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
wordB[i] = true;
break;
}
}
}
return wordB[s.length()];
}
bool wordBreak(string s, unordered_set<string> &dict) {
vector<bool> wordB(s.length() + 1, false);
wordB[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = i - 1; j >= 0; j--) {
if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
wordB[i] = true;
break;
}
}
}
return wordB[s.length()];
}
Monday, December 1, 2014
Lowest Common Ancestor of a Binary Tree
geeksforgeeks
leetcode
Lowest Common Ancestor of binary search tree
Lowest Common Ancestor of a Binary Tree with parent pointer:
way 1, use a hashmap to record a path to root until find a node that is already inserted in the map.
way 2, get the height of the two nodes, compute the difference.
leetcode
Lowest Common Ancestor of binary search tree
Lowest Common Ancestor of a Binary Tree with parent pointer:
way 1, use a hashmap to record a path to root until find a node that is already inserted in the map.
way 2, get the height of the two nodes, compute the difference.
Sqrt(x)
二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。代码如下：
int sqrt(int x) {
if(x<0) return -1;
if(x==0) return 0;
int l=1,r=x/2+1;
while(l<=r){
int m=l+(r-l)/2;
if(m<=x/m&&x/(m+1)<(m+1))
return m;
if(m<x/m)
l=m+1;
else r=m-1;
}
return 0;
}
//another flavor
int sqrt(int x) {
if(x<=1) return x;
int left=0, right=x, mid;
while( (right-left)>1 )
{
mid=left+(right-left)/2;
if(mid==x/mid)
return mid;
else if(x/mid < mid)
right=mid;
else
left=mid;
}
return left;
}
int sqrt(int x) {
if(x<0) return -1;
if(x==0) return 0;
int l=1,r=x/2+1;
while(l<=r){
int m=l+(r-l)/2;
if(m<=x/m&&x/(m+1)<(m+1))
return m;
if(m<x/m)
l=m+1;
else r=m-1;
}
return 0;
}
//another flavor
int sqrt(int x) {
if(x<=1) return x;
int left=0, right=x, mid;
while( (right-left)>1 )
{
mid=left+(right-left)/2;
if(mid==x/mid)
return mid;
else if(x/mid < mid)
right=mid;
else
left=mid;
}
return left;
}
Subscribe to:
Posts (Atom)