实习面试三

2015-06-02

春季开学以来，跟随大流，准备找一份实习工作，攒攒经验，顺便犒劳一下钱包，虽然不是什么大牛级别的人物，但是我对编程还是比较热爱，而且很有钻劲儿，有志于在IT行业有所建树。根据自己的情况，整理了一份简历，还算过的去，至少是通过了B（百度）A（阿里巴巴）T（腾讯）的筛选，由于不同的原因，三个公司都没去成，不过还是攒下了经验，记录下来，为秋季找工作铺垫。

前面已经有了两次面试，这是第三次了，等写完论文把前面的两次面经补上。

出于保密，还是隐去面试企业的信息，只关注我的解题思路。

这次面试的公司虽然不是BAT这样的比较火爆的单位，但是这个单位是我非常尊重的，所以我非常看重，真的非常希望能够进入这家单位实习，更希望毕业能够签这家单位，所有我需要再继续认真努力给自己充电。

隐去了单位的信息，我只谈面试题目，也给出我的想法。

面试题目一手写算法

给一个数组（递增）、一个关键值，找到第一个比关键值大的元素的下标。考察的应该是二分查找，不过要稍微复杂一下，我当时忽略了有重复元素的特殊情况，写出的程序有些问题，提示用递归可能会好一些？我想也是，可是，递归结束条件是什么？面试官给的函数参数列表需要修改一下，干脆我就自己写了一个程序。
刚才试了一下这个程序，还是真不好写，因为递归结束是个什么不好确定，还有就是边界检查问题。

#include <iostream>

using namespace std;

int func(int arr[],int low,int high,int key,int start,int end)
{
    if(low > high)
    {
        if(key < arr[low] && low <= end && low >= start)
            return low;
        else
            return -1;
    }
    int mid = (low + high) / 2;
    if(arr[mid] <= key)
        return func(arr,mid+1,high,key,start,end);
    else
        return func(arr,low,mid-1,key,start,end);
}


int main()
{
    int arr[]= {1,1,2,3,4,5,6,6};
    int key = 1;
    int t = func(arr,0,sizeof(arr)/sizeof(arr[0])-1,key,0,7);
    cout<<t<<endl;
    return 0;
}

有两点问题：
递归结束条件，其实按照这个程序的逻辑，mid+1或者mid-1，只有一个边界移动，所有肯定出现low==high的情况，若把这个条件作为递归结束条件，那么确定结果就要分为两种情况：

第一，mid+1引起的low==high，也就是说mid位置的元素是==或者<关键字的值的，所以新的搜索范围的左边界应该是mid+1，那么此时low==high，那么high位置的元素一定是结果吗？high是也是由mid-1得到的，从程序中的条件可以看出，这个mid位置的元素的，必然是>关键字的值的，所以新的搜索范围的有边界应该是mid-1，这里是不能保证新的high位置的元素值>关键字的值的，但是经过了若干次递归，high还没有变，且low==high了，那么此时可以确定high和low位置的元素小于等于关键字的值，并且high+1这个位置的原始是第一个大于关键字的，那么答案应该是high+1，那么返回high+1？那要low==high是由另外一种情况引起的呢？
第二，mid-1引起的low==high，同样可以分析，mid位置的元素一定是>关键字的值的，所以此时新的搜索范围的有边界应该是mid-1，结果导致low==high，那么low一定是结果吗？再考虑low是怎么得来的，low=mid+1，从程序中可以看出，这里的mid位置的元素的值是<=关键字的值，这里不能保证mid+1位置的元素值一定是>关键字的值的，但是经过若干次递归，low=mid+1的位置一直没变，并且已经到了low==high，那么此时可以确定low或者high位置的元素一定是第一个大于关键字值的元素，也就是此时应该返回low。
再分析两种low==high情况，如果，以low==high为递归退出的条件，那么就必须在里面判断了，第一种情况返回的是high+1，第二种情况返回的是high，不太容易判断；那么再让一点，让low>high，第一种情况是low的位置元素是小于等于关键字的值，再一次递归，就是mid+1，也是low+1，此时low的位置正好是要找的位置。第二种情况，low位置的元素是第一个大于关键字的，再一次递归，也就是mid-1，也是high-1，此时low的位置是要找的位置，所以用low>high作为递归结束条件比较方便。同时还能避免左侧越界问题，对于右侧越界问题，只能靠判断条件了。

越界，给参数列表添加数组左右边界，因为只会出现右越界，所以只判断右侧即可。

其实理解了这个思路，我感觉非递归的方式更好些。下面是非递归的代码，验证过，一样的。

int func(int arr[],int key,int len)
{
    int low,high;
    low = 0;
    high = len-1;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(arr[mid] <= key)
            low = mid +1;
        else
            high = mid -1;
    }
    if(low <len)
        return low;
    else
        return -1;
}

面试题目二手写算法

第二题相对简单一点，给定一个数组，每个数组代表一个间隔的高度，每个间隔的宽度都是一样的,都是1，所有间隔的长也是1，下雨后，两个高的间隔就有水，求下雨后累积水的最大的体积是多少？

我听到这一题的最直接的想法是用栈来实现，因为这个题目跟那个直方图最大矩形面积有些相似。

int func2(int arr[],int len)
{
    stack<int> s;
    bool flag = false;
    int left=0;
    int sum =0;
    for(int i=0;i<len;++i)
    {
        if(!flag)
        {
            if(s.empty())
            {
                s.push(arr[i]);
            }
            else
            {
                if(s.top() > arr[i])
                {
                    flag = true;
                    left = s.top();
                    s.push(arr[i]);
                }
                else
                {
                    s.pop();
                    s.push(arr[i]);
                }
            }
        }
        else
        {
            if(left > arr[i])
                s.push(arr[i]);
            else
            {
                while(!s.empty())
                {
                    sum += left - s.top();
                    s.pop();
                }
                flag = false;
                s.push(arr[i]);
            }
        }
    }
    return sum;
}

最后

感觉没有把自己的实力展现出来，希望进入面试。

面试题目一 手写算法

面试题目二 手写算法

最后

面试题目一手写算法

面试题目二手写算法