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

1from collections import deque
2from typing import List
3
4def jump_game(arr: List[int], start: int) -> bool:
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])
16    return False
17
18if __name__ == '__main__':
19    arr = [int(x) for x in input().split()]
20    start = int(input())
21    res = jump_game(arr, start)
22    print('true' if res else 'false')
23
1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.HashSet;
4import java.util.List;
5import java.util.Scanner;
6import java.util.stream.Collectors;
7
8class Solution {
9    public static boolean jumpGame(List<Integer> arr, int start) {
10        if (arr.get(start) == 0) {
11            return true;
12        }
13
14        HashSet<Integer> visited = new HashSet<>();
15        visited.add(start);
16        ArrayDeque<Integer> queue = new ArrayDeque<>();
17        queue.offer(start);
18
19        while (queue.size() > 0) {
20            int curr = queue.poll();
21
22            if (arr.get(curr) == 0) {
23                return true;
24            }
25            int index = curr - arr.get(curr);
26
27            if (index >= 0 && !visited.contains(index)) {
28                visited.add(index);
29                queue.offer(index);
30            }
31            index = curr + arr.get(curr);
32
33            if (index < arr.size() && !visited.contains(index)) {
34                visited.add(index);
35                queue.offer(index);
36            }
37        }
38        return false;
39    }
40
41    public static List<String> splitWords(String s) {
42        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
43    }
44
45    public static void main(String[] args) {
46        Scanner scanner = new Scanner(System.in);
47        List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
48        int start = Integer.parseInt(scanner.nextLine());
49        scanner.close();
50        boolean res = jumpGame(arr, start);
51        System.out.println(res);
52    }
53}
54
1function jumpGame(arr, start) {
2    if (arr[start] === 0) {
3        return true;
4    }
5    const visited = new Set();
6    visited.add(start);
7    const queue = [];
8    queue.push(start);
9
10    while (queue.length > 0) {
11        const curr = queue.shift();
12
13        if (arr[curr] === 0) {
14            return true;
15        }
16        let index = curr - arr[curr];
17
18        if (index >= 0 && !visited.has(index)) {
19            visited.add(index);
20            queue.push(index);
21        }
22        index = curr + arr[curr];
23
24        if (index < arr.length && !visited.has(index)) {
25            visited.add(index);
26            queue.push(index);
27        }
28    }
29    return false;
30}
31
32function splitWords(s) {
33    return s == "" ? [] : s.split(' ');
34}
35
36function* main() {
37    const arr = splitWords(yield).map((v) => parseInt(v));
38    const start = parseInt(yield);
39    const res = jumpGame(arr, start);
40    console.log(res);
41}
42
43class EOFError extends Error {}
44{
45    const gen = main();
46    const next = (line) => gen.next(line).done && process.exit();
47    let buf = '';
48    next();
49    process.stdin.setEncoding('utf8');
50    process.stdin.on('data', (data) => {
51        const lines = (buf + data).split('\n');
52        buf = lines.pop();
53        lines.forEach(next);
54    });
55    process.stdin.on('end', () => {
56        buf && next(buf);
57        gen.throw(new EOFError());
58    });
59}
60

Still not clear?Β SubmitΒ the part you don't understand to our editors.