记一次面试

前几天接到国内某大厂的邀请就去参加了面试。

虽然暂时没有换工作的打算，不过就当是查缺补漏了。

两轮技术面试一轮是电话面试，一轮是主程面试，总体下来还是有很多问题没有掌握好。

总结了四个面试中没答好的问题。

排序问题

有一组玩家的分数数据，要求在不排序的情况下求出前100名玩家。

面试过程中这道题完全被不排序这个条件唬住了，实际上不排序指的应该是不完整排序。

面试结束后重新思考了这个问题，这里应该需要的是局部的排序，局部排序我首先想到的是快排。

第一次排序，可以首先从分数中随机取一个值作为基准值，以这个值来进行排序，记录下左右子数组的个数，这样就能够把数组分为两部分，前N名和后M名玩家。这时比较N，M和我们需要的100，N大于100则对前数组再次快排，N小于100则对后数组进行快排。

第二次如何确定基准值呢？我的理解是可以在快排的过程中同时记录左右数组的平均值/中位数等统计值，通过统计值估算100名所在的大致分数区间，以这一区间作为基准，然后一直排序，直到子数组小于某一阈值，再对子数组进行全排序，从而求出具体的前100。

类似的问题我搜索了一下，有人提到计数排序。在这题，我们不知道分数区间，它可能分布在一个非常大的离散范围内，所以我认为计数排序不是一个很好的办法。当然这只是我个人的理解，如果有更好的算法希望能指出来。

动态规划

一个数组中有N个非负数，要求从数组中选择若干个数使它们之和最大，并且要求这些数不能相邻。 

面试之前完全没有准备过算法的问题，本身不是科班出身对这方面也不甚敏感，日常工作也不会接触算法，所以这样的简单问题没有答出来。

考虑0到i共i+1个数的最大和SumMax( 0, i ), 

选择第i个数的情况下，最大和为array[i] + SumMax( 0, i - 2 ); 

不选择第i个数的情况下，最大和为 SumMax( 0, i - 1), 

所以综合两种情况，SumMax( 0, i ) = Max( array[i] + SumMax( 0, i - 2 ), SumMax( 0, i - 1) ) 

得出递推关系后，即可求解这个问题，简单的C++实现如下：

template< int N > 
static int Do( int(&inputArray)[N] ) 
{ 
    if( N == 1 ) 
    { 
        return inputArray[0]; 
    } 
    int maxSumArray[N + 1]; 
    maxSumArray[0] = 0; 
    maxSumArray[1] = inputArray[0]; 
    for( int i = 2; i <= N; ++ i ) 
    { 
        maxSumArray[i] = std::max( inputArray[i-1] + maxSumArray[i-2], maxSumArray[i-1] ); 
    } 
    return maxSumArray[N]; 
} 

装箱问题

装箱问题是一个经典的NP算法问题，虽然从来没有了解过这个问题，不过至少提出了用贪心法来解答。相关内容网上有很多，不详细展开。

右值和右值引用

这是电话面试时提到的问题。关于右值和右值引用的问题，当时看书时只是匆匆浏览了一遍没有详细去理解它，所以面试的时候一知半解不能很好的回答。右值相关的问题等我整理完会详细的叙述。

总结

面试中基础问题都能够很好的回答，C++的基础还是比较牢靠。但是暴露出来的问题是算法相关的问题比较薄弱，虽然面试中不会问太困难的问题，但基本的算法基础还是需要的。

另外面试中也涉及一些渲染有关的问题，一些比较简单的问题虽然答上来了但并不算答得很好。作为游戏程序员而言，虽然不一定会去做渲染相关工作，但还是应该去学习相关知识的。