面试归来，问几道牛逼UNIX C/C++笔试题

sep

其实我奇怪，我可以算出2000！，为什么还要去数它后面还有几个0？

retuor

原帖由 cjaizss 于 2009-12-24 19:27 发表
第一题，建一个堆，也就是优先级队列
最后一题：2000+[2000/5]+[2000/5^2]+[2000/5^3]+[2000/5^4]=2419

这个公式明显不对嘛。如果把 2000 换成 3，那 3! 就至少含有 3 个圈了。

cjaizss

原帖由 retuor 于 2009-12-24 19:32 发表



这个公式明显不对嘛。如果把 2000 换成 3，那 3! 就至少含有 3 个圈了。

不好意思，算错了。
把开始那个2000去掉

cjaizss

第4题外排序由点意思

cugb_cat

第7题，算法比赛常考的题目
第1题，看算法导论堆排序那张，用大顶堆

heiniaoyuyoulin

第一道题应该用分组的方法，将N数分成m组，每组的元素数目应该远大于n，各组取其前n个，依次循环即可解决。

unistd

原帖由 cjaizss 于 2009-12-24 19:27 发表
第一题，建一个堆，也就是优先级队列
最后一题：[2000/5]+[2000/5^2]+[2000/5^3]+[2000/5^4]=499

讲讲原理。。。。。。

zhaohongjian000

原帖由 cugb_cat 于 2009-12-24 21:26 发表
第7题，算法比赛常考的题目
第1题，看算法导论堆排序那张，用大顶堆

要找最大的前n个吧，应该用小顶堆（最小堆）。

1.首先将前n个数做成小顶堆，O(n)。
2.后面每一个数和小顶堆的首元素比较，若大于，则置换，并保持堆的状态，O(mlogm) (m是剩余的数字个数)。
3.不要求顺序，就到此结束，否则对前n个数进行堆排,O(nlogn)。

感觉这个方法n越接近数据总数的一半效率越高。

zhaohongjian000

1、从N个数中选出n个最大的数，写出思路和实现。
先读入n个，并且排序，队列，就是有序的队列。然后再一个个读，比最大的那个大的时候就FIFO。

------------------------------------------------------------------------------

维持有序队列，效率明显不如堆高。

churchmice

1.这个可以用改进过的quicksort或者用最大堆解决
4.可以使用bitmap sort
/* phase 1: initialize set to empty */
for i = [0, n)
bit = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit == 1
write i on the output file

整数最大值不超过8亿，建立这个bitmap需要8亿/8/1000/1000=100M的空间，考虑到最多重复两次，所以需要200M内存
因而可以考虑处理两次，第一次处理0-4亿的数据，将结果存放在硬盘上。第二次处理5-8亿范围内的数据，将结果存放于硬盘上
详见编程珠玑第一章