百度 SRE工程师实习生 一面凉经

为了准备百度SRE运维实习岗，我特意花了一个周末先了解了运维的基本概念，再初步的认识了下SRE（站点稳定性工程师）。
面试是这周一12.28，因为疫情的原因，采用的是电话面试的形式，具体问了哪些问题有点记不清了，只知道自己回答得不是很好，很多都只是一知半解，自我感觉很多时候并没有答到面试老师想听到的点。最后给了一道简单的算法题，限制时间回答。
题目如下：

【题目】
给定一个字符串，给定一个数字k ( 0< k ≤ 字符串长度)，输出最长的包含k个不同字符子串的长度

【Example】
“cbca”, k=2，输出最长的包含2个不同字符子串的长度
答案：3

我面试时采用的是暴力的解法，就是求出字符串的所有子串，并找出不同字符为k的最长字符，Python代码如下：

def find_max_substring(string, k):
    str_length = len(string)
    sub_string_list = (string[i:i + j + 1] for j in range(str_length) for i in range(str_length - j))
    length_list = []
    for sub_string in sub_string_list:
        if len(set(list(sub_string))) == k:
            length_list.append(len(sub_string))
    return max(length_list)


if __name__ == '__main__':
    string = input()
    k = int(input())
    max_length = find_max_substring(string, k)
    print(max_length)

显然，这种实现方式效率是很低的，虽然使用了生成器，同时还会漏掉一些特殊情况，但是在性能方面还是有很大的问题。
后来查询了一些资料，使用了同向双指针和字典实现了优化后的方式：

def find_max_substring(string, k):
    str_length = len(string)
    if str_length == 0 or k == 0:
        return 0
    count = 0
    left = 0
    right = 0
    res = 0
    count_dic = {}
    while right < str_length:
        if string[right] not in count_dic or count_dic[string[right]] == 0:
            count += 1
            count_dic[string[right]] = 1
        else:
            count_dic[string[right]] += 1
        right += 1
        while count > k:
            count_dic[string[left]] -= 1
            if count_dic[string[left]] == 0:
                count -= 1
            left += 1
        res = max(res, right - left)
    return res


if __name__ == '__main__':
    string = input()
    k = int(input())
    max_length = find_max_substring(string, k)
    print(max_length)

在字符串长度为0或者k为0时直接返回0；
通过使用同向双指针的，可以做到只遍历一次字符串就能得到答案，从而使时间复杂度为O(n)，在字符串上移动滑动窗口的两个指针，来保证窗口内的字符不超过k个，具体如下：

• 设置指针left、right初始位置均为0，初始化计数数组；
• 当right小于字符串长度时，每次判断字符s[right]是否位于计数数组中，不在则计数count加1，同时对字典进行更新，并使right指针向右移动；
  • 在字符数超过k时，需要移去窗口中最左侧的字符string[left]，同时向右移动left指针使得滑动窗口只包含k个不同字符
  • 更新最大长度res = max(res, right - left)。

当然，理想很丰满、现实很骨感，等待结果的过程很焦虑，百度一面就凉凉了，愿给后来者借鉴。