谷歌（Google）技术面试——在线评估问题（一）

谷歌（Google）面试过程的第一步，你可能会收到一个在线评估链接。 评估有效期为 7 天，包含两个编码问题，需要在一小时内完成。 以下是一些供你练习的在线评估问题。

在本章结尾处，还提供了有关 Google 面试不同阶段的更多详细信息。

重复叠加字符串匹配

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。

示例 1：

输入：a = “abcd”, b = “cdabcdab”
输出：3
解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b是其子串。

示例 2：

输入：a = “a”, b = “aa”
输出：2

示例 3：

输入：a = “a”, b = “a”
输出：1

示例 4：

输入：a = “abc”, b = “wxyz”
输出：-1

提示：

• 1 <= a.length <= 104
• 1 <= b.length <= 104
• a 和 b 由小写英文字母组成

我们可以通过模拟的方式来解决这个问题。具体来说，可以不断叠加字符串 a 直到 b 成为叠加后的字符串 a 的子串，或者叠加次数达到一定的限制。

示例代码：

def repeatedStringMatch(a, b):
    n = len(b) // len(a) + 2 # 计算叠加次数的上限
    for i in range(1, n + 1):
        if b in a * i:
            return i
    return -1

# 示例 1
a = "abcd"
b = "cdabcdab"
print(repeatedStringMatch(a, b)) # 输出：3

# 示例 2
a = "a"
b = "aa"
print(repeatedStringMatch(a, b)) # 输出：2

# 示例 3
a = "a"
b = "a"
print(repeatedStringMatch(a, b)) # 输出：1

# 示例 4
a = "abc"
b = "wxyz"
print(repeatedStringMatch(a, b)) # 输出：-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这个函数首先计算叠加次数的上限 n，然后在循环中，依次尝试叠加 1 到 n 次字符串 a，检查叠加后的字符串是否包含 b，如果包含，则返回当前叠加次数。如果循环结束后仍然没有找到符合条件的叠加次数，则返回 -1。

K 个空花盆

n 个灯泡排成一行，编号从 1 到 n 。最初，所有灯泡都关闭。每天 只打开一个 灯泡，直到 n 天后所有灯泡都打开。

给你一个长度为 n 的灯泡数组 blubs ，其中 bulbs[i] = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。

给你一个整数 k ，请返回恰好有两个打开的灯泡，且它们中间 正好 有 k 个 全部关闭的 灯泡的 最小的天数 。如果不存在这种情况，返回 -1 。

示例 1：

输入： bulbs = [1,3,2]，k = 1
输出：2
解释：
第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0]
第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1]
第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1]
返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。

示例 2：

输入：bulbs = [1,2,3]，k = 1
输出：-1

提示：

• n == bulbs.length
• 1 <= n <= 2 * 104
• 1 <= bulbs[i] <= n
• bulbs 是一个由从 1到 n 的数字构成的排列
• 0 <= k <= 2 * 104

我们可以通过模拟的方式来解决这个问题。具体来说，我们可以遍历数组 bulbs，记录每个灯泡打开的位置，然后查找其中间有 k 个全部关闭的最小天数。

示例代码：

def kEmptySlots(bulbs, k):
    n = len(bulbs)
    days = [0] * n # 记录每个位置上灯泡打开的天数
    for i in range(n):
        days[bulbs[i] - 1] = i + 1 # 记录每个灯泡的打开天数
    
    left, right = 0, k + 1
    min_days = float('inf')
    
    # 循环查找最小天数
    while right < n:
        for i in range(left + 1, right):
            if days[i] < days[left] or days[i] < days[right]:
                left, right = i, i + k + 1
                break
        else:
            min_days = min(min_days, max(days[left], days[right]))
            left, right = right, right + k + 1
    
    return min_days if min_days != float('inf') else -1

# 示例 1
bulbs1 = [1,3,2]
k1 = 1
print(kEmptySlots(bulbs1, k1)) # 输出：2

# 示例 2
bulbs2 = [1,2,3]
k2 = 1
print(kEmptySlots(bulbs2, k2)) # 输出：-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这个函数首先遍历数组 bulbs，记录每个灯泡打开的天数，并初始化左右指针。然后在循环中，遍历数组找到两个灯泡之间有 k 个全部关闭的情况，更新左右指针。如果找到了这样的情况，则更新最小天数；否则继续查找。最后返回最小天数，如果不存在这样的情况，则返回 -1。

谷歌（Google）技术面试系列

• 谷歌（Google）技术面试概述
• 谷歌（Google）历年编程真题——数组和字符串（螺旋矩阵）
• 谷歌（Google）历年编程真题——数组和字符串（加一）
• 谷歌（Google）技术面试——在线评估问题（一）
• 谷歌（Google）技术面试——在线评估问题（二）
• 谷歌（Google）技术面试——在线评估问题（三）
• 谷歌（Google）技术面试——在线评估问题（四）
• 谷歌（Google）技术面试——全部面试流程