发信人: redarm (20131029), 信区: JobHunting
标  题: LGTF面经和总结
发信站: BBS 未名空间站 (Sat Nov 16 03:46:16 2013, 美东)

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

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，这样可以避免读写冲突的问题。原来的内容会被垃圾回收处理。
--

※ 修改:·redarm 於 Nov 17 00:39:47 2013 修改本文·[FROM: 50.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 71.]

--

本文来自: http://www.mitbbs.com/article_t/JobHunting/32578885.html