当前在线人数10117
首页 - 分类讨论区 - 海外生活 - 待字闺中版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:LGTF面经和总结
[同主题阅读] [版面: 待字闺中] [作者:redarm] , 2013年11月16日03:46:16
redarm
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: 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.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996