[转载 from mitbbs] Pinterest Interview Questions

发信人: sleeper7 (海景别墅), 信区: JobHunting
标  题: 分享一个图钉面筋
发信站: BBS 未名空间站 (Wed Apr  6 15:33:20 2016, 美东)

图钉公司 thumbtack
电话： 
1. Evaluate Reverse Polish Notation
2. constant space get median and mean, input stream, range [0, 10000), 用个
array[10000]就行了
Onsite:
1. design twitter search，面试官google出来的牛人老中，我虽然自己就做是
inverted index的，但答得还不不算太好。
2. 算search的TF/IDF, 题不难但是挺繁琐，search multiple strings, 返回一个总分
数，通过计算TF和IDF。我解释花了很多时间，白板字写得太烂了，最后还有点尾巴没
写完，就说了一下思路，也是老中面试官。
3. search 一个dict中所有前缀为一个string的word。Trie实现，laptop上跑过才行。
4. binary tree的serialization and deserialization. laptop上要能跑过才行。
5. 两轮跟manager, founder吹牛逼，我直接问了founder什么时候上市，founder大概
意思是反正不缺钱，不着急上市，5年内不会吧。
整体感觉里面人很牛，50个工程师撑出超过1B的融资，大部分都是FLG出来的。面试还
是很挑的，我虽然题都做出来了，还不是不成。

[转载 from mitbbs] Google Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: 狗家面经
发信站: BBS 未名空间站 (Fri Apr 15 01:20:25 2016, 美东)

电面太容易 ， 忘了

1. Number of Islands
2. Find Median from Data Stream, 举例描述每一步
3. Compute Avg for Data Stream, 小心overflow
4. MapReduce求稀疏矩阵乘法
5. Binary Search Tree Iterator, 举例描述每一步
6. Longest Alternating Subsequence

[转载 from mitbbs] Apple Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: 果子面经
发信站: BBS 未名空间站 (Fri Apr 15 01:27:04 2016, 美东)

电面: 只跟楼主go through了一下背景,  让我描述一下 lambda architecture. 怎么
解决cassandra 导数据速度的问题. 果家重度使用C*

Onsite
1.  Linked List Cycle
2. Valid Palindrome
3.  design apps store, 实现全球app同步,  各数据中心下载量同步. quorum, 
consitency, latency的选择. 
4. MapReduce实现表的Join

[转载 from mitbbs] Palantir Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: Palantir面经
发信站: BBS 未名空间站 (Fri Apr 15 01:44:22 2016, 美东)

电面: 
先给你看一下棋牌游戏介绍 https://en.wikipedia.org/wiki/Connect_Four

然后题目关系不大. 实现一个函数能解码以下被run length encoding的2D char数组 

|_|_|_|_|_|_|r|
|_|_|r|_|_|_|_|
|b|r|b|r|b|r|_|
|b|b|b|r|r|b|_|
|b|r|r|b|b|r|_|
|r|b|b|r|r|r|b|

   * 'r' 代表红棋
   * 'b' 代表黑棋
   * '_' to 代表空
例如以上例子编码是 6_r2_4_brbrbr_3b2rb_b2r2br_r2b3rb

函数返回char[6][7]

Onsite: 
1. 面试官突然拿出一副牌。说有N个人, 每人分一手牌.  按以下规则玩牌
   a) 每人出一张牌放桌面, 比大小, 不比花色, 没有joker
       * 其中只有一个人有最大牌，此人赢走桌面上的牌
       * 其中k人有最大牌, 此k人每人拿走三张手牌. k个人继续a)直到最后有一个赢
家出现,  此人赢走桌面上的牌
       * 如果在要出1张或3张牌的时候，手上没牌了, 此人彻底输了

   写一个函数, 输入每个玩家的手牌, 求最后的赢家

2. 设计一个类似JIRA的系统
3. 设计一个监控系统, 定时监控远端服务器的参数，远端服务器挂了能报警. 多线程
   
P家吃完午饭，放一小时demo, 如果下午没面, 说明已跪.

已跪

[转载 from mitbbs] Amazon Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: 亚麻面经
发信站: BBS 未名空间站 (Fri Apr 15 02:12:28 2016, 美东)

电面: 
geeksforgeeks: Sort a nearly sorted (or K sorted) array
亚麻是唯一见过电面面culture的公司, customer obsession, ownership
电面后culture跪了, 刷题pass. 

onsite: 
1. design rate limiter
2. 实现一函数， 输入为两字符串，其中任意一串为另一串的prefix返回true, 否则
false
3. 实现一数据结构, 支持以下两操作

void addURL(String url);
String getKthMostFrequentURL(int k);

4.  给一文本文件, 每行一整数. 写一函数，传入文件名, 输出K largetst numbers.
5. culture, culture, culture

[转载 from mitbbs] Cloudera面经

