Microsoft OA Jump Game Solution

Microsoft OA Jump Game Solution

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.

Also See: Microsoft Online Assessment Questions and Solution

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

Solution:

Program Python:

from collections import deque
from typing import List
def jump_game(arr: List[int], start: int) -> bool:
    seen = set()
    queue = deque([start])
    while queue:
        size = len(queue)
        for i in range(size):
            cur = queue.popleft()
            if arr[cur] == 0: return True
            if cur in seen: continue
            seen.add(cur)
            if cur + arr[cur] < len(arr): queue.append(cur + arr[cur])
            if cur - arr[cur] >= 0: queue.append(cur - arr[cur])
    return False
if __name__ == '__main__':
    arr = [int(x) for x in input().split()]
    start = int(input())
    res = jump_game(arr, start)
    print('true' if res else 'false')

Program Java:

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
    public static boolean jumpGame(List<Integer> arr, int start) {
        if (arr.get(start) == 0) {
            return true;
        }
        HashSet<Integer> visited = new HashSet<>();
        visited.add(start);
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (queue.size() > 0) {
            int curr = queue.poll();
            if (arr.get(curr) == 0) {
                return true;
            }
            int index = curr - arr.get(curr);
            if (index >= 0 && !visited.contains(index)) {
                visited.add(index);
                queue.offer(index);
            }
            index = curr + arr.get(curr);
            if (index < arr.size() && !visited.contains(index)) {
                visited.add(index);
                queue.offer(index);
            }
        }
        return false;
    }
    public static List<String> splitWords(String s) {
        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
        int start = Integer.parseInt(scanner.nextLine());
        scanner.close();
        boolean res = jumpGame(arr, start);
        System.out.println(res);
    }
}

Program JavaScript:

function jumpGame(arr, start) {
    if (arr[start] === 0) {
        return true;
    }
    const visited = new Set();
    visited.add(start);
    const queue = [];
    queue.push(start);
    while (queue.length > 0) {
        const curr = queue.shift();
        if (arr[curr] === 0) {
            return true;
        }
        let index = curr - arr[curr];
        if (index >= 0 && !visited.has(index)) {
            visited.add(index);
            queue.push(index);
        }
        index = curr + arr[curr];
        if (index < arr.length && !visited.has(index)) {
            visited.add(index);
            queue.push(index);
        }
    }
    return false;
}
function splitWords(s) {
    return s == "" ? [] : s.split(' ');
}
function* main() {
    const arr = splitWords(yield).map((v) => parseInt(v));
    const start = parseInt(yield);
    const res = jumpGame(arr, start);
    console.log(res);
}
class EOFError extends Error {}
{
    const gen = main();
    const next = (line) => gen.next(line).done && process.exit();
    let buf = '';
    next();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', (data) => {
        const lines = (buf + data).split('\n');
        buf = lines.pop();
        lines.forEach(next);
    });
    process.stdin.on('end', () => {
        buf && next(buf);
        gen.throw(new EOFError());
    });
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

• Maximal Network Rank Solution
• Min Deletions To Obtain String in Right Format
• Day of week that is K days later Solution
• Minimum Adjacent Swaps to Make Palindrome Solution
• Lexicographically Smallest String
• Longest Substring Without Two Contiguous Occurrences of Letter
• String Without 3 Identical Consecutive Letters
• Microsoft OA Longest Semi-Alternating Substring
• Microsoft OA Min Steps to Make Piles Equal Height
• Max Inserts to Obtain String Without 3 Consecutive ‘a’
• Concatenated String Length with unique Characters
• Largest K such that both K and -K exist in array
• Microsoft OA Min Adj Swaps to Group Red Balls
• Maximum Length of a Concatenated String with Unique Characters
• Microsoft OA Unique Integers That Sum Up To 0
• Find N Unique Integers Sum up to Zero
• Microsoft OA Particle Velocity Solution
• Microsoft OA Arithmetic Slices Solution
• Microsoft OA Widest Path Without Trees Solution
• Microsoft OA Jump Game Solution
• Microsoft OA Fair Indexes Solution