谷歌（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 ireturn -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

这个函数首先计算叠加次数的上限 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 + 1min_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 + 1breakelse:min_days = min(min_days, max(days[left], days[right]))left, right = right, right + k + 1return 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

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