Massive Algorithms: Linkedin Interview Misc 2

http://wxx5433.github.io/max-difference.html
Max Difference
给整数 x[0], x[1], ... x[n]，找 i<j, 使 x[i] - x[j] 最大
- scan from right to left, and maintains minValue so far

http://www.1point3acres.com/bbs/thread-198263-1-1.html

mid stack。例如push 1,3,6,5,4. 返回6。返回index的中值用双链表做,maintain一个pointer指向中间
follow up是写popMid()函数
Solution: http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/

http://www.1point3acres.com/bbs/thread-197890-1-1.html
一棵树，不限子节点。重构树，输入子节点数和Head节点。给出的Node Class没有写Child的方法，所以一直考虑从后往前生成子树。反正没有做完。后来烙印去开会，泰国裔的哥们说可以ClearChildrean，还给了一些操作Childeren Node的方面。我说Class里没有这些方面，他没有理我，感觉题目都换了。

一棵树有不限个数的子节点，有多层节点，不规则分布。给定子节点数K，重构这棵树。比如，子节点数是3。
那么第一层是1个节点，第二层是3个节点，因为root最多有可以有三个节点。第三层是9个节点，因为第二层的三...

http://www.1point3acres.com/bbs/thread-198305-1-1.html

R1:

1.Given  a k sorted link list, merge them into one sorted list. Code and explain the complexity.
2. Given a tournament tree, find the second smallest element. Code and explain the complexity.
3. Have a list of words, group words of anagram. Just need to discuss the idea and explain the complexity. No need to code.
R2
This is about data mining questions. Derive the maximal likelihood estimator for the probability p  of getting head for tossing a coin. Ask me to explain lagrangian multiplier, proximal algorithm from a paper, l1 regularization and so on.

R3: lunch

R4 data product design. On LinkedIn, connections of an user may have activities like changing a job, sharing an article, having new connection and so on. Was asked to create a metric so that you can rank those activities and display the top k, next top k activities to to a user. This is open ended questions. Discussion covered feature engineering, supervised learning, recommendation system and so on. Did not do well in this round.

R5: talked about background. Then was  asked to implement K mean clustering algorithm. Have to code a lot of details. Not allowed to use packages.

R6 with host manager. No technical questions. Mainly about background in PhD study, current job. Talked about Interests and why LinkedIn. I only asked a couple of questions at the end. Only lasted 50 mins for this round. Not sure whether its bad or not.HR反馈，第一轮coding比较好，第二轮 fine，第四轮产品设计跟第六轮host manager面不好。machine learning/data mining只懂理论方面的知识，缺少实际经验...到了面试就捉瞎
http://www.1point3acres.com/bbs/thread-167370-1-1.html

1. Given an array, shuffle it. API: void shuffle(vector<int> &nums)

a. When do shuffling, how to make sure each num is picked equally? Prove it.

b. How many permutation can you get?.

2. How to generate a performance report for a given URL? What to save, how to represent the result?

http://www.1point3acres.com/bbs/thread-167040-1-1.html

被安排了back to back interviews。第一轮被黑哥问culture fit。第二轮国人大哥的技术面，标准设计题两道。
1. https://leetcode.com/problems/two-sum-iii-data-structure-design/
无非就是问read heavy还是write heavy。然后两套方案两套代码。
2. Design and implement a cache which has a capacity. Dump the lowest ranked element if the cache is full.
然后就是追问怎么设计distributed cache system。

问了两道 permutation和lowestest common ancester(with parent pointer)

都是hashtable。read heavy就把所有sum 都算出来做pre-process。如果write heavy，就只是累加新加入数字的频率，read的时候去做2 sum计算。

read heavy就是每次add一个数就要把这个数和已经存在的数的sum都算出来存入hastable？

Set<Integer> nums for existing integers

Set<Integer> sums for sums

loop through each int in nums and add the new num. put the new sum to sums. don't care if it already exists. add new num to nums.

http://www.1point3acres.com/bbs/thread-159858-1-1.html

1. write back/write allocate cache的区别
2. suppose a==b, explain when ++a != ++b

我觉得第二题应该是 a 是 int ， b 是 long, 且 a== b == Integer.MAX_VALUE
3. give a string containing 'a' to 'z', sort lexicographically. Example " bbdda" - > "abbdd"
4. get influencer(celebrity)
5. maximum sum subarray, product array 这个就说了一下

http://www.1point3acres.com/bbs/thread-156463-1-1.html
第二轮：罗马数字和整数转换，两个方向都要写。需要考虑输入不
第二轮：罗马数字和整数转换，两个方向都要写。需要考虑输入不合法的情况，比如“VV”或者“IIII”都是不合法的输入，要输出错误信息
第三轮：机器学习基本概念考察，后来做了个算法设计，给一堆linkedin的job posting，怎么从中提取出工作的title和required skills，面试官要的答案是conditional random field
第四轮：机器学习系统设计，问了两个系统，一个是people you may know，另外一个忘了
第五轮：考察统计的基本概念，怎么evaluate AB实验结果的好坏，怎么估计p value，怎么估计置信区间
第六轮：找出1-3跳好友，算法和系统实现
http://www.1point3acres.com/bbs/thread-165529-1-1.html问简历+leetcode原题+machine learning knowledge。
简历不多说， leetcode 原题是 reverse polish equation那道。stack秒掉。followup 哪些地方应该handle exception。答了number和operator数对不上，还有number不valid，operator不valid的情况。之后按照要求写了try throw和catch。20分钟秒掉题目后，问了漫长的ML basic knowledge。楼主是做CV的，对ML只用不开发。所以只能回答基本的。人家问了SVM，Logistic Regression，和Random Forest。逐个用模糊的回忆答完。然后nice的小哥说还不错，但是detail还是需要多记住一些。。。这样就水过了一面。

