首页 > 百度 SRE工程师实习生 一面凉经
头像
寻梦者Corley
编辑于 2021-01-02 19:03
+ 关注

百度 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)

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

更多模拟面试

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