发信人: lusty (lusty), 信区: JobHunting
标  题: Cloudera面经
发信站: BBS 未名空间站 (Fri Apr 22 20:14:49 2016, 美东)

电面: 
1. 实现一个histogram, 能inc/get每种metric的counter.     
void incCounter(String metric)
int getCounter(String metric)
2. followup: 修改以上histogram应付并发读写


onsite: 
1. how to create a generic singleton class
2. 求integer流中最近k条数据的avg

public class KAvg {
    public KAvg(int k );

    public void add(int x);
   
    public int getKAvg();
}

followup: 并发add/getAvg

3. 用AtomicLong或compareAndSwap原语实现spin_lock, spin_semaphore, reentrant_
spin_lock
描述spin_lock的self deadlock情况

4. design whatsapp

5. behavior/ team conflict/strength/weakpoint

6. go through background

[转载 from mitbbs] Walmartlabs面经

发信人: lusty (lusty), 信区: JobHunting
标  题: Walmartlabs面经
发信站: BBS 未名空间站 (Fri Apr 22 20:00:06 2016, 美东)

电面， Environment Variable Resolution

给一堆环境变量定义
        A={B}_{C} //{B} is similar to $B
        B={D}
        C={D}
        D=x
这里的环境变量用{}括起来, 在linux是用$或${}
写程序把以上等式解析成
        A=x_x
        B=x
        C=x
        D=x


Onsite:

1.  给几个TB的文本文件， 文件每一行是一个登录时间timestamp. 用MapReduce求前
后登录时间差最大的n条记录
2. 要你讲各种常用design patterns. Singleton模式如何pass parameter
3. Singleton模式如何应付concurrency
4. go through background
5. behavior

[转载 from mitbbs] Intuit面经

发信人: lusty (lusty), 信区: JobHunting
标  题: Intuit面经
发信站: BBS 未名空间站 (Fri Apr 22 20:06:19 2016, 美东)

电面:  system design.  Intuit从各种源头收集报税信息， 怎么预算数据中心网络带
宽. 如何设计报税信息的格式

onsite: 

1. 死锁发生条件及解决办法
2. 按alphabet排序1TB的string
3. design database schemas以适应whatsapp这样的应用
4. 假设你在三维空间(x,y,z)， 有一系列星球的3D坐标, 求离你最近的K个星球
5. go through lambda architecture 大致如何实施

[转载 from mitbbs] FB On Site Interview Questions 面经

发信人: lusty (lusty), 信区: JobHunting
标  题: FB 面经
发信站: BBS 未名空间站 (Tue May 10 15:36:42 2016, 美东)


Jedi: 
  go through背景
  light coding: clone a graph

Ninjia:
　给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行
时间为5. 写一个函数输入task序列和interval, 输出运行时间。
　followup: 写一个调度函数，输入task序列和interval，输出task最优执行序列

Pirate: 
  设计一个大型在线多人视频系统，支持FB的scale

NinJia:
  Best Time to Buy and Sell Stock 
  followup: 返回买入和卖出时间的Index
  Search in Rotated Sorted Array

Pirate:
  设计一个系统。输入为FB用户的status流, 每个status的组成为多个tags, 用户可通
过　tag1 and tag2 or tag3之类的查询语句, 查出满足这些条件的status list.

Pirate: 
  设计一个google maps

Ninjia:
  leetcode Move Zeros变种
  leetcode Subsets变种

Pirate: 
  设计shortURL 系统

【转载 From MITBBS】Dropbox 面经

新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次

两个function;

void hit()

long getHits() //返回五分钟内hit了几次

Google System Design Interview Question

Design a system to hand out telephone numbers for Google voice.

You want to present numbers to people such that:
a person sees 10 numbers at a time
no two people should see the same numbers at the same time
they get 2 minutes to choose one of those numbers or ask for more. If they 
choose one after the 2 minutes are expired, the request fails.


Where you would put the various data elements - in a database, application 
servers, front-ends or the browser. 
What kinds of data structures you would use.

传说中 Databricks Interview Question

有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返

回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如

何利用原有方程，再写一个function，使得返回true和false的概率一样。

Interview Question: How to build a website: CS75 (Summer 2012) Lecture 9 Scalability Harvard Web Development David M...

Facebook Interview Question: Facebook and memcached - Tech Talk

Dropbox Interview Question: How We've Scaled Dropbox

[From MITBBS] Facebook and Google Interview Questions

Facebook:
Phone:
Input: Given a matrix of 0, there are some areas populated with 1, 2, 3s.
Output: Map<int, numOfRegions>

Onsite:
Round 1: cultural, project deep dive, things that can be done better
Round 2: Calculator, implement a function to output the current display 
based on the inputs that is already typed.
Round 3: Word Ladder II in Leetcode
Round 4: Design facebook event notification system (push on mobile app, and 
pull on web), discuss storage/api, how to generate events, prefer to use 
periodical job to scan incoming events and generate messages accordingly
Round 5: Culture fit, strength, how to deal with disputes among colleagues, 
reverse linked list in pairs