Given three sorted arrays A[], B[] and C[], find 3 elements i, j and k from A, B and C respectively such that max(abs(A – B[j]), abs(B[j] – C[k]), abs(C[k] – A)) is minimized. Here abs() indicates absolute value.
Example :
Input: A[] = {1, 4, 10} B[] = {2, 15, 20} C[] = {10, 12} Output: 10 15 10。 10 from A, 15 from B and 10 from C
Input: A[] = {20, 24, 100} B[] = {2, 19, 22, 79, 800} C[] = {10, 12, 23, 24, 119} Output: 24 22 23。24 from A, 22 from B and 23 from C

当时拿到这个有一点点小慌。因为是sorted array，就下意识想了个binary search(O(nlogn))的方法，感觉比BF(O(n^3))。可惜啊，说完想法，大哥不让这么做。说有O(n)的法子，再好好想想。于是就是我漫长的思考时间。大概用了5分钟，想到了3 pointers的方法。但是具体怎么3 个pointer 还是不太明确。看着时间流逝真是心里滴血啊。。。不管怎样就硬上了。开始边实现边想。实现到一半，幸运的云开雾散了。原来就是每次移动3个pointer 里面最小的那个就好了。记录整个过程找最近的3个数。3个数之中median没意义，距离主要由最小和最大决定。基本就是这个思路。很快编完就过了编程阶段。
之后就是漫长的ML问题design过程。问了如果给一个用户，如何设计一个app，计算一个ad与这个用户多么relavent。楼主做CV的，关于这个顶多明白点image retrieval的相关。答了简单用logistics regression算propability，和如何建立feature，如何获取training data，objective function是什么。怎么regularize。如何cross validation。之后又问了SVM， Random Forest， Kmeans等等。大概聊了有35分钟这些。。。太漫长了。。。
http://www.1point3acres.com/bbs/thread-167931-1-1.html
1. Isomorfic string
2. Insert Interval and get totalCoverdLength
http://www.1point3acres.com/bbs/thread-166531-1-1.html
1. 一个熊孩子爱吃糖，然后糖果店搞活动，可以用糖纸换糖（每颗糖都有糖纸），input是： N, C, M
N 代表熊孩子有多少钱，C 代表一颗糖多少钱，M代表用多少张糖纸可以换一颗糖
输出能吃几颗糖。。。2. Single number https://leetcode.com/problems/single-number/
3. 找一个图里面有几个相互之间不连通的部分
http://www.1point3acres.com/bbs/thread-167751-1-1.html

第一题：之前面经看到过，用糖纸换糖，N 代表钱，C 代表一颗糖多少钱，M代表用多少张糖纸可以换一颗糖，最后输出能吃几颗。
简单的while循环就行，记得要加上余下的糖纸第二题：上来背景很复杂，吓了一跳，题目是Game of Thrones，Robert国王受到了Dothraki的攻击，
它们唯一的攻击路径是经过一条河，然而河上有个桥，桥头有个门，国王想把它锁住，
然后锁住必须知道一个密码才能锁住。。。密码是anagram of palindrome string。。。
so 最后的问题就是leetcode原题Palindrome Permutation
第三题：连续子序列，判断和sum％k＝＝0，求出array中有多少个这样的subarray。然后我一开始写了O(n^2)算法，只过了4个test case其它全部超时，想了半天没想出O(n)的方法，后来才在stackoverflow上找到了O(n)的解，写出来了不过还是不太理解，贴上地址求大神给翻译翻译：http://stackoverflow.com/questio ... rays-divisible-by-k

http://www.1point3acres.com/bbs/thread-167700-1-1.html
1. permutations leetcode 原题，秒过2. find celebrity leetcode 原题，秒过
3. right rotate binary tree。。。没见过 linkedin 会问这题，应该跪了。。。。。跪得甘心
http://www.1point3acres.com/bbs/thread-167711-1-1.html
总之linkedin原题率很高，刷了刚才提到的两个题源，behaviour question答好，再加上以前如果有其他实习经历，应该没啥问题。
12月11日一面，印度哥哥，leetcode 65 和 leetcode 102
1月5日二面，白人哥哥两个，leetcode 254 和 leetcode 151(required to use C and inplace)
寒假把leetcode linkedin题库和careercup linkedin 所有面经大部分刷了两三遍，但偏偏二面考到的leetcode 254只做了一遍，因为当时是自己解出的，所以没多加复习，但面试现场比较紧张做得不是很顺，说话声音都抖了，甚至有那么一分钟紧张到天旋地转（楼主心理素质有待加强），但过程中的每一个bug和思路错误都是我自己发现和抓回来的，没经过提醒。leetcode 151只用了递归方法做，inplace方法脑子卡住还没想出，很诚实地说there might be some trick that i can't come up with right now, sorry.
看来选track 还是至关重要的我选的ML 进pool两周了。。。等待拒信中
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148877&extra=page%3D9%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
一开始在一个会议室吃早餐，hr让每个人介绍一下自己，发现将近一半是cmu的...随后一个senior manager做了一个20分钟的presentation，之后一拨人去了sunnyvale，剩下的留在mtv。
第一轮：manager聊简历，介绍你以前做过的两个project，问的非常细。
第二轮：大胡子烙印，两道coding。1) design a data structure that support add data, remove element, remove a random element in O(1) time.
2) give you a bunch of intervals, calculate the total time coverage午饭，当天的面试者和hr还有几个engineer一起吃。L家free food确实好。
第三轮：design a notebook application like evernote or onenote, it should support search, collabration.第四轮：coding. 1) For an application, it has 2 configurations, a global configuration and an app configuration, a configuration is just a map with key and value. If the app configuration has some keys that exist in the global configuration, it should overwrite the value in the global configuration. write a function to return the final configuration.

