[转载 from mitbbs] 骑马找独角兽的过程

发信人: geniusxsy (小尾羊), 信区: JobHunting
标  题: [bssd]糖一下骑马找独角兽的过程
发信站: BBS 未名空间站 (Sun Feb  7 04:28:51 2016, 美东)

干货不多，大家有兴趣打发时间的话就看看吧。这贴也许对fresh grad没啥意义吧，对
experienced或许更有用些。

＊＊＊＊＊＊＊ 我是小广告的分割线 ＊＊＊＊＊＊＊＊＊＊
帮ld求好心朋友帮忙内推下三番或者中半岛的轻松养老型的马工职位，ld在某软某办公
软件里呆了若干年，现在才发现没有积累到什么流行的技术，现在想找工作背景上比较
吃亏。不过ld底子和学习能力都很好的。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

背景是在西雅图地区的G干了五年多主要做backend。最近一两年前，身边朋友纷纷跳槽
，现在比较后悔的就是，早知道两年前刚拿到卡就该挪一挪，拖到现在算有点晚了。另
外一方面，在G干的活，现在也越来越提不起兴趣。朋友的怂恿和激励下，去年10月终
于下决心要跳了。
==> take away: 要跳趁早，时机不等人。

当时也没想要跳湾区，差不多就是一心想去打车公司的西雅图分店。其实去年夏天就有
些蠢蠢欲动了，刷了几道题后懒了又不了了之。10月份开始认真刷lc，刷的也不快，到
12月才勉强刷一遍。后来回想，浪费很多时间，其实各个种类挑着做50~100道应该就差
不多了。然后花了很多时间精力去复习系统相关的知识。G家自己的用过的infra复习下
，spanner没用过，正好跟新project沾点边就看了个大概。有些东西像chubby, pubsub
用过但是内部完全不懂，趁这个机会也翻翻人家的design doc有点大致的了解。当然最
后我觉得也没有真正派上太大的用，不过做为知识积淀也挺好。然后就是市面上的技术
我是完全没接触过，起初还很担心，不过学了一圈下来也觉得没啥高大上的，大多能在
G里面找到类似的，而且比起G做的更简化。这些花的时候不必刷题少，而且design doc
/tech report/paper这些读起来可没有做题那么有趣。
==> take away: experienced hire，刷题到一定程度就够了，其他的知识积淀还是更
重要。

废话一堆之后，来聊聊面试经历吧。如果你是来找算法题，可能要失望了。忘了有没有
签nda，不过遇上很多国人interviewer，慎重起见我尽量模糊化具体的面试题。其实我
说了也没用，真的，更重要的东西其实是在交流上。

12月朋友催我说打车公司又要融了以后pay的越来越少要来赶快啊，我总觉得没准备充
分犹豫了一阵，月底才鼓起勇气让朋友递了简历。对拼趣一直也挺感兴趣，也让朋友帮
递了，不过说实话，当时也就是想试试而已。然后顺手找人帮投了个脸书家，想拿来练
手。听说facebook考刷题比较多，我自以为擅长做题。加上我背景里面social graph, 
infra, product都沾点边，去面之前有种offer手到擒来的感觉。结果就悲剧了，怎么
说呢，也不算是被黑，发挥的也不好，有些很弱的失误回家路上就意识到了。算法题基
本上都是lc上的，有一道是hard但是那种非常经典大家都会做的，其他都是medium水平
的题，一共涉及了binary tree, stack, backtracking, prefix tree这些知识点。系
统题是让设计一个code search系统，基本上就是先装模作样分析估算下，然后画画大
的框架，反正差不多就是凭着经验和感觉走，然后接下来就是interviewer提问，对某
些component或者某些具体的情况zoom in进去讨论。虽然search我没做过，indexing系
统还是稍微接触过的，但是时间久了忘了不少，回家后又正好补了下知识。
==> take away: 面最心仪的公司前练练手也很有必要。

