TikTok·Machine Learning Engineer·Technical Phone Screen
- Given a sorted array of distinct integers representing stone positions in a river (starting at 0), determine whether a frog can reach the last stone. The frog starts at position 0, its first jump must be exactly 1 unit, and each subsequent jump can be k-1, k, or k+1 units where k was the previous jump length (and must be greater than 0). Design an efficient algorithm, justify its correctness, and analyze time and space complexity. Also discuss pruning strategies and what inputs would hit worst-case behavior.
“I went straight to DP with a hash map keyed on stone index storing the set of jump sizes that can land there.”