follow up: if value of some keys has references: e.g.
key1: $key2
key2: $key3
key3: "foo"
rewrite the function that return the final configuration, resolve all the references. Notice that assume global configuration has no knowledge about app configuration, so references in global config can't refer to values in app config.

2) for each library, it has some dependency:
"foo": ["bar", "abc"]
"bar": ["abc", "cde"]
....
give you the dependency map, and a query library, return all the dependent libraries of the query library.

比如
Global:
key1: $key2
key2: "foo"
key3: $key1

App:
key1: "bar"
key4: "apple"

那么最后输出
key1: "bar"
key2: "foo"
key3: "foo"
注意global config文件是看不到app config的，所以解析的时候不能把app的内容覆盖掉它。我的做法是，先解析global，再合并两个map，最后再解析剩下的reference.

面试前本来想投application，hr说不招了，就换到tools了. 去了mixer.
http://www.1point3acres.com/bbs/thread-159433-1-1.html
第一题本来想给我出find triangle的，结果很不幸我在第一轮做过了，然后面试官就给我换了个text justification。。。
第二题是repeated DNA
http://www.1point3acres.com/bbs/thread-158571-1-1.html
1. 自我介绍
2. 基础问题：write-through和write-back的区别？各自优劣势？
3. commonAncester
4. paint house I， follow up：paint house II

问题是DelayedSchduled，Java来实现。写是写出来了，但是他给的hint我全部是连猜带蒙。。。到后面整个人都要崩溃了。。。
DelayedScheduled 是那个greedy的题吗？
http://www.1point3acres.com/bbs/thread-154277-1-1.html
merge two lists
maximum sum subarray
maximum product subarray
two sum
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=145037&extra=page%3D7%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
开始白女hr带参观公司15分钟倒不错，面试间里面有带我名字的礼物，一个我自己linkedin的关系图，也是惊喜，回来看了一下此功能已不对外开放了，总的来说公司对面试者很重视，很注重细节，不过面试间很小，几个咖啡厅坐的那种高脚凳很不舒服，我那个房间空调太小也不能调很闷。另外linkedin一共5轮，除了hm那一轮，每轮都是两个人对你开火。环境方面，linkedin室内装饰不多，比google, facebook更严肃，也稍土气，其实facebook也很沉闷的感觉，只有google几个办公室都让人耳目一新。值得一提的是linkedin 9个技术面试官，6个是华人，3个是南亚人，华人大多很帮忙，起码能感到他们的友好，在此感谢；南亚人攻击性比较强，不给提示，一味逼问，最后一轮的南亚hm在那不停打哈欠，估计来之前就把我枪毙了。

一般有经验的都是两轮算法，一轮设计，一轮tech communication (很莫名其妙的一项，和hm内容基本重复), hiring manager

1. 两个华人。Design tiny URL 问了很多细节，最后居然问到了怎么配置memcache, 估计是不揭穿lz的画皮不甘心，不过相信他们是为了找我的亮点吧
长到短，要查长的是否已经存在，存在直接返回已有值（这个就是我说的查重）；如果不存在则生成一个唯一的短id存到数据库
短到长，查短id是否存在，不存在就报错，存在则返回。
其实都需要index, 然后根据需要load进cache，但是这些普通数据库都已经实现了，不需要我们操心。
当然你可以把index都load到memcache/redis加快点访问速度，不过这里都是没有必要的。

2 两个华人
2.1 find range of a number in an array with possible duplicates, 我写的其实有bug, 但是小哥欣然放过，感谢。
https://leetcode.com/problems/search-for-a-range/
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
2.2 find all palidrome string by deleting any letter from the given string. 这题比较难，我只做了dfs的bf解, 稍微加了个map trim branch一下。最优解在mitbbs有讨论，大家自己坐电梯去看
http://www.mitbbs.com/article/JobHunting/33053715_3.html
给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集。

这应该求的是subsequence，可以用DP解。只不过DP的字符串长度。如果有n个字符。开一个n x n的矩阵，初始化对角元素为1。因为base case，最短的palindrome是单个字符。dp[i][j]表示从i到j是否为palindrome。递归公式为dp[i][j] = dp[i+1][j-1] + 1，如果s[i] == s[j]。dp[i][j] = max(dp[i][j-1], dp[i+1][j])。
我觉得不太对，再说本题不求数量，求的是实际的palidrome, 要求返回List<String>

