Round 1
Questions: The coding question was titled "Game of Stairs" where the player, Ron, must move from the 1st stair to the M-th stair using a set of rules:
- Pressing the Up button moves the character up in powers of 2 (i.e., 2^0, 2^1, 2^2, etc.).
- Pressing the Down button brings the character down by one stair, but this button cannot be pressed consecutively.
- Stair 1 is stair 1 and ground is stair 0. The task is to determine the number of ways Ron can move from the 1st stair to the M-th stair.
For input: 1, output: 4 distinct ways to reach.
Candidate's Approach
To solve the problem, I would use dynamic programming. The idea is to maintain an array dp where dp[i] represents the number of ways to reach stair i. The transitions would be as follows:
- For each stair
i, I can reach it fromi - 2^j(wherejis a non-negative integer such that2^j <= i) by pressing the Up button. - Additionally, I can reach stair
ifromi - 1by pressing the Down button, but only if the last move was not a Down move.
The base case would be dp[1] = 1 since there is one way to be on the first stair (starting point).
The final answer would be dp[M].
Interviewer's Feedback
No feedback provided.