阿里巴巴工程师算法与数据四道笔试题及答案

1、 三个节点可以组成多少种树？

2、 一副牌共有 52 张（不包括大王和大王）。从中抽出两张牌，一张红一张黑的概率是多少？

编程问题：

3、设计一个最优算法，用于查找 n 元素数组中的最大值和最小值。我们知道一种需要 2n 次比较的方法。请给我们一个更好的算法。应特别注意优化时间复杂度常数。

4。存在三个已知的升序整数数组a[l]、b[m]和c[n]。在三个数组中分别找到使三元组距离最小的元素。三元组距离的定义为：假设a[i]、b[j]、c[k]是三元组，则距离为：

 **Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k]|, |b[ j ] – c[ k ]|)**

请设计一个最优算法求最小三元组距离并分析时间复杂度。

解决方案：（该方案非官方，仅供参考，如有错误请指正！谢谢）

1、三个节点可以组成多少个树结构？

说明：应该有5种；

2、 一副牌共有 52 张（大小王除外）。你抽到两张牌，一张红牌，一张黑牌的概率是多少？

测试你的概率论知识

解决方案1：

从52张牌中抽出两张，即情况C(2,52)。一红一黑是 C(1,26) * C(1, 26) 物种

P

= [C(1,26) * C(1,26) ] / C(2,52) = 26 * 26 / (26 * 51) = 26/51

解2：

全黑或全红的情况是C(2,26)。由于它是黑色和红色，所以必须乘以 2

P = 1 – C(2.26) / C(2.52) – C(2.26) / C(2.52) = 1 – 2 * ( 26 * 25)/ (51 * 52) = 1 – 25/51 = 26/51

3. 设计一个最优算法，用于查找 n 元素数组中的最大值和最小值。我们知道一种需要 2n 次比较的方法。请给我们一个更好的算法。应特别注意优化时间复杂度常数。

解决方案：将字段分组。如果数组元素的数量是奇数，则将其除以一。然后将每组中的两个数字匹配起来，较小的放在左边，较大的放在左边。右边，经过这样的遍历，总共比较次数是N/2次；根据前面的分组，可以得出结论，最小值必须在每组的左边部分找到，最大值必须在数组的右边部分，必须比较最大值和最小值N/2次和N/2次；这样就可以求出最大值和最小值。比较重复次数为

N/2*3 = (3N)/2 次

会更清晰如图：

代码实现：

4、 三个升序整数数组和[l]、b[m]和c[n]是已知的。在三个数组中分别找到使三元组距离最小的元素。三元组距离的定义为：假设a[i]、b[j]和c[k]是三元组，则距离为：

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 ]，则

距离 = max(|x1– x2|, |x1– x3|, |x2– x3|) = max( max(|x1– x2|, |x1– x3|) , |x2– x3|) – 公式 (2 )

根据公式(1)，max(|x1– x2|, |x1– x3|) = 1/2 ( |2x1– x2– x3| + |x2– x3|)，将其转换为公式 ( 2 ) ，得到

**距离 **= max( 1/2 ( |2x1– x2– x3| + |x2– x3|) , |x2– x3| )

=1/2 * max( | 2x1 – x2– x3| , |x2– x3| )+ 1/2|x2– x3|//分离相同部分 1/2|x2– x3|

= / 1 2 * max( |2x1– (x2+ x3)| , |x2– x3| )+ 1/2|x2– x3|//将(x2+ x3)视为整体并使用公式(1) *

=1/2 * 1/2 ((|2x1– 2x2| + |2x1– 2x3|)+ 1/2|x2– x3|**

= 1 /2 |x1– x2| + 1/2 * |x1– x3| + 1/2|x2– x3|

*=1/2 (|x1– x2| + |x - x3 | + |x2- x3 的最小值| 对于c中最小的数，计算一次它们最大距离的Distance，然后将字段指针移动到三个数中较小的一个并再次计算，移动一次一个，直到其中一个字段结束，最慢(l+ m + n)次，复杂度为O(l+ m +n)

代码如下：