3. tech communication. 一华一印，被强烈bs
4. 一中一印 leetcode原题 most points on same line. 但是leetcode的斜率用float直接表示，这里被要求用更好方式表示，搞了个横纵坐标的类，写gcd, 改hashcode, equals等吭哧半天。小中是一脸恨铁不成钢，不停提示我，恨不得上来帮我写，烙印是到处找茬，说你说lcd(lz没接受过正规cs教育, gcd说成lcd), 是不是还有led呢，blahblah。
5. 老印hiring manager, linkedin面试时会给你一个tablet, 里面有面试官的linkedin profile，我看了下，这个hiring manager还很有情怀的样子，自我介绍文艺范十足，不过见了面还是口音捎带咖喱味。问了一堆然无卵的行为问题，问了几下现在的项目，又问有没有mobile经验，问了一个类似dropbox的系统设计问题，lz用google三驾马车对付，对方不以为然。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=157908&extra=page%3D7%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

我根本没准备system的东西结果问了一堆问题看来是要跪。。我记得有虚拟内存，事务，进程和线程的区别，进程通信线程通信，答得很差
然后一道design的题。。。。实现一个容器能够randomremove和正常加和删。。。我傻傻用了三个hashmap小哥一步一步引导我走向正确答案不过前面答得太差了估计没戏了

我觉得单纯因为领英ml太缺人了。。。。system&infrastructure的bar会高一些吧毕竟大家都削尖脑袋想去

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156387&extra=page%3D9%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1. 给一个integer list，返回只出现过一次的整数。秒过
[1,1,5,6,2,4,3,1,2]
返回[5,6,4,3]
这道题我想到的办法就是用一个hash map.
key是数组中的数字，value是count.
先遍历一遍数组同时update hash map.
最后再遍历一遍hashmap，把count等于1的数字输出。
LZ当时有更好的方法吗？周一就面了，这几天正疯狂刷面经。
2. 给两个已经descending order sorted的数组，merge成一个descending order的数组。leetcode原题只不过次序变了一下，没啥好说的，秒了
3. 给一数组，让判断是否有三个数可以组成一个三角形。三个数代表三角形三边长，三角形的定义是仍和两边长相加要大于第三边。此题类似3sum和sliding window的组合，只要考虑清楚了也是容易得到线性解。我的思路是先排一遍序，然后每次固定一个数，扫一遍之后数组的相邻两个数字之差有没有比这个数小的。这样做的话时间复杂度就是O（N^2）的。求问楼主线性的解法是？

以3个数的window从头扫到尾，一旦有window[0] + window[1] > window[2] 就可以返回True了。我们只要detect是否有解，而不是需要返回所有解，所以线性就能解决了。
不过排序还是不可避免的，所以更正一下，Overall复杂度还应该是NlogN

二面：老美staff engineer
上来先聊简历和实习经历，为啥喜欢tools engineering，大概聊了有20分钟...开始做题
nested integer让算reversed weighted sum。也是一道L家的热门面经题了，写了个recursive的解，面试官看了N久然后问能不能iterative解决。脑抽想不出，接到提示可以用个queue, 恍然大悟BFS。由于此时时间已经不多，就让写了个pseudo code，面试官表示可以。提了个问题结束。
[1,[2, [3]]] 返回 1*3 + 2*2 + 3*1 = 10
这题得2 pass. 第一次pass是必须dfs找深度的，面试官的意思是第二个pass能不能用bfs.
Reversed Nested Integer - Linkedin

http://vosggll.blogspot.com/2014/12/l.html

2. 输出整数分解的全部解，解要从大到小的输出
Example:
input: n = 12
output:
12*1
6*2
4*3
3*2*2

10月20：

刚刚结束，印度人一个小时三道题，感觉bar又往上升了，大家好好准备吧

一个单词数组，求任意两个单词的距离实现List类，要有添加，删除，返回长度，o1复杂度
给一个嵌套list类似 {{1 1} 2 {1 1}}，每一个list里的元素相加乘以深度求和。这个
例子的话是，（1+1）*1 +２×２＋（１＋１）×１。最底层list深度是1，之前面经还
有问最顶层深度是1的情况

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

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

10月15：

两道题

打印一个数的所有乘数组合，从大到小，不要有重复

merge interval

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

10月13：

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

1. 层序打印 binary tree

2. 实现 BlockingQueue 的 take() 和 put()

10月14：

Q2: What is a singleton class and how would you design it. Some threading related things for it.

Q3: Write a parseInt function (Similar to Q1).

10月10：

投的职位Linkedin Test Engineer(Mobile&Web)

背景：cs master +一年test engineer工作经验；

电面一轮+onsite5轮；

电面：什么是singleton，两道算法，printTreeByLevel，字符串含数字求数字和。

Onsite，第一轮manager面（女阿三），基本都是 behavior questions，聊下文化和
做的项目；第二轮（国女）问的都是用selenium解决一些实际问题（automation），比
如在google search然后返回search结果的数目，怎么判断页面加载完毕等；第三轮吃
饭；第四轮（国男+印女），test strategy 给一个linkedin的feature，写一个完整的
test plan。最后一轮俩阿三，一男一女，问了一下做的项目，然后两道coding，这轮
答得不好，题目很简单，但是阿三表述一直不太清楚，感觉花了很久才明白到底问什么
；一个leetcode原题（fibonacci 数列的一个），还有一个实现stack的push和pop，但
要求每次返回middle number，主要是考察一些基本data structure。因为linkedin主
要是test在web和mobile，用的工具是selenium和appium，所以面试官也比较喜欢问这
方面。

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