Google:
1. Given a robot and a maze, the robot supports these apis:
Turn left, move forward, checkIsExit
Write a program to make it move to the exit

2. Design Youtube access control system, storage, scales

3. Suppose there are k threads, write a multi-thread program to make them 
come to deadlock, I use semaphore at first, then was asked to implement it 
with countDownLatch

4. RunLength encoding, discuss various ways to minimize the encoded string 
under different constraints

5. Design a system to generate Ids for distributed DBs, discuss various 
Zookeeper patterns (leader elections etc).
For a given number, how to return minimum number of squares that sums up to 
this number

【转载 From MITBBS】FB 设计题

传一个大文件到几个数据中心，每个中心上千台机器。

【转载 From MITBBS】Uber面经

U家的
其实主要是聊天, 聊快玩了才问题目, culture fit是他们最看重的. 

1. Scramble Game, given some letters, and a big dictionary, how to get
all words that can be generated by combing these letters (use Trie)
2. Simulation game: 假设有一圈人(1 - N)成环状排列, 其中一个投出飞盘, 打到前
面一个, 于是前面一个倒下, 下一个接起来继续扔向前, 知道只剩下一个人为止, 求这
个人的id
3. Find min in rotated Array, design 分布式metrics 系统
5. Read4K problem, followup, how to make it work with multiple calls, 
subsequent call should starts from where the last one ends

【转载 From MITBBS】Google, Microsoft, Zenefits 面经

Google
电面了2轮，题目有：
一个grid，点代表城市，边代表道路，输入是一个起始点跟一堆destination,还有哪些
路被blocked 打印所有能到的点
老题，2d matrix的row跟column都是sorted, 在里面搜某个数
oil pipeline problem, 下面这个链接的10.3-9
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10
补充问题是如果有2根pipeline，怎么放

Microsoft
电面了2个组，记得的题目：
best time to sell stock变种，每天只能买0或者1个，可以卖任意多个 
BST输出给定范围内的节点 
棒球比赛，有N个batter，要记录每人打中的球的数目，还要按分数排序输出batter名
字，写数据结构+伪代码
还问一些操作系统，数据结构基本概念 

Zenefits
在线做题，3个小时2道题，可以去搜面筋，重复率很高
可以在线跑test case然后改，会告诉你pass几个fail几个，但是不告诉你具体哪个
case fail
第一个题目是下面这个链接的第一题
http://www.meetqun.com/thread-7939-1-1.html
第2题 rank of permutation 

【转载 From MITBBS】FB 面经

一个月以前面的了，没什么营养，还是发给大家看看吧, 希望对大家有帮助，已经跪了。

电面： 中国大叔面的，大叔很nice，遇到我写有bug的时候都会着急的提醒我，题也很
简单。

1： 给n个点找出离远点最近的k个， k<<n。
2: 给三个 api isSmall()  isMid() isBig() 给一个array 排序，只要不被迷惑， 知
道其实是lc 上 sort color的变种就很简单了。

On Site：

1： 聊自己的research，白人manager，说自己以前是faculty，人非常nice。气场也比
较合， 我讲完之后还说把email给我，说我面试后有问题可以问他，然后问了个 two 
sum。

2：亚洲小哥，也很nice，第一道题是 Lc 上的String Multiplication。 然后出了一
个打印 tree路径的题，后来问我做过没有，只能说做过类似的，后来换了一道 的 
decode way 变形，要把所有的可能的组合都打印出来，写了一个recursion。

中午和内推我的本版汤唯姐姐吃饭，在此谢谢汤唯姐姐，大牛非常nice，大家内推可以
去找他。吃饭的时候还说，上午过了最难的两轮，下午都是国人面试官，应该简单点。

3：国人面试官，貌似气场不太合，我写code的时候尽量解释，可能人家
觉得我也做不出来，无聊的看了很久手机。出了这个题
http://www.mitbbs.com/article_t/JobHunting/32906379.html

class IntFileIterator {
  boolean hasNext();
  int next();
}

class{
  public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；

}
// return if the distance between a and b is at most 1.. 
// Distance: minimum number of modifications to make a=b
// Modification:
//   1. change an int in a
//   2. insert an int to a
//   3. remove an int from a

都怪自己事先没把本版的题都做一遍，然后就跪在这道题上了，巧的是貌似帖子的一个
妹子也是这个国人同学面的，大家记得一定把这道题做一下。

4. 国人面试官面出的 design：Shorten Url。面试官人非常nice，可是自己答的一般
，在此谢谢他。

白人经理很nice，果然当天就写了个email给我，说很enjoy 和我的talk。hr拖了很久,
上周通知，不出意料的跪了。