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
2
3def jump_game(arr: list[int], start: int) -> bool:
4 seen = set()
5 queue = deque([start])
6 while queue:
7 cur = queue.popleft()
8 if arr[cur] == 0:
9 return True
10 if cur in seen:
11 continue
12 seen.add(cur)
13 if cur + arr[cur] < len(arr):
14 queue.append(cur + arr[cur])
15 if cur - arr[cur] >= 0:
16 queue.append(cur - arr[cur])
17 return False
18
19if __name__ == "__main__":
20 arr = [int(x) for x in input().split()]
21 start = int(input())
22 res = jump_game(arr, start)
23 print("true" if res else "false")
241import 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}
541using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static bool JumpGame(List<int> arr, int start) {
8 if (arr[start] == 0) {
9 return true;
10 }
11
12 HashSet<int> visited = new HashSet<int>();
13 Queue<int> queue = new Queue<int>();
14 queue.Enqueue(start);
15
16 while (queue.Count > 0) {
17 int curr = queue.Dequeue();
18
19 if (arr[curr] == 0) {
20 return true;
21 }
22
23 int index = curr - arr[curr];
24
25 if (index >= 0 && !visited.Contains(index)) {
26 visited.Add(index);
27 queue.Enqueue(index);
28 }
29
30 index = curr + arr[curr];
31
32 if (index < arr.Count && !visited.Contains(index)) {
33 visited.Add(index);
34 queue.Enqueue(index);
35 }
36 }
37 return false;
38 }
39
40 public static List<string> SplitWords(string s)
41 {
42 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
43 }
44
45 public static void Main()
46 {
47 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
48 int start = int.Parse(Console.ReadLine());
49 bool res = JumpGame(arr, start);
50 Console.WriteLine(res ? "true" : "false");
51 }
52}
531"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}
621function jumpGame(arr: number[], start: number): boolean {
2 if (arr[start] === 0) {
3 return true;
4 }
5 const visited = new Set<number>();
6 visited.add(start);
7 const queue: number[] = [];
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: string): string[] {
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?: string) => 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