2021微软STCA苏州工程院实习笔经面经

01 Apr, 2021

笔试

三道算法题，都还算简单。大概描述一下：

第一题：输入ABCD四个数，分别是平面两个点的横纵坐标，但不知道具体对应关系，例如可能是p1(A,B)和p2(C,D)，也可能是p1(C,A)和p2(D,B)。求可能的两点距离平方最大值。

第二题：自己实现一个栈，输入可能是数字或者操作。如果是数字，压栈；如果是操作，按照操作说明进行计算。操作有：

POP 出栈一个数。
DUP 将栈顶的数拷贝一份放在栈顶
+ 将栈顶两个数相加压回栈中
- 将栈顶两个数相减压回栈中

最后返回栈顶的元素。但凡任意一步中出现了大于2^20 - 1的结果，或者某个操作栈中元素数不足，则返回-1

第三题：给出若干平面上的点的坐标，写出有多少三元组在同一条直线上。也就是说有多少个三点共线的情况。

下面是我的python版解答，写的比较暴力，但也得了满分：

1# 第一题
2def solution(A, B, C, D):
3    case1=(A-B)**2+(C-D)**2
4    case2=(A-C)**2+(B-D)**2
5    case3=(A-D)**2+(B-C)**2
6    maximum=max(case1,case2,case3)
7    return maximum

 1# 第二题
 2def solution(S: str):
 3    tokens = S.split(' ')
 4    stack = []
 5    lenth = 0
 6    for token in tokens:
 7        if token.isdigit():
 8            if int(token) - float(token) != 0:
 9                return -1
10            stack.append(int(token))
11            lenth += 1
12        elif token == 'POP':
13            if lenth > 0:
14                stack.pop()
15                lenth -= 1
16            else:
17                return -1
18        elif token == 'DUP':
19            if lenth > 0:
20                stack.append(stack[lenth - 1])
21                lenth += 1
22            else:
23                return -1
24        elif token == '+':
25            if lenth > 1:
26                num1 = stack.pop()
27                num2 = stack.pop()
28                res = num1 + num2
29                if isBadNum(res):
30                    return -1
31                stack.append(res)
32                lenth -= 1
33            else:
34                return -1
35        elif token == '-':
36            if lenth > 1:
37                num1 = stack.pop()
38                num2 = stack.pop()
39                res = num1 - num2
40                if isBadNum(res):
41                    return -1
42                stack.append(res)
43                lenth -= 1
44            else:
45                return -1
46        else:
47            return -1
48    if lenth > 0:
49        return stack.pop()
50    else:
51        return -1
52
53
54def isBadNum(num):
55    if num < 0 or num > 2 ** 20 - 1:
56        return True

 1# 第三题
 2class Point2D:
 3    x = 0
 4    y = 0
 5    # library with types used in the task
 6
 7
 8def solution(A):
 9    total=len(A)
10    table=[[0]*total for _ in range(total)]
11
12    for i in range(total-1):
13        for j in range(i+1,total):
14            table[i][j]=getSlope(A[i],A[j])
15
16    res=0
17
18    for i in range(total-2):
19        slops=table[i][i+1:]
20        slops_set=set(slops)
21        for slop in slops_set:
22            num=slops.count(slop)
23            if num>=2:
24                res+=int(num*(num-1)/(2))
25
26    if res>100000000:
27        res=-1
28
29    return res

一面

由于今年情况特殊，面试都是线上进行。

一面前面根据项目经历简单问了问，问到了Java中乐观锁和悲观锁（幸好前一天看到了）。然后就是两道算法题：

第一题：非递归方法，后序遍历二叉树。数据结构的课上学过，很快就写出来了。

第二题：从单链表中删除倒数第n个节点。最好的办法是用两个指针，中间具体为n，同时向后移动，后一个指针到链表尾部的时候前面的指针正好指向倒数第n+1个节点，就可以进行删除操作了。

两道题总体都比较简单，就顺利通过了。

三面

微软面试有个特点，如果一面面过了就直接三面，没过才需要二面，相当于多给一次机会。

三面感觉已经基本上不怎么问技术问题了，前面就问了一些工作生活的基本态度，比如不是由于自己的原因，但是自己负责的项目交付迟到了被领导批评要怎么做这样的问题。很像其他公司面试的HR面了。

最后让做了一道算法题：写一个函数，将十进制整数右移n位，把从各位溢出的位数补到开头。这个当时感觉做的不太好，因为很多情况没有考虑完全，比如n是负数之类的，被面试官指出来了。

后续

过了几天受到邮件，Thank you for applying… 我心想这凉了，结果点进去竟然是收集个人信息的问卷。

3月31日终于收到了Offer，开心！yes

#面试