2013、2014年阿里巴巴算法工程师校招笔试试题整理

2013、2014年阿里巴巴算法工程师校招笔试试题整理。

013、2014年阿里巴巴算法工程师校招笔试试题整理"

选择题

1、一次内存访问,SSD硬盘访问和SATA硬盘随机访问的时间分别是()

A、几微秒,几毫秒,几十毫秒 B、几十纳秒,几十微秒,几十毫秒

C、几十纳秒,几十微秒,几十毫秒 D、几微秒,几十微秒,几十毫秒

解析:内存访问速度通常在50ns到80ns范围内,SSD硬盘的访问速度一般是SATA硬盘的一千多倍,所以答案选C

2、8进制数256,转化成7进制数是(B)

A、356 B、336 C、338 D、346
解析:进制转换
八进制256转换为十进制:2*8*8 + 5*8 + 6*1 = 174
十进制174转换为七进制:336
答案:D

3、有一虚拟存储系统,若进程在内存中占3页(开始时内存为空),若采用先进先出页面澹算法,当执行如下访页页号序列后1,2,3,4,1,2,5,1,2,3,4,5,会产生(?)次缺页?

解析:
输入:1,2,3,4,1,2,5,1,2,3,4,5
先进先出,就是保存最近3个访问的记录在内存中
, , <—1 中断1次
, ,1<—2 中断1次
, 1,2<—3 中断1次
1,2,3 <—4 中断1次
2,3,4 <—1 中断1次
3,4 ,1<—2 中断1次
4,1,2<—5 中断1次
1,2,5<—1 命中,不中断
2,5,1 <—2 命中,不中断
5,1,2<—3 中断1次
1,2,3 <—4 中断1次
2,3,4 <—5 中断1次
3,4,5
累计中断12次

延伸题目:

在5个页框上使用LRU页面替换算法,当页框初始为空时,引用序列为0、1、7、8、6、2、3、7、2、9、8、1、0、2,系统将发生(C)次缺页
A、13 B、12 C、11 D、8
解析:
Least Recently Used 是指最近最少使用的页面被先换出,因此不是先进先出的机制,在淘宝面试题目中也出现过
分析:缺页为:0、1、7、8、6、2、3、9、8、1、0,共11次
参考的链接:http://www.cnblogs.com/freeyiyi1993/archive/2013/05/18/3084956.html

4、有3个节点的二叉树可能有(A)种

A、5 B、13 C、12 D、15
解析:不考虑节点的排列组合
leetcode有一样的题目

5、从一副牌(52张,不含打小怪)里抽出两张牌,其中一红一黑的概率是(D)

A、25/51 B、1/3 C、1/2 D、26/51
解析: 52张牌从中抽两张,就是C522种情况,一红一黑是C261* C261种情况,概率P= C261 * C261 /C522 =26/51
一定要注意,第一次抽完牌之后,有个牌的数目已经减少了。

6、某网络的IP地址空间为192.168.5.0/24,采用定长子网划分,子网掩码为255.255.255.248,则该网络的最大子网个数、每个子网内最大可分配地址个数各位(C)

A、8,32 B、32,8 C、32,6 D、8,30
解析:
IP地址空间为192.168.5.0/24是一个c类IP地址块(其中的24表示子网掩码的前24位为1,255.255.255.0),其默认子网掩码为255.255.255.0。若采用变长子网划分,子网掩码255.255.255.248的二进制表示为1111 1111.1111 1111.1111 1111.1111 1000,它是在255.255.255.0的基础上,向原主机号借用了5个比特位作为新的子网号,因此该网络的最大子网个数为2^5=32个,每个子网内的最大可分配地址个数=2^(32-29)-2=2^3-2=8-2=6 个,其中“-2“表示主机号全0的地址被保留用于标志子网本身,以及主机号全1的地址被保留用作 该子网的广播地址。

7、判断有向图是否存在回路,利用(A)方法最佳

A、拓扑排序 B、求最短路径
C、求关键路径 D、广度优先遍历
知识点:拓扑排序
一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

8、阿里巴巴有相距1500km的机房A和B,现有100GB数据需要通过一条FTP连接在100s的时间内从A传输到B。已知FTP连接建立在TCP协议之上,而TCP协议通过ACK来确认每个数据包是否正确传送。网络信号传输速度2*108m/s,假设机房间带宽足够高,那么A节点的发送缓冲区可以设置为最小(A)

