求问Twitter online coding test

昨天收到twitter recruiter的回复，说是techincal review之前得先做一个online coding test，不知道版上有没有同学做过，能分享下经验和机经什么的？不确定是不是类似amazon的online test，要写不少分析？

ivanlw 发表于 2014-3-7 18:11
请问第二题的思路是什么呢？

觉得可以用java的TreeMap<K, V>（Java里面TreeMap实现基于Red-Black Tree)，或者其他语言的BST结构，每个Node都是个<K, V> entry， K是数组里的这个element，V是这个element出现的次数。

先把所有element和出现次数存到Map里面。

然后iterate through这个Map：
int cnt = 0;
for (int each : map.keySet()) {
        if (map.containsKey(K - each)) {                               
                cnt += map.get(each) * map.get(K - each);
        }
}
return cnt;

这就行了。。

因为是java TreeMap基于BST的实现，所以基本操作时间都是O(lgn)，所以总的时间是O(n * lgn)；
空间的话，题目说space worst case O(n)，而用BST结构没有额外空间消耗，所以空间也是O(n)，符合要求（Hash等结构的map不能用，因为Hash结构有额外空间消耗，而且比较大，肯定不是O(n)）。

但是问题在于，不知道java Collections里面，TreeMap虽然理论上空间消耗，基于BST/RBT，是O(n)，但不知道java语言实现细节方面，会不会有其他消耗，会不会空间就能达到O(n)。。。

所以，有人知道不用容器或者其他什么数据结构，就用数组操作，时间O(nlgn)，空间O(n)的方法吗？？？

pc1000a 发表于 2014-6-8 06:13
觉得可以用java的TreeMap（Java里面TreeMap实现基于Red-Black Tree)，或者其他语言的BST结构，每个Node都 ...

可以先sort一遍然后two pointers 一左一右往中间靠．

因为java里Arrays用的是merge sort, O(n log n) for sorting, O(n) for extra space

同问，同问

有点类似Online Judge，给道题，然后写代码就是了，最后会生成个score report。你可以试试他的demo，熟悉下环境就行，题目难度都不难，基本算法的简单twist。

我记得amazon 也有这种online assessment 。 看了Amazon的很简单

lz是直接去twitter官网投的么？我和好几个小伙伴投twitter都是12小时内直接拿了rej，不知道lz投的是哪个职位？

starcroce 发表于 2013-11-4 10:42
lz是直接去twitter官网投的么？我和好几个小伙伴投twitter都是12小时内直接拿了rej，不知道lz投的是哪个职位 ...

我就是官网投的SDE Vancouver，没找人refer，周围有几个朋友先投的三藩的那个entry level也是很快就rej了，之后再投Vancouver那个职位也马上被拒，很奇怪

adlxk 发表于 2013-11-4 14:10
我就是官网投的SDE Vancouver，没找人refer，周围有几个朋友先投的三藩的那个entry level也是很快就rej了 ...

IPO前好像不招Entry-Level了，可能得过一阵儿才有open了~

zxyviopond 发表于 2013-11-4 14:16
IPO前好像不招Entry-Level了，可能得过一阵儿才有open了~

我也觉得是因为IPO的关系。。。dropbox好像最近也不大招engineer了，career fair上跟我们说只要sales和operation。。。

楼主能分享下题目么，谢谢！

题目大概是啥难度呢？

补充内容 (2014-1-9 00:31):
有那种读本地文件进行处理得吗