http://www.mitbbs.com/article_t/JobHunting/33111683.html

之前也onsite了dropbox, pintreset, 和whatsapp都挂了，后来才慢慢找到点感觉。我
把面的题基本都写下了，但我不在这里和大家讨论这些题了。

A (Airbnb)

1. 2D array, 访问顺序必须是‘回’字的方式，就是从外圈转到里圈，写出class, 
Iterator, hasNext(), next().
2. 电话号码和计费的一个log, 去parse 看规定时间内哪个号码产生费用最高。
3. leetcode anagram 的一题变种
4. 有很多个sorted queue存在不同服务器上，如何有效的读取到一个 sorted 大queue
里 (google也面到了这题）
5. 设计db, 如何存取房东和房客的reviews, 如何maintain他们之间的关系。

Airbnb确实和大家说得一样面试官很nice, 内部装潢笔格明显很高，非常酷炫.
offer: 160k + 5000股／2年 ＝ 260k


A (Amazon)

1. leetcode tree的一题，就是每层的nodes横着也是连着的
2. 设计搜索，在amazon搜索如何设计。
3. 写一个class可以把树存入到db里。
4. 设计游戏的背包ood.

onsite过了后，hr说onsite feedback很好，但要再加面一轮电面，电面只问了一些
behavior的问题，第二天收到据信，没见过这样欺负人的。


G（google)
1. 一段话，里面有几个关键词可以被替换成别的词，比如 $Foo 可以换成任意的词，
设计class搞这个。
2. 一道图的题，打印出所有的环。
3. 有很多个sorted queue存在不同服务器上，如何有效的读取到一个 sorted 大queue里
4. 在一个2d数组里，打印出某一块矩形所框范围内的所有值的和。
5. 2d数组里走格子，给你A点位置，有的格子不能走（石头）有的能走，问最短路径从
A到B.

感觉不难，面试官都很nice, 遇到的国人都很好。
offer: 150k + 500gsu ＝ 240k 报了别家offer试着match之后的数字

G (Groupon)
1. leetcode 存水那题变种
2. 设计hashtable
3. manager 聊天
4. 设计类似hdfs的一个题
5. 把一颗树按每一层砍断，每一层变成一个linkedlist, 然后根据linkedlist复原原
来那棵树
6. hr聊天

我觉得Groupon的人水平挺高的，很多背景很牛，就是乌泱泱的烙印(palo alto)
offer: 155k + 52k股票钱 ＝ 207k

后面几家真的记不太住了，都叉了，回头想起来再补上，我就先报一下数字，方便后人
参考。

L (linkedin)
offer: base很高，具体忘了，一年250k左右

C (cloudera)
offer: 130k + 7500rsu + 10% + signon 20k = 204K

Z (Zenefit)
offer: 160k + 50k options = 290k左右

U (Uber)

最给力的一家，也是我最后签的那家，我就多啰嗦几句。
offer: 135k + 17500RSU／4年 = 345k左右 （按48一股算的）

Uber是这几年争议最大的公司，我很喜欢他的不确定性，如果什么东西都被你看透了我
还玩个毛阿。uber不是一个去切蛋糕的公司，而是能把蛋糕做大的公司，Uber的收入、
增长率和执行力都很好，最牛的地方是在需求和供应之间建立了纽带，uber开始做你下
车的地方可以推荐附近好吃的餐馆和酒店；出去玩自动生成游玩路线和景点购票；还有
无人车，已经在路测了。实际上他在不停的创造新的行业，后面肯定会有小公司做起来
配合uber的服务形成新的产业链。我也愿意趁着年轻去拼搏一把，输赢都不重要，就如
同比起一直在岸边观看，我更喜欢和一帮小伙伴扬帆远航，探索新世界。

http://www.mitbbs.com/article_t/JobHunting/33109951.html

最近面了FLGU以及一些小公司, 运气较好，竟然全中。废话少说，直接总结准备过程并
上面经造福后人。中文表达障碍敬请谅解。打乱顺序以免麻烦。 其实这些题几乎100%
都是原题或者面经题啦。。

