life02
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  197 随笔 :: 3 文章 :: 37 评论 :: 0 Trackbacks
笔试题

2009.9.12日下午 迅雷2笔试题
一
有一副牌编号0~51，请把这副牌尽可能随机的发到4个人手里
注1：已经有rand()函数可以调用，但是rand()函数开销较大，请尽量少调用

a,b,c,d分别是13个元素的1维数组
函数原型 void deal( int[] a, int[] b, int[] c, int[] d );

二
实现字符串反转的c库函数 char* strrev(char* string)
注1：不可利用其他库函数，算法尽量高效、占用空间少。

三
有10亿个数，这些数的值都在0~1000万之内。实现接口 get_bigger_count( unsigned value )
输入一个值value，返回这10亿个数中比value值大的数的数目。
class order_calculate
{
public:
order_calculate();
~order_calculate();
unsinged get_bigger_count( unsigned value )
}
注1：get_bigger_count接口会被频繁的调用，实现要高效
注2：可以自己往内部任意添加变量和接口
注3：有个现成的接口 unsigned get_value_by_index( int idx ) 可以调用，该接口返回指定索引的value值
     比如 get_value_by_index( 100 )， 返回10亿个数中第100个数的值。该接口开销较大，尽量少调用。



http://topic.csdn.net/u/20090912/20/8c60e06e-321c-49a6-b2cc-59248ba9cf36.html?28642 

posted on 2009-09-13 16:29 life02 阅读(765) 评论(2)  编辑 收藏 引用 所属分类: 笔试

评论

# re: 笔试题 2009-09-14 18:16 life02
第三题正解如下：
这题很明显已经告诉各位了，算法复杂度是o（1），任何其他排序算法都是错的，只有桶排序可行，原因也很明显，符合桶排序的特征，0到1000万的取值范围已经固定了，相对10亿来说1000万是很小了。

所以只要设立0到1000万的桶，中间附加计数即可，什么意思呢，10亿个数据，如果缩小一点：范围是0到10的话
0，1，2，3，4，5，6，7，8，9，10

在每一个桶下面挂一个count,扫描完后，10亿个数据肯定都在这10个桶里（1000万类似）

这样在接下来查询的时候，其实比较空间只有0到1000万，和10亿一点关系都没有,而且每个桶还帮你记着大于该数的个数，所以假定要比较的数值是5，则结果就是5，6，7，8，9，10的count之和。

计算空间最大浪费就是在0到1000万里面，找到你的那个数值，但是总比N要小很多，这个结论拿出去，面试来说，应该可以得满分，至于效率，空间什么的，就自己优化1000万数据的比较算法啦。  回复  更多评论
  

# re: 笔试题 2009-09-18 10:09 life02
#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;


static unsigned int *pindex;

#define L 10000001
unsigned get_bigger_count(unsigned value)
{
assert(value<L-1);
static binit(false);
unsigned int rval(0);
if(!binit)
{
FILE *fp = fopen("datafile", "r+b");
unsigned int i = 0;
unsigned int shu;
pindex = new unsigned int[L];
memset(pindex, 0, sizeof(unsigned int)*L);

while(fscanf(fp,"%ld",&shu)!=-1){
/* cout<<shu<<endl;*/
pindex[shu]++;
}
fclose(fp);
for(i=L-1; i>0; --i)
pindex[i-1] += pindex[i];
}
binit = true;
rval = pindex[value+1];
return rval;
}




int main(){
unsigned un;
un=get_bigger_count(8738787);
cout<<un<<endl;
return 0;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理