阿里巴巴笔试题选解

摘要:
阿里巴巴笔试题精选答案——9月22日,阿里巴巴北站题:1.如果有三个节点,可以形成多少叉树?编程问题:3.设计一个最佳算法,以找到n个元素数组中的最大值和最小值。解决方案:应为5;2.一副52张牌,从中抽出两张牌,一张红一张黑的概率是多少?请在三个数组中找到一个元素。由形成的三元组的距离最小。

阿里巴巴笔试题选解

                                                               --9月22日,阿里巴巴北邮站

小题:(部分题目)

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 ]|)

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

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

 

题解:(题解非官方,仅供参考,有错误的地方望指正!谢谢)

1、有三个结点的,可以构成多少个种树形结构?

解:应该是5种;

 阿里巴巴笔试题选解第1张

2、一副牌52(去掉大小王),从中抽取两张牌,一红一黑的概率是多少?

考察概率论知识

解法一: 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

解法二: 全为黑或者全为红是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 次

如图会更加清晰:

阿里巴巴笔试题选解第2张

代码实现:

阿里巴巴笔试题选解第3张阿里巴巴笔试题选解第4张
#include <stdio.h>
#include <stdlib.h>
#define N 8
int main(void)
{
    //int arr[N] = {4, 1, 5, 9, 9, 7, 10};
    int arr[N] = {1,2,3,4,5,6,9,1};
    int iter = 0;
    int cnt = 0;
    for(iter = 0; iter < N ; iter += 2)
    {
        if(++cnt && arr[iter] > arr[iter + 1] )
        {
            int temp = arr[iter];
            arr[iter] = arr[iter + 1];
            arr[iter + 1] = temp;
        }
    }
    int i = 0;
    for(i = 0; i < N; i++)
    {
        printf("%-3d", arr[i]);
    }
    printf("
");
    int myMin = arr[0];
    for(iter = 2; iter < N ; iter += 2)
    {
        if(++cnt && arr[iter] < myMin)
        {
            myMin = arr[iter];
        }
    }
    int myMax = arr[1];
    for(iter = 3; iter < N; iter += 2)
    {
        if(++cnt && arr[iter] > myMax)
        {
            myMax = arr[iter];
        }
    }
    if(N % 2 != 0 && ++cnt && myMax < arr[N - 1]) myMax = arr[N - 1];
    printf("min is %d
", myMin);
    printf("max is %d
", myMax);
    printf("compare times is %d", cnt);
    return 0;
}
View Code

   上面的算法比较次数基本上已经是最优了,但是有朋友提出这样的顾虑,在极端的情况下,每次都做交换,可能会导致程序开销很大,这样的顾虑是对的,其实在上面的算法的基础上,可以不做交换就能找到最大值和最小值。

第3题  改进的算法:

  依旧把数组两两一组分配,不做交换操作,设置一个最大值Max和最小值Min,依次和每一组的两个数据做比较,把较大的值给Max,较小的值给Min,遍历一次就能找到数组的最大值和最小值。

  示例:数组为{(4, 1) , (5, 9) , (9 ,7)  ,(10,2)},经过第一组比较得到Max = 4,Min = 1,其中比较了3次;,经过第二组比较得到Max = 9,Min = 1,其中比较了3次;……到最后Max = 10,Min = 1;比较次数是3 * N/2 = (3N)/2,比较次数没有改变!代码实现不难,就不贴了

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 ]|)

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

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

  第一个关键点: 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|, |x1x3|, |x2x3|) = max(   max(|x1 – x2|, |x1x3|) , |x2x3|)   --公式(2)

  根据公式(1),max(|x1 – x2|, |x1x3|) = 1/2 ( |2x1x2x3| +  |x2x3|),带入公式(2),得到

Distance = max( 1/2 ( |2x1x2x3| +  |x2x3|) , |x2x3| )  

      =1/2 * max(  |2x1x2x3|  , |x2x3| ) + 1/2*|x2x3| //把相同部分1/2*|x2x3|分离出来

      =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 * |x1x3| + 1/2*|x2 – x3|

      =1/2 *(|x1 – x2| + |x1x3| + |x2 – x3|)  //求出来了等价公式,完毕!

  第二个关键点:如何找到(|x1 – x2| + |x1x3| + |x2 – x3|) 的最小值,x1,x2x3,分别是三个数组中的任意一个数,这一题,我只是做到了上面的推导,后面的算法设计是由csdn上的两个朋友想出来的方法,他们的CSDN的ID分别为 “云梦泽” 和 “shuyechengying ”.

算法思想是:

  用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离的Distance ,然后在移动三个数中较小的数组指针,再计算一次,每次移动一个,直到其中一个数组结束为止,最慢(l+ m + n)次,复杂度为O(l+ m + n)

代码如下:

阿里巴巴笔试题选解第5张阿里巴巴笔试题选解第6张
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define l 3
#define m 4
#define n 6
int Mymin(int a, int b, int c)
{
    int Min = a < b ? a : b;
    Min = Min < c ? Min : c;
    return Min;
}

