求问Twitter online coding test

adlxk 发表于 2014-1-10 01:01
Twitter也没说不能透题，就直接贴题目吧，两道题60min，都不难。Codility提供的demo做完会生成一个score re ...

请问第二题的思路是什么呢？

真的可以自己加自己么。。。
那要是数组的那些数全都是K/2怎么办，，，？

lastquarter 发表于 2014-2-6 03:05
谢谢！已经面完了！不过好像不太一样。但是还是谢谢·~

麻烦能透露一下面经吗？ 我也收到了信 说要提前做那个题目

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