微软实习生面试小记

发表于

这次微软实习生（软件工程师）面试我参加了3轮，都是通过Skype线上面的，前两轮主要针对写代码的能力和算法的能力（注重在实现）。最后一轮考察的是程序的设计思路和算法的设计思路（注重在思路）。作为一个本科和直博时期都不是计算机专业的伪程序员加菜鸡，感觉自己基本上被虐的很惨。

第一轮

先是让我自我介绍然后问了问基本情况，就开始打开白板做题了。

第一题：进制转换

说实话，第一题很简单，将十进制整数转换成N进制数，我说这个就是通过除法和取余数就可以解决了。然后给了我一个C++函数的框架，让我实现。思路大家都懂，但是自己很久没碰C++了，写起来那叫一个生疏，吭哧吭哧写出来还有一个bug，就是输入的数是0的话，我的程序会输出空字符串，那叫一个尴尬。

题目

将一个十进制整数转换成N进制数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
//整数转string
template <class T>
string toString(T& value)
{
    ostringstream oss;
    oss << value;
    return oss.str();
}
//超过9的数字转成字母
string convertChar(int n)
{
    if(n>9)
    {
        char x = n - 10 + 'A';
        return string(1, x);
    }
    else
    {
        return toString(n);
    }
}
//进制转换函数，n为需要转换的十进制整数，base为进制，返回string类型
string convertBase(int n, int base)
{
    string result;
    if(n==0)
    {
        result = '0';
        return result;
    }
    else
    {
        result = convertChar(n%base);
        while(n/base!=0)
        {
            n = n / base;
            result = convertChar(n%base) + result;
        }
        return result;
    }
}
int main(int argc, const char * argv[]) {
    int x;
    while(std::cin>>x)
    {
    	//测试用例
        cout << convertBase(x, 16) << endl;
    }
    return 0;
}

第二题：找最小未排序子列

题目

给一个未排序的数组，求出一个未排序的最小区间，当这个区间里的数组排序之后，整个数组就排好序了。

样例输入

[1, 3， 4， 2， 5]

样例输出

[1, 3] （index从0开始）

思路1

这道题我现在能想到的时间复杂度最低的方法就是先复制一个原数组，然后排序，再逐个比较对应index上的数，最左边的不一样的数对应的index就是左区间，最右边的不一样的数对应的index就是右区间。这个的时间复杂度应该是NlogN+N～NlogN，也就是线性对数复杂度，但是缺点是需要额外空间N。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
template <class Iterator>
pair<int, int> findUnsortedInterval(Iterator first, Iterator last)
{
	//取出迭代器所指的数据类型，定义为T
    typedef typename iterator_traits<Iterator>::value_type T;
    //新建一个vector存放数据用于后面排序
    vector<T> temp(last-first);
    int index = 0;
    for(Iterator i=first; i!=last; i++)
    {
        temp[index] = *i;
        index++;
    }
    //快速排序
    sort(temp.begin(), temp.end());
    pair<int, int> ret(0 ,0);
    Iterator i = first;
    typename vector<T>::iterator j = temp.begin();
    //逐个比较排序先后的元素
    while(i!=last && j!=temp.end() && *i==*j)
    {
        i++;
        j++;
    }
    if(i==last || j==temp.end())
    {
        return ret;
    }
    else
    {
        ret.first = (int)(i - first);
        while(i!=last && j!=temp.end())
        {
            if(*i != *j)
            {
                ret.second = (int)(i - first);
            }
            i++;
            j++;
        }
        return ret;
    }
 
}
int main(int argc, const char * argv[]) {
    int a[] = {4, 3, 2, 4, 7, 6};
    /／用例
    pair<int, int> result = findUnsortedInterval(a, a+6);
    cout << "<" << result.first << ", " << result.second << ">" << endl;
    return 0;
}

思路2