等脸书结果期间面了两轮u的店面，两轮都是很nice的中国人，跟第一位大哥中文聊天
也聊得非常愉快，coding题目也不难，用queue就能解决，大概也是放水吧。第二位系
统设计也是国人，问的google map，当时也没怎么准备过geospatial方面的话题，我觉
得磕磕碰碰的，结果还是承蒙面试官放水给过了。P家店面又是中国人，运气很好，问
了中等难度的lc题，就给水过了。不过有意思的是，这两家的coding都是online写完编
译调试，像我这样经常犯些typo或者弱智失误的，调试能力就可以弥补一些粗心，啪啪
啪的很快改完跑通，大概也给interviewer留下确实能干活的印象吧。不过坏处是如果
一两分钟没调出来，压力瞬间爆棚，只能扛着了。
==> take away: 其实大部分国人还是很nice的，遇上是缘分和运气！

这个时候fb悲剧的消息到了，感觉信心很受挫，情绪比较低落，本来觉得十拿九稳的事
情都黄了。其实现在想想悲剧是好事，让我带着卑微的心态努力尽力的准备之后的面试。

打车公司的onsite是在三番，虽然我申的职位是在西雅图。第一轮是老美mgr，名义是
考behavior，其实就是聊天，没有什么奇怪的问题。我准备的也比较充分，比较放松，
吹吹自己做项目的经历，侃侃对他家美好前景的向往，大家聊的也很愉快。第二轮是设
计题，他家的几道经典设计题目之一，设计netflix。还是先需求功能分析，然后画大
框架结构，然后主要问了下，serve media file怎么做到high available, high 
throughput，这方面其实不太懂，这个时候就只有借助知识储备开始瞎扯，一会儿瞎扯
些分布文件系统的东西，一会儿又瞎扯些backup requests，parallel read等方案，然
后上面的caching层再扯几句。接着又继续问了recommendation系统，时间不多，只能
大致提了下user-based/item-base CF这些。其实几年前粗略的看过一些netflix做推荐
的资料，马马虎虎应付一下还凑合。总的感觉还是聊的比较愉快，交流上基本上还是比
较合拍。接下来一轮，我现在还有点摸不着头脑的感觉，很open的problem solving，
说是design但又不是system design，大概就是主题公园排队时提供fast track，比如
，交5块钱，告诉你一个小时后回来，有点像scheduling系统。最后还让写code简单模
拟一下。我稀里糊涂的都忘了怎么答的，感觉答的如何心里很没谱，最后居然也还是给
过了，也许是我东扯西扯一堆，擦着边击中了面试官心里想听的点子上？接下来一轮是
coding，简单的有点莫名其妙，其实后来听了不少别人的面经，U家问简单coding题似
乎是很正常的！不过然后不停的followup，如果这个是正式的code，unit test你怎么
写，让你自己做code review，有哪些你会改的，怎么refactor？感觉是在考察实际工
作中写码的能力，其实也make sense，毕竟工作里面是没有机会写太fancy的算法。不
过我觉得这样面，有工作经验的人写码多的人，尤其是从像g这样code review严的地方
出来的，应该都能pass才对。最后一个人又是聊天，大概聊了一半时间后，顺带着引出
一个系统设计问题，也是经典的高频题，就是让设计他家的打车系统里面的一个
feature，轻松搞定，走人。

总的来说，一大半时间感觉都是聊天，扯，吹牛。他家也特别看重culture fit，就是
你要有passion，要有ownership，做事快，take risk。我觉得这些都是靠聊天里面慢
慢透露出来的信息，不是说简单直接了当的问。当然了，认真准备culture fit我觉得
是非常有必要的，其实技术上的水平和背景经历，面试之前基本上就是定下来了的，而
culture fit是可以通过认真准备更充分的体现自己的fit。对了，每个interviewer必
问一次为什么想来U家，我都快能背下我的答案了，最后一个人问的时候，我就明给他
说， 前面问过很多次了，I’ll try to answer this in a different way，然后就即
兴了。
==> take away: 面试中交流聊天非常重要，我觉得不亚于做题写码的重要性。

一个星期后就是拼趣的面试。这一个星期内主要的功夫是花时间用他家的产品，做功课
，产品功能，business model，并且想想哪些是做的很好的，哪些地方可以提高怎么提
高。然后拼趣家的四点文化，认真想下交谈中怎么结合自己的经历能体现出来，对于有
经验的人，我想这些下功夫都是能做好的。虽然我准备了这些，但是最后其实很多准备
的东西都没有机会用上，不过至少还是让我有足够的信心去和面试官交流。拼趣的中国
人非常多，更难得的是，中国人都很抱团很友善，有三轮都是中国人面试官。因为准备
加入拼趣，面试题就不详细写了。
==> take away: 有针对性准备充分，也许会胜过广撒网批发面

