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

2019-06-0410:43:58数据结构与算法Comments2,365 views字数 1786阅读模式
阿里巴巴算法、数据工程师四个笔试题及答案

1、有三个结点的,可以构成多少个种叉树?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

2、一副牌52张(去掉大小王),从中抽取两张牌,一红一黑的概率是多少?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

编程题:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

3、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

4、已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,是的组成的三元组距离最小。三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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

请设计一个求最小三元组距离的最优算法,并分析时间复杂度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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

题解:(题解非官方,仅供参考,有错误的地方望指正!谢谢)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

1、有三个结点的,可以构成多少个种树形结构?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

解:应该是5种;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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

2、一副牌52张(去掉大小王),从中抽取两张牌,一红一黑的概率是多少?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

考察概率论知识文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

解法一:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

52张牌从中抽两张,就是 C(2,52)种情况,一红一黑是C(1,26) * C(1,26)种文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

P文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

= [C(1,26) * C(1,26) ] / C(2,52) = 26 * 26 / (26 * 51) = 26/51文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

解法二:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

全为黑或者全为红是C(2,26)种情况,由于是黑和红两种,所以要乘以2文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

3、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

解:把数组两两一对分组,如果数组元素个数为奇数,就最后单独分一个,然后分别对每一组的两个数比较,把小的放在左边,大的放在右边,这样遍历下来,总共比较的次数是N/2次;在前面分组的基础上,那么可以得到结论,最小值一定在每一组的左边部分找,最大值一定在数组的右边部分找,最大值和最小值的查找分别需要比较N/2次和N/2次;这样就可以找到最大值和最小值了,比较的次数为文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

N/2*3 = (3N)/2次文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

如图会更加清晰:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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

代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

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

4、已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,是的组成的三元组距离最小。三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j] – c[ k ]|)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

请设计一个求最小三元组距离的最优算法,并分析时间复杂度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

解:这道题目有两个关键点:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

第一个关键点:max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 –公式(1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

我们假设x1=a[ i ],x2=b[ j ],x3=c[ k ],则文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

Distance = max(|x1– x2|, |x1– x3|, |x2– x3|) = max( max(|x1– x2|, |x1– x3|) , |x2– x3|) –公式(2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

根据公式(1),max(|x1– x2|, |x1– x3|) = 1/2 ( |2x1– x2– x3| + |x2– x3|),带入公式(2),得到文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

**Distance **= max( 1/2 ( |2x1– x2– x3| + |x2– x3|) , |x2– x3| )文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

=1/2 * max( |2x1– x2– x3| , |x2– x3| )+ 1/2|x2– x3|//把相同部分1/2|x2– x3|分离出来文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

=1/2 * max( |2x1– (x2+ x3)| , |x2– x3| )+ 1/2|x2– x3|//把(x2+ x3)看成一个整体,使用公式(1)*文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

=1/2 * 1/2 ((|2x1– 2x2| + |2x1– 2x3|)+ 1/2|x2– x3|**文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

=1/2 |x1– x2| + 1/2 * |x1– x3| + 1/2|x2– x3|文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

*=1/2 (|x1– x2| + |x1– x3| + |x2– x3|)//求出来了等价公式,完毕!文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

第二个关键点:如何找到(|x1– x2| + |x1– x3| + |x2– x3|) 的最小值,x1,x2,x3,分别是三个数组中的任意一个数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

算法思想是:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离的Distance,然后在移动三个数中较小的数组指针,再计算一次,每次移动一个,直到其中一个数组结束为止,最慢(l+ m + n)次,复杂度为O(l+ m +n)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html

阿里巴巴算法、数据工程师四个笔试题及答案
阿里巴巴算法、数据工程师四个笔试题及答案
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13357.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/13357.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定