我LD最近面了一堆公司，下面发她的面经攒人品。基本都是电面和onsite混着发的。
Google:
1. Wildcard match
2. http://www.fgdsb.com/2015/01/25/peek-iterator/类似。写一个de duplicator,wrap 几个stream，输出的stream全是不重复数字。
3. 求一个stream，出现次数最多的数字。然后扩展到N个machine的情况。
4. 假设某个company在不同国家都有office，每个国家的office，如果是当地的假期，
就可以放假了。假设可以查询任意航班的信息，每个星期只能呆在一个地方，只有周末
的时候才能飞去别的国家。找一个放假天数最多的schedule。
5. LRU + 一些 C++问题。
6. 这题记不大清楚了。好像是Longest increasing consecutive sequence， 然后一
个Tree的该进版。求longest increasing consecutive path。
7. file system design。就是设计一个大数据的存取问题。存在disk上。我就是
partition + hash + cache那一套糊弄过去了。
Facebook：
因为签offer了，就不说太详细了。基本都是常见题甚至LC原题。但是follow up问的很
多，基本上常见题能用多种方法做的都会全问你一遍。比如问了一题count and say，
老掉牙的题了，写出代码还让证明any count不会超过三。比如1 11 21所有的digit都
不大于3。
Machine Zone：
1. sort color。
2. 有两个设计api的题目，具体的忘记了，都不难就对了。
3. 有两轮纯写query。问了些perfomance的问题，主要就是index的原理。写个几个很
长的query，一个一黑板那种变态的。
4. 一个leetcode medium的dp问题。
5. linkedin word distance 那题
/* This class will be given a list of words (such as might be tokenized
* from a paragraph of text), and will provide a method that takes two
* words and returns the shortest distance (in words) between those two
* words in the provided text.
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
"quick", "brown", "fox", "quick"));
* assert(finder.distance("fox","the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*/
Pure Storage：
一模一样的题目！！
http://www.mitbbs.com/article_t/JobHunting/32702941.html
多了一道，设计c++ virtual mechanism的design。虽然看过一点，知道的不多。但是
会逐渐给提示，follow hint就可以。pure storage喜欢一个题用好几种方法解，每个
题目都让不断的优化优化。
Uber：
1. regex match
2. 实现trie
3. youtube architecture设计。
4. 聊天。
5. min stack
Palantir：
1. 判断长度为K的substr有木有重复的字符。
2. LRU
3. 有个grid，每个cell记录的是click的次数，0或者大于0。求点击次数最多的region
。每个region的定义，是非零连续的一片。
4. 设计asteroid 游戏。
5. 实现一个纸牌游戏的logic。每人拿出最上面那张，比较大小，最大的胜出，winner
可以搜刮走loser打出的牌。如果有俩人的牌一样大，就比较上面数第四章的牌。 直
到某个人赢得了所有的牌
6. system design。distributed hash table
7. stock price。
5/6 5/7 5/8
Stock1 : 100 200
Stock2: 50 100
Stock3: 150 200
Output: 250 350 500
空格代表价格没变化，跟前一天一样。如果第一天的为空，价格为0
ServiceNow：
1.各种概念啊！！ Javascript， Angular.js, SQL
2. 发过来code，让改bug优化。
3.又是各种概念啊。Javascript， Angular.js, SQL。还有自己project的介绍
BigCommerce：
1. 聊天3轮。聊project。我的project，他们的project
2. leetcode上absolute path那题。
3. 有一轮，算是system design吧。让设计他们的payment系统。
Amazon：
1. 竟然安排我面试QA。理所当然的挂了。问了一道很简单的hashtable的题目，然后问
我怎么测试amazon web page。。
2. 概念：hashtable 实现方式。
代码： 拓扑排序。
还写了个电话号码的regex expression。
电面就挂了，没onsite。
Linkedin：
1. Word distance
2. 2 sum
3.
/**
* Given a nested list of integers, returns the sum of all integers in the
list weighted by their depth
* For example, given the list {{1,1},2,{1,1}} the function should return 10
(four 1's at depth 2, one 2 at depth 1)
* Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1
, one 4 at depth 2, and one 6 at depth 3)
*/
4. permutation
5. reverse word in string (in place)
6. system design 类似这个
http://www.shuatiblog.com/blog/2015/01/09/big-data-real-time-to
7. 问project。把我问跪了。他们问的非常非常详细。我只准备了architecture，明显
不够用。一些具体logic也得准备。
8. minimum window substring
9. sqrt int + double版
Yelp：
1. Word ladder 2
2. 密码的combination。 phone number combination变体
3. 拓扑排序：一堆package，有dependency。求个安装顺序
4. permutation + combination合体，具体的太久忘记了，反正不难。
5. valid json。判断string是不是valid json object
跟版上很多人一样，题都不难，自我感觉良好。最后悲剧。
----------------
准备的话，虽然还是以leetcode为主，我协助她找工作也帮她做了一些事情，大家如果
觉得有用也可以看看：
1. 博客：http://www.fgdsb.com
这里面收集了不少leetcode没有的但是近期比较高频的面经题，我也提供了一些参考解
法。
当然有个别题的个别解法已经有热心观众指出错误了，但是由于我最近课比较多还没有
改，有空了一定改正，本人也不是搞竞赛出身，大牛求绕道。
2. 本地刷题平台：https://github.com/wangyanxing/Judge-at-fgdsb
现在支持mac和windows（windows启动速度比较慢）系统。类似于leetcode的本地版，
收集我博客里面大约40道比较常见的且LC没有的题并提供了测试案例和Judge功能。现
在支持C++/Java/Python/Lua/Ruby语言，当然你本地要有能运行的compiler。
现在还不是特别完善，但是已经完全可以用了，我还加了print功能，这个调试起来比
lc方便。有空我会把二叉树的visualization做了，相信大家对LC的 12##3#4 这种二叉
树表示方法不爽很久了哈哈。
release链接在这里：https://github.com/wangyanxing/Judge-at-fgdsb/releases
Tuesday, April 14, 2015
Monday, April 13, 2015
from mittbs http://www.mitbbs.com/article_t/JobHunting/32932495.html
Google，recruiter骚扰
店面：bag element按概率抽取(http://math.stackexchange.com/questions/389140/odds-of-choosing-items-out-of-a-bag)
onsite：
1.给定二维binary数组，要求分割然后压缩
2.sliding window求最大值
3.数组先升序后降序求顶点
4.game theory
5.给一个tree，每个node有往父节点的指针，求一个common祖先
这个比较早了，当时没准备好是抱着去玩的心态的，两星期后悲剧了。
Facebook，内推
店面：也是bag element提取。
onsite:
1.字符串排序变种
2.design面typeahead search
3.culture fit
4.suffix array的变种
design答得太差没办法，两星期后悲剧
Twitter，内推
店面1：callback function实现，要求thread safe
店面2：给一个binary stream，分析并写出parsing函数
onsite：
1.LRU Cache的变种
2.后缀计算式 + 数组除掉下标对应的元素以外的所有乘积。
3.一个二维矩阵从左上到右下的所有可能路径数。有obstacle。
4.bag element提取 + Lights Out + 设计题coordinate分布式sensor数据
5.设计题多个datacenter怎么生成unique的内容id要求时间相近id相近
第四轮的人不知道是不是要故意整我，出两道coding加一道design，虽然跌跌撞撞都答
出来了。两个星期后悲剧
Apple
内推
Apple不是general hire，简历match到了video组
店面：过简历
onsite：
9~11个人左右，过简历的比较多，问非常相关的专业问题；coding问c++，还有数学题。
人数实在太多，模糊记得一点面试内容，但detail都不太记得了。
两周后口头offer。再一周谈钱，再一周正式。
一定要吐槽A的recruiter各种出尔反尔，一开始说base没法聊，然后说觉得signon还可
以聊；那我就说那就signon加一点呗；然后立马又说不行signon没法聊，不过
relocation跟据你的实际情况我们多添一点你需要的，减掉你不需要的；然后又说不好
意思relocation是standard的也不能改。。。。。。
Linkedin
内推
店面两轮，onsite六轮
standard的coding questions；design也是standard的类型，考点是scalability
一周内搞定hc，teammatch，谈钱，正式offer。
店面：bag element按概率抽取(http://math.stackexchange.com/questions/389140/odds-of-choosing-items-out-of-a-bag)
onsite：
1.给定二维binary数组，要求分割然后压缩
2.sliding window求最大值
3.数组先升序后降序求顶点
4.game theory
5.给一个tree，每个node有往父节点的指针，求一个common祖先
这个比较早了，当时没准备好是抱着去玩的心态的，两星期后悲剧了。
Facebook，内推
店面：也是bag element提取。
onsite:
1.字符串排序变种
2.design面typeahead search
3.culture fit
4.suffix array的变种
design答得太差没办法，两星期后悲剧
Twitter，内推
店面1：callback function实现，要求thread safe
店面2：给一个binary stream，分析并写出parsing函数
onsite：
1.LRU Cache的变种
2.后缀计算式 + 数组除掉下标对应的元素以外的所有乘积。
3.一个二维矩阵从左上到右下的所有可能路径数。有obstacle。
4.bag element提取 + Lights Out + 设计题coordinate分布式sensor数据
5.设计题多个datacenter怎么生成unique的内容id要求时间相近id相近
第四轮的人不知道是不是要故意整我，出两道coding加一道design，虽然跌跌撞撞都答
出来了。两个星期后悲剧
Apple
内推
Apple不是general hire，简历match到了video组
店面：过简历
onsite：
9~11个人左右，过简历的比较多，问非常相关的专业问题；coding问c++，还有数学题。
人数实在太多，模糊记得一点面试内容，但detail都不太记得了。
两周后口头offer。再一周谈钱，再一周正式。
一定要吐槽A的recruiter各种出尔反尔，一开始说base没法聊，然后说觉得signon还可
以聊；那我就说那就signon加一点呗；然后立马又说不行signon没法聊，不过
relocation跟据你的实际情况我们多添一点你需要的，减掉你不需要的；然后又说不好
意思relocation是standard的也不能改。。。。。。
内推
店面两轮，onsite六轮
standard的coding questions；design也是standard的类型，考点是scalability
一周内搞定hc，teammatch，谈钱，正式offer。
Sunday, April 12, 2015
来自mittbs 面经 http://www.mitbbs.com/article_t/JobHunting/32923781.html
留下重点＝＝＝＝＝》
http://www.mitbbs.com/article/JobHunting/32899043_0.html
https://www.evernote.com/shard/s576/sh/%207e58b450-1abe-43a8-bf82-
fbf07f1db13c/049802174415b418a2e65f75b744ab72
http://www.mitbbs.com/article/JobHunting/32777529_0.html
面经
各位久等了。
1.
/**
Implement stairs(N) that prints all the ways to climb up a N-step-stairs
where
one can either take a single step or double step.
We'
ll use 1 to represent a single step, and 2 to represent a double step.
stairs(3)
111
12
21
There might be two requirements:
1. print
2. collect solutions in a list
**/
3. First non repeated character in string. Follow up is one pass solution.
http://www.geeksforgeeks.org/given-a-string-find-its-first-non-
5. Letter combination of phone book
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
6.
public interface PointsOnAPlane {
/**
* Stores a given point in an internal data structure
*/
void addPoint(Point point);
/**
* For given 'center' (which isn't necessarily the origin)
* point returns a subset of stored points that are closer
* to the center than others.
*
* E.g.
* Stored:
* (0, 1)
* (0, 2)
* (0, 3)
* (0, 4)
* (0, 5)
*
* findNearest(new Point(7, 3), 3) -> (0, 2), (0, 3), (0, 4)
*/
Collection<Point> findNearest(Point center, int n);
class Point {
final int x;
final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
7. 3Sum
https://leetcode.com/problems/3sum/
8..
/**
* Given two 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 "foo", "boa"; returns false
* we can map 'f' -> 'b', 'o' -> 'o', we can't map 'o' -> 'a'
*
* 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'
*/
9. Lowest common ancestor of binary tree
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree
10. Given array containing 3 repeated and unsorted letters m, l, h, do in
place sort so that l's are on the left, m's in the middle and h's on the
right.
11. Max points on a line
https://leetcode.com/problems/max-points-on-a-line/
12. A simple DP problem that I haven't seen. Really straight forward like a
sequence alignment.
13. Given positive integer n, return the list of squares that sum up to n.
Note that length of the returned list should be the shorted of all such
lists.
E.g. 5 => 4, 1
6 => 4, 1, 1
8 => 4, 4
11 => 1, 1, 9
12 -> 4, 4, 4
14. Binary tree in order traversal into a doubly circular linked list (
return is a list that represents in order traversal)
15. Given binary tree tell if it is binary search tree. O(lgn) space
complexity preferred (average case)
16. Design rate limiter
17. Design Tiny URL API
18. Design news Feed API
Other design problems I couldn't recall clearly but topics involved:
inverted index, consistent hashing, consistency level and partitioning (CAP)
, and map-reduce.
http://www.mitbbs.com/article/JobHunting/32899043_0.html
https://www.evernote.com/shard/s576/sh/%207e58b450-1abe-43a8-bf82-
fbf07f1db13c/049802174415b418a2e65f75b744ab72
http://www.mitbbs.com/article/JobHunting/32777529_0.html
面经
各位久等了。
1.
/**
Implement stairs(N) that prints all the ways to climb up a N-step-stairs
where
one can either take a single step or double step.
We'
ll use 1 to represent a single step, and 2 to represent a double step.
stairs(3)
111
12
21
There might be two requirements:
1. print
2. collect solutions in a list
**/
3. First non repeated character in string. Follow up is one pass solution.
http://www.geeksforgeeks.org/given-a-string-find-its-first-non-
5. Letter combination of phone book
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
6.
public interface PointsOnAPlane {
/**
* Stores a given point in an internal data structure
*/
void addPoint(Point point);
/**
* For given 'center' (which isn't necessarily the origin)
* point returns a subset of stored points that are closer
* to the center than others.
*
* E.g.
* Stored:
* (0, 1)
* (0, 2)
* (0, 3)
* (0, 4)
* (0, 5)
*
* findNearest(new Point(7, 3), 3) -> (0, 2), (0, 3), (0, 4)
*/
Collection<Point> findNearest(Point center, int n);
class Point {
final int x;
final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
7. 3Sum
https://leetcode.com/problems/3sum/
8..
/**
* Given two 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 "foo", "boa"; returns false
* we can map 'f' -> 'b', 'o' -> 'o', we can't map 'o' -> 'a'
*
* 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'
*/
9. Lowest common ancestor of binary tree
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree
10. Given array containing 3 repeated and unsorted letters m, l, h, do in
place sort so that l's are on the left, m's in the middle and h's on the
right.
11. Max points on a line
https://leetcode.com/problems/max-points-on-a-line/
12. A simple DP problem that I haven't seen. Really straight forward like a
sequence alignment.
13. Given positive integer n, return the list of squares that sum up to n.
Note that length of the returned list should be the shorted of all such
lists.
E.g. 5 => 4, 1
6 => 4, 1, 1
8 => 4, 4
11 => 1, 1, 9
12 -> 4, 4, 4
14. Binary tree in order traversal into a doubly circular linked list (
return is a list that represents in order traversal)
15. Given binary tree tell if it is binary search tree. O(lgn) space
complexity preferred (average case)
16. Design rate limiter
17. Design Tiny URL API
18. Design news Feed API
Other design problems I couldn't recall clearly but topics involved:
inverted index, consistent hashing, consistency level and partitioning (CAP)
, and map-reduce.
Subscribe to:
Posts (Atom)