发信人: 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的题目呢?
Subscribe to:
Posts (Atom)