Find the longest run in a float array where adjacent chosen values differ by at most 1. Why must you ask “contiguous or may I skip elements?” first?
Predict first
What do the contiguous and the skipping versions give?
func longestRun(_ a: [Double]) -> Int { // contiguous: neighbours differ by at most 1
guard !a.isEmpty else { return 0 }
var best = 1, cur = 1
for i in 1..<a.count {
cur = abs(a[i] - a[i - 1]) <= 1 ? cur + 1 : 1
best = max(best, cur)
}
return best
}
func longestSubsequence(_ a: [Double]) -> Int { // may skip elements; chosen neighbours differ by at most 1
guard !a.isEmpty else { return 0 }
var dp = [Int](repeating: 1, count: a.count)
for i in 0..<a.count { for j in 0..<i where abs(a[i] - a[j]) <= 1 { dp[i] = max(dp[i], dp[j] + 1) } }
return dp.max()!
}
let data: [Double] = [1.0, 1.5, 3.0, 2.5, 2.0, 3.5]
print("contiguous run:", longestRun(data))
print("subsequence:", longestSubsequence(data))
print(longestRun([]), longestSubsequence([]), longestRun([7]), longestSubsequence([7]))- contiguous run: 3 / subsequence: 4 / then 0 0 1 1
- contiguous run: 4 / subsequence: 4
- contiguous run: 3 / subsequence: 3
Mental model. Stepping stones across a river: if you must step on every stone in a row it is a single walk; if you may skip stones you have to try every earlier stone that is within reach.
The wording hides two different problems, and asking is the first thing to do. If the run must be contiguous (a subarray), one pass suffices: extend the current run while |a[i] - a[i-1]| <= 1, otherwise restart at 1; keep the best. O(n) time, O(1) memory. If you may skip elements (a subsequence, where each chosen value must be within 1 of the previously chosen one), a greedy scan fails and you need dynamic programming: dp[i] is the longest valid subsequence ending at index i, computed as 1 plus the best dp[j] over earlier j with |a[i] - a[j]| <= 1. That is O(n²) time and O(n) memory.
On [1.0, 1.5, 3.0, 2.5, 2.0, 3.5] the program gives 3 for the contiguous run (3.0, 2.5, 2.0) and 4 for the subsequence (for instance 1.0, 1.5, 2.5, 3.5), which is exactly why the two readings must not be confused. Floating-point notes: the comparison is exact here only because the data are halves; with computed values compare with a small tolerance, and mention that nan breaks ordering. An O(n log n) approach exists for the skipping version with a balanced tree keyed by value, which you can mention as an optimisation. Reported at Google (anonymous, unverified; the original wording was ambiguous).
Skipping elements allows a longer chain than the contiguous run, so the two readings give different answers on the same data.
Common traps
- Solving the subarray version when a subsequence was asked, or the reverse, because you did not ask.
- Using exact float equality on computed values. Allow a tolerance.
They might follow up with
- Can you do the skipping version faster than O(n²)? Yes, with an ordered structure over values (O(n log n)); worth naming, rarely required.
- What if the limit is a parameter? Pass it in and keep the same recurrence.
Related questions
- 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
- 29.2.8 Given two people’s busy intervals and working hours, find the time when both are free. How is it the…
- 29.1.7 Next permutation: rearrange an array into the next lexicographically greater order, in place. Walk through…
← Given two people’s busy intervals and working hours, find the time…