A、18M B、12M C、6M D、24M
解析:
TCP协议原理:TCP每发送一个报文段,就启动一个定时器,如果在定时器超时之后还没有收到ACK确认,就重传该报文。

数据包由A的缓冲区发往B,B在收到数据包以后,回发一个ACK确认包给A,之后A将该数据包从缓冲区释放。因此,该数据包会一直缓存在A的缓冲区,直到一个ACK确认为止。题目要求在100s内发送100GB数据,网络的传输速率至少是1G/s,某个数据包n在A中缓存的时间就是数据包n从A到B,再加上该数据包的ACK从B到A的时间:2*1500km/(2*108m/s)=1.5*10-2s,该段时间A中缓存的数据量至少是1G/s*1.5*10-2s约为15M

个人感觉这种方法不是十分准确,因为TCP连接有滑动窗口机制,可以在未收到ACK的时候继续发送数据,所以极端情况下A节点的发送缓冲区可以再减少一半,即在7.5M左右。不过题目里并没有说到滑动窗口机制,而是说通过ACK来确认每个数据报是否正确传送,所以应该不考虑这种极端情况。

9、假设有每个网络结点,两两之间建立相互通信之后可以记录(保存)对方的全部信息,

现在一个网络有17个结点,要使每个结点都保存其它所有结点的全部信息,至少要建立多少次通信?
解析:
假设有n个节点,直观的按照1-2-···-(n-1)-n传播顺序,最后n-1和n获得了所有节点的信息,然后取其中任一节点与1、2、···、n-2这些节点交换信息,即可让所有节点获得所有信息,这样通讯次数=n-1+n-2=2n-3;

如果分成两个组呢,假设两个组的节点个数分别为n1和n2,则每个组首先需要按序传播信息N1=n1-1+n2-1,然后第一组最后两个节点和第二组的最后两个节点就获得了各自组的所有信息,这四个节点两两交换信息,需要N2=2次,则这四个节点获得了两个组所有节点信息,然后取任一节点与每个组剩下的节点(分别是n1-2,n2-2)交换信息N3=n1-2+n2-2,则通讯任务完成,总共通讯次数N=N1+N2+N3=2n1-3+2n2-3+2=2(n1+n2)-4=2n-4;

如果分成三个组,同样的分析N=2n1-3+2n2-3+2n3-3+6=2n-3,其中6表示三个组的最后两个节点交换信息需要6次;

那如果分的组数更多呢,假设分为g组(g>=4),同上分析N=2n-3g+M,其中M表示g个组的最后两个节点交换信息所需要的最少次数。假设把这些点的通讯按照两个组的模式来处理,则M=2*(2g-4),N=2n+g-8>=2n-4。假设按三个组的模式来处理,则M=2*(2g-3),N=2n+g-6>=2n-2,可见它们都是大于等于2n-4,而且随着g的变大通讯次数也会增多。
所以最优的情况就是在分成两个组或者四个组的时候取到,最优情况下通讯次数为2n-4.

10(多选)、有朋自远方来,他乘火车,轮船,汽车,飞机来的概率分别是0.3,0.2,0.1,0.4,坐各交通工具迟到的概率分别是1/4,1/3,1/12,0,下列语句中正确的是(CD)

A、如果他准点,那么乘飞机的概率大于等于0.5
B、坐陆路(火车,汽车)交通工具准点机会比坐水路(轮船)要低
C、如果他迟到,乘火车的概率是0.5
D、如果他准点,坐轮船或汽车的概率等于坐火车的概率
解析:
设A1={坐火车},A2={坐轮船},A3={坐汽车},A4={坐飞机},B={迟到}
P(A1)=0.3
P (A2) =0.2
P (A3)=0.1
P (A4)=0.4
P(B|A1)=1/4
P(B|A2)=1/3
P(B|A3)=1/12
P(B|A4)=0
用全概公式得:
P(B)=0.3*1/4+0.2*1/3+0.1*1/12+0.4*0=3/20
乘火车来的概率用逆概公式得:
P(A1|B)=P(A1)*P(B|A1)/P(B)=1/2

11、有个苦逼的上班族,他每天忘记定闹钟的概率为0.2,上班堵车的概率为0.5,如果他既没定闹钟上班又堵车那他迟到的概率为1.0,如果他定了闹钟但是上班堵车那他迟到的概率为0.9,如果他没定闹钟但是上班不堵车他迟到的概率为0.8,如果他既定了闹钟上班又不堵车那他迟到的概率为0.0,那么求出他在60天里上班迟到的期望。

