一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1276|回复: 39
收起左侧

Twitter Online Test + 问题求解答

[复制链接] |试试Instant~ |关注本帖
pc1000a 发表于 2014-6-8 06:25:23 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Twitter - 内推 - 在线笔试 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚做了Twitter的Online Test, Twitter大部分申请的职位,junior level的,都是先在Codility做两道题,题目不难,以前也有人发过,如下:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1,  Find a single number in an array, while other numbers appears twice or more than twice.
               A: 参见Leetcode Single Number II
2, A non-empty zero-indexed array A consisting of N integers is given.
                A pair of integers (P, Q) is called K-complementary in array A if 0 ≤ P, Q < N and A[P] + A[Q] = K.
               
                For example, consider array A such that:. visit 1point3acres.com for more.
               
-google 1point3acres                  A[0] =  1  A[1] = 8  A[2]= -3
                  A[3] =  0  A[4] = 1  A[5]=  3
                  A[6] = -2  A[7] = 4  A[8]=  5
                  . from: 1point3acres.com/bbs
                The following pairs are 6-complementary in array A: (0,8), (1,6), (4,8), (5,5), (6,1), (8,0), (8,4).
                For instance, the pair (4,8) is 6-complementary because A[4] + A[8] = 1 + 5 = 6.
               
                Write a function:
               
                        class Solution { public int solution(int K, int[] A); }.鏈?枃鍘熷垱鑷�1point3acres璁哄潧.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        . from: 1point3acres.com/bbs
                that, given an integer K and a non-empty zero-indexed array A consisting of N integers,
                returns the number of K-complementary pairs in array A.
               
                For example, given K = 6 and array A such that:
               
                  A[0] =  1  A[1] = 8  A[2]= -3. more info on 1point3acres.com
                  A[3] =  0  A[4] = 1  A[5]=  3. 鍥磋?鎴戜滑@1point 3 acres
                  A[6] = -2  A[7] = 4  A[8]=  5
                  .鐣欏?璁哄潧-涓

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| pc1000a 发表于 2014-6-8 06:28:32 | 显示全部楼层
为什么没发全。。。。 接上贴

the function should return 7, as explained above.

Assume that:. From 1point 3acres bbs
                        N is an integer within the range [1..50,000];
                        K is an integer within the range [−2,147,483,648..2,147,483,647];
                        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Complexity:
                        expected worst-case time complexity is O(N*log(N));
                        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

.鏈枃鍘熷垱鑷1point3acres璁哄潧Answer & 问题求助:

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

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

然后iterate through这个Map:
// Java Code
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:48:12 | 显示全部楼层
顺便求问,Java里面,一个函数返回类型为List<List<Integer>>时,函数里面怎么定义这个要返回的东西?如:
public List<List<Integer>> func(int a) {
       List<List<Integer>> result = ???; // 怎么定义返回类型. 1point3acres.com/bbs
}
. 鍥磋鎴戜滑@1point 3 acres
因为List是接口,比如弄成ArrayList等才能instantiate。。。有人知道怎么弄吗?
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-8 08:58:36 | 显示全部楼层
pc1000a 发表于 2014-6-8 06:48
顺便求问,Java里面,一个函数返回类型为List时,函数里面怎么定义这个要返回的东西?如:
public List fu ...

?? 什么意思?

public List<List<Integer>> func(int a) { . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        return new ArrayList<List<Integer>>();
    }

这个?
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-8 09:01:30 | 显示全部楼层
pc1000a 发表于 2014-6-8 06:48. 1point3acres.com/bbs
顺便求问,Java里面,一个函数返回类型为List时,函数里面怎么定义这个要返回的东西?如:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public List fu ...

http://www.docjar.com/html/api/java/util/TreeMap.java.html. 鍥磋鎴戜滑@1point 3 acres

回复 支持 反对

使用道具 举报

tianyangche 发表于 2014-6-8 11:52:52 | 显示全部楼层
楼主你好,
我仔细研读了一下你的code,发现了一个小小的bug。
如果A[4]=A[5]=3,那么计算结果会比正确结果多2
回复 支持 反对

使用道具 举报

sotony 发表于 2014-6-8 13:05:35 | 显示全部楼层
pc1000a 发表于 2014-6-8 06:48. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
顺便求问,Java里面,一个函数返回类型为List时,函数里面怎么定义这个要返回的东西?如:
public List fu ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不是很明白你说的意思,但:.1point3acres缃
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> res = new ArrayList<Integer>();
这样?
回复 支持 反对

使用道具 举报

