b********6
发帖数: 97 | 1 背景：本科生物，统计master + 9个月工作经验
结果: offer: amazon, facebook, linkedin, google
Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
电面：
Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
有问题怎么trouble shooting的开放问题。
Linkedin 两个：
1 binary tree level order traversal, leetcode原题
2 pow(x,2) leetcode原题
3 判断一个string表示的数字是否valid，类似leetcode Valid Number原题，一些具体
要求要和面试官讨论后确定
4 permutation I and II leetcode原题
Facebook一个：
1 reverse linkedlist (这个我无话可说)
2 decide whether two strings are “similar”, definition of “similar” :
only allow at most one modification, definition of “modification”: insert,
delete, or replace
Google 两个：
1 reverse all the vows in a string
2. a list of log records, each one contains info of a function call [
function_name, start_time, end_time], for each function, print the average
call duration time.
3. a list of pairs (childNode_ID, parentNode_id), construct a tree given a
list which represents the structure, return root node.
4. follow up of the last one, construct a directed graph represented by the
list of pairs, return any node of the graph.
5. follow up, given one node in the graph(or root of the tree), return a
list of pairs representing the graph /tree structure.
Twitter两个：
1 spirally print out matrix, leetcode 原题
2 given a string and a list of words, return all the words in the list
starting with the input string (or having the input as the prefix )
3 bfs and dfs traversal a trie
4 implement a stack, O(1) push(), pop() and min()
Ebay两个：
1 a lot of different ppl share the same git respository, thousands of files
in it. A lot of commits everyday. Find a way to figure out how many files
are edited (just a number for the delta) per hour, or every 10 hours, or per
day.
2 review a piece of codes, discuss all the possible issue in it.
3 given a string and a dictionary, return unique substrings which are
contained in the dictionary.
Walmartlab 一个：
1 given an array of integers, positive, 0 or negative, find the maximum
value by multiplying three of the numbers.
2 return all the k v pairs in a long list of unparsed url. (using regular
expression)
Onsite:(不说公司名字，我就混在一起说了，也有群面的时候听来的。 题目也有改动
，如果大家觉得条件给得不对，可以提出来讨论)
1. 两个strings, 长string s 和短string t, 找出s中包括了t中所有字母的最短
substring, O(n)解法，leetcode原题
2. 一个online shopping的system,卖一种专门的商品，商品有一个专门的编号规则
，顾客在网上order了商品，信用卡上被扣了钱，但是商品却没有deliver到，作为一个
support engineer 怎么trouble shooting 这个issue.
3. 上面一个问题的followup, 这种商品相同的编号下有不同的version No. 但是
version No. 有可能是错的，编号数据存在怎样怎样的relational schema里，写sql抓
出错误信息.（抱歉实在不能给出更准确的信息了）
4. 四个小孩过独木桥，一个手电筒，通过时间分别是 1， 2， 5, 10min,每次通过
时不管几个人都必须有手电筒，问17min所有人过桥的solution
5. Given a string,尽可能满的填到一个nxn的grid里去，按一行行填进去，按一列
列打印出来
6. Linkedlist, node 中除了有next指针，还有below指针，below可能指向另一个
这种Linkedlist的头，given一个这样一坨（或者是n维）的linkedlist的头，把它压平
成一个一维的list,顺序无所谓，时间O(n),空间O(1) programming interview exposed
原题
7. 一段错误满满的java code，挑错
8. Find the lowest common ancestor in a binary tree,有parent 指针和没有
parent指针的两种情况。Followup是在有parent指针的情况下，只travel一遍tree怎么
做。
9. 和manager意见相左怎么办？
10. 给你一堆线段，可能有overlap,找出它们cover住的总长度，follow up,不
sort怎么做
11. Given an array of integers, 除一个数字出现奇数次外，所有数字都出现偶
数次
，找出那个出现奇数次的。
12. Given两个文件名，打印出重合的行
13. A B D F G _ 填出下一个字母（我保证这是我所有所有的面试题里最奇葩的，
给的hint是横杠上填H,然后问我下一个是什么，到最后也不知道怎么办，非常尴尬）
14. 挑出一个log出现次数最多的3条记录，答曰用heap,然后实现heap的extract
maximum 和maximize at index i的code
15. 密码题（板上讨论过多次），一个密码锁四位，可以用一个长string,来每四个
每四个读来试密码，怎么设计这个长string用尽可能少的digits来试出0000-9999这一
万种可能。Hamilton回路问题，NP, dfs+recursion，Wikipedia上有代码。但是也有别
的方法。
16. Count and say, leetcode原题
17. 实现两个methods, 一是ispalindrome(),这个很简单，一个是 ispalingram(),
given an alphabetic,判断一个string 是不是cover了alphabetic中的所有字母且不包
含alphabetic中没有的字母。
再给你一个set of words,任取一些words以不同的顺序拼起来都可产生phrases,问怎么
有效返回这个set能产生的所有既是palindrome又是palingram的phrases.
18. Anagrams,leetcode原题，O(n)解法
19. LRU cache,当时还不是，现在也是leetcode原题了
20. Sqrt(x), leetcode原题，followup是，如果用牛顿法，不是求f(x)=x^2=0这
个方程的解，而是一个whatever方程的解，怎么写code.
21. 两个int array, size 都是n,每个array各挑一个数相加，可以得到n^2个sum,
返回这些sum中最大的n个，O(nlogn)解法
22. Find Influencer，O(n)解法，http://www.glassdoor.com/Interview/Consider-an-X-x-Y-array-of-1-s-and-0s-The-X-axis-represents-influences-meaning-that-X-influences-Y-So-for-example-i-QTN_498161.htm
23. 设计一个类amazon商品的page,包括的内容有product info, reviews,
recommendations (like ppl who buy this also buy),要求user customized.
24. 设计一个youtube的type ahead search bar,涉及到数据结构，distributed
hashtable和估算内存。
25. A cluster of machines, merge sort
准备：
Cc150, programming interview exposed, introduction to Algorithm 第三版（当然
了没看完）leetcode 两遍半, careercup网站面经，本版面经，wikipedia
感想：
好好做题，自己做，做了要懂，不懂就问。
初级码工的job market还挺好的吧，大家加油。 | f*****d
发帖数: 209 | 2 flag齐了，哈哈
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| J****3
发帖数: 427 | | m****i
发帖数: 650 | 4 可以试试Twitter,如果想refer可以ping我，t相对小机会多：） | b*******e
发帖数: 123 | | w********s
发帖数: 214 | | c********e
发帖数: 186 | | m**p
发帖数: 189 | | u*****o
发帖数: 1224 | | l*********u
发帖数: 19053 | 10 congrats!
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| | | n******n
发帖数: 567 | 11 17， ispalingram是什么意思？
22， Find Influencer 这里用考虑间接的influence 么？ | f********4
发帖数: 988 | 12 这是多么牛的一个人啊，太崇拜了。有时候看本版，尤其是“找工作太郁闷”（我自己
也发过。。），和这种FlAG大满贯，实在不能不感慨天道酬勤
[发表自未名空间手机版 - m.mitbbs.com] | b********6
发帖数: 97 | 13 17,method的解释已经在文中给出： “given an alphabet,判断一个string 是不是
cover了alphabet中的所有字母且不包含alphabet中没有的字母。”string符合这个
要求,则ispalingram()返回true,否则false.
22,考虑，influence具有传递性。
【在 n******n 的大作中提到】
: 17， ispalingram是什么意思？
: 22， Find Influencer 这里用考虑间接的influence 么？
| f********e
发帖数: 91 | 14 能说下21题怎么做的吗？是先排序再用heap选出n个最大的数吗？
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| L****Y
发帖数: 355 | 15 基本都是leetcode原题或者面经。RP真好，怎么碰到的全是做过的。
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| z****s
发帖数: 409 | 16 都是什么职位？software engineer？ | c********p
发帖数: 1969 | | m****h
发帖数: 6 | | g******i
发帖数: 118 | 19 这是怎么一种牛气...
本科生物，统计master,找的是纯马公工作，拿的offer几乎完爆90%马公... | b********6
发帖数: 97 | 20 对的，但是不能对n^2个sum排序，不然达不到nlogn的复杂度。
而是对两个n的数组分别排序。在heap中存的元素类型是a pair of indice (ai,bi)
挑出来的第一个sum，必然是(a0,b0),接下来的做法就应该比较明晰了吧。
【在 f********e 的大作中提到】
: 能说下21题怎么做的吗？是先排序再用heap选出n个最大的数吗？
:
: file
: server
| | | s*****r
发帖数: 43070 | | P*******r
发帖数: 210 | 22 22题考虑传递性，假设 A->B->C， 是不是说 influence matrix中 Influence[A][C] =
false, 但是实际上A 还是通过B influence 了 C
这样的话，不能简单地做两两比较，好像这个O(n)算法就不能用了。
http://www.geeksforgeeks.org/the-celebrity-problem/
如何实现O(n)呢？
【在 b********6 的大作中提到】
: 17,method的解释已经在文中给出： “given an alphabet,判断一个string 是不是
: cover了alphabet中的所有字母且不包含alphabet中没有的字母。”string符合这个
: 要求,则ispalingram()返回true,否则false.
: 22,考虑，influence具有传递性。
| f********e
发帖数: 91 | 23 谢啦：）
【在 b********6 的大作中提到】
: 对的，但是不能对n^2个sum排序，不然达不到nlogn的复杂度。
: 而是对两个n的数组分别排序。在heap中存的元素类型是a pair of indice (ai,bi)
: 挑出来的第一个sum，必然是(a0,b0),接下来的做法就应该比较明晰了吧。
| J****3
发帖数: 427 | | I*****a
发帖数: 5425 | | n*****f
发帖数: 17 | 26 恭喜LZ！！！
题目不错，写些思路，如果有问题或者更好的思路，欢迎各位大牛指点
facebook
2. 先比较两个字符串的长度。如果相等，正向和反向分别求最长公共前缀，之和大于
等于串长-1就是similar；如果长度相差1，正向和反向分别求最长公共前缀，之和大于
等于短串的长度就是similar；否则不是similar。前两种情况可以合并一下，更简单，
O(n)
google
1. 维护两个指针从两头向中间扫
2. 每个function_name记录call的次数和总的duration time
3. parent -> child建边，入度为0的点是root，从root出发BFS或DFS
4. 同上
5. 同上
twitter
2. trie
ebay
1. 先git log找到相应时间段的commits，再用git diff找出时间段前后两次修改了哪
些file
3. ac自动机
walmartlab
1. 先看最大值能否正数，找最大的三个正数或绝对值最大的两负一正；如果不行，看
数组里有没有0；还不行就找绝对值最小的三个数
2. ^(https?:\/\/)?([\da-z\.-]+)+\/([^=,]*)=("[^"]*"|[^,"]*)
onsite
4. 题目少个条件，每次最多两人同时通过。1、2过去，1回来，5、10过去，2回来，1
、2过去。更一般的问题可以编程来解，根据每个人在桥的的哪一边为状态，建图，就
是最短路问题了。
5. 没理解啥意思啊。。。
8. 有parent指针，先得到两个结点的深度，然后较深的先走深度之差那么多步，然后
一起走；没有parent指针，DFS，记录两个结点从根出发的路径；followup边走边hash
10. 起点和终点看成两个事件，对所有事件排序，扫一遍；followup线段树
11. 异或
17. 先把包含不在alphabet里的字母的串都去掉，剩下的words reverse后建棵trie树
，DFS回文串前半部分的组合，用一个指针在trie树上跟着跑，如果找不到下一个结点
，就剪枝。
20. followup 还是一样的，能求出导数来就行
21. 两个array分别排序。一开始堆里只有一个元素，是两个array里最大的元素之后。
每次从堆里取出一个元素，然后把该元素对应的两个值分别向后移一个，对应的两对放
入堆里。
22. A influence B，则B不是celebrity；否则A不是。每轮去掉一个candidate。 | c********t
发帖数: 32 | 27 恭喜大牛
请问大牛具体如何从统计专业,自学可以转到SE这个行业里来呢?
如何自学过程?能否和版上的朋友分享一点经验，非常感谢大牛分享!! :) | t***t
发帖数: 6066 | 28 估计是长得像芭比娃娃。
【在 g******i 的大作中提到】
: 这是怎么一种牛气...
: 本科生物，统计master,找的是纯马公工作，拿的offer几乎完爆90%马公...
| l*****i
发帖数: 68 | | b********6
发帖数: 97 | 30 我觉得你说的对，如果influence有传递性的话，好像还是要O(n^2)因为要比较,只是进
出栈的次数是O(n)
=
【在 P*******r 的大作中提到】
: 22题考虑传递性，假设 A->B->C， 是不是说 influence matrix中 Influence[A][C] =
: false, 但是实际上A 还是通过B influence 了 C
: 这样的话，不能简单地做两两比较，好像这个O(n)算法就不能用了。
: http://www.geeksforgeeks.org/the-celebrity-problem/
: 如何实现O(n)呢？
:
| | | b********6
发帖数: 97 | 31 感谢你总结思路，基本都和我想的差不多，过独木桥问题我的确少了条件，已经改正了。
【在 n*****f 的大作中提到】
: 恭喜LZ！！！
: 题目不错，写些思路，如果有问题或者更好的思路，欢迎各位大牛指点
: facebook
: 2. 先比较两个字符串的长度。如果相等，正向和反向分别求最长公共前缀，之和大于
: 等于串长-1就是similar；如果长度相差1，正向和反向分别求最长公共前缀，之和大于
: 等于短串的长度就是similar；否则不是similar。前两种情况可以合并一下，更简单，
: O(n)
: google
: 1. 维护两个指针从两头向中间扫
: 2. 每个function_name记录call的次数和总的duration time
| s***e
发帖数: 403 | | P********t
发帖数: 4 | 33 Thank for sharing. LZ is touch. | d***n
发帖数: 832 | 34 牛人，不得不顶
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| w**7
发帖数: 22 | 35 I read the discussions of problem 15 (shortest password string), but I don't
feel this problem has really been solved. Can anyone post code that's been
verified? | m*******m
发帖数: 80 | | m********8
发帖数: 43 | 37 太牛了楼主~~能详细谈谈准备的过程吗？统计转过去，貌似跨度还不小，楼主之前的CS
基础如何？ | b********6
发帖数: 97 | 38 http://en.wikipedia.org/wiki/De_Bruijn_sequence
't
been
【在 w**7 的大作中提到】
: I read the discussions of problem 15 (shortest password string), but I don't
: feel this problem has really been solved. Can anyone post code that's been
: verified?
| q****m
发帖数: 177 | 39 ebay 第三题ac自动机怎么搞？感觉对每个word,用一次kmp吗？
【在 n*****f 的大作中提到】
: 恭喜LZ！！！
: 题目不错，写些思路，如果有问题或者更好的思路，欢迎各位大牛指点
: facebook
: 2. 先比较两个字符串的长度。如果相等，正向和反向分别求最长公共前缀，之和大于
: 等于串长-1就是similar；如果长度相差1，正向和反向分别求最长公共前缀，之和大于
: 等于短串的长度就是similar；否则不是similar。前两种情况可以合并一下，更简单，
: O(n)
: google
: 1. 维护两个指针从两头向中间扫
: 2. 每个function_name记录call的次数和总的duration time
| M*******a
发帖数: 1633 | 40 这个生物本科+统计master+9个月工作就能拿到这么offer？都是马宫？ | | | c*****u
发帖数: 35 | | c***z
发帖数: 6348 | 42 赞
拜牛人
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| w****a
发帖数: 710 | 43 赞楼主，
one edit distance那个题最近很hot啊。
在N个面经里看到了。 | j**********g
发帖数: 77 | | P********s
发帖数: 19 | 45 恭喜！
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| b******i
发帖数: 914 | 46 你好，（a0, b0）之后再怎么办呢，我好像还是不太知道，谢谢！
【在 b********6 的大作中提到】
: 对的，但是不能对n^2个sum排序，不然达不到nlogn的复杂度。
: 而是对两个n的数组分别排序。在heap中存的元素类型是a pair of indice (ai,bi)
: 挑出来的第一个sum，必然是(a0,b0),接下来的做法就应该比较明晰了吧。
| x****B
发帖数: 103 | 47 厉害。
file
server
【在 b********6 的大作中提到】
: 背景：本科生物，统计master + 9个月工作经验
: 结果: offer: amazon, facebook, linkedin, google
: Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
: 电面：
: Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
: 里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
: 有问题怎么trouble shooting的开放问题。
: Linkedin 两个：
: 1 binary tree level order traversal, leetcode原题
: 2 pow(x,2) leetcode原题
| J*******o
发帖数: 741 | |
|