coding准备: 就把leetcode刷了一遍， 大概有10几题觉得好烦到现在也没做。 还好没
做：P 我觉得刷题一定要集中，不要拖太久。我刷了一个月的时候觉得受不了了，白天
上班，晚上哄宝宝，宝宝睡觉后做题，累的崩溃， 于是赶紧投了。边投边刷，效率很
高。前后全算上一共两个月。

design准备：板上有几个design总结贴，非常管用。我就是照着 flamingos和beidapig
的两个总结贴，大概看了看，学习了不少知识。
http://www.mitbbs.com/article_t/JobHunting/32777529.html
http://www.mitbbs.com/article_t/JobHunting/32984309.html

扯淡准备： 我觉得聊天很关键啊。学会聊天有助于拿offer。我这几个公司多少都出了
点纰漏，没有做到完全bug free。当然，可能别人看到是女码农就降低标准了也说不定
。。

coding:
1. 一个黑白图，用quad tree表示。 先定义数据结构，然后找intersection of two 
quad trees
2. sort colors
3. 给一个string里边每个char表示一个job, 还给了一个k, k表示俩相同job中间的最
小间隔。 input string里的job顺序不要打乱， 求最后完成这些job的总时间。
4. i) 3sum smaller ii) one edit distance
5. matrix with obstacles, 给你起点终点，BFS算最短距离。
6. find power set of a given set, with no identical numbers。 
7. 验证 UTF-8  string是否合法, count # of chars
8. letter combination of phone numbers
9. regular expression matching
10. 给一大堆点，求k nearest points 
11. house robber I and II
12. roman to int && int to roman, 怎么验证roman是不是valid
13. bst 打印sum是一个target的所有path
14. 判断俩tree是不是对称， 是不是相等
15. alien dictionary
16. 3个矩形求覆盖的面积。
17. spiral matrix I and II
18. group anagrams 
19. 原题shortest word distance I II III
20. 一个很简单的dp, 实在记不住了

design:
1. 设计spotify, 怎么实现given k, 返回当前听的最多的k个歌。
2. 设计web crawler, 给你一定数量的家用机配置的机器，设计怎么把abcd.com/index
.html上的所有link和link里的link都下载下来。
3. 设计某location based service, client 每过几秒钟report location。
4. 假设有个server, 有一些client往server上上传数据， 每个数据有序列号。 
design需要message格式。 假设要support query,  给定一个序列号，返回>这个序列
号之后的data。 设计message什么格式。这些数据怎么存储。 很多discussion记不住
了 。。
5. 设计一个股票交易相关的service， 其实是存储股票实时的价格更新，和一些实时
query. 比如你会收到各种股票的update, （股票名，价格，时间），你要设计数据结
构，设计怎么得到最近一个interval内某股票最大值最小值平均值。 数据怎么存储，
怎么更新，怎么synchronization等。
6. 设计搜索引擎。inverted index怎么存在multiple machine上。query来了怎么处理
之类。

http://www.mitbbs.com/article_t/JobHunting/33099463.html

就是按照时间顺序执行Task那道题，我收集了一些答案自己写了一下，

还请大牛多多多多的指点下，有没有问题。

多谢，多谢！

public class ProcessingQueueTest extends Thread {
    //用个minHeap存Tasks
    private Queue<Task> Tasks = new PriorityQueue<>(new Comparator<Task>(){
        public int compare(Task a, Task b) {
            if (a.time < b.time) return -1;
            else if (a.time > b.time) return 1;
            else return 0;
        }
    });
    private boolean isRunning = true;
    // 加Task进Heap
    public void addTask(Task task) {
        synchronized (this.Tasks) {
            Tasks.add(task);
            this.Tasks.notifyAll();
        }
    }  
    // 停止run
    public void stopRunning() {
        synchronized (this.Tasks) {
            isRunning = false;
            this.Tasks.notifyAll();
        }
    }  
    // run函数
    public void run() {
        while (isRunning) {
            synchronized (this.Tasks) {
                try {
                    long sleepTime = 6000;
                    if (!Tasks.isEmpty()) {
                        sleepTime = Tasks.peek().getExecuteMillis() - System
.currentTimeMillis();
                    }
                    if (sleepTime > 0) {
                        this.Tasks.wait(sleepTime);
                    }
                } catch (InterruptedException ex) {
                    Logger.getLogger(ProcessingQueueTest.class.getName()).
log(Level.SEVERE, null, ex);
                }
                if (!this.Tasks.isEmpty()) {
                    Tasks.poll().execute();
                }
            }
        }
    }
}