打车公司最先给offer的，但是包裹一开始压的非常低，base跟现在差不多持平还略低
一点，只有$43w股票，基本上包裹就是跟现在持平，很失望。直到我有了拼趣的offer
，才追上来，谈到68w也谈不动了。

拼趣很快给了口头offer但是各种原因数字拖了一周才出来，base还不错比现在高，但
考虑到州稅。。。股票最后给涨到1个米，整个过程非常爽快，我也很开心。我知道有
牛人能要到更大的包裹，不过我想自己满意了就好。朋友说他家每年给的refresher也
比较给力，想起来纸面上的数字还是很吸引人。当然，如果没上市，就是一堆废纸。这
次也是我第一次真正经历negotiation，最后效果也还满意，也从朋友那里学习了不少
讨工钱的经验，如果有人有兴趣可以私信我，或者下次有空写写。

最后选了P，钱给的满意是比较小的一个因素，其实U给的也算还不错了。其他很多个人
的考虑，这里就不多说了。至于公司前景的比较上，不用说U的吸引力非常大上市几乎
是必定的，P的风险相比更大，但是潜力也不错，团队也很强，我觉得拼趣的
monetization做的不错，感到有比较强的信心。有机缘跟很多p家的国人接触过，觉得
他家中国人多而且友善团结融洽，这点很喜欢。

[转载 from mitbbs] System Design 总结

发信人: flamingos (flamingos), 信区: JobHunting
标  题: 我的System Design总结
发信站: BBS 未名空间站 (Mon Sep  8 02:49:55 2014, 美东)

我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面
试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言

这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目

== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍

2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid 
single point of failure
再强调一遍 非常好的资料！

3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想

结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)

== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频 
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下 
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了

4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看

5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube, 
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的

6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk 
很不错 可以看看

7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook 
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic

8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498

9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过 
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb

