Twitter实习第一轮电面总结 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Twitter实习第一轮电面总结

Twitter实习第一轮电面总结# JobHunting - 待字闺中

l*p2012-02-14 08:02

1 楼

面试前做功课，发现面试官是一个老墨，从GA的一个不知名的大学本科刚毕业，去年夏
天才加入twitter，心想这样的面试官应该好应付
开门见山第一个问题：你为什么要来Twitter
然后开始coding
1. fibonacci。我跟他说这是递归的一个经典案例，然后开始用最简单的递归写。写完
后自己检查一遍，然后跟他说这是最简单的实现方式，但是这个方式有严重的性能问题
，可以用动态规划方法优化。他可能对动态规划这个名字觉得太深奥，然后自己提出说
能不能用cache来优化，我心想这不就是动态规划的实质吗？于是我按他说的重新实现
了一遍。然后分析原来的性能是O(2^N)，优化后的性能是O(n)（单次调用）或接近O(1)
（多次调用）
2. 合并N个长度为k的有序数组。写完后一边检查，我一边跟他说要是平时我会写一个
unit test来测试。然后他提出让我写一个unit test。我说那我就用JUnit写，但由于
环境限制，我先不管那些导入各个包，定义类等，直接写方法。他说没关系，然后我就
写了
3. 问我有没有Unix的经验，我说Unix用得比较少，Linux比较多。我平常用的操作系统就是
Linux。然后他问我kill命令是干什么，我说结束一个进程的。接着问kill -7是什么意思，我说
我只用过kill -9，那个可以迅速结束一个进程，至于那个数字，我猜是urgent的程度吧
到这边就超时了，不过最后他还问我有什么问题。我把事先准备好的问题提出来：
Twitter到最后是不是想彻底放弃Ruby On Rails？他说这问题问得好，然后解释说ROR
性能比较成问题，所以他们现在慢慢转向JVM的一些语言，但是做为部署用的脚本还是
用Ruby写的，他自己的主要责任就是部署。然后我问他现在是用Capistrano吗？他说不
是，用他们自己实现的东西。然后急急忙忙说他得走了，就把电话挂了
没想到Twitter的第一轮电话面试会这么简单，估计是逐步递增吧。不像Google的电面
，三次难度都差不多

B*52012-02-14 08:02

2 楼

不是简单，是你牛

d*o2012-02-14 08:02

3 楼

牛人

i*r2012-02-14 08:02

4 楼

Fibonacci直接递推就是O(n)了
其实可以做到O(lgn)，如果你知道公式甚至是O(1)

1)

【在 l****p 的大作中提到】

: 面试前做功课，发现面试官是一个老墨，从GA的一个不知名的大学本科刚毕业，去年夏
: 天才加入twitter，心想这样的面试官应该好应付
: 开门见山第一个问题：你为什么要来Twitter
: 然后开始coding
: 1. fibonacci。我跟他说这是递归的一个经典案例，然后开始用最简单的递归写。写完
: 后自己检查一遍，然后跟他说这是最简单的实现方式，但是这个方式有严重的性能问题
: ，可以用动态规划方法优化。他可能对动态规划这个名字觉得太深奥，然后自己提出说
: 能不能用cache来优化，我心想这不就是动态规划的实质吗？于是我按他说的重新实现
: 了一遍。然后分析原来的性能是O(2^N)，优化后的性能是O(n)（单次调用）或接近O(1)
: （多次调用）

k*t2012-02-14 08:02

5 楼

第一个，为何不直接写递推或cached/DP的代码?
第二个，assume a heap was used to do N-way merge。
第三个，准确的讲，kill cmd is used to send signal. By default, SIGTERM is
sent. 9 is SIGKILL, 7 is SIGBUS.

1)

【在 l****p 的大作中提到】

P*P2012-02-14 08:02

6 楼

知道公式也需要log(n)吧，因为pow(a,n)需要log(n)

【在 i******r 的大作中提到】

: Fibonacci直接递推就是O(n)了
: 其实可以做到O(lgn)，如果你知道公式甚至是O(1)
:
: 1)

i*r2012-02-14 08:02

7 楼

我认为直接用函数算就是O(1)的了

【在 P***P 的大作中提到】

: 知道公式也需要log(n)吧，因为pow(a,n)需要log(n)

B*52012-02-14 08:02

