w*****t
发帖数: 485 | 1 Facebook面试Q&A （from: http://heliang.me/blog/）
Posted by roba on July 14, 2012 10 comments
续上篇文章，我把大家在得知此消息后普遍感兴趣的一些问题总结了一下，在此一并写
出。
说实话，其实我的眼界从来很狭窄，以前想的是，如果能在天朝帝都扎下脚跟，过上老
婆孩子热炕头的日子，对我来说已很满足。所以之前也从未对出国读书或工作有过准备
，下文所述很多内容都是我在最近的一小段时间里才接触到的，而且现在离正式入职还
早，对于fb内部的情况并没有什么了解，签证之类的麻烦事还在办理中，说不定去不成
了也是有可能的(-_-)……扯远了，总之就是说，虽然我已经尽力做到客观准确，但恐
怕难免会有错漏，请读者不吝赐教。本文仅供参考，引起什么不好的后果本人不负责任
=,=
Q: 你的学历、学校、专业、英语成绩、论文、竞赛获奖、工作经验、参与开源项目等
背景情况？一定很牛吧？
A: 真的不牛，矮丑穷，纯RP爆发而已。本科天津大学软件学院，硕士天津大学计算机
学院。高中无竞赛经历，本科阶段ACM-ICPC竞赛亚洲区域赛有几次... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 2 他说的不是二叉树，所以没有左右子树的歧义性。你给的两棵树其实是一样的。 |
|
C*******n
发帖数: 24 | 3 Q: You are given a binary tree in which each node contains a value Design an
algorithm to print all paths which sum up to that value Note that it can be
any path in the tree - it does not have to start at the root.
其实这个题本身就说的不清楚，我看了一下答案解析，发现题意是：给你一个二叉树，
每个节点都有一个数，再给你一个sum，求树中所有和为sum的路径，路径的开始可以
不为root。
答案中给出的解法号称O(nlgn)的时间复杂度（其实就是最直觉化的做法，每个节点都
DFS），但是我感觉答案对时间复杂度的分析有问题，因为他分析的时候有个条件是：
There are 2^r nodes at level r。我感觉他分析的这个不是最坏情况，最坏情况应该
是每一个level只有一个节点，时间复杂度为O(n^2)
求问刷过Cracking Coding Interview的前... 阅读全帖 |
|
l***m
发帖数: 339 | 4 来自主题: JobHunting版 - G/F面经 我觉得拓扑排序应该是定义一些关系，然后让你输出最终的order吧，比如现在定义的
字母顺序是a,b,c,d,e,f,g,他如果重新定义一些顺序比如c->a，等等，让你重新输出
order的序列，就是用拓扑排序。
穿线二叉树我猜是把树的每一层连起来成一个linked list吧。 |
|
O******i
发帖数: 269 | 5 又是不到两个小时的onsite，估计挂了。
本来是一个白人小兵，问了三道简单的C++题目，在白板上写，他说不错。突然又有一
个人敲门，进来一个亚裔小兵，噩梦开始了。亚裔问如何设计优先队列，我说了用heap
, 他说他不懂什么是heap，还以为我说的是C++用new时候的分配。我说了是数组表示二
叉树，对他的例子都做了heap的heapify操作。然后他说我用heap这个太复杂，他的方
法好像就是用数组来实现，晕。而且他看了板上我画的用来表示堆的树，还以为是BST.
.. |
|
g*******r
发帖数: 44 | 6 google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
... 阅读全帖 |
|
g*******r
发帖数: 44 | 7 google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
... 阅读全帖 |
|
h*******l
发帖数: 22 | 8 虽然记得不太清楚， 贡献一下面经回馈本版吧。只onsite过G和Y。其他大多电面， 而
且久远，就记不了那么清楚了。
Y 电面一个小时，只有一次电面，过了就onsite。难度和大多数电面都差不多。
Y我有两个onsite
第一个
1. 问了买卖股票（很遗憾， 没做过，不过最后还是整出线性时间的算法了，花的时间
比较多，要是leetcode上做过，会快很多），
2. LC Sequence（基础，飞快写完递归和非递归解法）；
3. hashtable实现 (基础，TA过高级数据结构)；
4. 二叉树高度，要求非递归解法
5. 数组找到第k个最大的（高频题，selection sort，平均n，最坏n平方；也可以用大
小为k的heap做，让我实现了其中一个）
6. 给一个堆，里头有无序的数，排序之，要求只用堆数据结构，最好只用两个，复杂
度最好用nlogn（我当时没有达到他的要求，看上去用了两个stack，其实用了程序自己
的stack，复杂度也没有达到n平方）
7. 单链表，有环，数据部重复， 找到环， 要求给出两种做法 （cracing google
interview上的题，两个指针... 阅读全帖 |
|
w********p
发帖数: 948 | 9 3. 继续判断这个二叉树是不是平衡树
A balanced binary tree is commonly defined as a binary tree in which the
depth of the two subtrees of every node differ by 1 or less,[3] although in
general it is a binary tree where no leaf is much farther away from the root
than any other leaf. (Different balancing schemes allow different
definitions of "much farther".[4]) Binary trees that are balanced according
to this definition have a predictable depth (how many nodes are traversed
from the root to a leaf, root counting ... 阅读全帖 |
|
G****A
发帖数: 4160 | 10 3. 判断这个二叉树是不是平衡树
recursive, top-down, O(n^2)
4. 优化3.
recursive, bottom-Up, O(n) |
|
d********p
发帖数: 9 | 11 [Last update on 04/11/2013 ]
说好的上面经。总共个面了四个公司，3个朋友推荐，1个是自己本来实习过。
1. Facebook
签了NDA就不具体说题。
电面
共一轮：一道二叉树，一道简单递归打印的题。都是常见题，难度中等。
Onsite
第一轮：Pirate。先问了一些研究相关的问题和细节，然后系统设计。
第二轮：Jetti (Jedi?)。论文探讨。同时也问了一些非技术问题，比如为何选择F这种
。最后时间还多，附加一道关于图像处理编程题。
第三轮：Ninja。上来直接编程，关于正则表达式的题，LeetCode上做过。现场没有做
好，见总结。
第四轮：Ninja。先是问了点简历，然后直接做题。经典题，二分搜索的题，也是
LeetCode上做过。
第五轮: Pirate。不知道为何多加了这一轮设计。感觉是培训面试官的一轮，旁边还有
一个人。（人称shadow？）
结果：被拒。
总结：第三轮，编程没有bug free，边角情况虽然不少，但LeetCode刷过一边，不应该
犯错。第四轮，没有给出面试官想要的解，虽然时空复杂度都一样。两轮设计题，也没
有表现出自己的... 阅读全帖 |
|
s**s
发帖数: 70 | 12 来自主题: JobHunting版 - A家面试题 先谢版主done推荐，虽然已跪了。
onsite见了5人，现在只记得部分：
1. 求用元素周期表中的每个元素代号，能评出的最长单词。
比如：T = { Si, C , K }. 结果为 sick.
(大小写无关， 每个元素可用几次， 怎么判断单词/已给字典， ... 这些前提假定都
要与面试官讨论)
2. 两棵二叉树，判断是否存在公共结点。
只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
，空间是O(M). 不知道有什么好的办法？？？
3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。
当时现场有些懵（最后一轮），主要没想清楚多少种状态（色子可以旋转）。
面试官提示后，又说我多算了几种。他认为是3种就行，我说的6种中，有2种重复了。
回来后仔细想了想，其实一样的。他说的3种中，每种可以双向旋转，所以一共 3 * 8
= 24.
而我一开始想的6种，每种如果规定只能按右手螺旋法则旋转，也就是 6 * 4 = 24. 其
实是一样的。
这题没见过，一共只给了25分钟左右想，感觉时间挺紧的。 |
|
l*********8
发帖数: 4642 | 13 考虑partition生成的二叉树。 如果加上编码：partition在左边的，标记为0，
partition在右边的，标记为1， 那么就是一颗编码树。 每个元素是均等的， 所以每
次partition分成尽可能相等的两份，得到的是Huffman tree, 编码总长度是最优的，
也就是partition的总比较次数是最少的。 |
|
h*******0
发帖数: 270 | 14 为啥第一题，第二题都是dp？ 第一题遍merge，边用两个index记录不就行了？ 第二题
同时recursive遍历两个二叉树不就可以了？ 是不是我哪理解错了？ |
|
d**e
发帖数: 6098 | 15 ☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Thu Mar 14 18:44:22 2013, 美东) 提到:
今天面试一个candidate, 人很随和，一看就是容易相处的人。问题是，他的编程确实
不过关。一道简单的编程，首先他很难总结出数学公式，经过提示，他可以总结公式了
，然后写程序比较困难。随后的复杂度分析，他也不是很有概念。本来这是内部转组，
我也不想刁难人，但是这样的面试，让我很难写一堆好话上去。
由此就想到版面上经常讨论的两个问题：
－我问题都答对了，为什么还是没有offer?
－为什么中国人喜欢刁难中国人？
从面试官的角度想，我反应过来：因为对方友善，又是内部的人，我没有道理跟他为难
。看见他的水平，我下面的问题就会稍微降一点难度。从他的角度看，似乎他的回答还
都在轨道上，没有完全卡住。
想想那些super-smart的面试官，他们多半也会类似的想法：如果给你一道题，你没能
在他预期的时间解出来，或者本来是个开胃的题，被解成了一道主菜，哪怕这种题做对
了，在他的印象也是大损... 阅读全帖 |
|
l*n
发帖数: 529 | 16 你再看看题目，是BST而不是general的二叉树。参数里的p & q用TreeNode就是个摆设
。new一个不是树的节点的node当然不会跟root相等啊。 |
|
J****3
发帖数: 427 | 17 攒人品
From MITBBS:
1. 给一个二叉树 返回镜像 (Binary Tree Mirror)
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favori... 阅读全帖 |
|
w*****h
发帖数: 423 | 18 interview 1:
1. 给一个char[]和一个字典，求所有在字典中并且由char数组里字母构成的单词，假
设isWord()可以直接判断某个单词在不在字典里。
2. 数组的permutation
3. 你会怎么设计1中的字典？
interview 2:
1. 8进制数的plus one
2. 写一个树（非二叉树）的iterator,注意不是traversal，并分析复杂度。
题目都不难，但是还是避免不了小bug，希望能过吧。。。顺求bless |
|
c******0
发帖数: 260 | 19 1.bloomberg:
电面一轮就挂了。。。
问了很多C++ 的问题，比如virtual 析构函数。最后竟然问了database的问题。怎么设
计表之类的。基本没懂到底要问什么。。。
2. LinkedIn
一轮电面水果。 判断string是否为合法整数。 还有一个算和的。非常简单。。
二面： pow（）实现（leetcode）. 最大子序列和（leetcode）. 根据第二题，改成最
大乘积（就挂在这题上了。。。）
3.rocket fuel
一轮电面： 好像版上有人面google也是这题： 一个数组A[], 构造数组B[]。 要求B[i
]= A中所以元素的乘积，除了A[i].不让用除法。 扫两遍数组搞定。
然后就是他家的经典题目 millions of ADs.
二轮电面： 跟面试官扯了很久做过的project。就出了一题。找出二叉树中任意两节点
的路径。面试官人很nice。开始思路不是很优化。给了点提示。时间关系没有写完。但
是基本上把最主要的找路径给写完了。
三轮电面： Young table 的问题。leetcode原题。 告诉面试官我知道这题。这种
matrix叫you... 阅读全帖 |
|
J*****a
发帖数: 4262 | 20 没有特地为FB准备，不变应万变，一样复习的
1）做leetcode oj, 这是最重要的。。。即使面试没有一模一样的题目，但练完100题
之后，写代码的速度、bug的数量都会和练之前有质的不同
另外自己多总结，比如哪些有linear解，哪些是指数复杂度，哪些是DP，哪些用stack
等。
如果思考的再深入些，可以想到更多，比如可以总结出什么样的二维DP一定可以把空间
复杂度由O(n^2)降至O(n)
2）看本版面经，题目一模一样的概率不大，但是看了面经心里踏实，知道大概流程是
怎么回事，题目大概是什么类型
3）对于lc oj没有覆盖的，自己做些功课，列一些我暂时能想起来的：
3a，简单常见的算法，自己写一遍，比如快速排序，merge排序，桶排序，quick
selection等等
3b，对于常用数据结构，虽然c++或java里可以从库直接拿来用，但是自己写一遍这些
数据结构的实现能加深理解，例如hashtable, heap, threadsafeblockingqueue, BST
的插入删除等。
而且有些面试题，你还是要自己写，比如LRU cache里的双向链表什么的，写写基本的
... 阅读全帖 |
|
l***4
发帖数: 1788 | 21 第一轮：
1.为什么喜欢CS。CS跟本专业的比较（lz转行）。
2. 基本数据结构概念：比较哈希表和二叉树，操作复杂度。电话本用什么数据结构。
前缀树查找的时间复杂度（这里差点说错）。
3. 编程题：输出字符流中频率最高的字符的频率（略拗口。。）以及扩展。
4. 对面试官提问题。
第二轮：
1. 为什么亚马逊。
2. 两个最喜欢的数据结构并说一下典型操作及其复杂度。
3. behavior问题：如果你要设计、实现和测试一个功能，如何分配时间；扩展：如果
这个功能（项目）很大很大，该怎么办
4. 编程题：大小为N的数组，所存值为1到N-1，其中有一个重复的值，如何找出这个值。
5. 编程题：atoi，并实验两个样本输入。
6. 对面试官提问题。
之前加了刷题群：229623621，收获很大，希望大家多交流。 |
|
l*********r
发帖数: 136 | 22 背景：中部弱校master，去年五月毕业，刚工作一年（中部小公司），骑驴找马中。
Onsite一共五轮：
--------------------------------------
第一轮（中东人）：
给一个字符串，让压缩并解压，压缩算法类似leetcode中的count and say
输入：aabbbccd 压缩结果：2a3b2cd（注意，'d'前面没有'1'）
引申：输入中如果有数字的话，解压时需要注意歧义问题，例如2a可以解压为'2a'或
者'aa'，问如何解决。答曰用类似ascii码中加反斜杠的做法，或者加个header来标
志压缩过的位，表示同意。
第二轮（老印）：
（leetcode） edit distance，以DP解之，喜。
（leetcode） word ladder，直接给出BFS，不喜，要优化，想了半天给出的答案皆不
喜，最后提示我可以双向BFS，时间不够，没有给出代码。
-----------------午饭-------------------
第三轮（老白）
给一个int的矩阵arr，让返回一个同样大小的result矩阵，每一个result[i][j]... 阅读全帖 |
|
z**a
发帖数: 69 | 23 Lz确定这题对的？不说比较两棵树，有O(1)空间，O(n)时间遍历二叉树的算法么？ |
|
|
c********6
发帖数: 33 | 25 来自主题: JobHunting版 - 一道面试题 不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
的set，
因为是post order所以可以保证 左右孩子都算完了再算父节点，
复杂度n2 |
|
c********6
发帖数: 33 | 26 来自主题: JobHunting版 - 一道面试题 不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
的set，
因为是post order所以可以保证 左右孩子都算完了再算父节点，
复杂度n2 |
|
i*********h
发帖数: 49 | 27 【总结】Java 搞定链表-面试常考题目精选
面试大总结之链表：
一、OverView:
链表是面试中常考的，本文参考了其它一些文章，加上小编的自己总结，基本每个算法
都测试并优化过。
算法大全（1）单链表 中还有一些链表题目，将来也会整理进来。这些题目虽然简单，
但如果能毫无BUG地写出，定能让面试官司对您印象分大增。
小亮点是：主页君用Recursion 和 Iterator 各写了一次所有题目，这样就算遇到不熟
悉的写法，我们也都可以运用自如。
二、代码
以下是原文和代码：
http://weibo.com/3948019741/BseJ6ukI3
三、代码目录：
1. 求单链表中结点的个数:
getListLength
2. 将单链表反转:
reverseList（遍历），reverseListRec（递归）
3. 查找单链表中的倒数第K个节点（k > 0）:
reGetKthNode
4. 查找单链表的中间结点:
getMiddleNode
5. 从尾到头打印单链表:
reversePr... 阅读全帖 |
|
a*****2
发帖数: 96 | 28 求最大的s[i]:
//就用二叉树就足够了吧，树的节点里记录比本节点小的个数
public int sln(){
BSTNode root = new BSTNode(a[n-1],0)
int result = 0;
for i in n-2:0{
//O(logn)
result = max(result,insert(root ,a[i],0));
}
return result;
}
class BSTNode{
int value;
int descendants;
BSTNode left = null;
BSTNode right = null;
}
public int insert(BSTNode root, int value, int cnt){
if(root == null)
return 0;
int result = 0;
if(root.value < value){
result += root.descendants+1;
... 阅读全帖 |
|
B********4
发帖数: 7156 | 29
会是o(n)
queue的长度是不定的，最大长度等于树的宽度，不是高度(深度）。题目中只说是
binary tree。如果是complete binary tree, 应该是n/2。
也许我的表达方式不对，准确地应该是
time complexity O(bxd)
space complexity O(b)
where b is the breadth of the tree, and d is the depth of the tree.
但是BFS一般都是写时间O(V + E) and 空间O (V)。实际上我对这个空间O (V)也不是太
明白，因为显然queue不用把所有节点都装进去。我个人以为这是考虑最坏情况。
因为这个题的数据结构不是图，是二叉树，不用管V，我想了几秒钟就还是写了O(n), O
(n).
反正现在已经绕糊涂了。 |
|
i*********e
发帖数: 21 | 30 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。
想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
我的感觉是没有的。当然，我可能是错的。
教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
，至少也知道你想到了一个方法。最忌讳闷头苦想，而面试官根本不知道你在想啥。
==========
去年还面了FB的onsite，挂在把二叉树转为双向链表上，吐血。当时昏了头拼了命要写
个functional style的，结果把自己绕进... 阅读全帖 |
|
k******n
发帖数: 451 | 31 面试2天后被据了。
面试题目包括： 1.ood 餐馆点菜和厨师做菜，要有menu，每道菜cook时间不一样，但
需要每桌上菜的时间一样，还要求有order给厨师的display。感觉答的很差。
2. 先是问了一些architech的题，表示不会后。换成从左到右，从下到上 打印二叉树。
3. manager进来问behaivor 问题
4. 烙印问leetcode原题，Longest Substring Without Repeating Characters， 分析
了一下空间复杂度。。
5. 用树实现字典查询， |
|
A*******e
发帖数: 2419 | 32 什么是“用iterator方法遍历树”？是给二叉树设计一个iterator吧？ |
|
M*******n
发帖数: 10087 | 33 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
f********t
发帖数: 6999 | 34 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
a******g
发帖数: 13519 | 35 什么题？给个链接。话说，我的二叉树题最弱了，这个周末我要好好恶补一下树图方面
的题目。 |
|
h*******o
发帖数: 8 | 36 G
电面，Leetcode 318 变形，返回所有满足条件的组合
Onsite1, 超nice国人大哥，recruiter一走就开始中文沟通，说就问一题就好. 输入一
个m * n grid 和若干个king坐标，规定king 周围一圈不能走，返回有没有路径从（0
，0）走到（m-1, n-1）
Onsite2, 白人小哥，先问给个有序数组找所有majority element，majority element
定义是出现次数超过1/4. 告知见过了并且给出解法. 小哥说好那我们换个题，纠结一
阵说咱们写个贪吃蛇吧。连说带写肺都疼了。
Onsite3 设计，另一个超nice国人大哥，超帮忙，来一个Leetcode LRU. 话说用
Objective-C写还挺蛋疼的.
Onsite4 另一轮设计，白人小哥，让设计iOS UndoManager 我说我没用过他说没事我给
你解释.
Onsite5 迟到印度小哥，第一题游程编码，输入编码后的字符串，写一个 iterator，
实现hasnext 返回还有没有数字，next返回编码前的数字。输入有可能含有非法的编码
。 比如 输入2103 那... 阅读全帖 |
|
发帖数: 1 | 37 统一标准就很公平。
我记得有一次面试完出门看到面试官。
考的数组构建满二叉树。
然后面试官说, It's a set.
It's a set?
I could give you a easier one.然后就紧张的走了。
那我就多练练树的题。 |
|
a**********0
发帖数: 422 | 38 interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是如
果用其他方式遍历 同样的复杂度啊 做serialization难道不要把所有节点都遍历一边
任何顺序都要遍历一边 任何方式复杂度相同啊 这点都理解不了 而且我解释了好几遍
还理解不了 didi labs雇的人白痴啊
从来没有这么烂的面试经历 真的很烂 didi lab... 阅读全帖 |
|
d*********2
发帖数: 48111 | 39 如果你碰见一S13问你做什么的你， 你说做二叉树排列的，
人问“什么树”
你该咋继续？ 能扯的出来吗？ |
|
q*********u
发帖数: 280 | 40 【 以下文字转载自 JobHunting 讨论区 】
发信人: yinyueyouge (隐约有歌), 信区: JobHunting
标 题: Re: java enclosure是什么-今天被hm问倒了
发信站: BBS 未名空间站 (Fri Oct 22 09:27:57 2010, 美东)
感觉对方是在问 Closure。
这个是 Java 对 Lambda 表达式的实现。Java 7 已经确定在语法上支持这个。
Java 6或者以前的版本只能靠 interface + anonymous class 来实现。
若是做过 functional programming（比如haskell），应该对 Lamdba 表达
式比较熟悉。
从C++的角度来看，就是 function pointer，但是它是 Strongly Typed。
举例代码来说明。假设要对二叉树遍历，代码很好写，比如：
void inOrder(Tree tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.p... 阅读全帖 |
|
M**u
发帖数: 10158 | 41 其实tree的类比较难写，估计红黑树，二叉树倒是比较多
of
the selfish and the tyranny of evil men. Blessed is he who in the name of
charity and goodwill shepherds the weak through the valley of darkness, for
he is truly his brother’s keepe: |
|
r********3
发帖数: 2998 | 42 STL的Map是红黑树是实现的，本质上就是二叉树。
我个人觉得HashMap还是更好一些。
另外，HashTable是线程安全的，STL的数据结构没有。 |
|
h**********c
发帖数: 4120 | 43 惯用译法，中文没有取音译，叫迈可罗
linked list 可以叫 林可历
二叉树叫 百耐历树 |
|
g*****a
发帖数: 340 | 44 就是说一个给定的二叉树，你用什么方法找到它的最大层数
我回答的是先随便找一条路线到底，然后向上一层，看另一条分支，到底，再向上一层
。。。递归法遍历一遍
树？ |
|
j**l
发帖数: 2911 | 45 Cong~, 俺去年7月第一轮的电面的第二题就问了serialize binary tree, 当时准备不
充分，挂了。我告诉他可以用Preorder + Inorder, 迅速反问我如何编写代码，我只好
说我知道这个结论可行，但是想不起来具体怎么操作了。然后给了一个只适合存储完全
二叉树的一维数组方法(参考堆的一维数组表示法), 结果人家又听不大懂这个方法，又
问复杂度，我鬼使神差的说是O(2^h), h是平均高度，其实应该直接说O(n),人家又以为
我说成了指数复杂度...
于是第二天就是客气的拒信，显然认为我不行。 |
|
K******g
发帖数: 1870 | 46 昨天下午FB的第一轮phone interview，整个过程50分钟，前面10分钟，问了我一些问
题，比如：我的research主要内容，为什么本科是EE，phd是CE，你既然喜欢你的
research为什么要来申请software engineer等等之类的。然后两道编程题，第一道二
叉树分层打印，他告诉我20分钟完成就好了，我只用了15分钟就完全写好，我敢保证绝
对正确。随后，他问算法的复杂度是多少，我说是O(N）。接着马上就是第二题，题目
很新，但是可以马上转化为一个在有大量重复整数的有序数组，找到第一个出现的某个
整数。我也用了不到15分钟做出来了。但是出了一个小问题，他说我有一个判断条件是
多余的，那个人问了我，我开始没有听明白，饶了一阵。但是最后他说，这个不影响你
程序的正确性。最后，我用5分钟时间问了他两个问题。
我感觉整个过程非常顺利，就是波澜不惊的那种。以为肯定可以进入第二轮，没有想到
收到一个据信。真是郁闷之极！
面试我的人是个美国人，英语讲的很清晰。但是比较冷淡。
我现在真是不明白，题目做的很顺利，为什么会被拒呢？问题出在那个判断条件上还是
出在我其他回答的问题上 |
|
j**l
发帖数: 2911 | 47 第二次电面过程中，被俄国人用那道必须用DP做的扔鸡蛋题的变体拷问的狼狈不堪，第
三次电面换了个nice的面试官，就问了两道常见的题目：
1) 经典反复考的老题，一维数组找到两个数之和等于某个定值
2) 设计a general deck of cards
前后快两个月了，希望不要再有第四次电面了。一年前，第一次电面就给那道序列化二
叉树的非热门题给灭了。 |
|
D********g
发帖数: 650 | 48 面试官里估计没有上MIT的。从版上获益良多，所以把题目贴出来回馈版面。
1.写程序判断一棵二叉树是不是对称的。
2.写程序求一个词到另一个词的最短变换路径。（二词长度相等）
3.Design auction ads bid的data holder class
4.Design Amazon 主页服务器的auto recovery，load balancing，应该minimize的指
标，针对指标估计标准值；对含有user ID信息的request如何load balancing。
5.提出一个对Amazon有用的feature，design。
6.假如你是一个start up公司的tech management最高层，公司的网站最近有些慢，如
何分析解决。（假设面试官是CEO)
7.写程序分层打印一个矩阵，如下例：
123
456
789
打印输出的顺序是：123698745
8.Machine learning的一些概念，bias, variance, boosting,SVM&DecisionTree&
NeuralNetwork比较
9.design 算法，抽取不同produc |
|
i*****e
发帖数: 5233 | 49 恭喜
7那个题amazon真是喜欢问啊
面试官里估计没有上MIT的。从版上获益良多，所以把题目贴出来回馈版面。
1.写程序判断一棵二叉树是不是对称的。
2.写程序求一个词到另一个词的最短变换路径。（二词长度相等）
3.Design auction ads bid的data holder class
4.Design Amazon 主页服务器的auto recovery，load balancing，应该minimize的指
标，针对指标估计标准值；对含有user ID信息的request如何load balancing。
5.提出一个对Amazon有用的feature，design。
6.假如你是一个start up公司的tech management最高层，公司的网站最近有些慢，如
何分析解决。（假设面试官是CEO)
7.写程序分层打印一个矩阵，如下例：
123
456
789
打印输出的顺序是：123698745
8.Machine learning的一些概念，bias, variance, boosting,SVM&DecisionTree&
NeuralNetwork比较 |
|
