《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,你要不要来?
把贵司招聘信息放这里
查看: 2173|回复: 39
收起左侧

Twitter Online Test + 问题求解答

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

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

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

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

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.鏈枃鍘熷垱鑷1point3acres璁哄潧
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:
               
                  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
                  
                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璁哄潧. 1point3acres.com/bbs
                        . 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. 鍥磋鎴戜滑@1point 3 acres
                  A[6] = -2  A[7] = 4  A[8]=  5
                  .鐣欏?璁哄潧-涓

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

the function should return 7, as explained above.

Assume that:
                        N is an integer within the range [1..50,000];. visit 1point3acres.com for more.
                        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].
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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.

Answer & 问题求助:

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

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

然后iterate through这个Map:
// Java Code
int cnt = 0;
. From 1point 3acres bbsfor (int each : map.keySet()) {
        if (map.containsKey(K - each)) {                                
                cnt += map.get(each) * map.get(K - each);. more info on 1point3acres.com
        }
}
return cnt;

这就行了。。-google 1point3acres

因为是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 = ???; // 怎么定义返回类型
}. 1point 3acres 璁哄潧

因为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) { .1point3acres缃
        return new ArrayList<List<Integer>>();
    }
. From 1point 3acres bbs
这个?
回复 支持 反对

使用道具 举报

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

http://www.docjar.com/html/api/java/util/TreeMap.java.html. 1point3acres.com/bbs

回复 支持 反对

使用道具 举报

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 ...

不是很明白你说的意思,但:
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) {. From 1point 3acres bbs
        this.comparator = comparator;
}. 1point3acres.com/bbs
这里面Comparator<? super K> comparator
那个<? 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. 1point3acres.com/bbs
?? 什么意思?
.1point3acres缃
public List func(int a) {
. visit 1point3acres.com for more.
果然哈 这样行。。谢啦
回复 支持 反对

使用道具 举报

 楼主| 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. From 1point 3acres bbs
楼主你好,
我仔细研读了一下你的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进行排序。

如果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.com/bbs
所以最终时间是O(fatorial(n))..对不对?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-6-9 04:38:54 | 显示全部楼层
asdfyou6 发表于 2014-6-8 13:34
楼主是啥时候投的twitter?可以透露一下么~
. 1point 3acres 璁哄潧
上个月。。。这个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都能。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-18 01:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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