10月7日：

Print a tree like reading a book, left to right.

phone 1:
1. Search for a Range (leetcode)2. Decide whether a target is covered by a list of intervals (类似merge
intervals)
第二题答的不好，感谢国人大哥大姐放水！

phone 2:
1. permutations (leetcode)2. permutations II (leetcode)3. 设计一个iterator class处理文件line by line

三哥看不懂2的solution，纠结了好几十分钟，最后3基本没时间写，悲剧了

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

intern 两个leetcode题目：
Maximum SubarrayMaximum Product Subarray

9月17：

1. valid number. LeetCode 原题，但是没写过，讨论了半天edge case，结果还是没考虑"-."的情况，最后经过提示算是勉强写出来了，但是code不是很clean。

2. Nested integer weighted sum. 一个list, 元素可能是list，也可能是Integer，

但是每个元素都包装在NestedInteger类里面了，求weighted sum. 例子是{2, {4, {6}}}. 应该返回2×1 + 4×2 + 6×3. 我可能该开始就省题不清，写成了 (((6*3) + 4)*2 + 1)*1. 经过面试官提醒，改了一个小地方就对了。感觉自己代码还算简洁，总共15行左右。

http://www.mitbbs.com/article_t1/JobHunting/32784787_0_2.html

实现stack的push和pop，返回middle number就是http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation

9月15：

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

9月6

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

9月5：

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

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

1. 2D matrix, sorted on each row, first element of next row is larger(or

equal) to the last element of previous row, now giving a target number,

returning the position that the target locates within the matrix

2. Given a binary tree where all the right nodes are leaf nodes, flip it

upside down * and turn it into a tree with left leaf nodes.

http://www.meetqun.com/thread-2083-1-1.html

8月29：

- How to find if nodes in graph are exactly 1/2/3 edges apart. how would you distribute graph across machines.

- Given set of characters and a string, find smallest substring which contains all characters.

- Implement a delayed scheduler for jobs using pthread apis (mutex/cond_var)

- You have bunch of numbers coming in, and a given a window size, how would you save numbers so that you can return number if present in window and provide average for current window.

- Manager round: You are given bunch of machines with services running on them, how would you improve things. very vague design talk.

- Reverse words in a string.

- Implement decimal to roman and vice versa.

8月26：

店面的，应该是挂了，完全不知道要做什么

就让实现一个file class的iterator

然后已经有一个method可以读取文件每一行。

需要返回一个iterator, 返回文件的下一行。

也可能题目我没理解明白，刚开始我打算写读取文件，他又说文件很大，不能一次读入

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

8月20：

1。查找2个单词的距离

/*

* Example:

* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",

"quick", "brown", "fox", "quick"));

* assert(finder.distance("fox","the") == 3);

* assert(finder.distance("quick", "fox") == 1);

*/

2. 洗牌要求in-place

* Return the smallest character that is strictly larger than the search

character,

* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'

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

http://www.careercup.com/question?id=5726366532108288

8月11：

两个面试官，master是中国人（WW），另一个是烙印。两题在网上都有一个是Nested Sum，第二个在sorted 的integer中找到给定的数的range。

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

7月17：

已挂，发了攒人品。

有一个array ["this", "is", "a", "is", "fox", "happy"]

需要返回两个单词的最近距离（用index计算）。

int dist(string word1, string word2)

比如dist("fox", "happy") = 1

dist("is", "fox") = 1 注意“is”是有重复的。

每个单词都是有可能重复的。

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

7月11

L:
pow(double a, double b)Nested Integer 求和
给两词，找在文档中这两词最短距离。

7月10：

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

1. 给定一个undirected graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。

注意，这个undirected graph使用adjacent array来表示一个节点的所有neighbors，并且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)

直接的BSF解法时间复杂度是O(n^3)。

要求设计Solution是时间 O(n^2)。

2. 设计一个hash table，实现set（int key，int val）和get（int key）

3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]...A[i - 1]A[i + 1]...A[n - 1] (i.e., A[i] is missing from B[i])

如果不可以用除法，如何解？要求solution是时间O(n)

4. 给出n个点，求最多点的数目(这些点在一条直线), leetcode原题

6月23：

L家 - 挂了：

电面1：白人，HM.
Chat 5 min.
Basic Question: 10 min: TCP vs UDP, Virtual Memory, Page fault, etc...
Question 1: Mirror a Tree

http://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/
Solution: recursive
Question 2: Implement a data structure class support: insert, delete and
random get
Solution: two hash map and move last to fill the hole when deleting

http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1

电面2：国人
Question: Java Blocking Queue,
Solution: 参见本版讨论

6月22：

1. Return if two strings are isomorphic. (character 1-1 match)

“zoo” -> “fee” ( z->f, o->e) true

“zoo” -> “dui” ( z->d, o->u, o-> ) false

“dui” -> “zoo” (d->z, u->o, i-> ) false

Use two hashmaps

*****************************************************************

2. K nearest points (solution see below) Time: O(nlgk)

*****************************************************************

1. Search in rotated sorted array

*****************************************************************

2. public interface Intervals {

/**

* Adds an interval [from, to] into internal structure.

*/

void addInterval(int from, int to);

/**

* Returns a total length covered by intervals.

* If several intervals intersect, intersection should be counted only

once.

* Example:

*

* addInterval(3, 6)

* addInterval(8, 9)

* addInterval(1, 5)

*

* getTotalCoveredLength() -> 6

* i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]

* [1,6] and [8,9] don't intersect so total covered length is a sum for

both intervals, that is 6.

*

* 0 1 2 3 4 5 6 7 8 9 10

*/

int getTotalCoveredLength();

}