sotony 发表于 2014-6-8 13:09:36 | 显示全部楼层
readman 发表于 2014-6-8 09:01
http://www.docjar.com/html/api/java/util/TreeMap.java.html

我一直有个疑问:
public TreeMap(Comparator<? super K> comparator) {. Waral 鍗氬鏈夋洿澶氭枃绔,
        this.comparator = comparator;
}
这里面Comparator<? super K> comparator.1point3acres缃
那个<? super K>是什么意思。难道说这个?是K的子类?
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-8 17:38:06 | 显示全部楼层
sotony 发表于 2014-6-8 13:09
我一直有个疑问:
public TreeMap(Comparator

说反了 是超类. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

<? super k> 的意思是 这个泛型 是 K的超类,并且包含K
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-9 02:16:57 | 显示全部楼层
为什么hashmap实现空间复杂度不是O(n)?看java的实现http://java.dzone.com/articles/hashmap-internal 应该还是O(n)吧。如果不想用别的数据结构可以先merge sort一下数组,然后用binary search
回复 支持 反对

使用道具 举报

asdfyou6 发表于 2014-6-9 02:34:11 | 显示全部楼层
楼主是啥时候投的twitter?可以透露一下么~
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 03:52:30 | 显示全部楼层
readman 发表于 2014-6-7 19:58
?? 什么意思?

public List func(int a) {

果然哈 这样行。。谢啦
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 03:58:51 | 显示全部楼层
sotony 发表于 2014-6-8 00:05
不是很明白你说的意思,但:
List result = new ArrayList();
List res = new ArrayList();

是的,已经解决了,多谢
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:02:32 | 显示全部楼层
sotony 发表于 2014-6-8 00:09
我一直有个疑问:
public TreeMap(Comparator

好像<? extends K>表示K或K的一个未知子类,<? super K>表示K或K的一个未知父类。。
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:20:27 | 显示全部楼层
tianyangche 发表于 2014-6-7 22:52
楼主你好,
我仔细研读了一下你的code,发现了一个小小的bug。
如果A[4]=A[5]=3,那么计算结果会比正确结 ...

好像是对的啊。。。注意题目说0 <= P, Q < N, P跟Q可以相等。比如说input array是{1,8,-3,0,3,3,-2,4,5}, K是6,那么结果Index对儿是:(0, 8), (1, 6), (4, 4), (4, 5), (5, 4), (5, 5), (6, 1), (8, 0).  一共8个组合,不是6个。。。因为P和Q是index,可以相等
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:29:32 | 显示全部楼层

Comparator<? super K>是不是这意思: 首先咱们知道TreeMap<K, V>里面需要针对K进行排序。. visit 1point3acres.com for more.

如果K的某一父类能够并且实现了用Comparator对某一data field进行比较的话,那么K因为是继承自父类,所以必然也继承了可比较的特性, 即Comparator的泛型为<? super K>可行;

而K不能排序,而K的某个实现的子类能排序的情况是存在的;但是,这种情况即使子类能排序,K不能排序也是白搭。。。。。 所以必须保证K或者K的父类可比较。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是不是这个意思?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:38:08 | 显示全部楼层
Neal 发表于 2014-6-8 13:16
为什么hashmap实现空间复杂度不是O(n)?看java的实现http://java.dzone.com/articles/hashmap-internal 应 ...

基于Hash的话,比如说HashCode的范围是100,那么即使只有20个元素,机器分给Hash的内存还是100。。。所以Hash就有无用的空间小号啦。。。所以才会有load factor这个东西存在。。

至于先sort再用binary search,虽然sort可以降到O(nlogn),但是你的想法应该是sort完,对于数组从头到尾(或到某处)的每一个element,进行binary search吧。。。那么,如果出现数组里有重复元素的情况,比如input array是{1,1,1,1,1},而需要找的sum是2,那么每次binary search找到target后都不能停,而是需要继续对左右的元素进行搜索,最坏情况每次binary search都会搜遍整个数组,例如对A[0],target = 2 - A[0] = 1, 那么每个元素都是1,所以就得搜遍整个数组。。。.1point3acres缃

所以最终时间是O(fatorial(n))..对不对?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:38:54 | 显示全部楼层
asdfyou6 发表于 2014-6-8 13:34
楼主是啥时候投的twitter?可以透露一下么~

上个月。。。这个university programs反应还是比较慢的
回复 支持 反对

使用道具 举报

laughingvito 发表于 2014-6-9 08:34:01 | 显示全部楼层
LZ, 只能用java么?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 08:53:54 | 显示全部楼层
laughingvito 发表于 2014-6-8 19:34
LZ, 只能用java么?

当然不是啦 什么都能 js ruby都能。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 01:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表