我在面试时比较紧张，没想到上面的方案，想到了一个时间复杂度$N^2$的算法，就是用插入排序的对逆序数的判断和交换得到左右区间，这个算法时间复杂度高，但是只需要常数级空间，不过会将原数组排序。不过我跟面试官讲这个方案的时候他没太听懂，然后要我写代码并将例子带入解释，然后我又吭哧吭哧写了半天，最后还是有个bug。

复杂版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <limits.h>
using namespace std;
template <class Iterator>
pair<int, int> complexFindUnsortedInterval(Iterator first, Iterator last)
{
    pair<int, int> ret(INT_MAX,0);
    for(Iterator i=first+1; i!=last; i++)
    {
        Iterator j = i;
        //就是将插入排序改了改
        while(j-1>=first && *j < *(j-1))
        {
            iter_swap(j, j-1);
            j--;
            if((int)(j-first)<ret.first)
                ret.first = (int)(j - first);
            if(ret.second<(int)(i-first))
                ret.second = (int)(i - first);
        }
    }
    return ret;
}

总结

两道这么简单的题就将近写了一个小时，写出来还有bug，自己真是菜鸡，还要勤加练习。

第二轮

其实第二轮紧接着第一轮，是位女面试官，上来就出题，说是一道很简单的题，但是随后给出的扩展题我觉得让我想一天也未必想得到，这轮面试就做了这一道题。

题目

给一个有N个元素的数组，其中的元素是1～N的正整数，里面的元素出现的次数要么是1次，要么是2次，要么没出现，要找出所有出现2次的元素。我想这道题常规的方法就是用字典或者哈希表建立一个次数索引，然后输出2次的元素。或者是先排序，然后扫描一次就可以找出出现两次的元素了。用Python写就很简单。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_duplicates(array):
	"""
	:type array: list
	:rtype: list
	"""
    d = {}
    for element in array:
        if element not in d:
            d[element] = 1
        else:
            d[element] += 1
    ret = []
    for k,v in d.iteritems():
        if v == 2:
            ret.append(k)
    return ret

扩展题及思路

但是面试官说不能用额外的空间，只能在原数组在操作，而且要在线性时间里完成。这题瞬间难了很多，后来面试官慢慢引导直到把答案告诉了我，然后让我实现它。面试官给的思路是大概用《编程珠玑》第一章节说说到的位排序的思路去做的。先去掉空间限制，就是新建一个N个bit的数组，这个数组的index就表示对应的数，bit为0表示没访问过，bit为1表示访问过（因为只有1～N的正整数）。然后遍历原数组，并用index访问相应的bit数组，访问时将bit置1，如果出现重复元素，第二次访问时会发想该bit已经为1，就输出这个元素。然后为了满足空间限制，我们只能在原数组上操作（原数组也是一个有N个元素的数组，也可以用index的值表示对应的1～N的数），那么我们如何才能在这个数组上操作而又能知道原来存的数是多少呢？因为所有的数都在1～N范围内，所以我们将原来bit位置1的操作换成加上N就可以了。如果出现重复元素，第二次访问时会发现该位置存的数大于N，那么就输出这个重复元素。我们也可以通过将超过N的元素减去N还原原来的数。听起来云里雾里的，看代码就清楚了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_duplicates(array, n):
	"""
	:type array: list
	:type n: int (range of number)
	:rtype: list
	"""
    ret = []
    for i in range(n):
        temp = array[i]
        if temp > n:
            temp -= n
        if array[temp-1] > n:
            ret.append(temp)
            continue
        array[temp-1] += n
    return ret

第三轮

第三轮没有写代码的题，问了好几个工程上的问题，比如如何设计一个shell，这种问题我瞎掰都掰不出啥，尴尬。最后问了一个如何设计五子棋AI的问题，我按照Alpha Go的套路蒙特拉罗树搜索来答的，但是只是说思路，感觉这个值得挖个坑，想一想具体的实现，看看以后能不能把这个坑填上了。