Microsoft Online Assessment (OA) - Jump Game

You are given an array of non-negative integers arr and a start index. When you are at an index i, you can move left or right by arr[i]. Your task is to figure out if you can reach value 0.

Example 1:

Input: arr = [3, 4, 2, 3, 0, 3, 1, 2, 1], start = 7
Output: true
Explanation:

left -> left -> right

Example 2:

Input: arr = [3, 2, 1, 3, 0, 3, 1, 2, 1], start = 2
Output: false

Try it yourself

Implementation

1
+
from collections import deque
1
2
from typing import List
2
3
3
4
def jump_game(arr: List[int], start: int) -> bool:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
5
+
    seen = set()
6
+
    queue = deque([start])
7
+
    while queue:
8
+
        size = len(queue)
9
+
        for i in range(size):
10
+
            cur = queue.popleft()
11
+
            if arr[cur] == 0: return True
12
+
            if cur in seen: continue
13
+
            seen.add(cur)
14
+
            if cur + arr[cur] < len(arr): queue.append(cur + arr[cur])
15
+
            if cur - arr[cur] >= 0: queue.append(cur - arr[cur])
5
16
    return False
6
17
7
18
if __name__ == '__main__':
8
19
    arr = [int(x) for x in input().split()]
Expand 3 lines ...