今天csoahelo协助了 候选人进行了 TikTok 的面试，面试官依次出了两道算法题。整体感觉非常注重算法思维和代码实现的效率，以下是我在面试中的具体经历和思路分享。
Question 1:
You are given two arrays with positive integers arr1 and arr2. A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not. A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix. You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2. Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.
Example 1:
Input: arr1 = [1, 10, 100], arr2 = [1000]
Output: 3
Explanation: There are 3 pairs (arr1[i], arr2[j]):
- The longest common prefix of (1, 1000) is 1.
- The longest common prefix of (10, 1000) is 10.
- The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.
问题 1:
给定两个包含正整数的数组 arr1 和 arr2。 一个正整数的前缀是由其从左边开始的一个或多个数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是。 两个整数 a 和 b 的共同前缀是一个整数 c，使得 c 是 a 和 b 的前缀。例如，5655359 和 56554 有一个共同前缀 565，而 1223 和 43456 没有共同前缀。 你需要找到所有整数对 (x, y) 的最长共同前缀的长度，其中 x 属于 arr1，y 属于 arr2。 返回所有对中最长共同前缀的长度。如果没有共同前缀，则返回 0。
示例 1:
输入: arr1 = [1, 10, 100], arr2 = [1000]
输出: 3
解释: 这里有 3 对 (arr1[i], arr2[j])：
- (1, 1000) 的最长共同前缀是 1。
- (10, 1000) 的最长共同前缀是 10。
- (100, 1000) 的最长共同前缀是 100。 最长共同前缀是 100，长度为 3。
我复述了题目并确认自己完全理解。接下来，我开始思考如何高效地解决这个问题。以下是我的解题思路和具体实现步骤：
- 理解前缀的定义：前缀必须从数字的左边开始，并且可以由一到多个数字组成。
- 暴力解法的考虑：直接比较每个
(x, y)对的前缀长度，虽然简单，但时间复杂度过高。 - 优化方案：决定使用字典树（Trie）来优化前缀匹配的过程。将
arr1中的所有数字构建成一个前缀树，然后逐个检查arr2中的数字，在前缀树中寻找最长匹配。
接下来，我开始编码：
面试官对我的实现表示满意，接着询问了我在实现过程中的优化思路和遇到的困难。我解释了如何通过构建Trie树来减少比较次数，并且详细描述了插入和查询的过程。
Question 2:
You are given a 0-indexed array nums and an integer target. A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself. Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.
Example 1:
Input: nums = [1, 2, 3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1, 2, 3, 1, 2, 3, 1, 2, 3, ...].
The subarray in the range [1, 2] has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.
Example 2:
Input: nums = [1, 1, 1, 2, 3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1, 1, 1, 2, 3, 1, 1, 1, 2, 3, ...].
The subarray in the range [4, 5] has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.
Example 3:
Input: nums = [2, 4, 6, 8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2, 4, 6, 8, 2, 4, 6, 8, ...].
It can be proven that there is no subarray with sum equal to target = 3.
问题 2:
给定一个 0 索引数组 nums 和一个整数目标值 target。 一个 0 索引数组 infinite_nums 是通过无限地将 nums 的元素附加到其自身来生成的。 返回数组 infinite_nums 中和等于目标值的最短子数组的长度。如果不存在这样的子数组，则返回 -1。
示例 1:
输入: nums = [1, 2, 3], target = 5
输出: 2
解释: 在这个例子中，infinite_nums = [1, 2, 3, 1, 2, 3, 1, 2, 3, ...]。
范围 [1, 2] 内的子数组的和等于目标值 5，长度为 2。
可以证明，长度为 2 是和等于目标值 5 的最短子数组。
示例 2:
输入: nums = [1, 1, 1, 2, 3], target = 4
输出: 2
解释: 在这个例子中，infinite_nums = [1, 1, 1, 2, 3, 1, 1, 1, 2, 3, ...]。
范围 [4, 5] 内的子数组的和等于目标值 4，长度为 2。
可以证明，长度为 2 是和等于目标值 4 的最短子数组。
示例 3:
输入: nums = [2, 4, 6, 8], target = 3
输出: -1
解释: 在这个例子中，infinite_nums = [2, 4, 6, 8, 2, 4, 6, 8, ...]。
可以证明，没有和等于目标值 3 的子数组。
我复述了题目并确认无误。以下是我的解题思路：
- 理解无限数组：明确
infinite_nums实际上是nums的无限循环。 - 滑动窗口技术：考虑使用滑动窗口来找到子数组的和，并计算最短长度。由于
infinite_nums是无限的，我们只需要在nums的两倍长度范围内查找即可。 - 边界处理：考虑目标值可能不存在的情况，在代码中进行相应处理。
Algorithm:
I think altough it's infinite, repeating it for a number of times so that we can add to target is probably
enough to make up to target, further repetition is not needed
let me think the implementation
we can use target / (sum of array) and take the ceiling of the result, that's the maximum number of time we would need to repeat,
so what we can do is to repeat the initially array for ceiling of target / (sum of array) number of times
and use sliding window to find shorting subarray
我快速实现了滑动窗口算法，并进行了验证：
面试官对我的滑动窗口算法表示认可，并进一步询问了我对滑动窗口技术的理解和应用场景。我详细解释了滑动窗口的优势以及在解决数组问题中的广泛应用。
总结
面试结束后，客户对我们辅助的面试表现感到满意。通过这次面试辅助服务，客户不仅向面试官展示了自己的算法能力和编码水平，还在与面试官的交流中学习到了新的优化思路和技巧。TikTok 的面试题目设计得很有挑战性，但也非常贴近实际应用。
希望这篇面经对未来准备 TikTok 面试的同学们有所帮助！
经常有同学会问我们，面试辅助和代面试有什么区别。在这里统一回答一下，面试辅助专注于解决面试中的技术问题，换言之如果你仅有技术是短板，其他方面非常擅长沟通面试的话，选择面试辅助是比较好的选择。
而代面试则更适合那些对自己各方面都不太自信的同学。扫码添加我的微信，欢迎随时联系我。
