9月份的面试，连续四天面了LGTF，准备面试的半年多时间来从本版受益匪浅，现在把
面经写出来回馈本版，希望大家把好的传统延续下去。
L偏重设计，也可能与面的组是platform有关，6个面试有三个是设计，而且涉及很多细
节，比如index，distribute hash, circule counting. 有一面是manager问项目，个
人觉得选一个自己从头到尾做过的项目，然后按我下面的6点进行准备，基本就够了。
L是有题库的，建议多刷版面和glassdoor。
G偏重coding，每一面都是coding开始，而且占很大比例，如果时间多的话可能有两个
coding，也有可能接一个design问题。
T的面试最没规律，感觉基本是面试官自己决定问什么，所以这里不怎么好做总结。
F的面试是最标准化的，两个半coding + 一个design + 半个项目介绍 (项目介绍同上
面L的), F的题目重现率比较高，看版上的题目就差不多了，design问题基本在之前版
上归纳的几个类别： 设计feed，message, search，存储，都和大数据沾边。
LFT面试官大部分是同胞，大部分同胞是很友好，很帮忙的，在此谢过! 但在L碰到一极
品同胞，和老外一块面我，始终一副很屌的样子。在T碰到一个老中manager，一副高高
在上的态度，不断challenge我的过去的项目和跳槽动机。在L和T各碰到一个烙印。G全
部是白人面试官，都很友好，也是最顺利的面试，感觉G的面试官是最认真负责的，我
在写code的时候，他们也很忙碌的把我的代码和过程记录下来。
准备内容:
1. Coding:
Leetcode, 1.5遍
2. 大数据:
Google的三篇论文 (GFS, Map-Reduce, Big-Table)
Hadoop, HDFS, HBase (等同于Google三篇论文，可二选一)
Amazon Dynamo, Facebook Cassandra (大数据的另一种存储方式)
CAP theorem, Distribute Hashing, Consistent hashing, Eventual
Consistent
3. 系统设计：
Multi-Thread
Message Queue, Memory Cache
Facebook, Twitter的一些tech talks
Coding
1. 问问题，理解题意，弄清楚输入、输出、流程，磨刀不误砍柴工
2. 多想几种解法(从brutal force开始)，简单例子，test case，画图 5到10分钟
3. 与面试官交流想法 2分钟
4. Pseudo code 在草稿纸上 , 分成子函数，模块化，将复杂问题交给子函数
5. Real code 在答题板上 10到20分钟
6. Verify, 检查错误，特殊条件，边界条件 5分钟
OO Design
1. 需求分析，问问题，列出input, output, use cases
2. 讨论性能要求和Specification, 讨论不同方案trad-off, 方便读还是方便写，
push 还是pull来发送更新
3. 分析流程，将用use cases转换成use scenario, 可以用(Given, When, Then)关键
词描述
eg: 取款流程
Give a person has a bank account with balance 100
When the person withdraw 30
Then the balance will be changed to 70
4. 根据use scenario设计data model
将上面例子中的名词抽取出来作为对象或属性，动作抽取作为方法
class Person{
long personId;
List<BankAccount> accounts;
}
class BankAccount{
long accountId
double balance;
}
class AccountService{
boolean withdraw(long personId, long accountId, double amount){}
double deposits(long personId, long accountId, double amount){}
double getBalance(long personId, long accountId)
}
5. 然后考虑高并发情况下，如何提升Scalability. 可以往LoadBalance, Partition/
Shading，cache等方面考虑, 讨论各种方式的优缺点
项目准备，选一个自己从头到尾做过的项目，先准备一个简单介绍，然后根据根据下面
6点准备具体内容
1. Most challenging: complexity legacy system, no testing, scalability
2. What you learn: unit test, decoupling, gray deployment
3. Most interesting: automatically test framework
4. Hardest bug: race condition / dead lock
5. Conflict with teammates: configuration migration
6. Failure: full dial up cause big issue // don't be too optimist // be
careful all the time
面试题
1. Find influencer, BF n^n, optimize to O(n)
2. sqrt(double x, double dlta) lg(x/dlta), m+dlta??, m - dlta??
3. Design a Message store system (in-memory storage) [seq_id, len, data]
chunk
4. Design monitoring system, circular array, storage, aggregation
5. Hiring manager, Project description
6. Design a key / value system, put, get, delete (copy on write)
1. Longest increasing sub-array? O(n), better than O(n)
Design a dropper box system.
2. Sort by type and timestamp
Num of routers
3. (startTime, endTime, load), find max load in a certain
4. Coding program to record event count
5. Largest summary in sub-array
Design tiny url
1. Present project
Copy Linked list with node point to other
2. Boogle, Trie
3. Design a feeds system, write and query
4. Find longest sub-array with sum to K
面经写出来回馈本版，希望大家把好的传统延续下去。
L偏重设计，也可能与面的组是platform有关，6个面试有三个是设计，而且涉及很多细
节，比如index，distribute hash, circule counting. 有一面是manager问项目，个
人觉得选一个自己从头到尾做过的项目，然后按我下面的6点进行准备，基本就够了。
L是有题库的，建议多刷版面和glassdoor。
G偏重coding，每一面都是coding开始，而且占很大比例，如果时间多的话可能有两个
coding，也有可能接一个design问题。
T的面试最没规律，感觉基本是面试官自己决定问什么，所以这里不怎么好做总结。
F的面试是最标准化的，两个半coding + 一个design + 半个项目介绍 (项目介绍同上
面L的), F的题目重现率比较高，看版上的题目就差不多了，design问题基本在之前版
上归纳的几个类别： 设计feed，message, search，存储，都和大数据沾边。
LFT面试官大部分是同胞，大部分同胞是很友好，很帮忙的，在此谢过! 但在L碰到一极
品同胞，和老外一块面我，始终一副很屌的样子。在T碰到一个老中manager，一副高高
在上的态度，不断challenge我的过去的项目和跳槽动机。在L和T各碰到一个烙印。G全
部是白人面试官，都很友好，也是最顺利的面试，感觉G的面试官是最认真负责的，我
在写code的时候，他们也很忙碌的把我的代码和过程记录下来。
准备内容:
1. Coding:
Leetcode, 1.5遍
2. 大数据:
Google的三篇论文 (GFS, Map-Reduce, Big-Table)
Hadoop, HDFS, HBase (等同于Google三篇论文，可二选一)
Amazon Dynamo, Facebook Cassandra (大数据的另一种存储方式)
CAP theorem, Distribute Hashing, Consistent hashing, Eventual
Consistent
3. 系统设计：
Multi-Thread
Message Queue, Memory Cache
Facebook, Twitter的一些tech talks
Coding
1. 问问题，理解题意，弄清楚输入、输出、流程，磨刀不误砍柴工
2. 多想几种解法(从brutal force开始)，简单例子，test case，画图 5到10分钟
3. 与面试官交流想法 2分钟
4. Pseudo code 在草稿纸上 , 分成子函数，模块化，将复杂问题交给子函数
5. Real code 在答题板上 10到20分钟
6. Verify, 检查错误，特殊条件，边界条件 5分钟
OO Design
1. 需求分析，问问题，列出input, output, use cases
2. 讨论性能要求和Specification, 讨论不同方案trad-off, 方便读还是方便写，
push 还是pull来发送更新
3. 分析流程，将用use cases转换成use scenario, 可以用(Given, When, Then)关键
词描述
eg: 取款流程
Give a person has a bank account with balance 100
When the person withdraw 30
Then the balance will be changed to 70
4. 根据use scenario设计data model
将上面例子中的名词抽取出来作为对象或属性，动作抽取作为方法
class Person{
long personId;
List<BankAccount> accounts;
}
class BankAccount{
long accountId
double balance;
}
class AccountService{
boolean withdraw(long personId, long accountId, double amount){}
double deposits(long personId, long accountId, double amount){}
double getBalance(long personId, long accountId)
}
5. 然后考虑高并发情况下，如何提升Scalability. 可以往LoadBalance, Partition/
Shading，cache等方面考虑, 讨论各种方式的优缺点
项目准备，选一个自己从头到尾做过的项目，先准备一个简单介绍，然后根据根据下面
6点准备具体内容
1. Most challenging: complexity legacy system, no testing, scalability
2. What you learn: unit test, decoupling, gray deployment
3. Most interesting: automatically test framework
4. Hardest bug: race condition / dead lock
5. Conflict with teammates: configuration migration
6. Failure: full dial up cause big issue // don't be too optimist // be
careful all the time
面试题
1. Find influencer, BF n^n, optimize to O(n)
2. sqrt(double x, double dlta) lg(x/dlta), m+dlta??, m - dlta??
3. Design a Message store system (in-memory storage) [seq_id, len, data]
chunk
4. Design monitoring system, circular array, storage, aggregation
5. Hiring manager, Project description
6. Design a key / value system, put, get, delete (copy on write)
1. Longest increasing sub-array? O(n), better than O(n)
Design a dropper box system.
2. Sort by type and timestamp
Num of routers
3. (startTime, endTime, load), find max load in a certain
4. Coding program to record event count
5. Largest summary in sub-array
Design tiny url
1. Present project
Copy Linked list with node point to other
2. Boogle, Trie
3. Design a feeds system, write and query
4. Find longest sub-array with sum to K
Update: 有人问key - value的设计题，这是我的一些理解，欢迎大家讨论指正
这是一个很有意思的题目，主要是考高并发下的key value存储系统，我一开始从
distibute hash入手，讲了讲分布式存储系统，类似 Dynamo. 后来面试官让我设计单
服务器上put, get, delete, update。可以借鉴GFS，比如以64K为存储块(block), 存
储块大小可以和面试官讨论，如果存储的value比较大，就用大的存储块(GFS是64M)，
在内存中维护一个Index(Key -> Block), 每次读写操作以存储块为单位，
1. Put: 在内存中写，写满64M，写入硬盘
2. Get: 根据Index找到对应存储块，如果存储块不在内存，从硬盘中读出，按LRU更新
内存中存储块，然后块内顺序查找
3. Delete: 直接从index上删除key，后台运行一个垃圾回收的程序，专门负责清理，
合并存储块
4. Update： Copy on Write, 先将原来的值copy出来存入新的块，update完成后
update index，这样可以避免读写冲突的问题。原来的内容会被垃圾回收处理。
distibute hash入手，讲了讲分布式存储系统，类似 Dynamo. 后来面试官让我设计单
服务器上put, get, delete, update。可以借鉴GFS，比如以64K为存储块(block), 存
储块大小可以和面试官讨论，如果存储的value比较大，就用大的存储块(GFS是64M)，
在内存中维护一个Index(Key -> Block), 每次读写操作以存储块为单位，
1. Put: 在内存中写，写满64M，写入硬盘
2. Get: 根据Index找到对应存储块，如果存储块不在内存，从硬盘中读出，按LRU更新
内存中存储块，然后块内顺序查找
3. Delete: 直接从index上删除key，后台运行一个垃圾回收的程序，专门负责清理，
合并存储块
4. Update： Copy on Write, 先将原来的值copy出来存入新的块，update完成后
update index，这样可以避免读写冲突的问题。原来的内容会被垃圾回收处理。
No comments:
Post a Comment