http://www.mitbbs.com/article_t/JobHunting/33099527.html

面试了一些公司，职位是testing/software engineer，跟大家分享下面挂的经历。

tableau：
1. 聊工作经验半小时
2. 设计一个算法使得一个string list通过serialize和deserialize后返回同样的list
。没有答出来，回家上网看了是leetcode 271题，完全没有刷到。
public String serialize(List<String> list)
public List<String> deserialize(String input)

ea:
1. 聊工作经验10分钟
2. leetcode group anagrams，没有刷到这题，经过国人大哥提示才做出来。
==>没有后文了

prosper:
1. 解释java object oriented concepts: polymorphysim, inheritance, 
encapsulation
2. java multithread how to start two threads
3. how to test a web page with asynchronized response
4. reverse string
5. print multiple of 3 and 5
6. count occurrences of character in the string
＝＝》没有后文了

affirm:
1. 聊工作经验15分钟
2. leetcode Valid Parentheses 原题，轻松做出来了。
＝＝》两天后照样被拒。

Liveramp:
1. online 做题，青蛙过河和班上面经一样，然后解释算法
2. 为啥liveramp
＝＝》两天后被拒


感觉工作经验是不是match和刷题一样重要，等假期回来继续刷题努力。

http://www.mitbbs.com/article_t/JobHunting/33096137.html

上周五的onsitee，只刷过三道leetcode题目，硬着头皮上了。免得是大数据platform
组SMTS，挂了，不知道谁黑的。

一个俄国小哥：
比较热情， 先问了stack用linklist和array实现的优缺点，然后问了如何用二维数组
存储神经网络，比较耐心的引导类型，最后时间没有了，就只讨论了一下为什么这么做
。俺提出了一些可能的；

印度人：
上来很详细的问了以前的做的东西，HIVE如何转化成TEZ的，TEZ和MAPREDUCE的性能区
别，Slider提交任务需要那三个文件，我说就是三个json文件关于资源请求，可执行文
件等等，半年前作的实在记不清了，他解释说是metainfo.xml， 和两个json文件，俺
就极力说服他，please检查slider的apache JIRA buglist，现在俺还有几个ticket要
解决，他说他会。没让写code


一个国人伯克利小伙子：
随便问了问以前的项目，然后让做题， 给两个string，一个str1，一个str2，找出
str1里所有的str2
出现的第一个位置：比如ababab，ab那么返回数组［0，2，4］。先让写testcase，都
写出来了，提示我有一个情况没写，俺解释说已经出现过了。然后坑坑粑粑的写完了程
序，时间到了，他说程序没问题

跟经理吃饭，behavior问题

美国人：
问了一个给定一分，二分，五分的硬币，如何给一个数字x，那么如何用最少的coin来
表示x：
俺分析了greedy algorithm，先跟5分取余，在跟2余，在1余，把除数加起来就是了。
然后改成1分，3。5分，5分，如何做？俺先想了probablilty的决策树，然后被direct
回图论，后来就是BFS，然后俺提出了一些优化方案，比如，如果跟3.5取余还有.5余数
，那么这一个分支就不用traverse了。

国人大哥：
系统设计：一个threadpoolexecutor的queue很多put，dispatcher在get，如果put很多
怎么办，要写个method，一个是put一个是get，俺先想了如果queue full了需要那么
put方法sleep，sleep时间可以采用fabnacci数列，但是有最大值限制，达到最大值后
再返回，因为queue的访问服从possion分布，后来问如何马上让put的线程知道。我说
我们可以用wait和notifyall，但是没用过，他比较nice的说这个很简单，但是你没用
过，我们问个别的吧。
问了个string permutation问题，
a：
ab： ab，ba
abc： abc，acb，cab，bac，bca，cba

