阿里在线笔试算法工程师附加题

前几天参加了阿里的在线笔试，报的职位是算法工程师，笔试感觉难度适中，选择题包含数据结构、离散数学、小的智力问题还有一些读程序选结果的题目。其中数据结构和排列组合最多。当时比较慌乱，没做记录。只记下了三个附加题。

第一题很简单。要求实现一个方法，在两个排好序（升序）的整型数组中找到中位数。传入4个参数，分别是两个数组和他们的大小。这个题目既然简单就要写的高效一些。我用的归并排序的思想，将两个数组合并，在合并的过程中找到中位数。并对奇偶分情况讨论，注意偶数情况下有可能出现小数。代码如下：

double findMedianSortedArrays(int a[],int m,int b[],int n)
{
    int sum=m+n;
    double tmp = 0.0;
    if (sum %2==0)
    {
        int pivot=0;
        sum/=2;
        int i=0,j=0;
        while (pivot<sum)
        {
            if (a[i]<b[j])
            {
                tmp=a[i];i++;pivot++;
            }
            else
            {
                tmp=b[j];j++;pivot++;
            }
        }
        if (a[i]<b[j])
            tmp+=a[i];
        else
            tmp+=b[j];
        tmp/=2;
    }
    else
    {
        int pivot=0;
        sum=(sum>>1)+1;
        int i=0,j=0;
        while (pivot<sum)
        {
            if (a[i]<b[j])
            {
                tmp=a[i];i++;pivot++;
            }
            else
            {
                tmp=b[j];j++;pivot++;
            }
        }
    }
    return tmp;
}

第二题是说在2.5D游戏中，各个物体有可能出现重叠和遮挡。例如树、房子等物品。当玩家点击一个地方时，如何判断哪个物体被选中。问题要求是，选取什么样的数据结构和算法，并给出伪代码。这个题我基本不会，但是感觉和图形学里学习的可见性有点像。一个图形学的创始人曾说过，图形学就是排序。意思为当有多个物体需要显示时，哪个物体被遮挡哪个物体显示，排序一下就好了。因此，我就比较无耻的选了数组和排序算法。写了简单的伪代码，希望蒙混一下。

第三题是一个ACM的题，比较难一些。当时截了个图，不知道有没有版权问题。

这个题的难处在于对时间复杂度和空间复杂度的要求。暴力的解法是O(n^2)的，空间复杂度要求不能额外申请与大小n有关d的数组。好在传过来的是一个数组，我们可以从前后同时向中间遍历。我想出的办法是：

用两个临时变量maxl和maxr记录两端向中间遍历时的最大值。max较小的一方采取行动，行动内容为访问下一个元素，如果这个元素小于max，那么max不变，该元素与max的差值为水数量。如果该元素大于max，max更新为该元素。直到两个游标相遇。

代码如下：

#include <iostream>
using namespace std;

int volume(int *height,int n)
{
    int max_l=height[0];
    int max_r=height[n-1];
    int i=0,j=n-1;
    int result = 0;
    while(i!=j)
    {
        if(max_l<=max_r)
        {
            i++;
            if(height[i]<max_l)
                result+=max_l-height[i];
            else
                max_l=height[i];
        }
        else
        {
            j--;
            if(height[j]<max_r)
                result+=max_r-height[j];
            else
                max_r=height[j];
        }
    }
    return result;
}
int main()
{
    int array[]={1,0,2,1,0,1,3,2,1,2,1};
    int result = volume(array,11);
    cout << result << endl;
    return 0;
}

阿里在线笔试算法工程师附加题

原文：http://blog.csdn.net/u010352695/article/details/44901887