6月20：

一面：国人大哥和美国妹妹，妹妹是shadow。

第一题： search in rotated sorted array，（with or without duplicates）

第二题： Given an array of integers, find out a triple of integers such that

they form a triangle. i.e. given a,b,c from the array, a +b >c, b +c >a, a

+c >b, 返回任何三个就可以了。

第一题：print binary tree level by level，外加c++ vector内部怎么实现以及复

杂度等细节

第二题： print factors of a given integer

example： 12 可以表示为：

12 ＊1

6 ＊2 ＊1

4 ＊3 ＊1

3 ＊2 ＊2 ＊1

要求走几个例子，写出完整的递归的stack trace

题目差不多都做出来了

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

5月27：

L phone interview:

1. Implement Linked list.

2. nested integer list, 求weighted sum. weight 就是嵌套的层数。

3. Find a number in rotated sorted array, leet code 原题

L onsite:

1. Senior manager 谈PhD 项目，出了个关于ads monetize 的粗浅问题。聊的很愉快.

2. Senior software engineer 谈之前工作中得项目和系统。考察communiation, 水过。

3. Design question, tiny url service.

4. Coding: text justification. 考查Implementation, leetcode 原题。不难，就是

繁琐。

5. Coding: same tree, calculate product of an array without the number

itself, sort

5月9日：

Pow(x,n)

: Insert Intervals

: Leetcode 原题

: PS2

: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。

: 1. string matching的题，具体忘了，很简单；

: 2. 带 parent member 的bst，找最深的 common ancestor. 就栽在这道题上，感觉被黑了

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

3月28：

电面1：印度 + 老毛

1. rotated binary search

2. 给你一个BST的pre-order traverse的结果，让你返回in-order traverse的结果。

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

sort pre-order to get in order of BST

电面2：国人大哥 +　老毛（结果老毛没来）

1. double power(a,b)

2. binary tree level traversal，然后追加了要打印出来他所需要的格式。

比如，给你：

3

/

2 5

/ / \

1 4 6

打印出来的格式要是：

3

2 5

1 4 6

on-site:

1. 跟经理聊天，介绍自己的背景，behavior interview。经理看起来是个ABC，刚开始

有点严肃，我也有点拘谨。到后来比较nice.

2. 详细介绍自己所做的项目，面试官还比较nice，人也很聪明，提的问题有时候一针见血。 stanford小印，全程比较严肃。

3. Lunch interview,就是一起吃饭

4. 题目是tiny URL那题，问的很细。

5. Coding : Implement a blocking bounded queue

6. Coding:

题目有点忘记了，大概好像就是：比如要安装gcc 2.1 这个程序，会有一些

dependency，让你写个程序，让你返回安装一个程序所需的所有dependency。

3月18：

1: sqrt(double) with double 精度,

2: Whether one list is merged into given lists.

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

3月5:

Parse the IP in a file, actually, it is not difficult View Answers (2)

3月：

一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是

一个链表。要求把它拍扁，顺序随意。

http://www.geeksforgeeks.org/flatten-a-linked-list-with-next-and-child-pointers/

2月25：

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

r1 1白男+1小印，题目是实现hashmap，写完后继续要求要考虑multi-thread。总体算

还行，但是第一轮有点紧张，出了几个小错误。

r2 印度人，三题， 1 实现sqrt，就是考察binary search。 2 给一个数组，返回一

个数组其中每个数是除了之前数组这个index的数以外所有数的乘积，主要就考虑有0的

情况。 3 linkedin 有两类用户，普通user和influencer，数据量都很大，写一个类，

要求O(1)的 get(user), set(user, type), getAllInfluencer. 我一开始用两个

hashset，问我有没更好的办法，后来问明白他其实就是想要bitset，写出搞定。

r3 两senior，其中一国人一印度女。就是问做过的project，但是之前做过的project

确实没有很大的user base，我做的也是偏前端的模块，聊不出太多scalable的东西。

所以我说的challenge的问题他们有些也不了解或者不感兴趣，感觉十八九悲剧在这轮。

r4 国人senior，设计一个web calendar，从interface到后台数据结构，因为没有标准

答案，面完也不知道算好算坏，有些地方他认为重要的我一开始没想到，有些地方我提

出了好的想法他也会做record。

r5 白人manager，基本在聊天，从大学毕业到现在的历程过了一遍，一个设计题是

linkedin要launch和大学合作认证课程的feature，让我想想要怎么去做，但问着问着

感觉变成了怎么向用户推广这个新feature... 然后他之前在amazon做了6年而我已经拿

了amazon的offer最后十多分钟就变成了他向我吐槽amazon...

2月24：

一面

1‘ Level order tree traversal. (Leetcode)

2' Find the distance between two words in a list. The words can repeat.

二面

1‘ pow(x, n), where x is a double, n is an integer (Leetcode)

2' Number factorization

2月11：

JAVA part:

1 interface 和 abstract class 区别

http://blog.csdn.net/b271737818/article/details/3950245

2 multithread, thread safe

3 equals 和 == 区别 : == 比较地址， equals: object, == basic

