Question

Microsoft | OA Coding Questions and Solutions | Set - 86 | 2022

Answer 1

https://leetcode.com/problems/jump-game-iii/

 

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

---

 

Related problems:

 

• https://leetcode.com/problems/jump-game/

Answer 2

Javascript recursive solution

 

function canReach(arr, start) {
  if (start < 0 || start > arr.length -1 || arr[start] === -1) return false
    const val = arr[start];  
    
    if (val === 0) return true
    
    arr[start] = -1;
    return canReach(arr, start + val) || canReach(arr, start - val)
};

Answer 3

From some position you go left and right
if left or right not in region skip
if we are at 0 return True
if we have been there before skip

 

def jumpGame(arr,start):
    memory = {}
    def helper(mem,start):
        if start < 0 or start > len(arr) - 1: return False
        if start in mem: return False
        if arr[start] == 0: return True
        mem[start] = 1
        return helper(mem,start+arr[start]) or helper(mem,start-arr[start])

    return helper(memory,start)

print(jumpGame([3, 4, 2, 3, 0, 3, 1, 2, 1],7))
print(jumpGame([3, 4, 1, 3, 0, 3, 1, 2, 1],7))

 

I hope I get back tracking examples, these take me like 3-5 mins to do. Everything besides these take me ages usually -___-

Answer 4

C++ Concise Solution

 

bool canReach(vector<int>& arr, int start) {
    int n = arr.size();
    vector<bool> seen(n, false);
    // breadth first search
    queue<int> q;
    q.push(start);
    seen[start] = true;
    while(!q.empty()) {
        start = q.front(); q.pop();
        if(arr[start] == 0) return true;
        int left = start - arr[start], right = start + arr[start];
        if(left >= 0 && !seen[left]) {
            q.push(left);
            seen[left] = true;
        }
        if(right < n && !seen[right]) {
            q.push(right);
            seen[right] = true;
        }
    }
    return false;
}

Answer 5

Java simple solution with DFS

 

class Solution {
    public boolean canReach(int[] arr, int start) {

        boolean[] visited = new boolean[arr.length];
        
        return canReach(arr, start, visited);
    }
    
    private boolean canReach(int[] arr, int start, boolean[] visited) {
        var x = arr[start];
        if(arr[start] == 0) return true;
        if(!visited[start]){
            visited[start] = true;
            if(start - arr[start] >= 0 && canReach(arr, start - arr[start], visited)) return true;
            if(start + arr[start] <= arr.length - 1 && canReach(arr, start + arr[start], visited)) return true ;
        }
        return false;
    }
}

Answer 6

super simple and easy c++

 

// start: 7:34, end: 7:45
class Solution {
public:
    std::unordered_set<int> d_visited;
    
public:
    bool canReach(vector<int>& arr, int start) { // [4,0,1], start = 1
        if (start < 0 || start >= arr.size()) return false;
        if (arr[start] == 0) return true;
        if (d_visited.count(start) != 0) return false;
        
        d_visited.insert(start);
        return    canReach(arr, start + arr[start]) 
               || canReach(arr, start - arr[start]);
            
    }
};

Answer 7

Java solution:

 

public static void main(String[] args) {
	int[] nums = {3, 4, 2, 3, 0, 3, 1, 2, 1};
	int start = 7;
	System.out.println(canReach0DFS(nums, start));
	System.out.println(canReach0BFS(nums, start));
}

private static boolean canReach0BFS(int[] nums, int start) {
	Queue<Integer> q = new LinkedList<>();
	q.offer(start);
	Set<Integer> visited = new HashSet<>();
	while(!q.isEmpty()) {
		int cur = q.poll();
		if(nums[cur] == 0)
			return true;
		if(!visited.contains(cur)) {
			visited.add(cur);
			if(cur - nums[cur] >= 0)
				q.offer(cur - nums[cur]);
			if(cur + nums[cur] < nums.length)
				q.offer(cur + nums[cur]);
		}
	}
	return false;
}

private static boolean canReach0DFS(int[] nums, int start) {
	Set<Integer> visited = new HashSet<>();
	List<String> lst = new ArrayList<>();
	return dfs(nums, visited, start, lst);
}

private static boolean dfs(int[] nums, Set<Integer> visited, int cur, List<String> lst) {
	if(cur < 0 || cur >= nums.length || visited.contains(cur))
		return false;
	if(nums[cur] == 0) {
		System.out.println(lst);
		return true;
	}
	visited.add(cur);
	lst.add("left");
	boolean lRes = dfs(nums, visited, cur - nums[cur], lst);
	lst.remove(lst.size() - 1);
	if(lRes) return true;
	lst.add("right");
	boolean rRes = dfs(nums, visited, cur + nums[cur], lst);
	lst.remove(lst.size() - 1);
	if(rRes) return true;
	return false;
}

---

 

[left, left, right]
true
true

Answer 8

Java BFS Solution

 

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 4, 2, 3, 0, 3, 1, 2, 1};
	    System.out.println(canReach(nums, 7));
        int arr[] = {3, 4, 2, 3, 0, 5, 1, 2, 1};
        System.out.println(canReach(arr, 7));
    }
    
    public static boolean canReach(int nums[], int start){
        if(nums[start] == 0){
            return true;
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while(queue.size()>0){
            int curr = queue.poll();
            if(nums[curr] == 0){
                return true;
            }
            int index = curr - nums[curr];
            if(index >= 0 && !visited.contains(index)){
                visited.add(index);
                queue.offer(index);
            }
            index = curr + nums[curr];
            if(index < nums.length && !visited.contains(index)){
                visited.add(index);
                queue.offer(index);
            }
        }
        return false;
    }
}