俺给了recursion方法，花的时间有点久，后来写的没时间了，跟他想的方法不太一样
，但是equavilent。

经理：
设计题：
1.如果slider提交的container继续trigger AM，那么YARN的RM会不会负责fault－
tolerance，答案是如果这个container提交AM时通过slider， yes，如果不是，NO。
2. 使用YARN＋SLIDER，如何保证applicationMaster是可以trace的，如果发生failure
，如何再次找到AM。刚开始俺说你保存到数据库，后来发现他问的是同一个
application，就告诉他说，YARN的RM会提供RESTAPI，直接用applicationID就可以找
到application master的host地址和port，YARN命令行也可以。他问为啥之前没想到
RESTAPI，俺说没理解你问的是同一个application
3. 给一个系统，如何准确的找出第一百万个用户click。
俺先系统的给了一个设计三角形，定点依次是：时间，空间和精确度，告诉他，图灵机
的设计如果需要节省时间，那么需要牺牲空间和精确度，对于需要节省空间和提高精确
度类似。当然时间是有最小值的，不是完全能用空间和精确度来trade的。等等。 然后
开始设计。

俺提供了如下方案：
a. memcache 或是redis类似的分布式kv数据结构。
b. 分布式系统的同步方法，就是第一个发送自己的数量和一个atomtic 
incrementalvalue，然后第二个收到后，加上自己的数，再increase the 个counter，
以此类推。他说如果网络如果很忙，cluster足够大，俺就说，你是不是想减少通信次
数，就提供了MPI使用的REDUCE机制只需要log（n）步，然后他加入了failure，俺说那
可能需要加入冗余, 因为failure的基本解决原则就是冗余。
c. 后来又提出可以在前端loadbalancer内部加入cache，几集cache, write back or 
write through等方法的优劣。

今天给经理发信，说是挂了，没给原因，大家帮忙分析一下为啥，谢谢。

http://www.mitbbs.com/article_t/JobHunting/33100463.html

System design
    a.    Output produce(Input input)
    b.    Output merge(Output o1, Output o2)
    c.    Now given a list of inputs List<Input> inputs, using k threads to
    generate the result. 
    d.    Queue, lock, thread safe and so on

any idea? Thanks,

http://www.mitbbs.com/article_t/JobHunting/33083975.html

前后三次onsite,每次过了之后才能进行下一次，感觉就是一条命打魂斗罗。他家每场
面试1.5hr，很耗体力。


一个月前online test过后安排店面，因为人在湾区，可以直接去公司onsite.
onsite 1. 
         写一个函数，从文件头和文件尾分块读取数据，然后交换后分块写回去
         如果写中途down机怎么办。方法是用transaction log记录操作，重新开始后
roll back
         题目比较基础，不过顺带会问大量c相关的问题

onsite 2.
          1.bit manuplation
          2.判断是否是BST, leetcode原题 
          3.重构一个malloc函数，如何开辟内存的初始地址是N的整数倍，如何设计
对应的free
           基本思想是开内存多留些冗余，修改要返回的指针指向地址，使其指向位
置指向整数位地址
           free的时候有个小trick，要在开内存时，找个地方把指针移动位置记录下
来，这样free时就能找到地址修改值，推算出原来指针修改前的位置，能全部释放
          4.问了大量char,array,point，OS，内存管理相关知识
   

onsite 3.
          1.buddy system https://github.com/jasonfeng1989/Tech_Interviews/
blob/master/others/buddy_bitmap.py
          2.task dispatching system
http://www.mitbbs.com/article_t/JobHunting/32702941.html
做题时候会顺带问大量multthread lock相关的知识，如果做题速度慢，没有很强
hands-on经验，即使题目做出来也很容易被看出来。  

感觉他家算法题目很基础，但面试时，会问大量相关OS，c/c++，存储方面知识，如果
相关经验不多会比较郁闷

LZ EE背景 wireless天线方向，骑驴找骂转行CS，c/c++回答的都还可以，但那个职位
对multthread OS要求很高，没有太多经验
，结果悲剧了。。。