8 楼

啥函数？pow？好吧。。。

【在 i******r 的大作中提到】

: 我认为直接用函数算就是O(1)的了

P*P2012-02-14 08:02

9 楼

复杂度定义是算法所需时间, 什么是算法, 就是图灵机上运行的一系列operations. 跟
面试官聊天时可以聊聊这个,绝对唬得住
pow(n)时间用o(1)的话空间就要用o(n)了

【在 i******r 的大作中提到】

: 我认为直接用函数算就是O(1)的了

a*s2012-02-14 08:02

10 楼

可视电话？还能看出是老莫，而且还知道是哪个学校毕业的？

l*p2012-02-14 08:02

11 楼

第一个一方面是想着步步为营，另一方面，面试不是经常先让用最简单的方式实现个算
法，然后问你怎么优化吗？我猜面试官当时也是这么准备的，所以我就迎合一下。
第二个不需要用到heap吧，因为几个子数组都已经排好序了，用heap不会更快吧
第三个面试后查手册才知道，原来kill是这样的。平常只用过kill和kill -9，以为就
是按字面意思用来杀死一个进程的

【在 k***t 的大作中提到】

: 第一个，为何不直接写递推或cached/DP的代码?
: 第二个，assume a heap was used to do N-way merge。
: 第三个，准确的讲，kill cmd is used to send signal. By default, SIGTERM is
: sent. 9 is SIGKILL, 7 is SIGBUS.
:
: 1)

l*p2012-02-14 08:02

12 楼

看他linkedin, twitter等账号就知道了

【在 a*****s 的大作中提到】

: 可视电话？还能看出是老莫，而且还知道是哪个学校毕业的？

l*a2012-02-14 08:02

13 楼

几个子数组各自有序
但是数组之间的数无序啊
刚好把他们放在堆里，每次取最小的，再放入下一个，然后调整堆

【在 l****p 的大作中提到】

: 第一个一方面是想着步步为营，另一方面，面试不是经常先让用最简单的方式实现个算
: 法，然后问你怎么优化吗？我猜面试官当时也是这么准备的，所以我就迎合一下。
: 第二个不需要用到heap吧，因为几个子数组都已经排好序了，用heap不会更快吧
: 第三个面试后查手册才知道，原来kill是这样的。平常只用过kill和kill -9，以为就
: 是按字面意思用来杀死一个进程的

w*z2012-02-14 08:02

14 楼

Seems like Priority Queue is the most popular way:
http://stackoverflow.com/questions/5055909/algorithm-for-n-way-
http://dzmitryhuba.blogspot.com/2010/03/n-way-merge.html

【在 l*****a 的大作中提到】

: 几个子数组各自有序
: 但是数组之间的数无序啊
: 刚好把他们放在堆里，每次取最小的，再放入下一个，然后调整堆

l*p2012-02-14 08:02

15 楼

赞！

【在 w**z 的大作中提到】

: Seems like Priority Queue is the most popular way:
: http://stackoverflow.com/questions/5055909/algorithm-for-n-way-
: http://dzmitryhuba.blogspot.com/2010/03/n-way-merge.html

i*e2012-02-14 08:02

16 楼

第二题还有另一个思路是用 divide and conquer。不过 heap 的解法比较好写代码。其实这题 brute force 写起来更要复杂，很多繁琐的 case 要考虑周到。
还有一个变种，就是 merge k-sorted lists，这道题还要稍微 tricky 一些，但思路一样。
Merge k Sorted Lists 这道题收集在这里了，制造了一些测试数据，方便大家测试代
码。
http://www.leetcode.com/onlinejudge

h*w2012-02-14 08:02

17 楼

mark一下

x*52012-02-14 08:02

18 楼

顶大牛

。其实这题 brute force 写起来更要复杂，很多繁琐的 case 要考虑周到。
路一样。

【在 i**********e 的大作中提到】

: 第二题还有另一个思路是用 divide and conquer。不过 heap 的解法比较好写代码。其实这题 brute force 写起来更要复杂，很多繁琐的 case 要考虑周到。
: 还有一个变种，就是 merge k-sorted lists，这道题还要稍微 tricky 一些，但思路一样。
: Merge k Sorted Lists 这道题收集在这里了，制造了一些测试数据，方便大家测试代
: 码。
: http://www.leetcode.com/onlinejudge