如题,今年春季的笔试题,不知道腾讯想表达什么意思,自己不是很精通STL。
感觉直接遍历一遍然后考察vector[i]>>1;
如果奇数就提出来,算法开销O(n),不知道是不是有什么更好的方法?
大神勿喷,这题有没有必要用hash?
1
jiang42 2015-04-07 22:54:56 +08:00
听说腾讯有让做fib53的,我觉得。。。这题O(n)算法就行了?
|
2
vibbow 2015-04-07 23:31:57 +08:00
直接循环一遍,在内存里判断QQ号最后一位二进制是不是1?
|
3
wind3110991 OP @vibbow 我也觉得。。不知道他要表达什么了
|
4
wind3110991 OP @jiang42 fib53?斐波那契?
|
5
xvsfezz 2015-04-07 23:45:57 +08:00
内存够不够。。
|
6
wy315700 2015-04-08 00:02:27 +08:00
是不是不允许copy
|
7
wind3110991 OP @xvsfezz 假如不够呢,是不是hash到n个文件里?
|
8
HanSonJ 2015-04-08 00:12:09 +08:00 via Android
明天面试楼主才来问之前的问题…
|
9
wind3110991 OP @HanSonJ 今天看大数据时突然想起没有比较好的解决方案,身边同学也觉得题有问题,就搁浅了,你觉得怎么解决?
|
10
wind3110991 OP @wy315700 好像没提到
|
11
HanSonJ 2015-04-08 00:21:37 +08:00 via Android
@wind3110991 我是战斗力只有5的渣
|
12
spacewander 2015-04-08 00:27:24 +08:00 1
count += (v[i] & 1);
类似这样? 没用无重复的条件,但是O(n)加较小的常数因子,感觉没有比它更快了 再快就只能用并行算法了…… |
13
acros 2015-04-08 01:09:13 +08:00 via iPhone
考内存管理的效率吗?
qq号一亿个int,长度按4算,内存肯定不够一次载入。 另外还有vector内部内存模型问题吧,我需要复习下..... |
14
acros 2015-04-08 01:14:35 +08:00 via iPhone
2了,现在qq号是11位以上了吧?存的string还是数值?
|
15
jesse_luo 2015-04-08 01:16:15 +08:00
|
18
jiang42 2015-04-08 04:21:44 +08:00
@wind3110991 对啊。。。
|
19
NCE 2015-04-08 08:49:56 +08:00
11wei % 2
|
20
lucifer9 2015-04-08 09:15:30 +08:00 11
给所有qq在线用户弹窗:
今天是马化腾的生日,挑出以下所有的偶数号码并回复偶数号码的个数有机会点亮头像哦 然后每个用户发10个号码,正好用上号码不重复的条件 运气好的话一遍就出来结果了 |
21
cheng007 2015-04-08 09:17:30 +08:00
有一个1亿的vector,说明内存不是问题,要拿出所有的奇数,必须完成一次遍历也就是O(n),这题目应该是考并发吧,开多个线程每个线程负责一个段数据。
|
23
zwzmzd 2015-04-08 09:21:26 +08:00 via Android
我记得题目是删除qq号
不过意思一样,用remove_if,原理类似于partition |
24
sigarron 2015-04-08 09:32:23 +08:00
@spacewander 这哥们貌似对的,位运算总是最快的,但是vector的意义是啥呢?存储的是int64还是string呢?这些问题都值得考虑下。
|
26
xinyewdz 2015-04-08 09:59:34 +08:00
普通的qq号是9位,大概就是1亿个。这数组不是稀疏数组,遍历一遍标注每个数组(用0和1标注)。然后直接输出下标是奇数并且值是1的。
|
27
ybh37 2015-04-08 10:06:53 +08:00
字符串和数字无所谓,只判断二进制的最后一位是不是0就可以了。
|
29
ugvfpdcuwfnh 2015-04-08 12:30:02 +08:00
拆半查找都可以吧,2的27次方大于一亿。
前几次是外部排序,后面就是内部排序。 |
30
lijinma 2015-04-08 13:22:49 +08:00
@ugvfpdcuwfnh 还要排序?排序那就更复杂了
|
31
ugvfpdcuwfnh 2015-04-08 13:56:29 +08:00
@lijinma 不是排序,本身就是排好的,应该是外部查找和内部查找。
|
32
ugvfpdcuwfnh 2015-04-08 13:58:57 +08:00
哎?我突然发现我没看清题目,是要选出奇数号,我以为是从一亿号里选出一个号。
好吧,我楼上的回复都无视吧..... |
34
ether 2015-04-08 14:14:05 +08:00
map reduce!
|
35
yuankui 2015-04-08 14:27:35 +08:00
把奇数插入到首部,吧偶数插入到尾部
要取奇数的话,就循环从首部取完,直到遇到偶数... 要取偶数的化,就循环从尾部取,直到遇到奇数... |
36
yuankui 2015-04-08 14:41:34 +08:00
我靠,如果有这种需求,为什么不用两个vector存储?
|
37
yuankui 2015-04-08 14:42:02 +08:00
你可以直接跟面试官说,你们这个前提很没水平
|
38
sage417 2015-04-08 16:10:23 +08:00
我觉得考的是大数据,跟技术还是偶数没什么关系,应该是map-reduce
|
39
sen506 2015-04-08 16:42:18 +08:00
2个迭代器A B
当当前数位奇数时*A++ = *B++; 当当前数为偶数时++B; B到达容器结尾时结束; 最后vector.erase(A, vector.end()); 应该就这样了吧。。 |
40
laotaitai 2015-04-08 17:12:11 +08:00
拿Python, 3秒就能把1亿个QQ遍历完
|
41
also24 2015-04-08 17:35:06 +08:00
看到中间越看感觉越奇怪……
返回头又看一遍才反应过来是 奇数 不是 质数 的我面壁去了…… (:o 」∠)_ |
44
luoqeng 2015-04-18 00:09:55 +08:00
vector<bool> == Bitmap
http://blog.csdn.net/u014082714/article/details/45022567 |
45
khan 2015-04-28 09:36:12 +08:00
判断低 bit位是否为1
|
46
khan 2015-04-28 11:00:02 +08:00
8byte int_64 * 100,000,000L 需内存约 100M
位运算 比 / %都要省 cpu, 剩下的内存问题可以多段分块加载 |
47
khan 2015-04-28 11:08:00 +08:00 1
体死早. 800M 内存 换成字符串大概不过2G, 加上指针 和 字符串本身内存, 分块处理 合并不可少
|
48
wind3110991 OP @khan 谢谢你的解答!我再想想,有点不理解
|