l****p
发帖数: 397 | 1 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
一边回忆Bayesian Network。他好像不想拷问我具体的原理，就开始说他怎么用
Bayesian Network来查找性能瓶颈的。他问我一般跑那些数据挖掘的程序要花多少天，
我说几个小时到一两天吧。那时间主要花在哪？我说把数据转换成数据挖掘算法需要的
格式需要很长时间。问如果数据已经整理好了呢？我说那就相对容易了，因为有很多现
成的数据挖掘包。最后我问他构建那些性能模型时怎么选取features，他说主要靠他自
己的经验。我说其实可以用一些feature selection算法，先搜集一大堆features，然
后对重要性排序。他觉得这主意挺好。
第四次面试。还是先聊我的研究。然后问二维网格中有一些点，怎么找出与某个给定的
点欧氏距离最近的。我说由于距离计算是O(1)，那一个个算过去的复杂度也只是O(n)。
他问O(n)是不是good enough，我说在大多数情况下已经不错了，但如果n很大，在实际
中还是不够。问怎么优化。我说可以用Manhattan distance做估计，选出几个比较有可
能的点来计算欧氏距离。代码写了一半，找几个数算了一下，觉得不对。只好推倒重来
，用breadth first search。但时间已经不够了，只能把思路说一遍。 |
s******n
发帖数: 3946 | |
L*****k
发帖数: 327 | 3 zan!
兴趣
【在 l****p 的大作中提到】
: 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
: 轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
: 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
: 长不重复的结点间路径。
: 第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
: 第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
: 。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
: 。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
: 么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
: 接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
|
g**********r
发帖数: 27 | 4 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
看你的面试间隔都好长啊，是twitter的处理速度很慢吗？ |
m****i
发帖数: 650 | 5 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
m****i
发帖数: 650 | 6 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
m*****y
发帖数: 93 | 7 对于Tree，两点之间有且仅有一条非重复节点的路径，所以最长和最短是一样的吧
【在 m****i 的大作中提到】
: 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
: 长不重复的结点间路径。
: 这个啥意思呢
|
l****p
发帖数: 397 | 8 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周
【在 g**********r 的大作中提到】
: 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
: 看你的面试间隔都好长啊，是twitter的处理速度很慢吗？
|
l****p
发帖数: 397 | 9 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
【在 m*****y 的大作中提到】
: 对于Tree，两点之间有且仅有一条非重复节点的路径，所以最长和最短是一样的吧
|
h**********l
发帖数: 6342 | 10 应该是最深和最浅两个leaf的距离
log(n)的复杂度
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
|
|
m*****y
发帖数: 93 | 11 1. Compute the depth of its subtree on each node, using a recursive way.
2. For any node u, the length of longest path "turning at this node" is
depth(u->left) + depth(u->right) + 2. Therefore, for each node u, compute
the length and take the maximum one.
Both steps are O(n).
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
t*********l
发帖数: 566 | 12
~~~~~
难道不是标准的K-Dtree问题么。。。？
哥其实知道有更好的解法，废点空间。。。哥就是不说
【在 l****p 的大作中提到】
: 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
: 很远的话，那也是很耗时的。
: Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周
|
g**********r
发帖数: 27 | 13 KD-Tree应该是更好的做法，预处理好像都得O(nlogn)时间，O(n)空间。这个代码写起
来挺复杂的，quora在interviewstreet上的比赛上出过这个题，现在上面还有数据可以
测试代码的正确性。 https://quora.interviewstreet.com/challenges/dashboard/#
problem/4f50c9fc9857b |
r*******m
发帖数: 457 | |
L*****k
发帖数: 327 | 15 re， k-d tree应该是对低维的数据search很有效的一种方法。题目中2D，肯定可以
记得是数据维度一高，k-d tree就不够好了，但不记得怎么判断了，可能和N有关
【在 g**********r 的大作中提到】
: KD-Tree应该是更好的做法，预处理好像都得O(nlogn)时间，O(n)空间。这个代码写起
: 来挺复杂的，quora在interviewstreet上的比赛上出过这个题，现在上面还有数据可以
: 测试代码的正确性。 https://quora.interviewstreet.com/challenges/dashboard/#
: problem/4f50c9fc9857b
|
l****p
发帖数: 397 | 16 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
Overall the interviewers felt you were weak on the coding side. Specifically
, they mentioned it that the coding was slow and you spent a lot of time
optimizing instead of addressing the algorithmic complexity.
我估计optimizing instead of addressing the algorithmic complexity是最后一个
面试官的评价。
总体上还是内功不行，怨不得别人。好好修炼吧 |
m*****y
发帖数: 93 | 17 pat, twitter's bar is high. btw, thanks for sharing.
Specifically
【在 l****p 的大作中提到】
: 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
: Overall the interviewers felt you were weak on the coding side. Specifically
: , they mentioned it that the coding was slow and you spent a lot of time
: optimizing instead of addressing the algorithmic complexity.
: 我估计optimizing instead of addressing the algorithmic complexity是最后一个
: 面试官的评价。
: 总体上还是内功不行，怨不得别人。好好修炼吧
|
g**********r
发帖数: 27 | 18 楼主好人，wish楼主其它公司顺利。我26号电面的twitter，到现在都还没消息，估计
是默拒了。sign |
S******t
发帖数: 151 | |
l*****a
发帖数: 559 | 20 先找最深的leaf节点，然后顺着往上到root节点的路径上，每个internal节点找除当前
路径以外的最深的leaf节点。
时间复杂度是O(n)。n为节点数。
能想到的就这么多了。
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
|
|
g*****e
发帖数: 282 | 21 最后一题跟最长回文一样，没练过的一口气写出bug free是神，写过的都不一定能完全
写对。只能背题了。。。
Specifically
【在 l****p 的大作中提到】
: 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
: Overall the interviewers felt you were weak on the coding side. Specifically
: , they mentioned it that the coding was slow and you spent a lot of time
: optimizing instead of addressing the algorithmic complexity.
: 我估计optimizing instead of addressing the algorithmic complexity是最后一个
: 面试官的评价。
: 总体上还是内功不行，怨不得别人。好好修炼吧
|
l****p
发帖数: 397 | 22 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
一边回忆Bayesian Network。他好像不想拷问我具体的原理，就开始说他怎么用
Bayesian Network来查找性能瓶颈的。他问我一般跑那些数据挖掘的程序要花多少天，
我说几个小时到一两天吧。那时间主要花在哪？我说把数据转换成数据挖掘算法需要的
格式需要很长时间。问如果数据已经整理好了呢？我说那就相对容易了，因为有很多现
成的数据挖掘包。最后我问他构建那些性能模型时怎么选取features，他说主要靠他自
己的经验。我说其实可以用一些feature selection算法，先搜集一大堆features，然
后对重要性排序。他觉得这主意挺好。
第四次面试。还是先聊我的研究。然后问二维网格中有一些点，怎么找出与某个给定的
点欧氏距离最近的。我说由于距离计算是O(1)，那一个个算过去的复杂度也只是O(n)。
他问O(n)是不是good enough，我说在大多数情况下已经不错了，但如果n很大，在实际
中还是不够。问怎么优化。我说可以用Manhattan distance做估计，选出几个比较有可
能的点来计算欧氏距离。代码写了一半，找几个数算了一下，觉得不对。只好推倒重来
，用breadth first search。但时间已经不够了，只能把思路说一遍。 |
s******n
发帖数: 3946 | |
L*****k
发帖数: 327 | 24 zan!
兴趣
【在 l****p 的大作中提到】
: 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
: 轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
: 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
: 长不重复的结点间路径。
: 第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
: 第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
: 。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
: 。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
: 么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
: 接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
|
g**********r
发帖数: 27 | 25 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
看你的面试间隔都好长啊，是twitter的处理速度很慢吗？ |
m****i
发帖数: 650 | 26 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
m****i
发帖数: 650 | 27 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
m*****y
发帖数: 93 | 28 对于Tree，两点之间有且仅有一条非重复节点的路径，所以最长和最短是一样的吧
【在 m****i 的大作中提到】
: 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
: 长不重复的结点间路径。
: 这个啥意思呢
|
l****p
发帖数: 397 | 29 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周
【在 g**********r 的大作中提到】
: 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
: 看你的面试间隔都好长啊，是twitter的处理速度很慢吗？
|
l****p
发帖数: 397 | 30 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
【在 m*****y 的大作中提到】
: 对于Tree，两点之间有且仅有一条非重复节点的路径，所以最长和最短是一样的吧
|
|
|
h**********l
发帖数: 6342 | 31 应该是最深和最浅两个leaf的距离
log(n)的复杂度
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
m*****y
发帖数: 93 | 32 1. Compute the depth of its subtree on each node, using a recursive way.
2. For any node u, the length of longest path "turning at this node" is
depth(u->left) + depth(u->right) + 2. Therefore, for each node u, compute
the length and take the maximum one.
Both steps are O(n).
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
t*********l
发帖数: 566 | 33
~~~~~
难道不是标准的K-Dtree问题么。。。？
哥其实知道有更好的解法，废点空间。。。哥就是不说
【在 l****p 的大作中提到】
: 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
: 很远的话，那也是很耗时的。
: Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周
|
g**********r
发帖数: 27 | 34 KD-Tree应该是更好的做法，预处理好像都得O(nlogn)时间，O(n)空间。这个代码写起
来挺复杂的，quora在interviewstreet上的比赛上出过这个题，现在上面还有数据可以
测试代码的正确性。 https://quora.interviewstreet.com/challenges/dashboard/#
problem/4f50c9fc9857b |
L*****k
发帖数: 327 | 35 re， k-d tree应该是对低维的数据search很有效的一种方法。题目中2D，肯定可以
记得是数据维度一高，k-d tree就不够好了，但不记得怎么判断了，可能和N有关
【在 g**********r 的大作中提到】
: KD-Tree应该是更好的做法，预处理好像都得O(nlogn)时间，O(n)空间。这个代码写起
: 来挺复杂的，quora在interviewstreet上的比赛上出过这个题，现在上面还有数据可以
: 测试代码的正确性。 https://quora.interviewstreet.com/challenges/dashboard/#
: problem/4f50c9fc9857b
|
l****p
发帖数: 397 | 36 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
Overall the interviewers felt you were weak on the coding side. Specifically
, they mentioned it that the coding was slow and you spent a lot of time
optimizing instead of addressing the algorithmic complexity.
我估计optimizing instead of addressing the algorithmic complexity是最后一个
面试官的评价。
总体上还是内功不行，怨不得别人。好好修炼吧 |
m*****y
发帖数: 93 | 37 pat, twitter's bar is high. btw, thanks for sharing.
Specifically
【在 l****p 的大作中提到】
: 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
: Overall the interviewers felt you were weak on the coding side. Specifically
: , they mentioned it that the coding was slow and you spent a lot of time
: optimizing instead of addressing the algorithmic complexity.
: 我估计optimizing instead of addressing the algorithmic complexity是最后一个
: 面试官的评价。
: 总体上还是内功不行，怨不得别人。好好修炼吧
|
g**********r
发帖数: 27 | 38 楼主好人，wish楼主其它公司顺利。我26号电面的twitter，到现在都还没消息，估计
是默拒了。sign |
S******t
发帖数: 151 | |
l*****a
发帖数: 559 | 40 先找最深的leaf节点，然后顺着往上到root节点的路径上，每个internal节点找除当前
路径以外的最深的leaf节点。
时间复杂度是O(n)。n为节点数。
能想到的就这么多了。
【在 l****p 的大作中提到】
: 是的，问题是要找出这么两个点使得它们间的路径最长，或者说找出距离最远的两个点
|
|
|
g*****e
发帖数: 282 | 41 最后一题跟最长回文一样，没练过的一口气写出bug free是神，写过的都不一定能完全
写对。只能背题了。。。
Specifically
【在 l****p 的大作中提到】
: 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
: Overall the interviewers felt you were weak on the coding side. Specifically
: , they mentioned it that the coding was slow and you spent a lot of time
: optimizing instead of addressing the algorithmic complexity.
: 我估计optimizing instead of addressing the algorithmic complexity是最后一个
: 面试官的评价。
: 总体上还是内功不行，怨不得别人。好好修炼吧
|
l**b
发帖数: 457 | |
h****n
发帖数: 1093 | 43 这个feedback怎么说，optimizing instead of addressing the algorithmic
complexity 我怎么感觉这两个是一个意思，你不断去优化不就是为了减低复杂度么。
Specifically
【在 l****p 的大作中提到】
: 最后更新一下：最终还是挂了。我问recruiter要feedback，这是她的回答：
: Overall the interviewers felt you were weak on the coding side. Specifically
: , they mentioned it that the coding was slow and you spent a lot of time
: optimizing instead of addressing the algorithmic complexity.
: 我估计optimizing instead of addressing the algorithmic complexity是最后一个
: 面试官的评价。
: 总体上还是内功不行，怨不得别人。好好修炼吧
|
l****p
发帖数: 397 | 44 他的意思是我做的optimizing只是在同一个asymptotic order里的小优化，并没有改变
asymptotic order
【在 h****n 的大作中提到】
: 这个feedback怎么说，optimizing instead of addressing the algorithmic
: complexity 我怎么感觉这两个是一个意思，你不断去优化不就是为了减低复杂度么。
:
: Specifically
|
h****n
发帖数: 1093 | 45 Got it bless
楼主是PHD吧
【在 l****p 的大作中提到】
: 他的意思是我做的optimizing只是在同一个asymptotic order里的小优化，并没有改变
: asymptotic order
|
l****p
发帖数: 397 | 46 引用一句经典回答：“你才是PHD，你全家都是PHD！！！”
哈哈
【在 h****n 的大作中提到】
: Got it bless
: 楼主是PHD吧
|
