Daily bit(e) of C++ | Bouncing ball
Daily bit(e) of C++ #7, Common interview questions: bouncing ball
Today, we will look at a common interview question - Bouncing ball.
Given a list of targets arranged in a line, determine whether a ball bounce can reach a final target. The ball can only bounce off the targets, and if it reaches a target with a horizontal speed of 'i', it will bounce off with horizontal speed 'i-1', 'i' or 'i+1'.
The ball will never completely lose forward horizontal speed (or bounce back).
The initial throw has a horizontal speed of 1.
As an example, for the input {0,1,3,4,6,9,13}, the ball can reach the final target by:
bouncing off target 1 with speed 2
bouncing off target 3 with speed 1
bouncing off target 4 with speed 2
bouncing off target 6 with speed 3
and finally bouncing off target 9 with speed 4 and landing on the final target
For the input {0,1,3,7,10,14}, the ball can't reach the final target, as the jump between 3 and 7 is too large.
Before you continue to read the solution, try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://godbolt.org/z/9x6PsheEW.
Solution
The main complication in this problem is that a target may be reachable from multiple other targets at different speeds, which also dictates different exit speeds.
However, if we would have the list of speeds at which a particular target is reachable, constructing the set of reachable targets from this one is trivial.
This already points us to a dynamic programming solution. In the beginning, we know only that the target at a distance of '1' is reachable from our starting position.
However, since the ball cannot bounce back, we can iterate over targets once and build up the database of speeds at which each target is reachable, using that information when we arrive at each target.
The complexity of this solution might not be apparent. Our outer loop iterates over all targets once, and the inner loop iterates over all possible speeds. Since there is only one speed at which two specific targets connect, at most, the inner loop will have the same cardinality as the outer loop.
This leads us to O(n*n) time complexity. Since our loops directly map to the storage, we also end up with O(n*n) space complexity.