网站架构变迁,室内设计联盟邀请码免费,网站域名注册价格,wordpress图片自适应1、 海量数据分布在100台电脑中#xff0c;想个办法高校统计出这批数据的TOP10。 方案1#xff1a; s 在每台电脑上求出TOP10#xff0c;可以采用包含10个元素的堆完成#xff08;TOP10小#xff0c;用最大堆#xff0c;TOP10大#xff0c;用最小堆#xff09;。比如求…1、 海量数据分布在100台电脑中想个办法高校统计出这批数据的TOP10。 方案1 s 在每台电脑上求出TOP10可以采用包含10个元素的堆完成TOP10小用最大堆TOP10大用最小堆。比如求TOP10大我们首先取前10个元素调整成最小堆如果发现然后扫描后面的数据并与堆顶元素比较如果比堆顶元素大那么用该元素替换堆顶然后再调整为最小堆。最后堆中的元素就是TOP10大。 2、 1000万字符串其中有些是重复的需要把重复的全部去掉保留没有重复的字符串。请怎么设计和实现 方案1这题用trie树比较合适hash_map也应该能行。 3、 一个文本文件找出前10个经常出现的词但这次文件比较长说是上亿行或十亿行总之无法一次读入内存问最优解。 方案1首先根据用hash并求模将文件分解为多个小文件对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理找出最终的10个最常出现的词。 4、腾讯面试题给40亿个不重复的unsigned int的整数没排过序的然后再给一个数如何快速判断这个数是否在那40亿个数当中 方案1oo申请512M的内存一个bit位代表一个unsigned int值。读入40亿个数设置相应的bit位读入要查询的数查看相应bit位是否为1为1表示存在为0表示不存在。 方案2这个问题在《编程珠玑》里有很好的描述大家可以参考下面的思路探讨一下 又因为2^32为40亿多所以给定一个数可能在也可能不在其中这里我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。 然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1 并将这两类分别写入到两个文件中其中一个文件中数的个数20亿而另一个20亿这相当于折半了 与要查找的数的最高位比较并接着进入相应的文件再查找 再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1 并将这两类分别写入到两个文件中其中一个文件中数的个数10亿而另一个10亿这相当于折半了 与要查找的数的次最高位比较并接着进入相应的文件再查找。 ....... 以此类推就可以找到了,而且时间复杂度为O(logn)方案2完。 附这里再简单介绍下位图方法 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一当集合中数据量比较大时我们通常希望少进行几次扫描这时双重循环法就不可取了。 位图法比较适合于这种情况它的做法是按照集合中最大元素max创建一个长度为max1的新数组然后再次扫描原数组遇到几就给新数组的第几位置上 1如遇到5就给新数组的第六个元素置1这样下次再遇到5想置位时发现新数组的第六个元素已经是1了这说明这次的数据肯定和以前的数据存在着重复。这 种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效 率还能提高一倍。 5、 寻找热门查询 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来每个查询串的长度为1-255字节。假设目前有一千万个记录这些查询串的重复读比较 高虽然总数是1千万但是如果去除重复和不超过3百万个。一个查询串的重复度越高说明查询它的用户越多也就越热门。请你统计最热门的10个查询 串要求使用的内存不能超过1G。 (1) 请描述你解决这个问题的思路 (2) 请给出主要的处理流程算法以及算法的复杂度。 方案1采用trie树关键字域存该查询串出现的次数没有出现为0。最后用10个元素的最小推来对出现频率进行排序。 6、 一共有N个机器每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到个数中的中数 方案1先大体估计一下这些数的范围比如这里假设这些数都是32位无符号整数共有2^32个。我们把0到2^32-1的整数划分为N个范围段每个 段包含2^32/N个整数。比如第一个段位0到(2^32/N) -1第二段为2^32/N到(2^32*2/N)-1…第N个段为2^32(N-1)/N到2^32-1。然后扫描每个机器上的N个数把属于第 一个区段的数放到第一个机器上属于第二个区段的数放到第二个机器上…属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是 O(N)的。下面我们依次统计每个机器上数的个数一次累加直到找到第k个机器在该机器上累加的数大于或等于N^2/2而在第k-1个机器上的累加 数小于N^2/2并把这个数记为x。那么我们要找的中位数在第k个机器中排在第N^2/2 -x 位。然后我们对第k个机器的数排序并找出第个数即为所求的中位数。复杂度是的O(N^2)。 方案2先对每台机器上的数进行排序。排好序后我们采用归并排序的思想将这N个机器上的数归并起来得到最终的排序。找到第N^2/2个便是所求。复杂度是O(N^2lgN^2)的。 7、 最大间隙问题 给定n个实数X1,X2,....Xn求着n个实数在实轴上向量2个数之间的最大差值要求线性的时间算法。 方案1最先想到的方法就是先对这n个数据进行排序然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法 s 找到n个数据中最大和最小数据max和min。 s 用n-2个点等分区间[min,max]即将[min, max]等分为n-1个区间前闭后开区间将这些区间看作桶编号为1,2,...,n-2,n-1且桶 i 的上界和桶i1的下届相同即每个桶的大小相同。每个桶的大小为dblAvrGap(max-min)/(n-1)。实际上这些桶的边界构成了一 个等差数列首项为min公差为ddblAvrgap且认为将min放入第一个桶将max放入第n-1个桶。 s 将n个数放入n-1个桶中将每个元素x[i]分配到某个桶编号为index其中 index (x[i]-min)/dblAvrGap 的下限 1 并求出分到每个桶的最大最小数据。 s 最大间隙除最大最小数据max和min以外的n-2个数据放入n-1个桶中由抽屉原理可知至少有一个桶是空的又因为每个桶的大小相同所以最大间隙 不会在同一桶中出现一定是某个桶的上界和某个桶的下界之间隙且该两桶之间的桶一定是空桶。也就是说最大间隙在桶i的上界和桶j的下界之间产生 j(i1)。一遍扫描即可完成。 1 #include iostream 2 #include vector 3 using namespace std; 4 5 struct Bucket{ 6 double min; 7 double max; 8 int flag; 9 };
10 //桶排序计算最大间隙
11 double MaxGap( double *arr, int len){
12 if( len0 ) return 0;
13 double maxarr[0],minarr[0];
14 for( int i0; ilen; i){ //找最大最小值
15 if( arr[i]max) maxarr[i];
16 if( arr[i]min) minarr[i];
17 }
18
19 vectorBucket bucket(len-1);
20 for( int i0; ilen-1; i){ //初始化桶
21 bucket[i].max mini*(max-min)/(len-1);
22 bucket[i].min min(i1)*(max-min)/(len-1);
23 bucket[i].flag0;
24 }
25
26 double gap(max-min)/(len-1);
27 for( int i0; ilen; i){ //分入桶中
28 int index(int)((arr[i]-min)/gap);
29 if( indexlen-1) index len-2;
30 if( bucket[index].flag0 ){
31 bucket[index].maxarr[i];
32 bucket[index].minarr[i];
33 }
34 if( bucket[index].maxarr[i] )
35 bucket[index].maxarr[i];
36 if( bucket[index].minarr[i])
37 bucket[index].minarr[i];
38 bucket[index].flag1;
39 }
40
41 double maxgap0;
42 double lowbucket[0].max;
43 for( int i0; ilen-1; i){ //找最大间隙
44 while( bucket[i].flag0 ) i;
45 if( ilen-1){
46 double t bucket[i].min-low;
47 maxgap tmaxgap?t:maxgap;
48 lowbucket[i].max;
49 }
50 }
51
52 return maxgap;
53 }
54 int main()
55 {
56 double arr[] {-31,-41,4,-3,4,-1,-97,-93,-23,-84};
57 coutMAX:MaxGap(arr, sizeof(arr)/sizeof(double));
58 return 0;
59 } 8、 将多个集合合并成没有交集的集合给定一个字符串的集合格式如{aaa,bbb,ccc},{bbb,ddd},{eee,fff},{ggg}, {ddd,hhh}。要求将其中交集不为空的集合合并要求合并完成的集合之间无交集例如上例应输出{aaa,bbb,ccc,ddd,hhh}, (eee,fff},{ggg}。 (1) 请描述你解决这个问题的思路 (2) 给出主要的处理流程算法以及算法的复杂度 (3) 请描述可能的改进。 方案1采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合顺序合并将两个相邻元素合并。例如对于{aaa,bbb,ccc}首 先查看aaa和bbb是否在同一个并查集中如果不在那么把它们所在的并查集合并然后再看bbb和ccc是否在同一个并查集中如果不在那么也把它 们所在的并查集合并。接下来再扫描其他的集合当所有的集合都扫描完了并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话首先可以记 录每个节点的根结点改进查询。合并的时候可以把大的和小的进行合这样也减少复杂度。 1 #include iostream 2 #include hash_map 3 #include vector 4 #include string 5 using namespace std; 6 //并查集 7 #define MAX 100 8 int father[MAX]; 9
10 void MakeSet(){
11 for( int i0; iMAX; i){
12 father[i]i;
13 }
14 }
15
16 int FindFather( int x){
17 if( x!father[x] )
18 father[x] FindFather(father[x]);
19 return father[x];
20 }
21
22 void Union( int x, int y){
23 xFindFather(x);
24 yFindFather(y);
25 father[x]y;
26 }
27
28 void UnionSet(vectorvectorstring set){
29 int k0;
30 hash_mapstring, int hash;
31 for( int i0; iset.size(); i){
32 for( int j0; jset[i].size(); j){
33 if( hash.find( set[i][j] ) hash.end() )
34 hash.insert(pairstring, int(set[i][j],k)); //转换成hash存储
35 }
36 }
37
38 MakeSet(); //初始化并查集
39 for( int i0; iset.size(); i){
40 for( int j1; jset[i].size(); j){
41 Union( hash[ set[i][j]], hash[set[i][j-1]] ); //合并
42 }
43 }
44
45 int lenhash.size();
46 vectorint kind;
47 for( int i0; ilen; i)
48 if( ifather[i] )
49 kind.push_back(i); //计算种类
50
51 //输出每一类
52 for( int i0; ikind.size(); i){
53 cout i:endl;
54 hash_mapstring,int::iterator iterhash.begin();
55 for( ;iter!hash.end(); iter){
56 if(father[iter-second]kind[i])
57 cout iter-firstendl;
58 }
59 }
60 }
61
62 int main()
63 {
64 string str1[] {aaa,bbb,ccc};
65 string str2[] {bbb,ddd};
66 string str3[] {eee,fff};
67 string str4[] {ggg};
68 string str5[] {ddd,hhh};
69 vectorvectorstring set(5);
70 set[0].assign(str1,str1sizeof(str1)/sizeof(string));
71 set[1].assign(str2,str2sizeof(str2)/sizeof(string));
72 set[2].assign(str3,str3sizeof(str3)/sizeof(string));
73 set[3].assign(str4,str4sizeof(str4)/sizeof(string));
74 set[4].assign(str5,str5sizeof(str5)/sizeof(string));
75 UnionSet( set );
76 return 0;
77 } 9、 最大子序列与最大子矩阵问题 数组的最大子序列问题给定一个数组其中元素有正也有负找出其中一个连续子序列使和最大。 方案1这个问题可以动态规划的思想解决。设b[i]表示以第i个元素a[i]结尾的最大子序列那么显然b[i1]b[i]0?b[i]a[i1]:a[i1]。基于这一点可以很快用代码实现。 最大子矩阵问题给定一个矩阵二维数组其中数据有大有小请找一个子矩阵使得子矩阵的和最大并输出这个和。 方案1可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素那么在这个范围内其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。 转自http://blog.csdn.net/huangxy10/article/details/8087478 转载于:https://www.cnblogs.com/heyonggang/archive/2012/12/13/2817046.html
