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 阅读(687) 评论(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;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理