B********t
发帖数: 147 | 1 可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度 这样就能保
证uniform了 |
|
|
|
f****e
发帖数: 34 | 4 来自主题: JobHunting版 - G/F面经 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见
过这个题目。
3. 9月底的时候google安排10月11号onsite... 阅读全帖 |
|
f*****e
发帖数: 2992 | 5 来自主题: JobHunting版 - G/F面经 找最底层最右边叶子结点？从根节点先右转再左转，然后从根节点先左转再右转找转捩
点，i.e.左拐or右拐点。每一步耗时2*h，然后recurse on next level。
所以sum(2*i)=O(h^2) |
|
c*****r
发帖数: 214 | 6 来自主题: JobHunting版 - G/F面经 cong!
现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了
第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random... 阅读全帖 |
|
c********t
发帖数: 5706 | 7 我觉得可能是dfs遍历过程，父节点向子节点传递range,所有结点都在range里就是bst |
|
K*********n
发帖数: 2852 | 8 是不是一棵树，每一个结点有三个孩子，一共7层，不考虑0和1的情况。然后dfs，看能
不能找到？好像也不是dfs啊，就是沿一条路找到底就行了吧。 |
|
c********t
发帖数: 5706 | 9 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
|
c********t
发帖数: 5706 | 10 我的笨办法,好像也没考虑负数。dfs求的是从结点到叶子的最大路径。
int dfs(BinNode root) {
if (root == null)
return 0;
if (root.left == null)
return root.value + dfs(root.right);
if (root.right == null)
return root.value + dfs(root.left);
return root.value + Math.max(dfs(root.left), dfs(root.right));
}
int maxpath(BinNode root) {
if (root == null)
return 0;
int p1 = dfs(root.left);
int p2 = dfs(root.right);
return Math.max(p1 + p2,
... 阅读全帖 |
|
|
f*******4
发帖数: 64 | 12 新增的结点可与所有孤边分别组成三角形，因此
F(n+1)=C(n,2)-3*F(n)+F(n)
求拍~ |
|
w****x
发帖数: 2483 | 13 第一题不需要build interval tree那么麻烦吧， 把所有结点部分启始还是结束混在一
起排序， 然后扫描一遍， n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true |
|
i******e
发帖数: 273 | 14 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
|
i******e
发帖数: 273 | 15 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
|
i******e
发帖数: 273 | 16 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
|
i******e
发帖数: 273 | 17 20
/ \
-3 -5
/ \
3 8
/ \ \
-2 -1 10
/ /
6 -7
这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
按照你的程序
在根节点 20： maxSum = max(max(helper(-3, leftG), helpfer(-5， rightG)， 20
+ leftG + rightG);
因为leftG包含了以结点3为子树根节点的一条路径（6 -> -1 -> 3 -> -3 -> 8 -> 10
）. 这条路径不能和根节点20一起构成一条新的路径. 所以得出的解是最大和（20 +
23 = 43）， 但是却不是一条有效路径。
请大家帮忙看一下是不是我哪算的有问题？ 谢谢。 |
|
|
l*****a
发帖数: 14598 | 19 不是有一个用dummy结点，解决那个链接同层sibling的题目吗
是不是可以借鉴? 空间constant instead of a Queue |
|
l*****a
发帖数: 14598 | 20 你说的比他问的难多了
他那个不需要care结点的值 |
|
l*****a
发帖数: 14598 | 21 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归 |
|
l*****a
发帖数: 14598 | 22 你说的比他问的难多了
他那个不需要care结点的值 |
|
l*****a
发帖数: 14598 | 23 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归 |
|
s****t
发帖数: 467 | 24 但是parent不是一个而是两个，这样就是graph不是tree了啊？还是可以把夫妻两个算
作一个结点？但是这样建树又太麻烦了。
我记得当时的讨论还包括的gay marriage的情况，可惜具体是什么不记得了。。 |
|
l*****a
发帖数: 14598 | 25 我的体会是这种题最好定义一个结构
class Info {
int depth;
boolean balanced;
}
来记录当前子树信息，因为这种题都需要用递归从root一直到leaves.
而且求depth要递归，判断balanced还要递归，最好一次递归就把所需要的值都存下来
类似的还有那道求树中两结点间最大path那题
这是我的code,见笑了
public boolean isBalanced(TreeNode root) {
return depth(root).balanced;
}
public Info depth(TreeNode root) {
if(root==null) return new Info(true,0);
Info leftInfo=depth(root.left);
Info rightInfo=depth(root.right);
boolean bo=(Math.abs(leftInfo.depth-rightInfo.depth)<=1... 阅读全帖 |
|
d*******y
发帖数: 27 | 26 如果是path的话，我觉得应该指的是有方向的吧，就是从祖先节点到其后继结点。 |
|
l*****a
发帖数: 14598 | 27 来自主题: JobHunting版 - 看不懂这题 linked list有一个指针data member,可能指向这个连表中任意结点 |
|
e****e
发帖数: 418 | 28 问题4.2在“十道海量数据处理”里的解答似乎有问题。
《《《《
方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个
小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解
得到的小文件的大小都不超过1M。
对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_
map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个
词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行
归并（类似与归并排序）的过程了。
>>>>>>>>
对每个小文件取出出现频率最大的100个词, 也许某个文件里包含出现频率第101大的词
,如果这个词和其他文件的同一个词合并后,频率很高,应出现在最终结果里.但是因为用
了上面的方法,而没有在最终结果里. i.e.
2个文件,找出频率最大的两个词.
file A: file B:
a 10 d 10
b... 阅读全帖 |
|
l*****a
发帖数: 14598 | 29 取了一个之后调整吗？
同层结点间没有顺序吧.怎么办？
10
3 7
1 2 5 6 |
|
s****u
发帖数: 7 | 30 1.判断回文
2.子数组和最大值
3.括号匹配，用栈和不用栈
4.求多叉树的兄弟结点和表兄弟节点
5.信用卡号校验问题，需考虑很多边界条件，要求在主循环里判断并处理特殊情况
6.线段重合问题，判断一段线段是否与之前的N条重合，重合次数 |
|
j******2
发帖数: 362 | 31 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。 |
|
f***s
发帖数: 112 | 32 的确听说许多客户要求知道自己的数据都在什么地方跑过，而回答是在某几个结点上，
可是不知在哪里。
万一一个节点机器被拿下，理论上可以得到所有全网的数据。从另一个方面，对于外部
，云平台的运行就是一个迷，需要找到可以攻击的逻辑规律。 |
|
p*****2
发帖数: 21240 | 33 前几天总结了multi threading, OO design 和 system design, 现在有点闲了。请问
下一步应该总结点啥了？ |
|
s********0
发帖数: 4 | 34 R&D两个小兵，问了些简历，空类里有什么，类的大小，两道编程题，一道是字符串去
逗号，一道是把树同一层的结点连起来。
感觉面得不错，然后就没有然后了，hr来了就送我走了，没见到hm
自我感觉题练的不错了，但就是不能拿到intern。之前的amazon，BOA，Cisco，
Symantic也全都挂掉了，尽管心理素质很好，还是很气馁。恳求板上的同志们大神们如
果能提供一些intern的refer，出手助一下，将不胜感激。 |
|
s**s
发帖数: 70 | 35 来自主题: 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分钟左右想，感觉时间挺紧的。 |
|
Q****s
发帖数: 1301 | 36 而且这题是考idea, 想法到了, code不值钱.
不像有的题, 想法人人会, code技巧要求太高, 比如颠倒链表中的几个结点等等, 你会
也不一定写对. |
|
z****e
发帖数: 54598 | 37 root是xml的概念
就是根结点
root就是这个tag
XML Documents Must Have a Root Element
XML documents must contain one element that is the parent of all other
elements. This element is called the root element.
http://www.w3schools.com/xml/xml_syntax.asp |
|
e*******8
发帖数: 94 | 38 我的想法和你其实差不多。这个题关键就是要算每个connected component的大小：可
以用dfs算，也可以用union find找。我没用dfs，是因为union find的时间复杂度基本
上和dfs差不多，用union find＋hash table比较节省空间（因为id的大小范围虽然是
０-１０＾５，但是输入有可能实际上没那么大）。union find的算法基本上就是找
CLRS的伪代码一行一行翻译成C＋＋代码的-_-bbb，唯一的改动是CLRS里面把一个tree
附到另个tree上的时候用的是rank（一个tree height的估计），我用的是tree实际的
结点数目（算法在这里http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/16-unionfind.pdf） |
|
z****e
发帖数: 54598 | 39 如果第一个bottom结点的结果就是true的话，dfs会快 |
|
|
n*****f
发帖数: 17 | 41 把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。 |
|
n*****f
发帖数: 17 | 42 把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。 |
|
r*********r
发帖数: 53 | 43 其实删除倒不是问题。 用 ListIterator就可以。http://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html
ListIterator 可以向前也可以向后，可增加可以删除。
但是问题是每次一改变linkedlist后，原来的ListIterator就不能用了，如果用的话会
抛出concurrency的异常，所以我们没办法用把它放到hashmap里，因为一旦linkedlist
里增加或者删除了某个结点，在这次增加或者删除之前存在hashmap里的其它iterator
就不能用了。
我还没有找到其它更好的方法。 java里的iterator不如c++里的iterator强大。
如果有大牛知道怎么作的话，求教。 |
|
m**********0
发帖数: 18 | 44 最后那个其实我开始也没有很懂……相同结点首先是里面value一样，同时在第一个题
当中，它的父节点们也必须是一样的才行，比方说
树A：
A
B C
D F E G T
L
树B：
A
M C
D F G T E
L
同样的节点有A,C,G,E，尽管D俩树都有，但是第二个的D的父节点跟第一个D的父节点不
一样，所以不是。L尽管俩树都有，且第一个父节点一样，但是再上面父节点不同，所
以也不是。
第二问的话，相同的可以有不同的set选择，可以选择 {A,C,,G,T} 或者{A,C,E},让找
到最多成员的set的选择，使得成员中的相对顺序相同 |
|
n*****f
发帖数: 17 | 45 第二题有n+log(n)次比较的方法，两两PK，胜者再两两PK，直到决出冠军，整个过程就
构成了一棵树，把冠军对应的那些点标出来，第二名只可能出现在这些点的兄弟结点上
。 |
|
g*****g
发帖数: 34805 | 46 常见数据库做ID的方法就两种。一种是依靠RDBMS，一次取一段，比如每个结点到数据
库一次取10000个，数据库用transaction保证不冲突。
另一种就是type 1 UUID，就是mac+timestamp+synchronized counter on host。因为
cluster通常在在同一个子网上，mac肯定不会冲突。 |
|
g*****g
发帖数: 212 | 47 需要澄清，1 char数组中部分字母还是要求全部字母组成单词， 2 数组中有重复字母吗
1.1， 1.2同一个意思吧，似乎只能试该数组的permutation，挨个检查isword了。
假设全部字母组成单词，允许重复：
1.3 字典：trie，字典中所有单词，trie 路径是按 a-z顺序排序的变形词，叶子结点
保存原始单词
peek => e->e->k->p (peek)
如此 输入char数组，排序是O(n)， match O(n) |
|
A*********c
发帖数: 430 | 48 That's the right question to ask.
我觉得coderfe解法的主要问题是没有解决这个问题。
Tree不balance，你相对好说，用balanced Implementation。
关键是这个kth in BST naive的算法你要做inorder, 而且是每次query Kth都要做一次
traversal。
这个题目的实际意义一定是处理无限数据流的频繁查询的问题, 所以多次query
每次都traversal是不行的。
除非你augment你的BTS data structure, 每个节点加入左右子树子结点个数的信息，第
一你得说明白怎么augment，第二查询复杂度还是log(n)。
所以我second狂且的solution。每次adjust heap size是O(1), 插入O(log(n)), query
O(1）。
而且少了上面所说的所有的overhead。 |
|
g*****g
发帖数: 212 | 49 定义双重属性的结点
class Node
{
int v;
List subs;
} |
|
s*****p
发帖数: 108 | 50 看了本版很多面经，获益良多，所以我也把我近期面试的过程写下来，并且给出一些我
对系统设计题的想法，希望对正在找工作的人会有一点帮助。我的背景非cs非ee，不过
和编程相关，而且平时自己也经常写写程序。cc150和leetcode各刷了两遍。这次只申
请了F和G，最后F悲剧，G offer。
由于我有一些iOS的经验，所以申请F时申请的是iOS developer的职位。
F电面只有一轮：
先问了一些近期做的项目，然后编程是实现UIControl里的几个method，比如addTarget
什么的。不难。电面过后一周就安排了onsite。
F onsite 有4轮，全是白人：
1. 问了一些behavior的问题，比如简历里写的项目什么的，然后还问了最喜欢
facebook app的哪个功能，有什么可以改进的地方，怎么改进。还有为什么想去
Facebook。这些问题我基本都已经准备过，所以应该都答得不错。最后给了一个简单的
coding题，就是逆序打印链表里的值。我说了三个方法，一个是递归，一个是用stack
（和递归也差不多），还有就是先反转链表，按顺序打印，然后再反转一次恢复原状。
... 阅读全帖 |
|
