Thursday, October 29, 2015
Talk with Craig
For
an onsite interview, they want to know what they have and what you are looking
for so that they can make a decision on hiring you for a long term.
Behavior Question
Below
are several behavior questions you might be asked. You don’t have to tell every
details. For each questions, list 2 or 3 bulletin would be good.
Why you leave?
I
like my previous job. But unfortunately, they are going for different
directions. The company is doing a shift on out sourcing most of their project.
And as a result, they are shrinking their software development team. That is
why I am leaving.
What are you
looking for in the next couple of years?
For
what I am looking for, firstly, I want to continuously developing my Java
skills. That is what I am good at and also love to do. I am planning to be a
J2EE Architect in the future.
Secondly, I want to do software development in a large scale environment such that there would be different kinds of projects going around. For typical technical company, there is usually only one product. When time is flying, your ability will be limited to just that specific kind of project. However, in XXX I can be involved in numerous applications for different groups. That is exciting for me.
Thirdly,
when I am developing software I’d like to hear feedback from the users. It
would be great to talk to the users directly, know what they want and deliver
exactly the features they want. User’s satisfaction with my product would make
me happy. In financial industry, usually the user will be the colleagues in
other departments. You can talk to them directly and find out whether they like
your contribution or not.
Technical Question
The technical questions can be expected by researching the
job description and your resume. For an onsite interview you need to show what
you have on the table and let the interviewer decide how much you matching this
role. If you are 85% matching, you probably will get the offer. If you only
match 50%, you are going to lose.
You are not able to answer correct all the questions. You have
to know that. Based on this, you need to know how to handle this situation.
When you don’t know the answer, say you don’t know, then tell them a story in
your last job when you need to learn new stuffs to handle the position. It’s
Okay to not know something but you need to let them know you are willing to
learn new stuff and based on history you learn it fast and well.
Do you have any questions?
For
this question, it is time for you to get to know better about the group and the
situation of the project. Interview is like a date. You are not a man who want
a one night stand. You are going to work with the team for long term. So you
need to know the situation before you enter in. And of course, you should know
that you are able to handle this role. When the interviewer asks this question,
it’s time for you get more information about the team. That information can be
used for consideration when you decide which offer to take.
What kind of project you guys are doing? What technologies are you guys using?
What kind of project you guys are doing? What technologies are you guys using?
This
question is to know if you are interested in the project and also if you need
to learn new stuff when taking this role.
Where
are you in the process of project? Will
that be released soon? How often do you guys release?
These questions are to know how much pressure you are going to
take when you take the role. Most people expect an easy to hard mode rather
than hard mode all the time.
How much are you expecting for this role?
When you are asked this question, it means they are
considering to give you an offer. You should not hide the current salary you
make. Because they will know that eventually. When negotiating, DO NOT give
them a number. Tell them the current salary. Tell them for the next job you are
looking for various things, not only money. Tell them you are interviewing with
some other companies, DO NOT tell them the name.
Tuesday, October 27, 2015
Longest Valid Parentheses
Given a string containing just the characters
'(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For
"(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is
")()())", where the longest valid parentheses substring is "()()", which has length = 4.
思路:
1. 使用一个和字符串等长的数组，初始化为0。
2. 使用堆栈存放左括号，如果为 '(' 则压入 '(' 所在位置index。
3. 如果是 ')' 且堆栈不为空，则在数组中设置栈顶左括号的位置和当前右括号的位置的值为1. 弹出栈顶。
4. 此时数组中只有0和1，合法的括号，一定是连续的1. 此题变为最大子序列和。为1计算，为0清零。
4. 此时数组中只有0和1，合法的括号，一定是连续的1. 此题变为最大子序列和。为1计算，为0清零。
Valid Parentheses
Given a string containing just the characters
'(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order,
"()" and "()[]{}" are all valid but "(]" and "([)]" are not.
思路：
1. 利用堆栈的性质，为空则压入新值，依次检查字符串中字符与堆栈顶端是否匹配。
2. 匹配则弹出堆栈顶部值，同时不压入新值。
3. 对于所有右键的情况，直接压入。
Sunday, October 25, 2015
Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given
思路：
1.
2.
3.
Given
{1,2,3,4}, reorder it to {1,4,2,3}.思路：
1.
2.
3.
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
思路：
1.
2.
3.
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list:
Given this linked list:
1->2->3->4->5
For k = 2, you should return:
2->1->4->3->5
For k = 3, you should return:
3->2->1->4->5
思路：
1.
2.
3.
Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given
Given
1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
思路：
1.
2.
3.
Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
思路：
1.
2.
3.
Given n will always be valid.
Try to do this in one pass.
思路：
1.
2.
3.
Friday, October 23, 2015
Thursday, October 22, 2015
Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given
return
Given
1->2->3->4->5->NULL and k = 2,return
4->5->1->2->3->NULL.
思路：
1. 题目中k是非负，所以k可以等于0，k也可以大于链表长。
2. 空链表，单节点以及k为0时，直接返回原链表。
3. 链表长是必须得到的参数。
4. k存在大于链表长度的情况。此时应该用k除以链表长取模，得到真实的反转值。
5. 如果k是链表长度的倍数。直接返回原链表。
6. 双指针，其中从头开始一个先走k%size步，之后双指针同时走，直到先走的指针的next为空。
7. 反转。
2. 空链表，单节点以及k为0时，直接返回原链表。
3. 链表长是必须得到的参数。
4. k存在大于链表长度的情况。此时应该用k除以链表长取模，得到真实的反转值。
5. 如果k是链表长度的倍数。直接返回原链表。
6. 双指针，其中从头开始一个先走k%size步，之后双指针同时走，直到先走的指针的next为空。
7. 反转。
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given
Given
Given
1->2->3->3->4->4->5, return 1->2->5.Given
1->1->1->2->3, return 2->3.
思路：
1. 与 Remove Duplicates from Sorted List 不同， 这里是要去除所有重复过得节点。
2. 这题很难
Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given
Given
Given
1->1->2, return 1->2.Given
1->1->2->3->3, return 1->2->3.
思路：
1. 分配一个内存空间存之前节点的值。
2. 三个指针，从头到尾撸一遍。如果有重复就删除节点。
3. 记得考虑输入节点为空和单节点的情况。
Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given
return
Given
1->4->3->2->5->2 and x = 3,return
1->2->2->4->3->5.
思路：
1. 设置左链和右链，撸一遍。
2. 最后检查左链是否为空。为空则返回右链。
3. 左链不为空，合并左右两链。
Wednesday, October 21, 2015
Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given
Given
1->2->3->4->5->NULL, m = 2 and n = 4,
return
1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Reverse Linked List
Reverse a singly linked list.
思路：
1. 首先考虑链表为空和链表只有一个节点的情况。此时无需反转，直接返回原链表。
2. 三个指针
a) 第一个指针p1指向头指针，
b) 第二个指针p2指向头指针的next
c) 第三个指针p3作为缓存，保存第二个指针的next。
3. 注意第一次分配完三个指针后，就可以改变头指针的next为空，以免之后忘记。
4. 开始反转，先保存p2.next到p3，再将p2.next设为p1，最后将p1和p2指针挪到下一步。
5. 重复步骤4，直到p2为空，此时p1即为结果。
思路：
1. 首先考虑链表为空和链表只有一个节点的情况。此时无需反转，直接返回原链表。
2. 三个指针
a) 第一个指针p1指向头指针，
b) 第二个指针p2指向头指针的next
c) 第三个指针p3作为缓存，保存第二个指针的next。
3. 注意第一次分配完三个指针后，就可以改变头指针的next为空，以免之后忘记。
4. 开始反转，先保存p2.next到p3，再将p2.next设为p1，最后将p1和p2指针挪到下一步。
5. 重复步骤4，直到p2为空，此时p1即为结果。
Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
思路：
1. 第一眼看到以为要先reverse，其实不需要。
2. 考虑两个链表只要有一个为空，就可以直接返回另一个。
3. 双指针分别指向两个链表，一步步做相加，直到其中有一个为空指针。考虑进位。
4. 此时分两种情况讨论
a) 双指针同时为空，只需考虑进位大于0的情况，加入一个新的节点。
b) 其中有一个指针为空，则另一个指针进入新的循环，直到另一个指针也为空时结束。
结束前也需考虑如果进位大于0，则在末尾加入一个新的节点。
Output: 7 -> 0 -> 8
思路：
1. 第一眼看到以为要先reverse，其实不需要。
2. 考虑两个链表只要有一个为空，就可以直接返回另一个。
3. 双指针分别指向两个链表，一步步做相加，直到其中有一个为空指针。考虑进位。
4. 此时分两种情况讨论
a) 双指针同时为空，只需考虑进位大于0的情况，加入一个新的节点。
b) 其中有一个指针为空，则另一个指针进入新的循环，直到另一个指针也为空时结束。
结束前也需考虑如果进位大于0，则在末尾加入一个新的节点。
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null.
Note: Do not modify the linked list.
思路：
1. 首先借用 Linked List Cycle 的结果判断链表是否存在环状结构。
2. 如果不存在返回为空。
3. 使用不同速度的双指针（p1速度为1， p2速度为2）赛跑，直到双指针相遇。
3. 从双指针相遇开始记录环状结构的长度，继续赛跑，直到下一次相遇。
4. 再次相遇时，可以确定慢指针p1从前一次相遇开始到现在走过的步数就是环状结构的长度。
5. 重置双指针，一个先走等同于环状结构长度的步数。一个停留在head。
6. 双指针以相同速度前进，直到它们相遇，此时节点就是环状结构的起始点。
1. 首先借用 Linked List Cycle 的结果判断链表是否存在环状结构。
2. 如果不存在返回为空。
3. 使用不同速度的双指针（p1速度为1， p2速度为2）赛跑，直到双指针相遇。
3. 从双指针相遇开始记录环状结构的长度，继续赛跑，直到下一次相遇。
4. 再次相遇时，可以确定慢指针p1从前一次相遇开始到现在走过的步数就是环状结构的长度。
5. 重置双指针，一个先走等同于环状结构长度的步数。一个停留在head。
6. 双指针以相同速度前进，直到它们相遇，此时节点就是环状结构的起始点。
Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
思路：
1. 首先考虑链表为空，链表为单节点以及双节点的特殊情况。
2. 不同速度的双指针（p1速度为1， p2速度为2）赛跑。
3. 赛跑的过程中如果发现快指针p2的next为空就一定没有环。
4. 如果存在环状结构，那么慢指针p1和快指针p2一定会相遇。
5. 如果快慢指针相遇，则一定存在环状结构。
Can you solve it without using extra space?
思路：
1. 首先考虑链表为空，链表为单节点以及双节点的特殊情况。
2. 不同速度的双指针（p1速度为1， p2速度为2）赛跑。
3. 赛跑的过程中如果发现快指针p2的next为空就一定没有环。
4. 如果存在环状结构，那么慢指针p1和快指针p2一定会相遇。
5. 如果快慢指针相遇，则一定存在环状结构。
Tuesday, October 20, 2015
S面经
转载
个人背景：
本科：XXX大学 EE（power）； 学过数据库，计算机基础， C++
研究僧：XXX EE（power）;学过算法，Web Technology，数据库。
plus ：project是Web那门课的。Java自学，OS正在自学TAT
Done！！你没有看错我的背景就是这么弱。
准备过程：
2014~2015：
2月~5月：学习算法， java， Web Technology，主要学习基础和构建建立上的project；（要做grader和上自己专业的课，比较忙）
5月~7月：CC150 中的七章过了两遍，（ 因为TI 4， 我要去看啊没怎么好好学习。）
7月~11月：leetcode 第一遍结束第二遍进行中。
11月：与各类icc纠缠中联系烙印英语，java基础，接着第二遍。
12月~2月：刷完第三四遍，刷XXXgoogle面经， XXX的epic OA题目，XXX的Facebook电面面经
2月：专注XXXFacebook面经一万年（2月初拿到2月底的onsite），也开始刷了XXX的Online Judge
总结来说：
Tips：
Last but not least：
我只想告诉大家，成功真的没有这么难，即使我花了一年去学习，我没觉得特别苦，每天都有收获，才有意义嘛。
最重要的事情是，你弄明白你为什么要做SDE了么？
个人背景：
本科：XXX大学 EE（power）； 学过数据库，计算机基础， C++
研究僧：XXX EE（power）;学过算法，Web Technology，数据库。
plus ：project是Web那门课的。Java自学，OS正在自学TAT
Done！！你没有看错我的背景就是这么弱。
准备过程：
2014~2015：
2月~5月：学习算法， java， Web Technology，主要学习基础和构建建立上的project；（要做grader和上自己专业的课，比较忙）
5月~7月：CC150 中的七章过了两遍，（ 因为TI 4， 我要去看啊没怎么好好学习。）
7月~11月：leetcode 第一遍结束第二遍进行中。
11月：与各类icc纠缠中联系烙印英语，java基础，接着第二遍。
12月~2月：刷完第三四遍，刷XXXgoogle面经， XXX的epic OA题目，XXX的Facebook电面面经
2月：专注XXXFacebook面经一万年（2月初拿到2月底的onsite），也开始刷了XXX的Online Judge
总结来说：
- 个人认为准备的时间和开始面试的时间比例是2 : 1最好
- 其次找工作的时候，记住先练手，学习如何吹b，记得总结只是漏洞
- 每个机会都要全力以赴，认真研读面经，我不建议去在没准备好的情况下面很多，感觉会打乱学习知识的节奏。
Tips：
- 题目真的要好好刷，cc lc XXX面经三大法宝，不会的上XXX搜。现在XXX又出了Online Judge (XXX)，也是大法宝。
- 不要埋头蛮干，这样会少走很多弯路，12月以前我都是自己单干，走了不少弯路，后来进了XXX，上升很快，获取知识的途径非常直接暴力。你就往里填就好了，中国人最擅长的难道不是应试么？
- 大胆讨论，发现没听说过的东西，自己不明白的东西赶紧弄懂，不要过夜
- 对了，对于FB这样的公司，带逗B属性是极好的，至少culture fit这轮你不用愁了，当然热情也是要有的
- 关于烙印，不要怕，一遍听不懂问第二遍，听懂为止，千万别自己吓捉摸。。
- 我想想还有别的没。。
- 我觉得自己学习。。都胖了TAT无情
Last but not least：
我只想告诉大家，成功真的没有这么难，即使我花了一年去学习，我没觉得特别苦，每天都有收获，才有意义嘛。
最重要的事情是，你弄明白你为什么要做SDE了么？
Monday, October 19, 2015
求职总结
转载
自我介绍一下. 毕业快两年了. Master读的是普通学校的水专业Information Science. 我是极其水,几乎零基础,项目都抱别人大腿, 当时没有好好学习知识, 现在别提多后悔了... 去年开始找工作的时候, 连HashMap是什么都不知道... Leetcode就刷了七十道, 总拿女生不要太累了要不就这样吧这种谎言安慰自己... 找到了现在的SDET工作,公司和待遇自然也是好不了. 今年三月开始奋发图强, 八月初开始投简历, 十月十五日当天拿到Google和WalmartLabs的两个offer (对没错,WalmartLabs真的不给考虑时间,当天deadline). 总之是零基础, 靠努力学习和坚持不懈活了下来. 如果你跟我的情况类似,希望我的经验可以帮到你~
CC150. 看了一遍version 5. 据说新版本v6页数多了一倍... 还是希望大家坚持把每一章都看了,对新手帮助很大.
Leetcode. (没有做过Lintcode等等, 我觉得选一个刷题网站全弄会了其实就可以...) 三月到十月共刷5遍,订了subscription,每遍仔细做了每一道题. 过程确实相当痛苦,每天还要上班,一有空就得刷题,周末也不得停歇. 尤其前两遍,基本都是看完答案背着写一遍的,可能也是因为我比较笨... 但是幸亏坚持下来了~ 当我做到第四遍的时候, 有一种通了的感觉, 即使拿到一道新题, 也能比较快的有思路. 这里还是希望我们找工作的朋友们好好刷Leetcode, 弄通弄懂算法精髓, 举一反三. 不要有侥幸思想, 非牛人刷了一遍就想找到非常满意工作的真的少之又少.
Geeksforgeeks. 讲解非常清楚明白易懂, 尤其在学习数据结构和算法上面帮助很大. 它对于很多算法都会有一系列的问题的讲解, 看过之后基本对于某一部分的题目都没什么问题了. 比如Trie,BST的讲解, longest common subsequence一个系列,KMP算法等等,我都是得益于它. 一个算法想不明白,可以先去搜搜geeksforgeeks有没有讲解~
Data structure & Algorithms. 最基础也是最重要的部分, 千万别小瞧基础. 为什么一再强调数据结构与算法基础? 就算刷了十遍leetcode/lintcde等等刷题网站,面试还是会有没见过的题的. 遇到完全没见过的题该怎么办,没有强大的基础知识储备,怎么看穿这道题的本质,怎么很快有思路? 一切都要靠基础, 甚至比刷题本身更重要. 每个数据结构一定要做到彻底明白概念, 结构, 功能, 怎么用. 一定要亲自在IDE里面至少implement一遍!! 推荐书目: 我精读了Data Structures and Algorithms in JAVA. 非常适合初学者, 每个数据结构的实现和用法都写的极其详细. 精读了每一章, 并且implement了两遍里面所有数据结构. 我也听有的人说精读Introductions to Algorithms, 但是这本书感觉不是很适合我这种初学者... 如果你有基础或者是科班出身,面试之前详读Intro to Algo我觉得会很受用的. 刷题的过程中,会遇到很多没见过的算法和数据结构的用法. 比如说graph, 在leetcode里面会有用到dfs, bfs, topology, dijkstra等等算法, 每当遇到一种没见过的, 就脱离这道题, 去网上搜索这究竟是什么, 怎么实现的, 怎么用, 在IDE里面自己亲自实现算法本身, 很生疏的算法要多实现几遍. 这个过程是让我提高最大最快的一步.
Java Conception. 内推我Google的大牛朋友让我看Thinking in Java和Effective Java这两本书. 虽然没有看完,但是确实是非常棒的两本书, 尤其是Thinking in Java. 据说每看一遍都会对Java有全新的认识, 非常值得一看. 如果实在没有时间,只是为了面试紧急补课, 至少看会这个网站的Java面试题。
http://www.programmerinterview.com/
Big Data. 今年以来,我发现几乎所有公司的面试都不约而同的添加了大数据相关的问题,就连Walmartlabs的SDET职位的面试中都遇到了,不得不说大数据真是现在一个很猛的trend... 在面Bloomberg的时候就是因为大数据的问题不会而吃了亏挂了,回家以后恶补了很久...
这里推荐这个blog,很多朋友都应该过: http://blog.csdn.net/v_july_v/article/details/7382693我很想知道写这个blog的是个怎样的人,真心膜拜... 他的总结几乎囊括了所有大数据方面的知识背景,实在赞叹. 对于这个帖子里面提到的知识点,他都有专门介绍的链接,全面又方便. 如果想面试无敌的话,每个知识点都要自己多查资料弄懂,每道题都自己过一遍. 对于里面提到的不同方法要多比较, 每种方法什么时候适用, trade off是什么都要清楚. 重中之重是Map Reduce和External sort.
Thread & Locks. 考得不多但是面ebay碰到了. 主要知识点: thread和process区别, multithread, lock, semaphore, 对resource分配, deadlock, 怎么解决/预防deadlock. 还有BlockingQueue 和 Producer-Consumer经典题要会implement.这里有几个经典问题:
http://www.careercup.com/question?id=4783236498587648
http://www.careercup.com/question?id=5652784707796992
OOD. 老老实实实现了两遍Singleton, Factory, 还有MVC pattern. 设计一个class应该也算在OOD范围里: 写过无数遍LRU, Trie, Iterator, BST以及变种, BlockingQueue等等, 生怕被问到...
System Design. 这个对不住大家,我最后没面到过系统设计,所以不太知道自己这点准备到底充不充分... 如果你要面Facebook几乎肯定是要考系统设计的,还是得好好准备. 一定要看FB的engineering blog, 看的越多越好. 基础的概念至少要会: load balancer, cache, memcache, consistent hashing, round robin, master slave, sharding, pre-computed, map reduce, difference with SQL/NoSQL.... 有很多牛人总结的系统设计帖,我就不多置喙了,这里推荐几个帖子.http://massivetechinterview.blogspot.com/2015/06/itint5.html
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://blog.csdn.net/sigh1988/article/details/9790337
还有这个公开课,太棒了,新手入门必备,谢谢成哥推荐~
https://www.udacity.com/course/viewer#!/c-cs253/l-48737165
Resume. 就一点,要把自己简历上每个项目都弄熟, 写下项目介绍背下来, 这样被问到的时候可以张口就来. 也要把你要面试的单位的简介自己总结一遍背下来, 还有你为什么想来我们单位, 如果你有工作你为什么想跳槽, 你觉得为什么适合这个职位等等. 其实这些都是标答, 只要好好准备过一次就能适用于各个公司...
这里有一个我总结的软加分项. 尤其对妹子, 说实话妹子是可以很占优势的, 特别如果你是个漂亮妹子~ 你的性别,说话的态度,眼神,都可以成为你的加分项, 一定要利用这一点. 为什么我突然说这个,不是说这只是个锦上添花的事情,而是因为这个点非常重要,其实男生也一样. 一个面试官想要找的不仅仅是能够做出题的人,更需要的是找到一个合适的teammate. 你是不是好说话,是不是能聆听而不是一味反驳别人坚持自己,是不是能马上接纳别人,接受别人的idea并且有接受新知识的能力,从某些方面来说,比仅仅能做出来这道题重要得多. 所以面试的时候, 那天早上就告诉自己今天是去跪舔的,别耍态度,如果你是大神可以除外... 最好全程微笑,遇到不会的题的时候更要微笑. 把想题的过程全部说出来, 不能成为心理活动, 让对方知道你在非常努力的思考, 而且态度很好, 所以就算你没有完全想出来, 他是非常愿意给你hint的. 态度决定很多事,甚至人生.
好啦,我啰啰嗦嗦了那么多真是不好意思T T.... 但愿这篇总结能给任何人一点点的帮助我就没白写~多努力就有多幸运.希望大家都能坚持到底,不倒在黎明前,最终拿到很多大offer,进入自己梦想中的公司,开启人生新的篇章!
面经：
我面的职位是Softwre Engineer, Tools and Infrastracture, 所以开发和测试的问题都会问到.
Phone interview 1:
白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping.
第二问是写一个method, 返回 在Interval 1而不在Interval 2的区域.
一道如此简单的题...因为我前面实在太紧张了全身是汗面的吭吭哧哧...面完以后我都准备move on了, 看来小哥最后还是放了我一码让我有了二面。
Phone interview 2:
白人小哥.更简单了... Leetcode原题Plus One
如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work? 意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.
最后他还开心的问了我的名字到底怎么念,我就知道大概有个底儿了~
Onsite:
第一轮: 印度哥哥. 大早上的堵了一个多小时开过去腿都麻了,上来就开始coding,直接蒙圈儿。
第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个 数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n。
第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在 这种情况下binary search出来的数.
第二轮: 韩国哥哥.
经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode. encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗? 我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题...然后又问他,如果原String本来就是"5xt"这种结构, decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧.
写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了... 因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了... 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了. 但是这种方法违背了encode后要变短的rule,所以我是真没想出来.....
还讨论了好多种情况, 最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个? 实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好...面完我就觉得跪了....
第三轮: 中国小哥
第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误。
第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了...
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗? 但是我要run这个method好多次比如k次, 怎么最快能求出array被 rearrange了k次以后的结果? 最后我就推倒出求LCM. 面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~
第四轮: 印度姐姐.
假装没有准备的样子现场想题目... 谢谢姐姐没有对我下死手T T
海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上, 包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛. 先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写. 全程想给我挑错, 不断质疑我的代码... 还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫...
第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭...
第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大...手都写疼了...
第二题, 给个Google map, 你就测吧...
我的offer效率很高我完全没想到, 5个工作日从onsite到签offer, 真心感谢hr姐姐. 因为我有个WalmartLabs的competing offer正好是那天截止, hr的意思也是我的feedback很好,所以HC没有犹豫,也马上有组想要我, 所以hr加班加点在进HC当天就跟offer team合作把offer弄出来了. 这里再次感谢各位面试官对我高抬贵手, 以及WalmartLabs....
自我介绍一下. 毕业快两年了. Master读的是普通学校的水专业Information Science. 我是极其水,几乎零基础,项目都抱别人大腿, 当时没有好好学习知识, 现在别提多后悔了... 去年开始找工作的时候, 连HashMap是什么都不知道... Leetcode就刷了七十道, 总拿女生不要太累了要不就这样吧这种谎言安慰自己... 找到了现在的SDET工作,公司和待遇自然也是好不了. 今年三月开始奋发图强, 八月初开始投简历, 十月十五日当天拿到Google和WalmartLabs的两个offer (对没错,WalmartLabs真的不给考虑时间,当天deadline). 总之是零基础, 靠努力学习和坚持不懈活了下来. 如果你跟我的情况类似,希望我的经验可以帮到你~
CC150. 看了一遍version 5. 据说新版本v6页数多了一倍... 还是希望大家坚持把每一章都看了,对新手帮助很大.
Leetcode. (没有做过Lintcode等等, 我觉得选一个刷题网站全弄会了其实就可以...) 三月到十月共刷5遍,订了subscription,每遍仔细做了每一道题. 过程确实相当痛苦,每天还要上班,一有空就得刷题,周末也不得停歇. 尤其前两遍,基本都是看完答案背着写一遍的,可能也是因为我比较笨... 但是幸亏坚持下来了~ 当我做到第四遍的时候, 有一种通了的感觉, 即使拿到一道新题, 也能比较快的有思路. 这里还是希望我们找工作的朋友们好好刷Leetcode, 弄通弄懂算法精髓, 举一反三. 不要有侥幸思想, 非牛人刷了一遍就想找到非常满意工作的真的少之又少.
Geeksforgeeks. 讲解非常清楚明白易懂, 尤其在学习数据结构和算法上面帮助很大. 它对于很多算法都会有一系列的问题的讲解, 看过之后基本对于某一部分的题目都没什么问题了. 比如Trie,BST的讲解, longest common subsequence一个系列,KMP算法等等,我都是得益于它. 一个算法想不明白,可以先去搜搜geeksforgeeks有没有讲解~
Data structure & Algorithms. 最基础也是最重要的部分, 千万别小瞧基础. 为什么一再强调数据结构与算法基础? 就算刷了十遍leetcode/lintcde等等刷题网站,面试还是会有没见过的题的. 遇到完全没见过的题该怎么办,没有强大的基础知识储备,怎么看穿这道题的本质,怎么很快有思路? 一切都要靠基础, 甚至比刷题本身更重要. 每个数据结构一定要做到彻底明白概念, 结构, 功能, 怎么用. 一定要亲自在IDE里面至少implement一遍!! 推荐书目: 我精读了Data Structures and Algorithms in JAVA. 非常适合初学者, 每个数据结构的实现和用法都写的极其详细. 精读了每一章, 并且implement了两遍里面所有数据结构. 我也听有的人说精读Introductions to Algorithms, 但是这本书感觉不是很适合我这种初学者... 如果你有基础或者是科班出身,面试之前详读Intro to Algo我觉得会很受用的. 刷题的过程中,会遇到很多没见过的算法和数据结构的用法. 比如说graph, 在leetcode里面会有用到dfs, bfs, topology, dijkstra等等算法, 每当遇到一种没见过的, 就脱离这道题, 去网上搜索这究竟是什么, 怎么实现的, 怎么用, 在IDE里面自己亲自实现算法本身, 很生疏的算法要多实现几遍. 这个过程是让我提高最大最快的一步.
Java Conception. 内推我Google的大牛朋友让我看Thinking in Java和Effective Java这两本书. 虽然没有看完,但是确实是非常棒的两本书, 尤其是Thinking in Java. 据说每看一遍都会对Java有全新的认识, 非常值得一看. 如果实在没有时间,只是为了面试紧急补课, 至少看会这个网站的Java面试题。
http://www.programmerinterview.com/
Big Data. 今年以来,我发现几乎所有公司的面试都不约而同的添加了大数据相关的问题,就连Walmartlabs的SDET职位的面试中都遇到了,不得不说大数据真是现在一个很猛的trend... 在面Bloomberg的时候就是因为大数据的问题不会而吃了亏挂了,回家以后恶补了很久...
这里推荐这个blog,很多朋友都应该过: http://blog.csdn.net/v_july_v/article/details/7382693我很想知道写这个blog的是个怎样的人,真心膜拜... 他的总结几乎囊括了所有大数据方面的知识背景,实在赞叹. 对于这个帖子里面提到的知识点,他都有专门介绍的链接,全面又方便. 如果想面试无敌的话,每个知识点都要自己多查资料弄懂,每道题都自己过一遍. 对于里面提到的不同方法要多比较, 每种方法什么时候适用, trade off是什么都要清楚. 重中之重是Map Reduce和External sort.
Thread & Locks. 考得不多但是面ebay碰到了. 主要知识点: thread和process区别, multithread, lock, semaphore, 对resource分配, deadlock, 怎么解决/预防deadlock. 还有BlockingQueue 和 Producer-Consumer经典题要会implement.这里有几个经典问题:
http://www.careercup.com/question?id=4783236498587648
http://www.careercup.com/question?id=5652784707796992
OOD. 老老实实实现了两遍Singleton, Factory, 还有MVC pattern. 设计一个class应该也算在OOD范围里: 写过无数遍LRU, Trie, Iterator, BST以及变种, BlockingQueue等等, 生怕被问到...
System Design. 这个对不住大家,我最后没面到过系统设计,所以不太知道自己这点准备到底充不充分... 如果你要面Facebook几乎肯定是要考系统设计的,还是得好好准备. 一定要看FB的engineering blog, 看的越多越好. 基础的概念至少要会: load balancer, cache, memcache, consistent hashing, round robin, master slave, sharding, pre-computed, map reduce, difference with SQL/NoSQL.... 有很多牛人总结的系统设计帖,我就不多置喙了,这里推荐几个帖子.http://massivetechinterview.blogspot.com/2015/06/itint5.html
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://blog.csdn.net/sigh1988/article/details/9790337
还有这个公开课,太棒了,新手入门必备,谢谢成哥推荐~
https://www.udacity.com/course/viewer#!/c-cs253/l-48737165
Resume. 就一点,要把自己简历上每个项目都弄熟, 写下项目介绍背下来, 这样被问到的时候可以张口就来. 也要把你要面试的单位的简介自己总结一遍背下来, 还有你为什么想来我们单位, 如果你有工作你为什么想跳槽, 你觉得为什么适合这个职位等等. 其实这些都是标答, 只要好好准备过一次就能适用于各个公司...
这里有一个我总结的软加分项. 尤其对妹子, 说实话妹子是可以很占优势的, 特别如果你是个漂亮妹子~ 你的性别,说话的态度,眼神,都可以成为你的加分项, 一定要利用这一点. 为什么我突然说这个,不是说这只是个锦上添花的事情,而是因为这个点非常重要,其实男生也一样. 一个面试官想要找的不仅仅是能够做出题的人,更需要的是找到一个合适的teammate. 你是不是好说话,是不是能聆听而不是一味反驳别人坚持自己,是不是能马上接纳别人,接受别人的idea并且有接受新知识的能力,从某些方面来说,比仅仅能做出来这道题重要得多. 所以面试的时候, 那天早上就告诉自己今天是去跪舔的,别耍态度,如果你是大神可以除外... 最好全程微笑,遇到不会的题的时候更要微笑. 把想题的过程全部说出来, 不能成为心理活动, 让对方知道你在非常努力的思考, 而且态度很好, 所以就算你没有完全想出来, 他是非常愿意给你hint的. 态度决定很多事,甚至人生.
好啦,我啰啰嗦嗦了那么多真是不好意思T T.... 但愿这篇总结能给任何人一点点的帮助我就没白写~多努力就有多幸运.希望大家都能坚持到底,不倒在黎明前,最终拿到很多大offer,进入自己梦想中的公司,开启人生新的篇章!
面经：
我面的职位是Softwre Engineer, Tools and Infrastracture, 所以开发和测试的问题都会问到.
Phone interview 1:
白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping.
第二问是写一个method, 返回 在Interval 1而不在Interval 2的区域.
一道如此简单的题...因为我前面实在太紧张了全身是汗面的吭吭哧哧...面完以后我都准备move on了, 看来小哥最后还是放了我一码让我有了二面。
Phone interview 2:
白人小哥.更简单了... Leetcode原题Plus One
如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work? 意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.
最后他还开心的问了我的名字到底怎么念,我就知道大概有个底儿了~
Onsite:
第一轮: 印度哥哥. 大早上的堵了一个多小时开过去腿都麻了,上来就开始coding,直接蒙圈儿。
第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个 数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n。
第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在 这种情况下binary search出来的数.
第二轮: 韩国哥哥.
经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode. encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗? 我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题...然后又问他,如果原String本来就是"5xt"这种结构, decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧.
写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了... 因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了... 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了. 但是这种方法违背了encode后要变短的rule,所以我是真没想出来.....
还讨论了好多种情况, 最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个? 实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好...面完我就觉得跪了....
第三轮: 中国小哥
第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误。
第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了...
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗? 但是我要run这个method好多次比如k次, 怎么最快能求出array被 rearrange了k次以后的结果? 最后我就推倒出求LCM. 面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~
第四轮: 印度姐姐.
假装没有准备的样子现场想题目... 谢谢姐姐没有对我下死手T T
海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上, 包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛. 先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写. 全程想给我挑错, 不断质疑我的代码... 还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫...
第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭...
第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大...手都写疼了...
第二题, 给个Google map, 你就测吧...
我的offer效率很高我完全没想到, 5个工作日从onsite到签offer, 真心感谢hr姐姐. 因为我有个WalmartLabs的competing offer正好是那天截止, hr的意思也是我的feedback很好,所以HC没有犹豫,也马上有组想要我, 所以hr加班加点在进HC当天就跟offer team合作把offer弄出来了. 这里再次感谢各位面试官对我高抬贵手, 以及WalmartLabs....
GFS阅读笔记
== 文章结构 ==
Abstract
1. Introduction
2. Design Overview
2.1 Assumptions
2.2 Interface
2.3 Architecture
2.4 Single Master
2.5 Chunck Size
2.6 Metadata
2.6.1 In Memory Data Structures
2.6.2 Chunk Locations
2.6.3 Operation Log
2.7 Consistency Model
2.7.1 Guarantees by GFS
2.7.2 Implications for Applications
3. System Interactions
3.1 Leases and Mutation Order
3.2 Data Flow
3.3 Atomic Record Appends
3.4 Snapshot
4. Master Operation
4.1 Namespace Management and Locking
4.2 Replica Placement
4.3 Creation, Re-replication, Rebalancing
4.4 Garbage Collection
4.4.1 Mechanism
4.4.2 Discussion
4.5 Stale Replica Detection
5. Fault Tolerance and Diagnosis
5.1 High Availability
5.1.1 Fast Recovery
5.1.2 Chunk Replication
5.1.3 Master Replication
5.2 Data Integrity
5.3 Diagnostic Tools
6. Measurements
6.1 Micro-benchmarks
6.1.1 Reads
6.1.2 Writes
6.1.3 Record Appends
6.2 Real World Clusters
6.2.1 Storage
6.2.2 Metadata
6.2.3 Read and Write Rates
6.2.4 Master Load
6.2.5 Recovery Time
6.3 Workload Breakdown
6.3.1 Methodology and Caveats
6.3.2 Chunkserver Workload
6.3.3 Appends versus Writes
6.3.4 Master Workload
7. Experience
8. Related Work
9. Conclusions
== 1. 背景介绍 ==
1. Component Failure are norm rather than exception.
2. Files are huge than traditional standards.
3. Most data are mutated by appending new data rather than overwriting existing data.
4. Co-designing the applications and the file system API benefits the overall system by increasing our flexibility
== 2. 设计概要 ==
1. 前提假设
a) The system is built from many inexpensive commodity components that often fail.
b) The system stores a modest number of large files.
c) The workloads primarily consist of two kinds of reads:large streaming reads and small random reads.
d) The workloads also have many large, sequential writes that append data to files.
e) The system must efficiently implement well-defined semantics for multiple clients that concurrently append to the same file.
f) High sustained bandwidth is more important than low latency.
2. 接口
a) GFS provides a familiar file system interface which supports the usual operations to create, delete, open, close, read, and write files.
b) Snapshot creates a copy of a file or a directory tree at low cost.
c) Record append allows multiple clients to append data to the same file concurrently while guaranteeing the atomicity of each individual client’s append.
3. 架构
a) A GFS cluster consists of a single master and multiple chunkservers and is accessed by multiple clients.
b) Each of these is typically a commodity Linux machine running a user-level server process.
c) Files are divided into fixed-size chunks.
Each chunk is identified by an immutable and globally unique 64 bit chunk handle assigned by the master at the time of chunk creation.
Each chunk is replicated by default 3 replicas on multiple chunkservers.
d) The master maintains all file system metadata including the namespace, access control information, the mapping from files to chunks,
and the current locations of chunks.
e) It also controls system-wide activities such as chunk lease management, garbage collection of orphaned chunks, and chunk migration between
chunkservers.
f) The master periodically communicates with each chunkserver in HeartBeat messages to give it instructions and collect its state.
g) Clients interact with the master for metadata operations, but all data-bearing communication goes directly to the chunkservers.
h) Neither the client nor the chunkserver caches file data because most applications stream through huge files or have working sets too large to be cached.
4. 单主服务器策略
a) Clients never read or write file data through master.
b) Instead Clients ask the master which chunkserver it should contact.
c) The client will cache the information until it expires.
d) So when accessing start, client already know which chunkserver it needs to access.
e) It will first send out request to master, master will reply with a chunk handle and location of replicas.
f) The client will send request to 1 of the replicas which is the closest one.
5. 块大小的选择 (64MB)
优点：
a) Reduce client's need to interact with Master.
b) Reduce network overhead by keep a persistent TCP connection to the chunkserver over an extended period of time.
c) Reduce size of metadata on Master.
缺点：Small file like only 1 chunk size will be hot spots if many clients are accessing the same file.
临时解决方案：多备份，默认3个备份可以提高到100等等。
长期解决方案：允许client间相互传送数据。
Abstract
1. Introduction
2. Design Overview
2.1 Assumptions
2.2 Interface
2.3 Architecture
2.4 Single Master
2.5 Chunck Size
2.6 Metadata
2.6.1 In Memory Data Structures
2.6.2 Chunk Locations
2.6.3 Operation Log
2.7 Consistency Model
2.7.1 Guarantees by GFS
2.7.2 Implications for Applications
3. System Interactions
3.1 Leases and Mutation Order
3.2 Data Flow
3.3 Atomic Record Appends
3.4 Snapshot
4. Master Operation
4.1 Namespace Management and Locking
4.2 Replica Placement
4.3 Creation, Re-replication, Rebalancing
4.4 Garbage Collection
4.4.1 Mechanism
4.4.2 Discussion
4.5 Stale Replica Detection
5. Fault Tolerance and Diagnosis
5.1 High Availability
5.1.1 Fast Recovery
5.1.2 Chunk Replication
5.1.3 Master Replication
5.2 Data Integrity
5.3 Diagnostic Tools
6. Measurements
6.1 Micro-benchmarks
6.1.1 Reads
6.1.2 Writes
6.1.3 Record Appends
6.2 Real World Clusters
6.2.1 Storage
6.2.2 Metadata
6.2.3 Read and Write Rates
6.2.4 Master Load
6.2.5 Recovery Time
6.3 Workload Breakdown
6.3.1 Methodology and Caveats
6.3.2 Chunkserver Workload
6.3.3 Appends versus Writes
6.3.4 Master Workload
7. Experience
8. Related Work
9. Conclusions
== 1. 背景介绍 ==
1. Component Failure are norm rather than exception.
2. Files are huge than traditional standards.
3. Most data are mutated by appending new data rather than overwriting existing data.
4. Co-designing the applications and the file system API benefits the overall system by increasing our flexibility
== 2. 设计概要 ==
1. 前提假设
a) The system is built from many inexpensive commodity components that often fail.
b) The system stores a modest number of large files.
c) The workloads primarily consist of two kinds of reads:large streaming reads and small random reads.
d) The workloads also have many large, sequential writes that append data to files.
e) The system must efficiently implement well-defined semantics for multiple clients that concurrently append to the same file.
f) High sustained bandwidth is more important than low latency.
2. 接口
a) GFS provides a familiar file system interface which supports the usual operations to create, delete, open, close, read, and write files.
b) Snapshot creates a copy of a file or a directory tree at low cost.
c) Record append allows multiple clients to append data to the same file concurrently while guaranteeing the atomicity of each individual client’s append.
3. 架构
a) A GFS cluster consists of a single master and multiple chunkservers and is accessed by multiple clients.
b) Each of these is typically a commodity Linux machine running a user-level server process.
c) Files are divided into fixed-size chunks.
Each chunk is identified by an immutable and globally unique 64 bit chunk handle assigned by the master at the time of chunk creation.
Each chunk is replicated by default 3 replicas on multiple chunkservers.
d) The master maintains all file system metadata including the namespace, access control information, the mapping from files to chunks,
and the current locations of chunks.
e) It also controls system-wide activities such as chunk lease management, garbage collection of orphaned chunks, and chunk migration between
chunkservers.
f) The master periodically communicates with each chunkserver in HeartBeat messages to give it instructions and collect its state.
g) Clients interact with the master for metadata operations, but all data-bearing communication goes directly to the chunkservers.
h) Neither the client nor the chunkserver caches file data because most applications stream through huge files or have working sets too large to be cached.
4. 单主服务器策略
a) Clients never read or write file data through master.
b) Instead Clients ask the master which chunkserver it should contact.
c) The client will cache the information until it expires.
d) So when accessing start, client already know which chunkserver it needs to access.
e) It will first send out request to master, master will reply with a chunk handle and location of replicas.
f) The client will send request to 1 of the replicas which is the closest one.
5. 块大小的选择 (64MB)
优点：
a) Reduce client's need to interact with Master.
b) Reduce network overhead by keep a persistent TCP connection to the chunkserver over an extended period of time.
c) Reduce size of metadata on Master.
缺点：Small file like only 1 chunk size will be hot spots if many clients are accessing the same file.
临时解决方案：多备份，默认3个备份可以提高到100等等。
长期解决方案：允许client间相互传送数据。
Subscribe to:
Comments (Atom)