x****1
发帖数: 118 | 1 Linkedin
phone1：烙印
lowest common ancestor w/ and w/o parent pointer
phone2：国人
search in rotated sorted array
onsite:
1.两个国人
implement addInterval(start, end) and getcoverage(),
2.两个国人
talk projects and some behavior question
3.烙印
lunch, talk about technologies interest
4.亚裔，不确定是否国人
Manager, talked a lot of behavior questions, interest and projects
5.烙印
Design: tinyurl
6.烙印+小白
1.exclusive array, give an arr1, return a new arr2, arr2[i] is the
multiplication of all elements in arr1 except arr1[i]
2.boolean isMirrorTrees(tree1, tree2)/inplace convert a tree to its mirror
tree/create a new mirror tree
3.find the intersection of two linked list(do not use hashmap)
Amazon
phone1: 烙印
Given a list of test results (each with a test date, Student ID, and the
student’s Score), return the Final Score for each student. A student’s
Final Score is calculated as the average of his/her 5 highest test scores.
You can assume each student has at least 5 test scores.
phone2:白男
1.大数plusOne
2.给你一个按字母顺序排好的字典（但你不知道字母顺序,非英语），要求找出字母顺序
例：
单词顺序：
wrt
wrf
er
ett
rftt
字母顺序：
w,e,r,t,f
onsite:
1. 白男
class MagicNumber{
boolean isMagicNum(long num);
long nextMagic(long num){
while(!isMagicNum(num)){
num++;
}
return num;
}
}
consider a data structure to improve the nextMagic(long num)
2. 烙印
behavior questions and text editor design(insert, add, search, cut, paste)
3. 白男
大数加法 (int数组表示大数，每一个元素代表一个2^31进制数字)
4. 日本人manager
lunch interview:
4.1 describe a time you are stressful to meet a deadline
4.2 describe a time you feel most proud in your professional career
4.3 what would you change in your past project if you have a chance
5. 白男
give API: List getMovies(Actor a); List getActors(Movie m);
implement: int findDistance(Actor a, Actor b)
6. 白男
System design, open question, give your solution, describe pros and cons
Google
phone： 白男
1. remove duplicates of the array in place
2. 一道BFS题。具体是什么记不清了
on-site:
1. 白男
count islands in a m*n grid （一个联通的值为1的区域被视为一个island）
例：
0011010
0010010
1000110
0000001
4 islands found in above grid
Design： copy and shuffle lines in a 8 GB file, memory limit 1 GB (you are
given multiple machines)
2.国人
void minMSwap(int[] num, int m), return the min array after m swaps， each
swap happens only between two adjacent elements([4,2,1,3], 2 return [1,4,2,3
] )
4,2,1,3
4,1,2,3
1,4,2,3
design a protocol to syncing gmail messages among different client apps
3.小白
give a list of , build the tree(not limited to a
binary tree), then update each node’s sum value(sum is the sum of all its
descendents’ weights)
int[] num incremental(大数加一)
design interface for memory cache
4. 国女
find a intersection to build office so that the sum of all employees’
commute distances is minimum. （the map is represented as a m*n grid, you
are given each employee’s coordination, they can only move in up-down and
left-right directions）
5. 白男manager
How to find median of unsorted integers in linear time
Design the system architecture(FE and BE) for above service in a distributed
system (find optimal office location).
FB
phone: 小白
word break, suffixtree
Onsite:
1. 越南人？
Talked the resume, project and behavior questions. lowest common ancestor
with parent pointer.
2. 白男
is valid binary search tree (handle edge case), if the tree size exist
memory limit, how to handle?
3. 白男
Design question, FB search
4. 国人
give a time, search in a log file. 需要自己提问需求，并考虑边界情况。
00:23 *****
00:24 *****
00:56 *****
01:02 *****
how to distribute the work to 10 servers?
5. 白男
Celebrity Problem | x****1
发帖数: 118 | | h*******e
发帖数: 125 | | c********r
发帖数: 286 | | o********t
发帖数: 1655 | 5 果然L三最多，其他还好
【在 x****1 的大作中提到】
: Linkedin
: phone1：烙印
: lowest common ancestor w/ and w/o parent pointer
: phone2：国人
: search in rotated sorted array
: onsite:
: 1.两个国人
: implement addInterval(start, end) and getcoverage(),
: 2.两个国人
: talk projects and some behavior question
| g**4
发帖数: 863 | | x****1
发帖数: 118 | 7 我遇到的烙印面试官都有一个很明显的细节，你在回答他们问题的时候，只要稍有
迟疑他们都会在本上记录，虽然不知道写的什么，但肯定不是好话。其他面试官无
论国人还是老美都没有这样。据经验人士称，这样做他们在写你坏话的时候就显得有凭
有据了，会抓住小问题大做文章。另外，A家店面的烙印不让我改写online code，都要
求我注释并保留更改的地方。这点我当时就觉得很恶心，他们提交feedback的时候可以
随便讲故事了，而且又是显得有凭有据。这一点是不是值得国人面试官学习。
【在 o********t 的大作中提到】
: 果然L三最多，其他还好
| t********o
发帖数: 10 | 8 是这样的，我遇到的几乎所有烙印面试官，只要你有迟疑不确定的表现，或任何思考过
程中表现出的不完美，都立刻在小本本上记录下来。烙印面试官会问“are you sure”
然后狂敲键盘或赶紧拿笔写在笔记本上。
例如烙印问我非OSI网络分层有几层，我回答5层，烙印问你确定？不是四层？，我回答
他哪五层，然后烙印一脸鄙视的看看我，低头在小本上记录。
【在 x****1 的大作中提到】
: 我遇到的烙印面试官都有一个很明显的细节，你在回答他们问题的时候，只要稍有
: 迟疑他们都会在本上记录，虽然不知道写的什么，但肯定不是好话。其他面试官无
: 论国人还是老美都没有这样。据经验人士称，这样做他们在写你坏话的时候就显得有凭
: 有据了，会抓住小问题大做文章。另外，A家店面的烙印不让我改写online code，都要
: 求我注释并保留更改的地方。这点我当时就觉得很恶心，他们提交feedback的时候可以
: 随便讲故事了，而且又是显得有凭有据。这一点是不是值得国人面试官学习。
| C******m
发帖数: 213 | | x****g
发帖数: 1512 | 10 void minMSwap(int[] num, int m), return the min array after m swaps([4,2,1,
3], 2 return [1,4,2,3] )
这个应该是[1,2,3,4]?
4和1换
完了4和3换
就是从高到低，每次换最小的？呵呵。 | | | x****1
发帖数: 118 | 11
忘记说明了，只能swap相邻的两个元素
【在 x****g 的大作中提到】
: void minMSwap(int[] num, int m), return the min array after m swaps([4,2,1,
: 3], 2 return [1,4,2,3] )
: 这个应该是[1,2,3,4]?
: 4和1换
: 完了4和3换
: 就是从高到低，每次换最小的？呵呵。
| l***c
发帖数: 55 | 12 big cow, minMSwap有什么好思路没？
我想来想去不知道对不对：
找最小的元素，判断swap它需要的最少交换次数n，如果n<=m，swap过来，m -= n, 递归
如果n>m?那就找次小的，重复上面的步骤
这个复杂度不乐观 | x****1
发帖数: 118 | 13
递归
我当时也就想到这个解法。我觉得可以优化的是当找到最小元素，不用真的一个一个
swap，直接memMove或者Array.Copy会减少内存的占用
【在 l***c 的大作中提到】
: big cow, minMSwap有什么好思路没？
: 我想来想去不知道对不对：
: 找最小的元素，判断swap它需要的最少交换次数n，如果n<=m，swap过来，m -= n, 递归
: 如果n>m?那就找次小的，重复上面的步骤
: 这个复杂度不乐观
| s****n
发帖数: 147 | 14 多谢LZ的信息……麻烦问下tinyurl这个有什么好的思路吗？多谢！
【在 x****1 的大作中提到】
: Linkedin
: phone1：烙印
: lowest common ancestor w/ and w/o parent pointer
: phone2：国人
: search in rotated sorted array
: onsite:
: 1.两个国人
: implement addInterval(start, end) and getcoverage(),
: 2.两个国人
: talk projects and some behavior question
| x****1
发帖数: 118 | 15 比较流行的做法是用base64算法把long url 转换成 short url，另外你可以搜一下分
布式系统中的键值存储
【在 s****n 的大作中提到】
: 多谢LZ的信息……麻烦问下tinyurl这个有什么好的思路吗？多谢！
| c******0
发帖数: 260 | 16 下面两题不会，可以请LZ说一下自己的想法么？
FB
is valid binary search tree (handle edge case), if the tree size exist
memory limit, how to handle?
//难道要把tree 写进文件里？？
give a time, search in a log file. 需要自己提问需求，并考虑边界情况。
00:23 *****
00:24 *****
00:56 *****
01:02 *****
//要搜索什么？？这个也得考虑内存不够吧？分解文件成下文件？
【在 x****1 的大作中提到】
: Linkedin
: phone1：烙印
: lowest common ancestor w/ and w/o parent pointer
: phone2：国人
: search in rotated sorted array
: onsite:
: 1.两个国人
: implement addInterval(start, end) and getcoverage(),
: 2.两个国人
: talk projects and some behavior question
| x****1
发帖数: 118 | 17 1.树的节点太多，一台机器存不下，怎样distribute到多台机器，另外要考虑算法的空
间复杂度所占用的系统资源。
2.给你一个时间点，找到这个时间点之后的第一条log，比如给你00：30， 你要返回
00：56这一行log
【在 c******0 的大作中提到】
: 下面两题不会，可以请LZ说一下自己的想法么？
: FB
: is valid binary search tree (handle edge case), if the tree size exist
: memory limit, how to handle?
: //难道要把tree 写进文件里？？
: give a time, search in a log file. 需要自己提问需求，并考虑边界情况。
: 00:23 *****
: 00:24 *****
: 00:56 *****
: 01:02 *****
| s**x
发帖数: 7506 | | l**********a
发帖数: 181 | | f******s
发帖数: 25 | 20 或者可以找m steps内最小的swap， 就不需要重新再找
递归
【在 l***c 的大作中提到】
: big cow, minMSwap有什么好思路没？
: 我想来想去不知道对不对：
: 找最小的元素，判断swap它需要的最少交换次数n，如果n<=m，swap过来，m -= n, 递归
: 如果n>m?那就找次小的，重复上面的步骤
: 这个复杂度不乐观
| | | j*********n
发帖数: 34 | 21 哪位大牛能不能说说google第4轮那个grid中找一个点到其他所有点距离最短的
solution? 看到好几个google面经都问了这个题。 网上搜了搜也没找到靠谱的答案 | f*****e
发帖数: 2992 | 22 convex
【在 j*********n 的大作中提到】
: 哪位大牛能不能说说google第4轮那个grid中找一个点到其他所有点距离最短的
: solution? 看到好几个google面经都问了这个题。 网上搜了搜也没找到靠谱的答案
| o******e
发帖数: 14 | 23 我觉得这个题可以先建个minHeap把(value, index) pair存起来，每个循环里面按照上
面说的思路去做，最后到了最小值m!=0的话就最小和次小之间不断转换。
复杂度O(nlogn)
【在 x****1 的大作中提到】
: 1.树的节点太多，一台机器存不下，怎样distribute到多台机器，另外要考虑算法的空
: 间复杂度所占用的系统资源。
: 2.给你一个时间点，找到这个时间点之后的第一条log，比如给你00：30， 你要返回
: 00：56这一行log
| x****1
发帖数: 118 | 24 这道题以前讨论过。解法很简单。就是分别求x，y轴坐标的中值。所以下一道题是如何
求一个未排序数组中值，面试官提示说有O(n)解法，但是我只会nlog(n)
【在 j*********n 的大作中提到】
: 哪位大牛能不能说说google第4轮那个grid中找一个点到其他所有点距离最短的
: solution? 看到好几个google面经都问了这个题。 网上搜了搜也没找到靠谱的答案
| s*********n
发帖数: 191 | 25 grid这道题的考点是set的 union and find, 答道点子上就ok了。 github里面能找到
很优美的代码经典解。
未排序数组的中值线性解是quicksort的partition函数的变体，这是很基础的算法了。
开个玩笑，以前有个同事专门喜欢问第二个题，他说：可以刷掉那些不理解算法，背题
刷题的人。。。。囧
【在 x****1 的大作中提到】
: 这道题以前讨论过。解法很简单。就是分别求x，y轴坐标的中值。所以下一道题是如何
: 求一个未排序数组中值，面试官提示说有O(n)解法，但是我只会nlog(n)
| r****r
发帖数: 54 | 26
请教这道题用set的union and find怎么解？
未排序数组找median用randomized selection O(n)可解，但是worst case可能超过O(n
).非randomized的比较复杂，但是worst case是O(n). union-find可以更简单的解这道题
么？
update: 貌似union-find讲的是另一个grid问题么？Find number of island？
【在 s*********n 的大作中提到】
: grid这道题的考点是set的 union and find, 答道点子上就ok了。 github里面能找到
: 很优美的代码经典解。
: 未排序数组的中值线性解是quicksort的partition函数的变体，这是很基础的算法了。
: 开个玩笑，以前有个同事专门喜欢问第二个题，他说：可以刷掉那些不理解算法，背题
: 刷题的人。。。。囧
| b*******r
发帖数: 50 | | m********l
发帖数: 791 | 28 phone第二轮 字典那题
是不是给定的输入时保证输出只有一种可能性？
比如
wrt
wrf
er
ett
rftt
就只有一种可能性w->e->r->t->f，但是
wrt
wrf
er
ef
rftt
就有多个可能性了,w->e->r->f是可以确定，但是t的位置不能确定，有多种可能 | x****1
发帖数: 118 | 29 你理解的对，面试的时候只需要把你的这种观察说出来就好了。
【在 m********l 的大作中提到】
: phone第二轮 字典那题
: 是不是给定的输入时保证输出只有一种可能性？
: 比如
: wrt
: wrf
: er
: ett
: rftt
: 就只有一种可能性w->e->r->t->f，但是
: wrt
|
|