解析:
定闹钟概率0.8 未定闹钟概率0.2 堵车概率0.5 不堵车概率0.5
迟到概率 定闹钟 未定闹钟
堵车 0.9 1
不堵车 0 0.8
定闹钟迟到次数期望=0.8*(0.5*0.9+0.5*0)=0.8*0.5*0.9=0.36
不定闹钟迟到次数期望=0.2*(0.5*1+0.5*0.8)=0.18
所以迟到次数期望=0.36+0.18=0.54
60天迟到次数期望=60*0.54=32.4

12、有一堆石子共100枚,甲乙轮流从该堆中取石子,每次可取2、4或6枚,若取得最后的石子的玩家为赢,若甲先取,则(C)

A、谁都无法取胜 B、乙必胜 C、甲必胜 D、不确定
分析:
先取的人只需要保证最后剩8枚就胜了。而要保证最后剩8枚,则必须要保证每一个回合内取的数是一个可控的固定数,显然这个数字是8,所以只需要保证第一次取完后,剩下的数字是8的倍数,就一定能胜。100除以8余数为4,故而,甲先取4枚,之后每一个回合所取数与上一个回合乙所取数之和为8,就能保证必胜。

13、假定一个二维数组的定义语句为“int a[3][4]={{3,4},{2,8,6}};”,则元素a[1][2]的值为(A)

A、6 B、4 C、2 D、8

14、下列有关图的遍历说法中,不正确的是(C)

A、有向图和无向图都可以进行遍历操作
B、基本遍历算法两种:深度遍历和广度遍历
C、图的遍历必须用递归实现
D、图的遍历算法可以执行在有回路的图中

解析:
C肯定是不正确的,用队列辅助的话,可以不必使用递归实现
A对的,B对的,遍历并没有显示是否是有向,
D应该是对的,只需要对访问过的节点进行标记,也就不用考虑是否有回路,或者说,无向图本身就不用考虑是否有回路
知识点:图的深度遍历和广度遍历的递归和非递归实现

15、在16位机器上跑下列foo函数的结果是(B)

void foo()
 {
   int i = 65536;
    cout << i<<”,”;
      i = 65535;
      cout << i;
 }

A、-1,65535 B、0,-1 C、-1,-1 D、0,65535

解析:
16位机器的int型变量为16位
16位int的表示范围:-32768到32767
65536(十进制) = 10000000000000000(二进制)
65535(十进制) = 1111111111111111 (二进制)
上面是原码表示
转换为补码,除了最高位,其它位取反,加一
补码表示:分别为0和-1

16、有一段年代久远的C++代码,内部逻辑复杂,现在需要利用其实现一个新的需求,假定有以下可行的方案,应当优先选择(D)

A、修改老代码的接口,满足新的需求
B、将老代码抛弃,自己重新实现类似的逻辑
C、修改老代码的内部逻辑,满足新的需求
D、在这段代码之外写一段代码,调用该代码的一些模块,完成新功能需求

17、设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,且要求三趟归并完成排序,问归并路数最少为(D)

A、8 B、7 C、6 D、5
**分析:**m个元素k路归并的归并趟数s=logk(m),代入数据:logk(100)≦3

18、一个优化的程序可以生成一n个元素集合的所有子集,那么该程序的时间复杂度是(B)

A、O(n!) B、O(2 n ) C、O(n 2 ) D、O(nlog n)

19、2-3树是一种特殊的树,它满足两个条件:

(1)每个内部节点有两个或三个子节点;
(2)所有的叶节点到根的路径长度相同;
如果一颗2-3树有9个叶节点,下列数量个非叶节点的2-3树可能存在的有(BE)
A、8 B、7 C、6 D、5 E、4

分析:根据条件(2),叶节点只能在同一层,根据条件(1),上一层的父节点只能是3个或4个,只能是如下图所示的两种结果
这里写图片描述
这里写图片描述

20、下列有关进程的说法中,错误的是(ABC)

A、进程与程序是一亿对应的 B、进程与作业时一一对应的
C、进程是静态的 D、进程是动态的过程

21、下列函数定义中,有语法错误的是(D)

A、void fun(int x, int y){x = *y;}
B、int * fun(int *x, int y){return x += y;}
C、void fun(int *x, int y){*x += y;}
D、void fun(int x, int y){*x = *y;}

