Accenture Core Computer Science Core Computer Science Medium

Q11 /20 There is a staircase of n steps and you are on the bottom of the staircase, on the...

Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.

There is a staircase of n steps and you are on the bottom of the staircase, on the 0-th step. You can go up any of 1, 2, or 3 steps at a time.

Let us consider the problem of counting the number of step-taking patterns that will put you on exactly the n-th step from the bottom.

For instance, if there are n = 4 steps, there are 7 patterns as follows. Each number is the number of steps you take at one time.

1, 1, 1, 1.
2, 1, 1.
1, 2, 1.
1, 1, 2.
2, 2.
1, 3.
3, 1.

For this problem, you implemented a function solve as follows:

Note that all the variables are multiple precision integers.

function rec(i):
  if i == 0:
    return 1
  else:
    ans = 0
    if i >= 1:
      ans += rec(i-1)
    if i >= 2:
      ans += rec(i-2)
    if i >= 3:
      ans += rec(i-3)
    return ans

function solve(n):
  return rec(n)

However, the program is too slow and it does not return the answer for n = 1000 even if you wait a whole day. You want to speed up the program so that it returns the answer in one second even if n is in the range between 1000 and 10,000.

Which one of the following correctly states the reason the function is too slow and the solution to fix the slowness?

Show answer & explanation

Answer: C. Although `rec(i)` always returns the same value, every time `rec(i)` is called, it calls the function three times recursively. That is why the program is so slow. We can speed up the program by storing the value `rec(i)` for each `i` when it is calculated for the first time, and reusing that value every time it is called thereafter.

The original function exhibits exponential time complexity O(3^n) due to massive overlapping subproblems. For example, rec(2) is computed independently by rec(3), rec(4), and higher calls, leading to redundant recalculation billions of times. Memoization (storing and reusing computed values) reduces complexity to O(n), making n=1000 solvable in milliseconds. Options A and B address cosmetic issues (loop structure and non-existent overflow) rather than the core algorithmic problem.

Step-by-step Derivation:
Time Complexity Analysis:

Without memoization, rec(n) calls rec(n-1), rec(n-2), and rec(n-3)
Each of those calls branches into 3 more calls, creating a ternary tree
Total nodes in tree ≈ 3^n (exponential)
For n=1000: 3^1000 ≈ 10^477 operations — computationally impossible

With Memoization:

Each unique subproblem rec(i) where i ∈ [0, n] is computed exactly once
Results stored in dictionary/cache on first computation
Subsequent calls to rec(i) return cached value in O(1)
Total operations: O(n) — linear time
For n=1000: ~1000 operations — completes in milliseconds

Implementation sketch:

function solve(n):
  memo = {}
  
  function rec(i):
    if i in memo:
      return memo[i]
    
    if i == 0:
      result = 1
    else:
      result = rec(i-1) + rec(i-2) + rec(i-3)  (with bounds checks)
    
    memo[i] = result
    return result
  
  return rec(n)

Q11 /20 There is a staircase of n steps and you are on the bottom of the staircase, on the...

More Accenture technical mcq questions