I recently attended a tech OA interview and stumbled upon this question. I am able to come up with the Top Down memoization approach myself. But I am struggling to get the Bottom up code for the same problem even though I am able to figure out the recurrence relation.
Question:
Maximum Reachable index There is an infinite array of integers numbered consecutively from 0. At each step, a pointer can move from index i to index i+j, or remain where it is. The value of i begins at 0. The value of j begins at 1 and at each step, j increments by 1. There is one known index that must be avoided called badIndex. Determine the highest index that can be reached in a given number of steps. Example steps = 4 badElement = 6 The pointer is limited to 4 steps and should avoid the bad item 6.
• Scenario 1:
• In the first step, i starts at 1. Move 1 unit to index 0+1=1 and j = 2.
• At step 2, move 2 units to index 1+2=3, and j = 3.
• At step 3, do not move. Otherwise, the pointer will move 3 units to the bad item 6. Now j = 4.
• At step 4, move 4 units to item 3 + 4 = 7.
• Scenario 2:
At step 1, remain at index 0. Now j = 2.
• At step 2, move 2 units to index 0+2=2 and j = 3.
• At step 3, move 3 units to index 2+3=5 and j = 4
• At step 4, move 4 units to index 5+4=9
So the answer, the maximum reachable index is 9
My Top Down Approach code:
class Solution:
def maxIndexAvoidingBadIndex(self, steps, badIndex) -> int:
memo = {}
def dfs(i, j):
# Base cases
if i == badIndex:
return 0
if j == steps + 1:
return i
if (i, j) in memo:
return memo[(i, j)]
result = max(dfs(i + j, j + 1), dfs(i, j + 1))
memo[(i, j)] = result
return result
return dfs(0, 1)
I need help in understanding how to derive the bottom up tabulation solution for this one, thanks! I am just also pasting the bottom up code, that I have in mind right now even though it's not the right one, just for the reference.
def maxIndexAvoidingBadIndex_BU(self, steps, badIndex):
dp = [0] * (steps + 2)
dp[0] = 0
for j in range(1, len(dp)):
if j + dp[j - 1] != badIndex:
dp[j] = max(j + dp[j - 1], dp[j - 1])
print(dp)
return dp[-1]
Maybe this isn't answering the question as asked, but I don't think this is a dynamic programming problem. If you never remain where you are, you'll get to index 1, 3, 6, 10, and so on up through the triangular numbers. If badIndex is a triangular number you can minimally miss it by remaining where you on on step 1.
So the logic is:
if istriangular(badindex) && badIndex <= n*(n+1)/2 {
return n*(n+1)/2 - 1
}
return n*(n+1)/2
where istriangular(k) is true when k is a triangle number. You can search around for how to implement this efficiently (effectively O(1)).