解答题:

1、有一个算法,查找n个元素的的数组的最大值和最小值,要比较2n次;请写一个最高效的算法,并说明他要比较的次数。请注意复杂度的常数 (不用写代码,说明步骤和过程即可,要定出比较的次数,没写不给分)

解析:
分析:已知的比较2n次的方法,显然是将每个元素和最大值、最小值各比一次,要减少比较次数,可以有多种优化方法:

方法一:一个元素先和最大值比较,如果比最大值大,就不用再和最小值比较(或者先和最小值比较,如果比最小值小,就不用再和最大值比较),一般情况下,这种优化后的比较次数一定会少于2n

方法二:把数组两两一对分组,如果数组元素个数为奇数,就最后单独分一个,然后分别对每一组的两个数比较,把小的放在左边,大的放在右边,这样遍历下来,总共比较的次数是 N/2 次;在前面分组的基础上,那么可以得到结论,最小值一定在每一组的左边部分找,最大值一定在数组的右边部分找,最大值和最小值的查找分别需要比较N/2 次和N/2 次;这样就可以找到最大值和最小值了,比较的次数为N/2 * 3 = (3N)/2 次

2、有三个非递减序列的数组a[l]、b[m]、c[n],求他们之间的最小距离。已知距离的定义如下:distance = max(|a[i]-b[j]|, |a[i]-c[k]|, |b[j]-c[k]|)

解析:
这道题目有两个关键点:

