笔试

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

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

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

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

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

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

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

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

# 第二题
def solution(S: str):
    tokens = S.split(' ')
    stack = []
    lenth = 0
    for token in tokens:
        if token.isdigit():
            if int(token) - float(token) != 0:
                return -1
            stack.append(int(token))
            lenth += 1
        elif token == 'POP':
            if lenth > 0:
                stack.pop()
                lenth -= 1
            else:
                return -1
        elif token == 'DUP':
            if lenth > 0:
                stack.append(stack[lenth - 1])
                lenth += 1
            else:
                return -1
        elif token == '+':
            if lenth > 1:
                num1 = stack.pop()
                num2 = stack.pop()
                res = num1 + num2
                if isBadNum(res):
                    return -1
                stack.append(res)
                lenth -= 1
            else:
                return -1
        elif token == '-':
            if lenth > 1:
                num1 = stack.pop()
                num2 = stack.pop()
                res = num1 - num2
                if isBadNum(res):
                    return -1
                stack.append(res)
                lenth -= 1
            else:
                return -1
        else:
            return -1
    if lenth > 0:
        return stack.pop()
    else:
        return -1


def isBadNum(num):
    if num < 0 or num > 2 ** 20 - 1:
        return True

# 第三题
class Point2D:
    x = 0
    y = 0
    # library with types used in the task


def solution(A):
    total=len(A)
    table=[[0]*total for _ in range(total)]

    for i in range(total-1):
        for j in range(i+1,total):
            table[i][j]=getSlope(A[i],A[j])

    res=0

    for i in range(total-2):
        slops=table[i][i+1:]
        slops_set=set(slops)
        for slop in slops_set:
            num=slops.count(slop)
            if num>=2:
                res+=int(num*(num-1)/(2))

    if res>100000000:
        res=-1

    return res

一面

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

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

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

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

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

三面

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

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

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

后续

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

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