1 get 和 post 区别

2 http 和 https 区别

Algorithm:

1 NestedInteger 如 {2, 4, {6, {8}}} calculate weighted sum. weight is the

depth.

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

2 Two sum

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

电面1：

第一题：给一个words list, 输入两个单词，找出这两个单词在list中的最近距离(先

写了一个没有预处理的，又写了一个预处理建index的)

['green', 'blue', 'orange', 'purple', 'green'] f.distance(list, 'blue', '

green') # output 1

第二题：类似binary search的一题，要注意boundary case

电面2：

binary tree level order traversal, 写了三种方法。。。(BFS用arraylist，类似

DFS，BFS用queue)

2月24：

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

1. given the list {{1,1},2,{1,1}}，返回10……因为，(four 1's at depth 2, one

2 at depth 1). 给定 {1,{4,{6}}} ，返回27……因为， (one 1 at depth 1, one 4

at depth 2, and one 6 at depth 3)

2. leetcode: traversal binary tree level by level

3. 给2个string，判断是否可以map. say (foo, abb) 这2个string是可以map的, f->a

, o->b. say (foo, sdf)，是不可以map的……返回bool值

4. 给一个string，每10个letter一组，输出所有出现次数超过一次的strings with

length of 10. 一定要用rolling hashing做

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

5. 给一个数组，输出连续元素的最大和。

6. 判断2个linkedlist是否在某一点会重合. O(1) space.

7. leetcode: Max Points on a Line

8. string reverse. 输入 "Hello, word"，输出 "word Hello,".

9. 给一个数组，输出连续元素的最大乘积。

10. leetcode: permutations

11. 给一个数组，a(10, 2, 5)……输出一个数组, b(10, 50, 20)……b[i]是除了a[i

]以外剩下a中所有元素的乘积……不准用除法.

assume size of a is n

用2个数组

prev[i] = a[0]*a[1]*...*a[i]

back[i] = a[i]*a[i+1]*...*a[n-1]

结果

res[i] = prev[i-1] * back[i+1]

注意处理下边界情况

L家是有题库的，把版上的面经都看一遍就差不多了……design是设计amazon product page的后端

2月24：

Write a method implementing a given interface to merge two streams of numbers. Answer Question

2月18：

a) Find the nearest K point given a set of N point.

b) Print a tree level-by level.

c) Given a dictionary find and set of two words find path from one word to another such that all the intermediate words are also from dictionary.

Example: GOD -> GID -> DID -> DIG -> DOG.

At each time we are allowed only one character change.

d) Design an Hangman. { They expect MVC architecture. }

2月16:

2) Return true if there are any users who are not following any other user but been followed by every other user. View Answer

2月15：

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

1. 阿三经理

80年代IIT毕业，口音没问题

a. 问项目经验

b. 分布式相关问题，没深入细节，包括2pc, paxos, zookeeper的实现等

2. 波兰小伙

有点害羞，但人非常好。

a. message{msgId,byte[]}。大量message持续的input，要支持Message[] getAll(

msgId)，问怎么存储message。

3. 阿根廷帅哥

专做搜索的，长的好像诺维斯基。。。

问题：如何设计分布式倒排索引，如何进行query。

4. 阿三

小印，口音重，发了篇SIGMOD，不过第一作者是国人:)

a. 假设有函数int[] getConnection(memberID)，结果是有序的，要求实现：

isFirstDegree(member1,member2)

isSecondDegree(member1,member2)

isThirdDegree(member1,member2)

就是判断一度，二度，三度好友关系，是系统设计题，伪代码即可。

follow up：分布式下怎么做

b. tinyurl

follow up:问如何scala-out

5. 埃塞俄比亚小伙

悲剧的一轮，小伙人很好，但英语比阿三还难懂，有史以表现最差的一次。

a. 给一个矩阵，followMatrix[i][j]==true，表示j影响了i。求influencer，即影响

所有人，且不被任何人影响

b. 三角形问题，输入一些线段的长度，找出能形成三角形的三条线段

6. 老美

表现最好的一轮，有相似的项目经验，聊的比较投机

a. max points on a line

b. 给int[] a,求int[] result。其中result[i]=a1*a2…*ai-1*ai+1*…an，follow

up:不能用除法

6轮下来，5表现非常不好，2也不太理想（都没有进入follow up分布式的情况），所以基本是跪了。

2月11：

两星期前onsite, 面了一个 Web-based hangman design 跪在这上了其他都是老题比

如 integer to roman, roman to inthttp://www.mitbbs.com/article_t/JobHunting/32613585.html eger, 他们家貌似喜欢考这种messy的编程题

onsite:

1. romanToInt, intToRoman,

N points, m nearst ones

2. 双向链表，每个node可能都有父节点和子节点，每个父子节点又是一个链表。把它

拍扁，顺序随意，O(1)空间复杂度

edit distance

3. system deisign: design amazon product page

4. project presentation

5. group fit

2月8：

PS1:

senior staff engineer，老美，70年代大学毕业。

1. 聊简历和技术背景

2. 子数组最大和，我说见过，说了O(n)的方案，没coding

3. Search in rotated sorted array。开始没考虑重复元素，后来修正了。但面试官

似乎不知道重复元素的影响，举了几个例子验证后，说OK

最后，我问了一些linkedin infra的问题，解答很详细，并推荐了rest.li，后来和同

事研究了下，在服务发现这块设计的很赞

