软软子的校招活动越来越丰富了，作为微软第一站姐表示无比欣慰！

这次的offer养成计也是微软给小朋友们一次熟悉笔面试流程的机会，于是毫不犹豫就上车了。

ps：本贴是在所有同学笔试结束后才发出来的，坚决保卫笔试的公正哦。希望为没参加的盆友们参考一下题目，以及期待和参加的盆友们一起探讨！
pps：有想投微软PM的兄弟姐妹们请联系我！可以一起准备哦 ღ( ´･ᴗ･` )

笔试介绍

• 平台：Codility
• 时长：130min，任选时间进入
• 题量：3道题，个人感受是1 easy + 1 medium + 1 hard，难度均衡得挺好
• 日期：2022年7月15日

笔试经验

• 平常做leetcode时，我一直是白板做题。但是毕竟是笔试，IDE不用白不用^ ^，所以我都先在IDE中写好测试好，然后粘贴到codility中。不然我担心自己不小心按到codility的提交按钮sos
• 我不了解面试官在筛选的时候，有多大比重会考虑做题速度（这个我打算后续咨询一下！）。但无论如何，我依然选择略牺牲速度来提高代码的优美性，能加的注释全都加得整整齐齐的。

题解分享

• 以下仅为个人解法，如果代码有错误（最好不要qwq） or 有更优的解法，欢迎大家在评论区提出！
• 我写python比较顺手，也欢迎大家提出其他语言的解法。

T1：气球走开！

• 题目：
  • 给定字符串S，只由大写字母组成，每次移走一个BALLOON（不用在意字母顺序），问可以移走几个BALLOON
• 限制：
  • S: [1, 2 x 10^5]
• 思路：
  • 遍历字符串S，记录S中每个字母出现的次数。
  • 对于BALLOON中的每个字符，计算S中该字符的数目能够构成几个BALLOON
  • 根据木桶原理，取这些字符分别能构成BALLOON的个数的最小值，即为结果
• 复杂度：
  • 时间复杂度：O(n)，n为S的长度
  • 空间复杂度：O(|∑|), ∑是字符集，本题为26个大写字母

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

from collections import defaultdict

def solution(S):
    # Time complexity: O(n), where n represents the length of S
    # Space complexity: O(|Sigma|), where Sigma is 26

    # step1: build a dict of 'balloon'
    word = defaultdict(int)
    word['B'] = 1
    word['A'] = 1
    word['L'] = 2
    word['O'] = 2
    word['N'] = 1

    # step2: build another dict of the frequency of all the characters in S
    counter = defaultdict(int)
    for ch in S:
        counter[ch] += 1

    # step3: traverse all the characters, calculate how much balloon can construct only considering this character
    # and the min value will be the answer
    min_num = float('inf')
    for ch in word:
        min_num = min(min_num, counter[ch] // word[ch])
        # print(ch, counter[ch], word[ch], counter[ch] // word[ch])
    return min_num

S = 'BAONXXOLL'
S = 'BAOOLLNNOLOLGBAX'
S = 'QAWABAWONL'
S = 'ONLABLABLOON'
S = 'BALLOON'
S = ''
res = solution(S)
print(res)

T2：两只跳跳蛙

• 题目：
  • 给定一排荷叶blocks[]，值代表荷叶的高度。
  • 青蛙从荷叶i跳到荷叶j的条件是：i j相邻，且 blocks[j] >= blocks[i]。
  • 对于荷叶i和j（i <= j），两片荷叶的距离为j - i + 1。
  • 请问：有两只青蛙初始站在同一片荷叶上，它们俩可以按照上述规则分别跳跃，求两只青蛙的可能的最远距离。
• 举例：
  • blocks = [1, 5, 5, 2, 6]，最好的情况是两只青蛙初始化站在第3片荷叶上（即高度为2），一只向左跳2次，一只向右跳1次，最终的距离是2+1+1=4
• 限制：
  • N <= 2*10^5
  • blocks[i] <= 1*10^9
• 思路：
  • 计算以i为起点，向左和向右分别能跳多少步，两者相加再加1就是从该点初始的最远距离。
  • 所有的最远距离取最大值即为结果。
• 复杂度：
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

# Remember, all submissions are being checked for plagiarism.
# Your recruiter will be informed in case suspicious activity is detected.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(blocks):
    # Task: find the longest possible distance between two frogs
    # Limit: N <= 2*10^5, blocks[i] <= 1*10^9

    # Method: starting from each block[i], find the longest steps jumping to the left, and the longest steps to the right.
    #         Add them together and add one. The longest will be the answer
    # Time Complexity: O(n)
    # Space Complexity: O(n). I'm not sure if there exists a method with more efficient space complexity.

    n = len(blocks)

    # step1: find the longest steps jumping to the left
    # `jump_to_left[i]` means how many steps the frog can jump to the left
    jump_to_left = [0] * n
    sum_ = 0
    for i in range(1, n):
        # the current block is no higher than the left one
        if blocks[i] <= blocks[i - 1]:
            # can jump one more block
            sum_ += 1
            jump_to_left[i] = sum_
        else:
            sum_ = 0

    # step2: find the longest steps jumping to the right
    # `jump_to_right[i]` means how many steps the frog can jump to the right
    jump_to_right = [0] * n
    sum_ = 0
    for i in range(n-2, -1, -1):
        # the current block is no higher than the right one
        if blocks[i] <= blocks[i + 1]:
            # can jump one more block
            sum_ += 1
            jump_to_right[i] = sum_
        else:
            sum_ = 0

    # step3: find the longest distance between the two frogs
    res = 0
    for i in range(n):
        res = max(res, jump_to_left[i] + jump_to_right[i] + 1)

    return res


blocks = [2, 6, 8, 5]
# blocks = [1, 5, 5, 2, 6]
# blocks = [1, 1]
# blocks = [1]
# blocks = [1, 2, 3]
# blocks = [3, 4, 1, 6, 5, 2, 7]


res = solution(blocks)
print(res)

T3：三点共线

• 题目：
  • 给定二维平面上的点坐标的列表A，A[i].x表示第i个点的横坐标，A[i].y表示第i个点的纵坐标。A中的点没有重合
  • 求这些点中，有多少个三元组，满足这三点共线。
  • 如果答案超过10**8，返回-1。
• 举例：
  • 
  • 假设点集如上图所示，结果将返回6，代表有6个三元组。它们分别是
    • (A[0], A[1], A[2])
    • (A[0], A[1], A[3])
    • (A[0], A[2], A[3])
    • (A[1], A[2], A[3])
    • (A[2], A[4], A[5])
    • (A[3], A[5], A[6])
• 限制：
  • n <= 10^3, 意味着不能用O(n^3)的暴力法
  • A.x, A.y < 10^4
• 思路：
  • 假设结果为res。对于每个点i，
    • 建立哈希表slopes，记录每个斜率出现的次数
    • 遍历点j（j > i），求出i与j的斜率，设为slope，那么，slopes[slope]应该加一。
    • 遍历所有的斜率，设某斜率slope对应num个点，那么包含点i在内的斜率为slope的三元组数目为C(num, 2) = num * (num - 1) // 2。res加上该值即可。
• 难点：
  • 斜率涉及到小数精度问题，所以这里slopes中不存真正的斜率，而是存坐标差。具体而言，计算dx和dy，然后求最大公约数进行约分，以字符串的形式存到slopes中。
  • 可以类比leetcode 149. 直线上最多的点数的。
• 复杂度：
  • 时间复杂度：O(n^2 * log(m)), n 是A的长度, m是两点的最大坐标差值
  • 空间复杂度：O(n)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

# from extratypes import Point2D  # library with types used in the task

class Point2d:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def get_A(li):
    res = []
    for x, y in li:
        res.append(Point2d(x, y))
    return res


from collections import defaultdict

# find the greatest common divisor
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def solution(A):
    # Task: find how many triplets that can form a line
    # Limit: (1) n <= 10^3, (2) A.x, A.y < 10^4, (4) A is distinct

    # Method: Hash Map, using gcd to record slopes
    # Time Complexity: O(n^2 * log(m)), where n is len(A), m is max difference of x coordinates and y coordinates
    # Space Complxity: O(n)

    n = len(A)
    res = 0
    # traverse the first point A[i]
    for i in range(n - 1):
        x1, y1 = A[i].x, A[i].y
        # 'slopes' format is like {slope1: num1, slope2: num2, ...}
        slopes = defaultdict(int)
        # find the slopes between A[i] and all other later points
        for j in range(i + 1, n):
            x2, y2 = A[j].x, A[j].y
            dx, dy = x2 - x1, y2 - y1
            # find the most simple form
            g = gcd(dx, dy)
            if g != 0:
                dx //= g
                dy //= g
            # record this slope
            slopes["{}/{}".format(dy, dx)] += 1

        # The result would add C(n, 2) = n * (n-1) // 2
        for slope in slopes:
            res += slopes[slope] * (slopes[slope] - 1) // 2
    # Do not exceed the limit
    if res > 10 ** 8:
        return -1
    return res

li = [[1, 1], [0, 0], [2, 2], [3, 2], [4, 2], [3, 3], [5, 1], [4, 4]]
res = solution(get_A(li))
print(res)

OK，以上就是本次笔经。笔试结束后就收到收集意向的邮件了，果断选了PM！历尽千帆，还是做PM最快乐。祝愿有面试机会 & 面试顺利！