这算违纪吗? 老师怎么发现的? :) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

这算违纪吗? 老师怎么发现的? :)

这算违纪吗? 老师怎么发现的? :)# Joke - 肚皮舞运动

p*82012-10-10 07:10

1 楼

1）一个数组，除了一个数只出现一次，其他都出现两次，找出这个数。经典题之一，
XOR就行了
2）很大一个文件，内存放不下，里面都是整数，有重复，求只出现一次的整数的个数
。应该是大数据吧，我就说了hash到多个小文件，保证一样的整数到同一个小文件，然
后依次读进内存用hashmap/hashset处理，面试官说如果所有数都一样，hash后还是一
个文件，我想了下想再hash一次，后来想干脆用hadoop搞，用两个job，第一个每个map
读进来，key是integer本身以及map task id，reducer负责输出这个task的unique的整
数，partioner根据integer和map id进行分配，然后第二个job把reducer设置成1个进
行合并。感觉杀鸡用牛刀了，但想不到啥其他方法
3）差不多的题，这次输出所有unique的数。我想了下先把所有一样的数hash到小文件，
如果小文件size还太大，再进行二次hash，根据文件size进行平均分配，然后处理每个
小文件，最后合并结果。
感觉2）3）答得不好，大数据以前就稍微看了下top k之类的，都是hashmap + heap搞
定，本身没这方面的经验，打算好好研究下那篇博客了。希望大家给点思路，下次碰到
就不怕了，也希望对大家有用。

v*a2012-10-10 07:10

2 楼

EB23类
好奇一下

c*72012-10-10 07:10

3 楼

=。=

j*y2012-10-10 07:10

4 楼

2), 可以用两个 bit vector v1, v2 吗？ if( i exist) then v1[i] = 1
if(i 重复) then v2[i] = 1;

map

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

: 1）一个数组，除了一个数只出现一次，其他都出现两次，找出这个数。经典题之一，
: XOR就行了
: 2）很大一个文件，内存放不下，里面都是整数，有重复，求只出现一次的整数的个数
: 。应该是大数据吧，我就说了hash到多个小文件，保证一样的整数到同一个小文件，然
: 后依次读进内存用hashmap/hashset处理，面试官说如果所有数都一样，hash后还是一
: 个文件，我想了下想再hash一次，后来想干脆用hadoop搞，用两个job，第一个每个map
: 读进来，key是integer本身以及map task id，reducer负责输出这个task的unique的整
: 数，partioner根据integer和map id进行分配，然后第二个job把reducer设置成1个进
: 行合并。感觉杀鸡用牛刀了，但想不到啥其他方法
: 3）差不多的题，这次输出所有unique的数。我想了下先把所有一样的数hash到小文件，

l*g2012-10-10 07:10

5 楼

置顶的Googledoc 上🈶，自己看

z*n2012-10-10 07:10

6 楼

没有主语，是谁玩弄谁的

【在 c*******7 的大作中提到】

: =。=

p*82012-10-10 07:10

7 楼

i的范围不确定，跨度很大，所有数有可能都不重复，有可能都重复，所以不大可能用
array吧，而且内存放不下，应该是要一个有效的分割的方法，我也不是很确定。。

r*32012-10-10 07:10

8 楼

又没说是自己的

j*y2012-10-10 07:10

9 楼

32位整数的话用 bit还是可以应付， 64位就不行了，太大。

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

: i的范围不确定，跨度很大，所有数有可能都不重复，有可能都重复，所以不大可能用
: array吧，而且内存放不下，应该是要一个有效的分割的方法，我也不是很确定。。

z*n2012-10-10 07:10

10 楼

btw，字写的不错

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

: 又没说是自己的

t*h2012-10-10 07:10

11 楼

i think this is a good idea. if bitmap can't hold, then why not hadoop?

【在 j*****y 的大作中提到】

: 2), 可以用两个 bit vector v1, v2 吗？ if( i exist) then v1[i] = 1
: if(i 重复) then v2[i] = 1;
:
: map

r*32012-10-10 07:10

12 楼

上面遮住学生的名，下面遮住姓。。。

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

: btw，字写的不错

p*82012-10-10 07:10

13 楼

我要跟没想到用bit，没经验啊，其实做过用bit弄的题。。还得加强内功

【在 j*****y 的大作中提到】

: 32位整数的话用 bit还是可以应付， 64位就不行了，太大。

c*72012-10-10 07:10

14 楼

哈哈哈哈哈，给你看出来哦：）
是不是亮点很多。

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

: 上面遮住学生的名，下面遮住姓。。。

b*u2012-10-10 07:10

15 楼

2 还是用哈希，每个小文件里存放一个map，这样再多相同的数也不过是1
个entry
最后遍历一下几个map，return 值为0的key

h*e2012-10-10 07:10

16 楼

可能是玩弄别人的

t*e2012-10-10 07:10

17 楼

(2) 和（3）区别是什么？出现一次 = unique，不是么

b*u2012-10-10 07:10

18 楼

可能有三个字。

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

: 上面遮住学生的名，下面遮住姓。。。

p*82012-10-10 07:10

19 楼

主要还是要处理怎么分割小文件吧，比如所有数都一样的情况，得进行二次分割吧

是1

【在 b*****u 的大作中提到】

: 2 还是用哈希，每个小文件里存放一个map，这样再多相同的数也不过是1
: 个entry
: 最后遍历一下几个map，return 值为0的key

r*e2012-10-10 07:10

20 楼

都高二乐

【在 c*******7 的大作中提到】

: =。=

j*22012-10-10 07:10

21 楼

请问可以暗示下是哪家吗？

p*82012-10-10 07:10

22 楼

2）是要统计unique次数，3）是要输出这些数，反正我觉得我没答好，这两题方法上应
该要有区别才对。。

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

: (2) 和（3）区别是什么？出现一次 = unique，不是么

p*82012-10-10 07:10

23 楼

找到答案了，就是那篇秒杀海量数据的文章，有个双层桶划分的方法，一模一样的题，
有兴趣的看看吧。。

j*y2012-10-10 07:10

24 楼

能给个link吗？多谢.

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

: 找到答案了，就是那篇秒杀海量数据的文章，有个双层桶划分的方法，一模一样的题，
: 有兴趣的看看吧。。

p*82012-10-10 07:10

25 楼

http://blog.csdn.net/v_july_v/article/details/7382693

【在 j*****y 的大作中提到】

: 能给个link吗？多谢.

j*y2012-10-10 07:10

26 楼

many thanks :)

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

: http://blog.csdn.net/v_july_v/article/details/7382693

e*e2012-10-10 07:10

27 楼

I think this will work if the memory is more than 512M and integer is 32bit.

【在 j*****y 的大作中提到】

: 2), 可以用两个 bit vector v1, v2 吗？ if( i exist) then v1[i] = 1
: if(i 重复) then v2[i] = 1;
:
: map

m*k2012-10-10 07:10

28 楼

2) 3)比较好的工程做法是外排序，然后uniq.
比如 sort file | uniq -u, 或者 sort file | uniq -d