第一个关键点:
max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 –公式(1)
我们假设x1=a[ i ],x2=b[ j ],x3=c[ k ],则
Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) –公式(2)
根据公式(1),max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2×1 – x2– x3| + |x2 – x3|),带入公式(2),得到
Distance = max( 1/2 ( |2×1 – x2– x3| + |x2 – x3|) , |x2 – x3| )
=1/2 * max( |2×1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分1/2*|x2 – x3|分离出来
=1/2 * max( |2×1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一个整体,使用公式(1)
=1/2 * 1/2 ((|2×1 – 2×2| + |2×1 – 2×3|) + 1/2|x2 – x3|
=1/2 |x1 – x2| + 1/2 |x1 – x3| + 1/2*|x2 – x3|
=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出来了等价公式,完毕!

第二个关键点:
如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值,x1,x2,x3,分别是三个数组中的任意一个数,算法思想是:
用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离的Distance ,然后在移动三个数中较小的数组指针,再计算一次,每次移动一个,直到其中一个数组结束为止,最慢(l+ m + n)次,复杂度为O(l+ m + n).

3、在黑板上写下50个数字:1至50。在接下来的49轮操作中,每次做如下动作:选取两个黑板上的数字a和b檫去,在黑板上写|b-a|。请问最后一次动作之后剩下数字可能是什么?为什么?

解析:
第一步:奇偶分析,证明结果不可能为偶数
有以下三种操作:
1. | 奇 – 偶 | = 奇
2. | 偶 – 偶 | = 偶
3. | 奇 – 奇 | = 偶
也就是说每次操作减少0个或者2个奇数。
而原有 1,3,5,…,49 共25个奇数
所以以上操作知道剩余一个数时,此数必为奇数

第二步:构造所有奇数的解
首先注意到对于 a, a+1, b, b+1 四个数,在操作
| (a+1) – a | = 1
| (b+1) – b | = 1
| 1 – 1 | = 0
后,化为了0
而0与任意数k执行以上操作 | k – 0 | = k,无影响。
总结为自然语言就是“两个连续整数对,可以直接忽略”。
更进一步总结为“偶数个连续整数对,可以直接忽略”。
然后开始构造了:
需要得到结果2k-1,其中k=1,…,25
我们就先把1和2k拿出来,
则余下了 2,3,4,…,2k-1, 2k+1,…50
一共24个连续整数对,
根据我们刚才的结论,这是可以直接忽略的。
所以,得到了 | 2k – 1 | = 2k-1

4、(4分)已知如下代码,并在两个线程中同时执行f1和f2,待两个函数都返回后,a的所有可能值是哪些?

int a = 2, b = 0, c = 0;
void f1()                         void f2()
{                                 {
    a = a * 2;                        c = a + 11;
    a = b;                            a = c;
}                                 } 

分析:
考虑四行代码的执行顺序即可
(1)b=a*2,c=a+11,a=c,a=b a=4
(2)b=a*2,c=a+11,a=b,a=c a=13
(3)b=a*2,a=b,c=a+11,a=c a=15
(4)c=a+11,a=c,b=a*2,a=b a=26

5、文件分配表FAT是管理磁盘空间的一种数据结构,用在以链接方式存储文件的系统中记录磁盘分配和追踪空白磁盘块,整个磁盘仅设一张FAT表,其结构如下所示,如果文件块号为2,查找FAT序号为2的内容得知物理块2的后继物理块是5,再查FAT序号为5的内容得知物理块5的后继物理块是7,接着继续查FAT序号为7的内容为“Λ”,即该文件结束标志,

这里写图片描述
假设磁盘物理块大小为1KB,并且FAT序号以4bits为单位向上扩充空间。请计算下列两块磁盘的FAT最少需要占用多大的存储空间?

分析:
(1)磁盘块大小为1KB,540MB的硬盘可以分成540MB/1KB=5.4*105个磁盘块,因此至少需要5.4*105<220个编号,需要20bit存储空间
(2)同理,1.2G至少需要1.2*106<221个编号,为21bit,由于FAT序号以4bits为单位向上扩充,因此需要24bit存储空间

6、有一个怪物流落到一个荒岛上,荒岛上有n条鳄鱼。每条鳄鱼都有实力单独吃掉怪物。但是吃掉怪物是有风险的,会造成体力值下降,然后会有可能被掉其他鳄鱼吃。问,最后那个怪物是危险的还是安全的?

解析:
F(n)表示n条鳄鱼时,怪物的安全状态。1表示安全,0表示不安全。
鳄鱼吃掉怪物后,变成怪物。
n=1时,怪物不安全,F(1)=0
n=2时,第一条鳄鱼吃掉怪物后,会被另一条吃掉。所怪物是安全的。F(2)=1
n=3时,第一条鳄鱼吃掉怪物后,另外两条都不敢吃第一条鳄鱼。F(3)=0

由上面的推导可见,若F(n-1)为安全状态,那么一条鳄鱼可以肆无忌惮地吃掉怪物;如果F(n-1)为不安全状态,那么就没有鳄鱼敢吃怪物。
F(n)= 1 if F(n-1)=0
F(n)=0 if F(n-1)=1
再由初始F(1)=0,F(2)=1可以得到:
n为奇数是不安全,n为偶数时安全

7、有N-1个群众和1个明星,所有的群众都认识该明星,但明星不认识任何一个群众,群众之间是否认识未知。假如你是一个机器人,具有询问一个人是否认识另外一个人的功能,请设计一个最佳算法,在这N个人中最快地找到该明星。

解析:
其实解法很简单,假设有1,2,3,4,5个人
从1开始,问1是否认识2
如果认识,留下2,淘汰1
如果不认识,留下1,淘汰2
之后留下的继续询问3…….
最终剩下的那个就是所谓的明星。
这种解法利用的是减小数据规模的思路,不断将问题的解集合缩小,最终得到解。和从n个数中找到出现次数大于n/2的那个问题很类似。

void findmin(int 
*a,int n)
{  int i,find=0;
   for(i=1;i<n;i++)
   {
 if(a[find]>a[i])
 {
  find=i;
 }
   }
 printf("%dn",find+1);
}

8、这道题的大意是:有一个淘宝商户,在某城市有n个仓库,每个仓库的储货量不同,现在要通过货物运输,将每次仓库的储货量变成一致的,n个仓库之间的运输线路围城一个圈,即1->2->3->4->…->n->1->…,货物只能通过连接的仓库运输,设计最小的运送成本(运货量*路程)达到淘宝商户的要求,并写出代码。

解析:
http://blog.csdn.net/l_f0rm4t3d/article/details/23967995
假设n个仓库的初始储货量分别为warehouse[1],warehouse[2],…,warehouse[n]
计算平均储货量
average = (warehouse[1]+warehouse[2]+…+warehouse[n])/n
就算出来了最终的结果中,每个仓库应该有的存量
首先,从仓库1向仓库n运送k;
然后,从1到n-1,依次向下运送某一特定值,使得每一个仓库的余量都为average,剩下的问题就是求总代价的最小值了。
设第0步从1仓库向n仓库(注意因为是圆圈,所以路径长度是1)运出k存量,k可以为负,如果为负数,意味着从n向1运输|k|存量,然后从循环,从(1到n-1),从i仓库向i+1仓库运输,运输的量需要保证i仓库在运输完毕后等于average
第0步(从仓库1向仓库n运送k):花费代价为 |k|,
第1步(确保仓库1的余量为average):需要花费代价为|warehouse[1]-average-k|,也就是从1向2伙从2向1运输
第2步(确保仓库2的余量为average):代价为 |warehouse[2]+warehouse[1]-average-k-average|=|warehouse[1]+warehouse[2]-2*average-k|
…n-1.
第n-1步:代价为|warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k|,此时,仓库n剩下的货物量:
(warehouse[n]+k)+warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k=(warehouse[1]+warehouse[2]+…+warehouse[n])-(n-1)*average=average

刚好也满足,其实这里不用推导,因为平均值是算好的,所以最胡一定是刚好完成的。
总的代价为:
不妨令sum[i] = warehouse[1]+warehouse[2]+…+warehouse[i]-i*average
则,总代价可表示为:|k|+|sum[1]-k|+|sum[2]-k|+…+|sum[n-1]-k|
这个式子可以看成在水平数轴上寻找一个点k,使得点k到点0,sum[1],sum[2],sum[3],…,sum[n-1]的距离之和最小,显然k应该取这n个数的中位数。至此问题解决。

9、战场上不同的位置有N个战士(n>4),每个战士知道当前的一些战况,现在需要这n个战士通过通话交流,互相传达自己知道的战况信息,每次通话,可以让通话的双方知道对方的所有情报,设计算法,使用最少的通话次数,使得战场上的n个士兵知道所有的战况信息,不需要写程序代码,得出最少的通话次数。

和选择题第9题一是一样的。

10、补全反转数组的代码,如A{1,2,3,4}反转之后A{4,3,2,1}

void f(int *A,int n)
{
int i,temp;
for(i=0;i

算法工程师 附加题】

请设计一个算法,在满足质因数仅为3,5,7或其组合的数中,找出第K大的数。比如K=1,2,3时,分别应返回3,5,7。要求算法时间复杂度最优。
解析:
我们可以用3个队列来维护这些数。第1个队列负责乘以3,第2个队列负责乘以5, 第3个队列负责乘以7。算法描述如下:
1. 初始化结果res=1和队列q3,q5,q7
2. 分别往q3,q5,q7插入1*3,1*5,1*7
3. 求出三个队列的队头元素中最小的那个x,更新结果res=x
4. 如果x在:
q3中,那么从q3中移除x,并向q3,q5,q7插入3*x,5*x,7*x
q5中,那么从q5中移除x,并向q5,q7插入5*x,7*x
q7中,那么从q7中移除x,并向q7插入7*x
5. 重复步骤3-5,直到找到第k个满足条件的数
注意,当x出现在q5中,我们没往q3中插入3*x,那是因为这个数在q5中已经插入过了。

最优解:
其实当我们第一次看到这个题,都会想到K是不是一个可以求解的数。
但马上困难就出现了,我们不知道如何为3^x,5^y,7^z排序。
对数学较敏锐的人会马上想出方法:
5^y=3^(log3(5)*y)
7^z=3^(log3(7)*z)
这样一来:
a(n)=3^x*5^y*7^z=3^(x+log3(5)*y+log3(7)*z)
就只需要对x+log3(5)*y+log3(7)*z的第K大的数进行求解。
因为这里x,y,z之间是固定比例,很容易做。

【附加题】淘宝上每天都产生大量的用户行为,比如搜索、收藏、购买等等,设计一个方案,根据这些历史用户行为,来推断用户的性别。

参考:

http://blog.csdn.net/thebestdavid/article/details/11975809
http://blog.163.com/yichangjun1989yichangjun1989yichangjun1989@126/blog/static/1319720282014518222755/
http://www.sjsjw.com/kf_www/article/023165ABA015253.asp
http://www.cnblogs.com/ksedz/p/3346294.html

作者:jimmybao0730

链接:http://blog.csdn.net/linglun3/article/details/44835223

本文采用「CC BY-SA 4.0 CN」协议转载自互联网、仅供学习交流,内容版权归原作者所有,如涉作品、版权和其他问题请给「我们」留言处理。

(0)
上一篇 2016-11-08 06:30
下一篇 2016-11-16 05:50

相关文章

关注我们
关注我们
分享本页
返回顶部