10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems(http://www.amazon.com/gp/product/1617290343) --
twitter的前员工讲述如何处理实时数据 目前市面上讲解big data最好的一本书

10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read 
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system 
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题

最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论

== FAQ ==
1. New Grad需要看System Design么?

答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?

[转载 From MITBBS] Asana, Microsoft, Zenefits Interview Questions

Asana:
(1)    Given an array, return an array of product without current value
example:
given [1,2,3,4] => return [24,12,8,6]
(2)    OOP: 如何solve拼图
(3)    Regular expression match, 不是leetcode的那个题，主要考点是计算reverse
index，没让写code，主要讨论想法
(4)    中午吃饭前三道编程题 （1） 不用除号实现除法 （2） 设计data structure
存储java script file （3） 拓扑排序
(5)    饭后讨论三道编程题
(6)    Powof4， OOP design国际象棋 （从来没下过，纯粹现想）

Microsoft:
(1)    Anagrams
(2)    Sorting (考点是counting sort, 题目大概是，给你一个数组，但数组里面的
数保证范围在1 – 100 之间) 这样对于数组很大的情况把每个数都数一遍更快，一开
始没想到，耽误了一点时间
(3)    计算reverse index， 类似与merge sort的题目，一个g内存，16g文件要求输
出reverse index of each word of the given file
(4)    Populate binary tree next pointer

Zenefits:
四轮全是烙印
(1)    一轮两个题，第一题是DFS 具体题目忘了，另外一道是打印公司所有雇员名单
，要求自己选data structure，input 文件是每一个公司职员的名称，如果是manager,
还会有这个manage管理人的名单。要求输出是给一个人名，输出这个下面的所有report
  chain，每一级要缩进。 这一轮面的不错，第二题把意思一讲面试官说ok，就写了几
个主要function，感觉他还挺满意
(2)    给一个array， 找出最高点或最低点，例子如下
【1,2,3,2,1】 => 3
【3,2,1,2,3】=> 1
  [1,2,3,4,5] =>-1
第二题是simple calculator (leetcode)
(3)    设计一个cache，要求实现如下功能:
1.    Add
2.    Search
3.    Delete 
4.    Delete all
要求每个function的时间都是O(1)，catch是这个cache只会存储 1 – 500M的数字；挺
有意思的一道题，当时想出来了，面试官看起来还挺满意
(4)    Manager behavior questions

[转载 From MITBBS] LinkedIn, Google, Facebook, Twitter 面经

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

LinkedIn Interview Questions from Glassdoor

LinkedIn – Glassdoor 面经

permutations (Scramble an array with an equal chance for every value. Return a list of all permutations of an array.).  

Max subarray problem
Print Tree Level by level

1.      Find the shortest path between two words (like "cat" and "dog), changing only one letter at a time. You need to write code on a laptop and explain the code, run time etc?
2. Design round - In a distributed system cluster set-up, you've exceptions on each and every machine. How would get TOP 10 exceptions in last 24 hr time window.

3. Book Keeping round with Manager - lots of book keeping questions why linkedin etc?

4. One more book keeping round this time with one more guy.

There was no unexpected question as such. One of them involved searching in a matrix sorted row wise. The other one involved finding the exponent of a number in an efficient manner. I figured the exponentiation by squaring method and wrote the pseudo code for that which was correct. All in all, nothing unexpected and the questions can be answered with a little bit of practice. 

 Two sum Problem and check if it is a BST

 Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if $array[3,7] is 1 that means that 3 influences 7.

An "influencer" is someone who influences every other person, but is not influenced by any other member.

Given such an array, write a function to determine whether or not an "influencer" exists in the array. 

At the end of a long day of interviews I was asked about a prior success in my career. I was not told that there was a second more critical part of the interview - another coding exercise at the whiteboard.

Code a non blocking thread safe queue
and
code a text justification routine (Given a line length insert white space so text is uniformly displayed within the given length).

Both are fairly straightforward, but I had spent time on the first portion. 

How would you design amazon.com?   View Answer

Program an iterator for a Linked List which may include nodes which are nested within other nodes. i.e. (1)->(2)->(3(4))->((5)(6). Iterator returns 1->2->3->4->5->6  

1.      mobile backend system design
2. security system design
3. DP question
4. binary tree question (encode in a line and decode)  

2. Implement a shooting algorithm for the game of Battleship.   Answer Question
3. Implement an algorithm to convert an integer into a roman numeral string and vice versa. 

Implement a hash table

Given a list of numbers L, output a list of numbers where the value at index i is the product of all values in L, excluding the value at index i.

Solve this without using division.

How to write a deep iterator.

 Implement an RPN calculator in Java

One interview was on system design where they asked me to implement my own web crawler system. Again very technical and deep. I didn't know much about search systems so didn't do very well here. Two interviews focused on coding. First was a Dynamic programming question that I had not seen before. Required a bit of help to realize that it was a DP. Was able to write code after I realized the approach. Second coding question was to find the longest arithmetic progression in an array of integers. This was easy.

Implement a function to solve an string given in reverse polish notation. 

 In the first interview: they asked me to implement a pow(base, exp) function. I did a linear solution and they asked me to improve it (time complexity). There's a logN solution for this problem. 

A couple tricky questions. One required writing a modified binary search, the other dealt with data structures and how to efficiently check if a given set of numbers contained two numbers summing to some other number x. 

Implement java's pow function 

None really. Design data structures for different purposes, read a string as a number, write a polish calculator method. 

implement power of POW(double x, int b). Look for special if b<0. write it in O(Log n) time. 

given like +77288.100, a772sb, 2000.00.11.
return if it's a number.
you could either write a regular expression or simply go through the string.
1. it should start with "+/-" or "0-9".
2. there should only have one "." in the string.
3. all other character are "0-9"

 design a key value store 

 Breadth first search  

 implement a concurrent read-write buffer.

Code an RPN calculator with only (+, -, x, /) operations where each operation only takes in two integers as input.  

 Write a function to determine if a string is an integer.

Do you know Design Patterns and can you write a function in java to implement it?  

What is Abstract Class and its use. Gave me a example and asked me to extend and implement its methods   

Write a function to implement BFS.

 The question is how to decide whether the input is a double or not. 

 Traverse a binary there so that the order returned is ordered from smallest to greatest. 

 Find the sqrt of a number

nic interview. 1 coding question and reject.

/**
 * Given two (dictionary) words as Strings, determine if they are isomorphic. Two words are called isomorphic
 * if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all
 * occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters
 * may map to the same letter, but a letter may map to itself.
 *
 * Example:
 * given "foo", "app"; returns true
 * we can map 'f' -> 'a' and 'o' -> 'p'
 *
 * given "bar", "foo"; returns false
 * we can't map both 'a' and 'r' to 'o'
 *
 * given "turtle", "tletur"; returns true
 * we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' ->'r'
 *
 * given "ab", "ca"; returns true
 * we can map 'a' -> 'c', 'b' -> 'a'
 */

Onsite:
1. Find the shortest path between two words (like "cat" and "dog), changing only one letter at a time. You need to write code on a laptop and explain the code, run time etc?
2. Design round - In a distributed system cluster set-up, you've exceptions on each and every machine. How would get TOP 10 exceptions in last 24 hr time window.

3. Book Keeping round with Manager - lots of book keeping questions why linkedin etc?

4. One more book keeping round this time with one more guy.

One of them involved searching in a matrix sorted row wise.

The other one involved finding the exponent of a number in an efficient manner. I figured the exponentiation by squaring method and wrote the pseudo code for that which was correct. 

Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if $array[3,7] is 1 that means that 3 influences 7. An "influencer" is someone who influences every other person, but is not influenced by any other member. Given such an array, write a function to determine whether or not an "influencer" exists in the array. 

Code a non blocking thread safe queue
and
code a text justification routine (Given a line length insert white space so text is uniformly displayed within the given length).

·         How would you design amazon.com?   View Answer

·         Program an iterator for a Linked List which may include nodes which are nested within other nodes. i.e. (1)->(2)->(3(4))->((5)(6). Iterator returns 1->2->3->4->5->6  

1. mobile backend system design
2. security system design
3. DP question
4. binary tree question (encode in a line and decode)   Answer Question

 Three of the interviews were similar in format to the phone screen where a shadow interviewer would sit in on the interview. Two of these interviews were coding interviews where I was asked to write code on a white board. The third interview was a design interview where I was asked to design an object oriented web application. The fourth interview was with a hiring manager and seemed more to determine if I would make a good personality fit.

I heard back at the end of the week that I had been extended an offer.

Given a list of numbers L, output a list of numbers where the value at index i is the product of all values in L, excluding the value at index i.

Solve this without using division. 

How to write a deep iterator.

 Implement an RPN calculator in Java

One required writing a modified binary search, the other dealt with data structures and how to efficiently check if a given set of numbers contained two numbers summing to some other number x. 

read a string as a number, write a polish calculator method.

read a string as a number, write a polish calculator method.

 given like +77288.100, a772sb, 2000.00.11.
return if it's a number.
you could either write a regular expression or simply go through the string.
1. it should start with "+/-" or "0-9".
2. there should only have one "." in the string.
3. all other character are "0-9"
that's it.  

** Onsite Interview (6.5 hours)
2x simple coding interviews, 1x design architecture interview, 1x interview with higher up management + lunch, 1x HR.

I would not recommend people to apply or work at this company because management issues can be seen even during the interview process:
1) Each interview you get a senior interviewer and a junior interviewer, during the interview I can see the junior interviewer trying to please the senior interviewer and get attention from the senior interviewer.
2) Higher management guy I met with did not have fond words to say about LinkedIn. When we had lunch, we bumped into a lot of people but no one greeted him. I did not get a feeling that higher management is very liked/approachable by others in the company.

Code an RPN calculator with only (+, -, x, /) operations where each operation only takes in two integers as input. 

 Write a function to determine if a string is an integer.  

·         Do you know Design Patterns and can you write a function in java to implement it?  Answer Question

·         What is Abstract Class and its use. Gave me a example and asked me to extend and implement its methods   Answer Question

·         Write a function to implement BFS. 

Write an iterative version of a recursive function. Yes, it sounds basic, and yes it's easy to do for many problems (tree walking, Fibonacci series, etc). This wasn't one of the straightforward cases.  

double rpn(List<String> ops)' to compute some result using RPN. 

In the final session, the interviewer asked me to pick my favorite project and describe the design in detail. Actually, the paraphrased question was 'you just hired a new developer on this project, how would you get him/her up to speed on developing this new feature'. I described a bit about project and release management logistics, but they were more interested in hearing about and seeing class diagrams, module, component, and network topologies. Finally, the question that threw me off a bit was (since the project I described happened 10 years ago): how would you modernize the project for 2012? What different components or approaches would use and why?

·         How would you design an enhancement to the LinkedIn homepage that displays 24-hour trailing lists (5-minute, 1-hour, 1-day) of the top 5 URLs that users post onto the site?   View Answer

·         Given an interface called IntStream with methods 'bool hasNext()' and 'int next()', implement the function 'IntStream merge(IntStream[] streams)' where each input IntStream produces strictly increasing, possibly infinite number of, integers, and the resultant IntStream also produces strictly increasing integers by merging the input streams. The interviewer also provides a simple test harness that prints the first 5000 integers from that function.   Answer Question

·         Given a single-line text string and a maximum width value, write the function 'string justify(string text, int maxWidth)' that formats the input text using full-justification, i.e., extra spaces on each line are equally distributed between the words; the first word on each line is flushed left and the last word on each line is flushed right. 

Write a routine to find all collinear points in a plane. Constraint: The time complexity cannot be greater than O(n^2). 

 check if a given string is a number

Second one was to write a deep iterator. 

·         Describe your recent project. The reason why you leave the current job.   Answer Question

·         Find maximum successive sum in a array   Answer Question

·         given an article, output in a format that for each line, spaces between words are equal. (If impossible, how to deal with)   Answer Question

·         Reverse words in a sentence  

How u would build a site providing url shortening service.

 How would you improve LinkedIn's personal profile page

This time it was a tough question about writing a program where given a sorted array, repetitions allowed, and given an integer, I had to return the start index and end index of that integer in the array. I chose the Binary Search approach but some modifications had to be made to make it optimistic in run-time.

Find a number in a matrix which is sorted by row and column  

How do you design the monitoring system for linkedin servers?

Some C, C++ questions..also on Data structures...   Answer Question

How do you design the reporting system for linkedin servers

Given a large document and a short pattern consisting of a few words (eg. W1 W2 W3), find the shortest string that has all the words in any order (for eg. W2 foo bar dog W1 cat W3 -- is a valid pattern) 

 Intersection of 2 number arrays.

Design a scalable server for the hangman game

·         Design and implement LRU cache   View Answer

·         Reverse a linked list   View Answer

·         Online system design for monitoring   Answer Question

·         How do you rampup someone fresh from school  

Design and code a system that can accept millions of events in real time and report the number of events for the last 10 minutes (sliding window). The system has to account for performance and concurrency. 

 filteriterator hasnext() and next() function 

 Design a hangman game

·         2 integers that add up to a sum in an array.   Answer Question

·         Top 3 integers in an array   Answer Question

·         Top million word counts in a very large data set like web.   Answer Question

·         Online hangman. About security scaling session stAte etc 

Check if an element is present in a completely sorted 2D array.

Its an easy problem to code, if you can figure out the right approach. 

designing hangman web application

·         Given a unbounded non-block queue, implement a blocking bounded queue   View Answers (2)

·         Give an array that has only the values 1, 2 or 3, sort the array in place. 

·         which project you did before you like most   Answer Question

·         consider a B2C website like Amazon, which will receive thousands requests from buyer per minutes. How will you design the "shop cart " component for it? where should the customs' shop cart data stored? 

·         implement a O(1) min function for Stack   View Answers (6)

·         implement LRU cache 

·         Explain how hashmap is implemented, particularly the put() method.   Answer Question

·         Two cooperative threads, how do you make one thread yield until certain condition is met. 

·         MergeSort   Answer Question

·         Cache design

·         Given a list of numbers, find the contiguous sublist that has the largest sum.   View Answers (5)

·         Given a sorted list of integers, an arbitrary split is made such that the end of the first list is appended to the first, i.e.:

1 2 3 4 5 6 7 8 becomes:

6 7 8 1 2 3 4 5

Find the index of a number N in the array, returning -1 if it does not exist.

determine if a graph is bipartite  

Given an array with duplicate elements give an algorithm to get the count of distinct elements in the array

·         design LRUCache   Answer Question

·         explain about scalability for web applications 

Given a grid of size m by n, write an algorithm that computes all paths from 0,0 to m,n such that you can always step horizontally or vertically but cannot reverse. 

Reverse a single linked list.