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)is1. - The longest common prefix of
(10, 1000)is10. - The longest common prefix of
(100, 1000)is100.
The longest common prefix is 100 with a length of 3.
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 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,...]. 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,1,1,...]. 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.
These two problems are classic array-and-prefix interview questions. The first asks for the longest shared leading digits between any number from two arrays, which is commonly solved with a trie over decimal prefixes or another prefix-based lookup structure. The second asks for the shortest subarray summing to a target in an infinitely repeated array, typically handled with prefix sums and a sliding window or two-pointer strategy over a bounded expansion of the array. Both emphasize recognizing prefix structure and turning it into an efficient search.
