微软苏州面试

发表于 更新于 分类于 Disqus：

在@lxc师兄的内推下，我有幸可以前往 苏州微软，面试O365部门的暑期实习生。虽然最后失败了，但从这次失败的经历中，我学习到很多。
总结在此，为未来的找实习和工作做准备。

面试环节

一面

  • 尾递归，斐波那契（不会）
  • 合并2个列表
  • makefile 编译顺序确定
  • memcpy的实现方式和安全问题

用尾递归优化递归斐波那契数列

斐波那契数列大家应该都很熟悉，高中数学课本上提到的经典递归数列。
其数学定义为：

fn={fn−1+fn−2if n>21if n=0,1f_n = \begin{cases} f_{n-1} + f_{n-2} & \quad \text{if } n > 2 \\ 1 & \quad \text{if } n = 0, 1 \end{cases}

根据数学递推式，很容易地可以写出递归版的斐波那契数列：

1
2
3
4
5
6
7
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

根据函数调用的原理，每次需要递归调用2次本函数，当参数为n时，需要的栈帧的数目为O(2^n)。
可以利用尾递归来优化这个问题。
尾递归是尾调用的一种递归调用形式。
我对尾递归的理解是
函数式编程中使用函数调用以实现循环的方式。
所以，首先给出内存占用为O(1)的斐波那契数列循环实现。

1
2
3
4
5
6
7
8
9
10
def fibonacci(n):
    if n == 0:
        return 0
    f_n_sub_1 = 1
    f_n_sub_2 = 0
    i = n
    while i > 1:
        f_n_sub_1, f_n_sub_2 = f_n_sub_1 + f_n_sub_2, f_n_sub_1
        i -= 1
    return f_n_sub_1

从循环实现可以看出，整个循环实现需要2个变量(f_n_sub_1和f_n_sub_2)来记录中间的结果，
一个循环变量(i)以控制循环次数(即循环结束条件)。
将这些变量当作函数的参数即可得到尾递归版本的斐波那契数列实现。

1
2
3
4
5
6
7
def fibonacci(n):
    def func(n, ret1, ret2):
        if n == 0:
            return ret1
        else:
            return func(n - 1, ret2, ret1 + ret2)
    return func(n, 0, 1)

memcpy的实现方式和安全性问题

也是一个字节一个字节的复制。不是我想当然的认为一整块一整块的复制，这样会更快。
回忆计算机组成原理的知识：
CPU和Memory之间由总线连接，一次（一个时钟周期）只能读取和写入一个字的数据。

安全性：很不安全。
回忆操作系统的知识：进程的内存空间映射到物理内存。
直接一个一个字节从低到高地复制粘贴容易覆盖到其他指针指到的数据（破坏了其他指针的数据）甚至本身的数据。

比如memcpy一个大小为200字节的指针(地址100)到地址200，会把自己的数据(200-300)的部分先覆盖掉，之后的copy就都是错的。（这是面试官给出的解释，但我后来发现，这点是不一定不成立的。因为之后我查了一些标准库中memcpy的实现，这种情况下可能会采用自后向前复制的方法防止覆盖要复制的数据。
无保护措施的gcc
有保护措施
）

面试官指点

面试时在Notepad里写代码，在纸上写代码，和在白板上写，
容易程度或方便程度是：
白板 > 纸 > Notepad

被告知面试题目后，首先要考虑清楚初始条件和具体要求，不清楚的一定要和面试官问清楚，不要上来就写。
否则后来发现歧义，再问时就晚了。

其他收获

有时间一定要好好看看SICP，函数式编程的尾递归在其中就有讲。
面试官估计也读过。

二面

  • 求树的最深度
  • 最大和的链
  • 可以拐弯的最大和的链
  • 数组权重最大的重新排序（不会）

其他收获

在面试时，ACM选手有天然的优势。
该面试官本科时，可能玩过ACM，因为他说“数组权重”那道题是他上学时自己出得。

p.s. 面试官说他也毕业不久。

三面

周二去苏州参加完面试后，周五出结果，约了第二周周二的视频面试。
说实话，视频面试前我还真有点紧张，而且由于学校出了点状况，上午才知道下午有视频面试。
仓促之前，也没有午睡，休息好。面试之前特别困。
好在真正到面试时，肾上腺素上升，不困了。

三面的面试官也很nice。
听说我熟悉SQL，就出了一道SQL题目给我。

类似教务管理系统。有3张表：学生（学号，姓名），课程表（课程ID，课程名），选课表（学号，课程ID，成绩）。
查询每个学生的数学成绩和语文成绩，结果为（姓名，数学成绩，语文成绩）。
刚开始假设每个学生都选了数学和语文，后来取消了这个假设（考察outer join）。

第二道题

第二道题目考察IEEE的一种round实现。

首先，列出一些数字，让我观察规律。
在面试官的引导下，我猜测出来了：四舍六入五看下一位。
之后使用C语言实现这一ieee_round。

结果

No Hire.

很遗憾，Lead面试官最后给的是No Hire。他认为你编写代码能力不稳固。你的优点是思考能力很强，缺点是不善于展现和询问，不能从错误中获取新的解决办法，今后需要加强这方面。

希望你研究生期间继续努力，欢迎再加入苏州微软。

Lead面试官的眼光还是蛮准的，给出的建议的是一针见血的。我会继续努力，早日达到微软爸爸的要求的。

除此之外，一开始说好的报销火车票最后也没给报，经济上还损失了1200￥。