PS2:

国人主面，老外shadow

1. 聊项目经验，问的很仔细，英文水平有限，又没法画图，解释的不太好

2. Java和OS相关概念

3. coding，序列化和反序列二叉树。用了leetcode的表示法。春节期间没练习，手生

，结果有逻辑bug，当时感觉完全没信心了，提问阶段只问了一个就不想说了。

2月2日：

Final round was kind of unexcited, was asked to write out all the combination of factors of one number. another was about implementing hash table. Answer Question

1月：

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

L:

问答题

Write-through cache vs write-back cache

what's memory mapped file

算法题，都是老题

1) 给一个nested的int array，返回sum of int weight by its depth

2) 写一个支持removeRandom的hashtable

3) 一串字符串，返回有多少个substring符合某些pattern，这些pattern都是10char的

长度，所以逐个比较就可以了

4) tree lowest ancestor( tree node have parent pointer)

2013年12月：

Given a sorted array with duplicates and a number, find the range in the

form of (startIndex, endIndex) of that number. For example,

find_range({0 2 3 3 3 10 10}, 3) should return (2,4).

find_range({0 2 3 3 3 10 10}, 6) should return (-1,-1).

The array and the number of duplicates can be large.

2013年12月：

已从L onsite面的有设计挺经典的O(1) insert/remove/random pick数据结构，

distributed topk exception，扯amazon.com如何设计，版上似乎都有原题

代码不一定是bug free 我觉得挺看思路也就是overall approach的

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

2013年12月：

第1题：Leetcode原题：由一个binary tree的inorder及preorder traversal结果，重

构原binary tree。

第2题：Leetcode原题：一个已排序的数组中查找某给定element重复的个数。

Round 2：tech电面2。国人大哥。

第1题：level sum，算是deep iterator的变种。一个多重nested array，例如{a,{b,c},{{d},e}}，返回level sum = a + 2 * (b + c) + 3 * d + 2 * e。

第2题：First Common Ancestor with parent pointer。What if the parent pointer is not available?

2013年11月：

刚面完，不得不赞下面试的国人大哥，一上来中文寒暄，亲切感一下就上来了哈哈，还有一个面官不知道是不是国人。表示后面我都不敢说中文。。不说其他的，上题。

2013年8月：

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. View Answers (7)

题目：

1.Resume

2.LCA(with parent pointer)

3.Lower and upper bound of target number index in a sorted array

2013年4月20：

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

LinkedIn:2轮电面，5轮onsite见9个人。2天后offer。每一个遇到的人都很nice，

onsite的时候会给准备零食放在会议室，会打印出InMap，手写卡片等，非常sweet收拢

人心。

电面1-2 请搜索版内面经，基本重复。

onsite 1: behavior questions with their director, 最后讲了讲如果设计一个系

统（和我master研究相关）可能会存在的问题。

onsite 2：介绍我现在的工作，考察technical communication skills

onsite 3: justify text, leetcode上原题

onsite 4：minimize the cost of painting K houses, each house has different

costs to paint in different colors,

2 houses (next to each other) cannot be painted in the same

color. DP 问题

很简单，忽略。

onsite 5：设计题，涉及到分布式系统，缓存算法，缓存更新，读取速度优化，面试

2013年6月：

code a text justification routine (Given a line length insert white space so text is uniformly displayed within the given length).

2013年2月20日：

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

电面：

1. 给一个二叉树，返回它的镜像

实现一个 thread-safe blocking queue

嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。就是类似树遍历一样的方法

Onsite:

第一个: 给两个单词，比如head, tail: 找到一个最短的转换，从head到tail，每

次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest

path

第二个: memcpy: 源区域和目标区域可能有重叠

BST 插入和删除操作实现

BST iterator 实现

3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时

，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个

call O的线程返回（产生一个水分子），其他的都block。

4: Given a social graph, find if there is a path between two persons with at

most 2 steps (3rd level connection), how to handle it in distributed way (

large graph stored at a large number of nodes, minimize cross-communication)

5: 设计题: a restful server with 4GB,

given a request such as: http://seq=4?len=60?xxxxdata

the system will store the binary data with that sequence number.

given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

multiple clients calling simutaneous

what data structure, concurrency, locking, etc..

2012年：

Phone Interview

都是老题。先问LinkedIn最喜欢的：double pow(double a, int b)

我的Algorithm Project里有这个题，当时很想直接贴答案。后来忍住了。这是个中等难度的题，里面很多细节，如果贴的话，他一问，我没有过脑子，有可能被问住，那个印象就太差了。如果自己解的，哪怕有错，思考过之后，我很快会有相应的回答。不管多简单的题，我都会错，但我会补得很快。

想清楚，开始写。尽管很小心，最后还是在边界条件错了，就是第一句：

if (b < 0) return pow(a, -b);

我少写了1.0/pow(a, -b);

但我不后悔，如果他因为这个把我毙了，那我也只能认倒霉。

接着给Amazon的favorite, 2-sum to fixed number, 我不喜欢写这个题。就直接告诉他：两种答案，hashtable, 2个指针，我都写过，你要哪种？他挺理解，说，既然你写过，给我讲一下性能差别，然后就放过了。

接着第三题，算逆波兰表达式。又是一个细节题，我知道会写错。小心翼翼地写，一边写一边解释，最后还是有小错。

Linkedin Interview Misc 2

Labels

Popular Posts