z******u
发帖数: 30 | 1 Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
且被他家恶心到了， 就回复说不想再面了。
希望对要面他家的人有帮助。
1 面，印度女面的。
1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
2。 找出一个tree中所有pair of nodes with path of d。
其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
算出tree。
2面， 貌似美国人。
1。 把一个integer convert 一下， 比如 input 是123， 生成321。 延伸一下如果是
负数怎么办。
2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
后来又用BFS， level by level visit， 再improve 用两个queue BFS。
这轮面的挺好， 面完recruiter 马上就给了onsite， 当我发信给时间的时候， 又反
悔，说要第三面。
三面，貌似美国人。
全是design题。一个用户在brower里打他家会发生什么， 大概是想考应该如何
organize它的用户， 给了陷阱问是不是用database， 我一下子跳了进去， 说是。后
来想应该用big table 和DHT。
给你一堆tweet， 如何就算出每个word的count. 其中我当时认为word 可以用
whitespace分开。 但是应该有其他的分界符， 比如#什么的，没想到这里。
其他就是你如何improve twitter， 如何计算trend(词的频率是不够的）
， 等等。
三面面挂了。 |
G*********t
发帖数: 71 | |
t********3
发帖数: 567 | |
w****f
发帖数: 684 | 4 一个半月前，recruiter 说next week要安排面试。。。next week。。。next week
。。。
前天收到email。。。next week |
p*****2
发帖数: 21240 | 5 2。 找出一个tree中所有pair of nodes with path of d。
其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
算出tree。
这题没看懂呀。具体点啥意思呀？ |
p*****2
发帖数: 21240 | 6 2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
后来又用BFS， level by level visit， 再improve 用两个queue BFS。
两个queue什么地方有优化呢？ |
r***y
发帖数: 4379 | 7 三面这个没有看懂要问啥子...
"一个用户在brower里打他家会发生什么， 大概是想考应该如何organize它的用户，
给了陷阱问是不是用database"
麻烦lz有空解释一下
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
l*****a
发帖数: 14598 | 8 先存下来
不知什么时间看
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
y**********u
发帖数: 6366 | 9 感觉一题都不会啊。。。
现在的题目都太难了
程序
果是
method，
【在 l*****a 的大作中提到】
: 先存下来
: 不知什么时间看
|
l*****a
发帖数: 14598 | 10 那帮你转h1b的公司都问你什么了？
【在 y**********u 的大作中提到】
: 感觉一题都不会啊。。。
: 现在的题目都太难了
:
: 程序
: 果是
: method，
|
|
|
t**********h
发帖数: 2273 | |
y**********u
发帖数: 6366 | 12 问了啊，都不会。。。
【在 l*****a 的大作中提到】
: 那帮你转h1b的公司都问你什么了？
|
l*****a
发帖数: 14598 | 13 同学题目说清楚点吧
我基本都看不懂在问什么
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
z******u
发帖数: 30 | 14 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
children， 并且返回root， 这样才构建了tree。
【在 p*****2 的大作中提到】
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 这题没看懂呀。具体点啥意思呀？
|
z******u
发帖数: 30 | 15 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
以用两个queue 来做。
【在 p*****2 的大作中提到】
: 2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
: 后来又用BFS， level by level visit， 再improve 用两个queue BFS。
: 两个queue什么地方有优化呢？
|
z******u
发帖数: 30 | 16 原题就是问一个用户在browser里打他家地址会发生什么， 我就答了一堆dns，tcp的东
西。 但是他想问的是browser的request 怎么handle， 那么多用户， 如何分配在不同
的机器上。 关于这种如何分布大规模的用户， 是比较热的考点， 似乎最近DHT 考得
很多， 上次版上有人贴了个paper， 觉得很有用。 拾人牙慧，贴在这里希望对大家有
帮助： Dynamo: Amazon’s Highly Available Key-value Store
【在 r***y 的大作中提到】
: 三面这个没有看懂要问啥子...
: "一个用户在brower里打他家会发生什么， 大概是想考应该如何organize它的用户，
: 给了陷阱问是不是用database"
: 麻烦lz有空解释一下
|
p*****2
发帖数: 21240 | 17
如果要是只找pair的话，建个图就可以出来。
如果要是建树的话直接就可以建。
如果不限制最后的数据结构，两个可以merge起来。
【在 z******u 的大作中提到】
: 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
: 但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
: 父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
: children， 并且返回root， 这样才构建了tree。
|
z****h
发帖数: 164 | 18 lz说的最短路径只是想知道root到leaf的层数对吧？
还是必须打印所有经过的节点？
【在 z******u 的大作中提到】
: 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
: 以用两个queue 来做。
|
p*****2
发帖数: 21240 | 19
我怎么觉得不用呀？depth随便用个变量不就解决了吗？
【在 z******u 的大作中提到】
: 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
: 以用两个queue 来做。
|
z******u
发帖数: 30 | 20 因为给定的node的structure里只有父亲的filed， 所以只能由孩子到父亲，没法子由
父亲到孩子。 所以还是要有一个新的structure， 再建一个新的tree的。
【在 p*****2 的大作中提到】
:
: 我怎么觉得不用呀？depth随便用个变量不就解决了吗？
|
|
|
z******u
发帖数: 30 | 21 只要知道层数就行了。
【在 z****h 的大作中提到】
: lz说的最短路径只是想知道root到leaf的层数对吧？
: 还是必须打印所有经过的节点？
|
z******u
发帖数: 30 | 22 其实后来我也觉得用不着两个ｑｕｅｕｅ， 只用两个variable 就行了， 一个记录
depth, 一个记录current level 的最后一个ｎｏｄｅ， 每次到最后一个ｎｏｄｅ的
时候， ｄｅｐｔｈ就加一。
【在 p*****2 的大作中提到】
:
: 我怎么觉得不用呀？depth随便用个变量不就解决了吗？
|
c*****r
发帖数: 214 | 23 不一定要重建树吧
有parent node的话，计算两个node之间的距离很容易，从两个node出发一直往上走到N
ULl为止，然后找lowest common ancestor就行了
野蛮算法的复杂度应该是O（n^2 d）
改进一下，应该能达到O(n^2),应该就是最优复杂度
【在 z******u 的大作中提到】
: 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
: 但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
: 父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
: children， 并且返回root， 这样才构建了tree。
|
p*****2
发帖数: 21240 | 24
我觉得最简单的是数据结构可以指向parent。这样两个算法就可以merge起来了。
如果不能有parent指针还需要另外的数据结构。
【在 z******u 的大作中提到】
: 因为给定的node的structure里只有父亲的filed， 所以只能由孩子到父亲，没法子由
: 父亲到孩子。 所以还是要有一个新的structure， 再建一个新的tree的。
|
l*********8
发帖数: 4642 | 25 O(n^2)只计算了两个点之间的距离。 总共有n*(n-1)/2 个pair, 每个pair用O(n^2)时
间。 那么总共算法就是O(n^4)了。
到N
【在 c*****r 的大作中提到】
: 不一定要重建树吧
: 有parent node的话，计算两个node之间的距离很容易，从两个node出发一直往上走到N
: ULl为止，然后找lowest common ancestor就行了
: 野蛮算法的复杂度应该是O（n^2 d）
: 改进一下，应该能达到O(n^2),应该就是最优复杂度
|
l*********8
发帖数: 4642 | 26 1面第二道，我的想法是：
首先对每个节点，找到它的所有祖先，并和距离一起存到hash table中, 距离超过k就
不用存。 对一个节点平均是O(min(k,logN)) time. 所有节点O(N * min(k,logN))
time
然后对于每个pair of nodes, 利用第一步生成的hash tables来检查最短距离是否是k
。 每个pair平均 O(min(k,logN))时间。 N*(N-1)/2个pair共 O(N^2 * min(k,logN))
时间 |
j******f
发帖数: 825 | 27 三面是map/reduce 典型问题吧？楼主看来拘于细节啦。 |
z******u
发帖数: 30 | 28 面试官希望时间复杂度是O(n), 然后提示可以用任何structure.
k
))
【在 l*********8 的大作中提到】
: 1面第二道，我的想法是：
: 首先对每个节点，找到它的所有祖先，并和距离一起存到hash table中, 距离超过k就
: 不用存。 对一个节点平均是O(min(k,logN)) time. 所有节点O(N * min(k,logN))
: time
: 然后对于每个pair of nodes, 利用第一步生成的hash tables来检查最短距离是否是k
: 。 每个pair平均 O(min(k,logN))时间。 N*(N-1)/2个pair共 O(N^2 * min(k,logN))
: 时间
|
p******9
发帖数: 47 | 29 我的思路：
（1）重建树: O(n)
（2）然后后序遍历这棵树，对于某一步的根结点，找出两个点之前路径和为某一指定
值只有三种情况，或者两个结点同时在左子树，或者两个结点同时在右子树，或者一个
在左一个右。前两种情况可以递归到更小的情况，所以关键是求出两个结点一个在左一
个在右的情况。由主定理可知，这一步的时间复杂度必要低于O(n)，否则时间复杂度将
至少为O(n)。
我们知道一棵二叉树的高度是o(log(n))，因些在遍历的时候，需要维护一个不同高度
对应的结点的结构，每一步迭代更新这个结构花费log(n)，生成路径花费log(n) * log
(n)
总的时间是O(n) |
l*********8
发帖数: 4642 | 30 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
时间求出？
【在 z******u 的大作中提到】
: 面试官希望时间复杂度是O(n), 然后提示可以用任何structure.
:
: k
: ))
|
|
|
p*****2
发帖数: 21240 | 31
n)
支持。
【在 l*********8 的大作中提到】
: 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
: 时间求出？
|
r****c
发帖数: 2585 | 32 binary tree or any tree? I think lz miss lot of info
n)
【在 l*********8 的大作中提到】
: 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
: 时间求出？
|
l*********8
发帖数: 4642 | 33 any tree, I think.
【在 r****c 的大作中提到】
: binary tree or any tree? I think lz miss lot of info
:
: n)
|
p******9
发帖数: 47 | 34 如果只是求pair个数的话，对于比较平衡的二叉树，我觉得O(N)应该是可以的 |
p******9
发帖数: 47 | 35 如果只是求pair个数的话，对于比较平衡的二叉树O(N)应该是可以的 |
z******u
发帖数: 30 | 36 树是任意的树。
我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
【在 p******9 的大作中提到】
: 如果只是求pair个数的话，对于比较平衡的二叉树O(N)应该是可以的
|
c****x
发帖数: 15 | 37 这题挺有趣，在tree上用sliding window就能O(n)
window的顶部对应root
底部对应所有把到root所有刚好>=d的node
不断下移就行。
要写成O(n),coding难度还是挺大的，要维护一颗hidden的树。
【在 z******u 的大作中提到】
: 树是任意的树。
: 我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
: node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
: ， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
: ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
: 的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
: 对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
: 是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
|
m****i
发帖数: 650 | |
c***e
发帖数: 542 | 39 Co-ask?
【在 p*****2 的大作中提到】
:
: n)
: 支持。
|
g****y
发帖数: 240 | 40 你sliding windows 不行。因为有可能两个nodes通过他们ancestor相连。
【在 c****x 的大作中提到】
: 这题挺有趣，在tree上用sliding window就能O(n)
: window的顶部对应root
: 底部对应所有把到root所有刚好>=d的node
: 不断下移就行。
: 要写成O(n),coding难度还是挺大的，要维护一颗hidden的树。
|
|
|
g*****e
发帖数: 282 | 41 twitter店面才45min，客套5min。这种难度的40分钟bug free两题太难了。是不是非最
优的他们其实也能接受了。。。
【在 z******u 的大作中提到】
: 树是任意的树。
: 我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
: node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
: ， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
: ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
: 的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
: 对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
: 是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
|
d**********x
发帖数: 4083 | 42 是的
但是onsite太难。。
【在 g*****e 的大作中提到】
: twitter店面才45min，客套5min。这种难度的40分钟bug free两题太难了。是不是非最
: 优的他们其实也能接受了。。。
|
j********x
发帖数: 2330 | 43 dynamo是在cap定理基础上取availability和partition tolerance而牺牲consistence
的distributed key value storage，这个跟问题关系不大，当然他本身是有负载均衡
的技术需要的。
web的负载均衡，我理解这个问题的考点，是个挺复杂的系统问题，可以：
dns均衡 不同地域的ip将域名解析到不同的data center ip
cdn均衡 依靠cdn分发静态网页资源
http均衡 http request在data center内部分发到不同的worker node
http proxy，比如nginx做个异步的proxy专门解析http request，分发到后台的apache
server处理，跟上面的区别是这个是在应用层
明白两个概念：vertical scalability 应用性能随着单个机器性能提高得以提高，
horizontal scalability，应用性能随着机器数目的增加得以提高。后者目前更受关注
，原因显而易见。从这个角度理解这个问题我觉得更容易把握本质，说到底负载均衡就
是希望能够非常简易地通过添加更多的机器改善应用性能。
【在 z******u 的大作中提到】
: 原题就是问一个用户在browser里打他家地址会发生什么， 我就答了一堆dns，tcp的东
: 西。 但是他想问的是browser的request 怎么handle， 那么多用户， 如何分配在不同
: 的机器上。 关于这种如何分布大规模的用户， 是比较热的考点， 似乎最近DHT 考得
: 很多， 上次版上有人贴了个paper， 觉得很有用。 拾人牙慧，贴在这里希望对大家有
: 帮助： Dynamo: Amazon’s Highly Available Key-value Store
|
z******u
发帖数: 30 | 44 Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
且被他家恶心到了， 就回复说不想再面了。
希望对要面他家的人有帮助。
1 面，印度女面的。
1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
2。 找出一个tree中所有pair of nodes with path of d。
其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
算出tree。
2面， 貌似美国人。
1。 把一个integer convert 一下， 比如 input 是123， 生成321。 延伸一下如果是
负数怎么办。
2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
后来又用BFS， level by level visit， 再improve 用两个queue BFS。
这轮面的挺好， 面完recruiter 马上就给了onsite， 当我发信给时间的时候， 又反
悔，说要第三面。
三面，貌似美国人。
全是design题。一个用户在brower里打他家会发生什么， 大概是想考应该如何
organize它的用户， 给了陷阱问是不是用database， 我一下子跳了进去， 说是。后
来想应该用big table 和DHT。
给你一堆tweet， 如何就算出每个word的count. 其中我当时认为word 可以用
whitespace分开。 但是应该有其他的分界符， 比如#什么的，没想到这里。
其他就是你如何improve twitter， 如何计算trend(词的频率是不够的）
， 等等。
三面面挂了。 |
G*********t
发帖数: 71 | |
t********3
发帖数: 567 | |
w****f
发帖数: 684 | 47 一个半月前，recruiter 说next week要安排面试。。。next week。。。next week
。。。
前天收到email。。。next week |
p*****2
发帖数: 21240 | 48 2。 找出一个tree中所有pair of nodes with path of d。
其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
算出tree。
这题没看懂呀。具体点啥意思呀？ |
p*****2
发帖数: 21240 | 49 2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
后来又用BFS， level by level visit， 再improve 用两个queue BFS。
两个queue什么地方有优化呢？ |
r***y
发帖数: 4379 | 50 三面这个没有看懂要问啥子...
"一个用户在brower里打他家会发生什么， 大概是想考应该如何organize它的用户，
给了陷阱问是不是用database"
麻烦lz有空解释一下
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
|
|
l*****a
发帖数: 14598 | 51 先存下来
不知什么时间看
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
y**********u
发帖数: 6366 | 52 感觉一题都不会啊。。。
现在的题目都太难了
程序
果是
method，
【在 l*****a 的大作中提到】
: 先存下来
: 不知什么时间看
|
l*****a
发帖数: 14598 | 53 那帮你转h1b的公司都问你什么了？
【在 y**********u 的大作中提到】
: 感觉一题都不会啊。。。
: 现在的题目都太难了
:
: 程序
: 果是
: method，
|
t**********h
发帖数: 2273 | |
y**********u
发帖数: 6366 | 55 问了啊，都不会。。。
【在 l*****a 的大作中提到】
: 那帮你转h1b的公司都问你什么了？
|
l*****a
发帖数: 14598 | 56 同学题目说清楚点吧
我基本都看不懂在问什么
【在 z******u 的大作中提到】
: Update：Recruiter 一直没理我，以为三面面挂了， 结果前两天又给我发信让接着面
: 。 这都一个月了， 估计是放在waiting list里了。 不过已经拿到很想去的offer，
: 且被他家恶心到了， 就回复说不想再面了。
: 希望对要面他家的人有帮助。
: 1 面，印度女面的。
: 1。 找出一个array中的所有两数的和是一个给定的值， 我用hashset 作的。
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 2面， 貌似美国人。
|
z******u
发帖数: 30 | 57 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
children， 并且返回root， 这样才构建了tree。
【在 p*****2 的大作中提到】
: 2。 找出一个tree中所有pair of nodes with path of d。
: 其中tree中的node 给的是个array of nodes， node 只知道自己的父亲。 要先写程序
: 算出tree。
: 这题没看懂呀。具体点啥意思呀？
|
z******u
发帖数: 30 | 58 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
以用两个queue 来做。
【在 p*****2 的大作中提到】
: 2。 给一个tree， 如何计算从root到leaf的最短路径。 我先给出recursive method，
: 后来又用BFS， level by level visit， 再improve 用两个queue BFS。
: 两个queue什么地方有优化呢？
|
z******u
发帖数: 30 | 59 原题就是问一个用户在browser里打他家地址会发生什么， 我就答了一堆dns，tcp的东
西。 但是他想问的是browser的request 怎么handle， 那么多用户， 如何分配在不同
的机器上。 关于这种如何分布大规模的用户， 是比较热的考点， 似乎最近DHT 考得
很多， 上次版上有人贴了个paper， 觉得很有用。 拾人牙慧，贴在这里希望对大家有
帮助： Dynamo: Amazon’s Highly Available Key-value Store
【在 r***y 的大作中提到】
: 三面这个没有看懂要问啥子...
: "一个用户在brower里打他家会发生什么， 大概是想考应该如何organize它的用户，
: 给了陷阱问是不是用database"
: 麻烦lz有空解释一下
|
p*****2
发帖数: 21240 | 60
如果要是只找pair的话，建个图就可以出来。
如果要是建树的话直接就可以建。
如果不限制最后的数据结构，两个可以merge起来。
【在 z******u 的大作中提到】
: 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
: 但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
: 父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
: children， 并且返回root， 这样才构建了tree。
|
|
|
z****h
发帖数: 164 | 61 lz说的最短路径只是想知道root到leaf的层数对吧？
还是必须打印所有经过的节点？
【在 z******u 的大作中提到】
: 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
: 以用两个queue 来做。
|
p*****2
发帖数: 21240 | 62
我怎么觉得不用呀？depth随便用个变量不就解决了吗？
【在 z******u 的大作中提到】
: 因为level by level 需要assume 每个node有个field记录depth， 如果不想的话， 可
: 以用两个queue 来做。
|
z******u
发帖数: 30 | 63 因为给定的node的structure里只有父亲的filed， 所以只能由孩子到父亲，没法子由
父亲到孩子。 所以还是要有一个新的structure， 再建一个新的tree的。
【在 p*****2 的大作中提到】
:
: 我怎么觉得不用呀？depth随便用个变量不就解决了吗？
|
z******u
发帖数: 30 | 64 只要知道层数就行了。
【在 z****h 的大作中提到】
: lz说的最短路径只是想知道root到leaf的层数对吧？
: 还是必须打印所有经过的节点？
|
z******u
发帖数: 30 | 65 其实后来我也觉得用不着两个ｑｕｅｕｅ， 只用两个variable 就行了， 一个记录
depth, 一个记录current level 的最后一个ｎｏｄｅ， 每次到最后一个ｎｏｄｅ的
时候， ｄｅｐｔｈ就加一。
【在 p*****2 的大作中提到】
:
: 我怎么觉得不用呀？depth随便用个变量不就解决了吗？
|
c*****r
发帖数: 214 | 66 不一定要重建树吧
有parent node的话，计算两个node之间的距离很容易，从两个node出发一直往上走到N
ULl为止，然后找lowest common ancestor就行了
野蛮算法的复杂度应该是O（n^2 d）
改进一下，应该能达到O(n^2),应该就是最优复杂度
【在 z******u 的大作中提到】
: 就是要找出一个tree中所有pair的nodes，使得他们距离为d。
: 但是没有给root of tree， 而是一个array of nodes， node 中只有一个field 就是
: 父亲， 要先定义新的数据结构使得有field of children， 然后计算每个node的
: children， 并且返回root， 这样才构建了tree。
|
p*****2
发帖数: 21240 | 67
我觉得最简单的是数据结构可以指向parent。这样两个算法就可以merge起来了。
如果不能有parent指针还需要另外的数据结构。
【在 z******u 的大作中提到】
: 因为给定的node的structure里只有父亲的filed， 所以只能由孩子到父亲，没法子由
: 父亲到孩子。 所以还是要有一个新的structure， 再建一个新的tree的。
|
l*********8
发帖数: 4642 | 68 O(n^2)只计算了两个点之间的距离。 总共有n*(n-1)/2 个pair, 每个pair用O(n^2)时
间。 那么总共算法就是O(n^4)了。
到N
【在 c*****r 的大作中提到】
: 不一定要重建树吧
: 有parent node的话，计算两个node之间的距离很容易，从两个node出发一直往上走到N
: ULl为止，然后找lowest common ancestor就行了
: 野蛮算法的复杂度应该是O（n^2 d）
: 改进一下，应该能达到O(n^2),应该就是最优复杂度
|
l*********8
发帖数: 4642 | 69 1面第二道，我的想法是：
首先对每个节点，找到它的所有祖先，并和距离一起存到hash table中, 距离超过k就
不用存。 对一个节点平均是O(min(k,logN)) time. 所有节点O(N * min(k,logN))
time
然后对于每个pair of nodes, 利用第一步生成的hash tables来检查最短距离是否是k
。 每个pair平均 O(min(k,logN))时间。 N*(N-1)/2个pair共 O(N^2 * min(k,logN))
时间 |
j******f
发帖数: 825 | 70 三面是map/reduce 典型问题吧？楼主看来拘于细节啦。 |
|
|
z******u
发帖数: 30 | 71 面试官希望时间复杂度是O(n), 然后提示可以用任何structure.
k
))
【在 l*********8 的大作中提到】
: 1面第二道，我的想法是：
: 首先对每个节点，找到它的所有祖先，并和距离一起存到hash table中, 距离超过k就
: 不用存。 对一个节点平均是O(min(k,logN)) time. 所有节点O(N * min(k,logN))
: time
: 然后对于每个pair of nodes, 利用第一步生成的hash tables来检查最短距离是否是k
: 。 每个pair平均 O(min(k,logN))时间。 N*(N-1)/2个pair共 O(N^2 * min(k,logN))
: 时间
|
p******9
发帖数: 47 | 72 我的思路：
（1）重建树: O(n)
（2）然后后序遍历这棵树，对于某一步的根结点，找出两个点之前路径和为某一指定
值只有三种情况，或者两个结点同时在左子树，或者两个结点同时在右子树，或者一个
在左一个右。前两种情况可以递归到更小的情况，所以关键是求出两个结点一个在左一
个在右的情况。由主定理可知，这一步的时间复杂度必要低于O(n)，否则时间复杂度将
至少为O(n)。
我们知道一棵二叉树的高度是o(log(n))，因些在遍历的时候，需要维护一个不同高度
对应的结点的结构，每一步迭代更新这个结构花费log(n)，生成路径花费log(n) * log
(n)
总的时间是O(n) |
l*********8
发帖数: 4642 | 73 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
时间求出？
【在 z******u 的大作中提到】
: 面试官希望时间复杂度是O(n), 然后提示可以用任何structure.
:
: k
: ))
|
p*****2
发帖数: 21240 | 74
n)
支持。
【在 l*********8 的大作中提到】
: 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
: 时间求出？
|
r****c
发帖数: 2585 | 75 binary tree or any tree? I think lz miss lot of info
n)
【在 l*********8 的大作中提到】
: 题目要求找到所有的pair, 而符合要求的pair的数目可能是O(n^2)的，怎么可能用O(n)
: 时间求出？
|
l*********8
发帖数: 4642 | 76 any tree, I think.
【在 r****c 的大作中提到】
: binary tree or any tree? I think lz miss lot of info
:
: n)
|
p******9
发帖数: 47 | 77 如果只是求pair个数的话，对于比较平衡的二叉树，我觉得O(N)应该是可以的 |
p******9
发帖数: 47 | 78 如果只是求pair个数的话，对于比较平衡的二叉树O(N)应该是可以的 |
z******u
发帖数: 30 | 79 树是任意的树。
我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
【在 p******9 的大作中提到】
: 如果只是求pair个数的话，对于比较平衡的二叉树O(N)应该是可以的
|
c****x
发帖数: 15 | 80 这题挺有趣，在tree上用sliding window就能O(n)
window的顶部对应root
底部对应所有把到root所有刚好>=d的node
不断下移就行。
要写成O(n),coding难度还是挺大的，要维护一颗hidden的树。
【在 z******u 的大作中提到】
: 树是任意的树。
: 我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
: node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
: ， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
: ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
: 的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
: 对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
: 是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
|
|
|
m****i
发帖数: 650 | |
c***e
发帖数: 542 | 82 Co-ask?
【在 p*****2 的大作中提到】
:
: n)
: 支持。
|
g****y
发帖数: 240 | 83 你sliding windows 不行。因为有可能两个nodes通过他们ancestor相连。
【在 c****x 的大作中提到】
: 这题挺有趣，在tree上用sliding window就能O(n)
: window的顶部对应root
: 底部对应所有把到root所有刚好>=d的node
: 不断下移就行。
: 要写成O(n),coding难度还是挺大的，要维护一颗hidden的树。
|
g*****e
发帖数: 282 | 84 twitter店面才45min，客套5min。这种难度的40分钟bug free两题太难了。是不是非最
优的他们其实也能接受了。。。
【在 z******u 的大作中提到】
: 树是任意的树。
: 我当时是这样想的： 先建树， 然后从root 开始， 对每一个node Ｎ 找以这个
: node为根节点的深度为d 的ｓｕｂｔｒｅｅ， 然后对于一个枝干上深度为ｉ的 节点
: ， 另外一个枝干上深度为ｄ－ｉ的节点组成一个ｐａｉｒ。 这样就能找到所有ｐａ
: ｉｒ的节点， 他们之间的长度为ｄ的路径一定会经过这个ｎｏｄｅ Ｎ， 至于其他
: 的ｐａｉｒ的节点， 他们之间长度为ｄ的路径就一定不会经过这个ｎｏｄｅ Ｎ。
: 对于每个ｎｏｄｅ， 计算深度为ｄ的ｓｕｂｔｒｅｅ时间是ｆ（ｄ）， 那么总时间
: 是Ｏ（ｎ*f(d)）, 也就是Ｏ（ｎ）
|
d**********x
发帖数: 4083 | 85 是的
但是onsite太难。。
【在 g*****e 的大作中提到】
: twitter店面才45min，客套5min。这种难度的40分钟bug free两题太难了。是不是非最
: 优的他们其实也能接受了。。。
|
j********x
发帖数: 2330 | 86 dynamo是在cap定理基础上取availability和partition tolerance而牺牲consistence
的distributed key value storage，这个跟问题关系不大，当然他本身是有负载均衡
的技术需要的。
web的负载均衡，我理解这个问题的考点，是个挺复杂的系统问题，可以：
dns均衡 不同地域的ip将域名解析到不同的data center ip
cdn均衡 依靠cdn分发静态网页资源
http均衡 http request在data center内部分发到不同的worker node
http proxy，比如nginx做个异步的proxy专门解析http request，分发到后台的apache
server处理，跟上面的区别是这个是在应用层
明白两个概念：vertical scalability 应用性能随着单个机器性能提高得以提高，
horizontal scalability，应用性能随着机器数目的增加得以提高。后者目前更受关注
，原因显而易见。从这个角度理解这个问题我觉得更容易把握本质，说到底负载均衡就
是希望能够非常简易地通过添加更多的机器改善应用性能。
【在 z******u 的大作中提到】
: 原题就是问一个用户在browser里打他家地址会发生什么， 我就答了一堆dns，tcp的东
: 西。 但是他想问的是browser的request 怎么handle， 那么多用户， 如何分配在不同
: 的机器上。 关于这种如何分布大规模的用户， 是比较热的考点， 似乎最近DHT 考得
: 很多， 上次版上有人贴了个paper， 觉得很有用。 拾人牙慧，贴在这里希望对大家有
: 帮助： Dynamo: Amazon’s Highly Available Key-value Store
|
l**b
发帖数: 457 | |
c****0
发帖数: 784 | 88 谢谢分享。
刚好收到twitter recruiter的电话邀请面试，正在向要不要挪挪窝呢。
还有什么其他的twitter面经吗？ |
q****m
发帖数: 177 | 89 假设树的高度是 h 的话， 每个 node 到 root只用 O(h) 步，那么找两个node的
lowest common ancestor 只需要 O(h) 步.
【在 l*********8 的大作中提到】
: O(n^2)只计算了两个点之间的距离。 总共有n*(n-1)/2 个pair, 每个pair用O(n^2)时
: 间。 那么总共算法就是O(n^4)了。
:
: 到N
|
l*******s
发帖数: 1258 | 90 三面里面计算word count和trend，已经是NLP的题目了，跟编程没啥大关系。
word count：简单的方法，写一堆Regex，把所有标点符号甚至连字符之类的都考虑进
去；复杂的方法：弄一堆实现分好词的tweets，搞一个classifier，比如naive bayes
或者maxEnt之类的，训练一下，效果能比Regex好不少。
计算trend:既然光词频不够，那么就要考虑其他的东西，比如tfidf之类的。不过感觉
词频其实还是最主要的feature。往大了说，又麻烦了。 |