int Solvingviolence(int a[], int b[], int c[])
{
    //暴力解法,大家都会,不用过多介绍了!
    int i = 0, j = 0, k = 0;
    int MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
//    int store[3] = {0};
    int Sum = 0;
    for(i = 0; i < l; i++)
    {
        for(j = 0; j < m; j++)
        {
            for(k = 0; k < n; k++)
            {
                Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
                if(MinSum > Sum)
                {
                    MinSum = Sum;
//                    store[0] = i;
//                    store[1] = j;
//                    store[2] = k;
                }
            }
        }
    }
//    printf("the min is %d
", minABC);
//    printf("the three number is %-3d%-3d%-3d
", a[store[0]], b[store[1]], c[store[2]]);
    return MinSum;

}

int MinDistance(int a[], int b[], int c[])
{
    int MinSum = 0; //最小的绝对值和
    int Sum = 0;  //计算三个绝对值的和,与最小值做比较
    int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值
    int cnt = 0;  //循环次数统计,最多是l + m + n次
    int i = 0, j = 0, k = 0;  //a,b,c三个数组的下标索引
    MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
    for(cnt = 0; cnt <= l + m + n; cnt++)
    {
        Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
        MinSum = MinSum < Sum ? MinSum : Sum;
        MinOFabc = Mymin(a[i] ,b[j] ,c[k]);//找到a[i] ,b[j] ,c[k]的最小值
        //判断哪个是最小值,做相应的索引移动
        if(MinOFabc == a[i])
        {
            if(++i >= l) break;
        }//a[i]最小,移动i

        if(MinOFabc == b[j])
        {
            if(++j >= m) break;
        }//b[j]最小,移动j
        if(MinOFabc == c[k])
        {
            if(++k >= n) break;
        }//c[k]最小,移动k

    }
    return MinSum;
}
int main(void)
{
    int a[l] = {5, 6, 7};
    int b[m] = {13, 14, 15, 17};
    int c[n] = {19, 22, 24, 29, 32, 42};

    printf("
By violent solution ,the min is %d
", Solvingviolence(a, b, c));
    printf("
By Optimal solution ,the min is %d
", MinDistance(a, b, c));
    return 0;
}
View Code

 5这几天有点事,第5题还没仔细研究,要是解出来会第一时间更新博客!有求解方法的朋友欢迎评论!

题目部分摘取自july CSDN网站:http://blog.csdn.net/v_july_v/article/details/11921021

免责声明:文章转载自《阿里巴巴笔试题选解》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Robots.txt 协议—百度之星《从0到1》笔记 第十章 打造帮派文化下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

2.3、Python迭代器、列表解析及生成器(0530)

1、动态语言 sys.getrefcount()      //查看对象的引用计数 增加对象的引用计数场景 对象创建时:以赋值的方式,创建变量名的同时就会创建变量 将对象添加进容器时:类似list.append() 当对象被当作参数传递给函数时 多重目标赋值时:s1 = s2 = s3 = 'abc' 为对象创建另外的变量名 减少引用计数 引用此对象...

JavaScript-基础知识

一、JavaScript-简介Web前端有三层: HTML:从语义的角度,描述页面结构 CSS:从审美的角度,描述样式(美化页面) JavaScript:从交互的角度,描述行为(提升用户体验) JavaScript历史背景介绍 布兰登 • 艾奇(Brendan Eich,1961年~),1995年在网景公司,发明的JavaScript。 开始JavaS...

TCP协议粘包问题详解

TCP协议粘包问题详解前言   在本章节中,我们将探讨TCP协议基于流式传输的最大一个问题,即粘包问题。本章主要介绍TCP粘包的原理与其三种解决粘包的方案。并且还会介绍为什么UDP协议不会产生粘包。   基于TCP协议的socket实现远程命令输入   我们准备做一个可以在Client端远程执行Server端shell命令并拿到其执行结果的程序,而涉及...

句柄类与继承

前一小节《容器与继承》http://blog.csdn.net/thefutureisour/article/details/7744790提到过: 对于容器,假设定义为基类类型,那么则不能通过容器訪问派生类新增的成员;假设定义为派生类类型,一般不能用它承载基类的对象,即使利用类型转化强行承载,则基类对象能够訪问没有意义的派生类成员,这样做是非常危...

boost asio 异步实现tcp通讯

---恢复内容开始--- asioboost 目录(?)[-] 一前言 二实现思路 通讯包数据结构 连接对象 连接管理器 服务器端的实现 对象串行化 一、前言 boost asio可算是一个简单易用,功能又强大可跨平台的C++通讯库,效率也表现的不错,linux环境是epoll实现的,而windows环境是iocp实现的。而tcp通讯是项...

面试准备

编程基础: (关注代码的时间复杂度空间复杂度) 进程间通信方式 线程和进程 线程的状态转化 数组和链表的区别 数据结构学过哪些,回答了数组,链表,然后问他们各自的特点以及适合在什么场景下应用,以及他们的时间复杂度 死锁产生的条件,以及如何避免死锁,银行家算法,产生死锁后如何解决 java内存模型java内存区域 java中创建类的实例有几种方法 死锁的原因...