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 the 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        cur = queue.popleft()
9        if arr[cur] == 0:
10            return True
11        if cur in seen:
12            continue
13        seen.add(cur)
14        if cur + arr[cur] < len(arr):
15            queue.append(cur + arr[cur])
16        if cur - arr[cur] >= 0:
17            queue.append(cur - arr[cur])
18    return False
19
20if __name__ == "__main__":
21    arr = [int(x) for x in input().split()]
22    start = int(input())
23    res = jump_game(arr, start)
24    print("true" if res else "false")
25

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

1"use strict";
2
3function jumpGame(arr, start) {
4    if (arr[start] === 0) {
5        return true;
6    }
7    const visited = new Set();
8    visited.add(start);
9    const queue = [];
10    queue.push(start);
11
12    while (queue.length > 0) {
13        const curr = queue.shift();
14
15        if (arr[curr] === 0) {
16            return true;
17        }
18        let index = curr - arr[curr];
19
20        if (index >= 0 && !visited.has(index)) {
21            visited.add(index);
22            queue.push(index);
23        }
24        index = curr + arr[curr];
25
26        if (index < arr.length && !visited.has(index)) {
27            visited.add(index);
28            queue.push(index);
29        }
30    }
31    return false;
32}
33
34function splitWords(s) {
35    return s === "" ? [] : s.split(" ");
36}
37
38function* main() {
39    const arr = splitWords(yield).map((v) => parseInt(v));
40    const start = parseInt(yield);
41    const res = jumpGame(arr, start);
42    console.log(res);
43}
44
45class EOFError extends Error {}
46{
47    const gen = main();
48    const next = (line) => gen.next(line).done && process.exit();
49    let buf = "";
50    next();
51    process.stdin.setEncoding("utf8");
52    process.stdin.on("data", (data) => {
53        const lines = (buf + data).split("\n");
54        buf = lines.pop();
55        lines.forEach(next);
56    });
57    process.stdin.on("end", () => {
58        buf && next(buf);
59        gen.throw(new EOFError());
60    });
61}
62