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')
231import 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}
541function 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}
60Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.