Question

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

Answer 1

Image of ques

Answer 2

Java solution:

 

public static void main(String[] args) {
	int[] nums1 = { 3, 4, 2, 3, 0, 3, 1, 2, 1 };
	int[] nums2 = { 1, 0, 2, -3 };
	int[] nums3 = { 0, 0, 0, 3};
	int s = 3;
	System.out.println(canReach0(nums1, s));
	System.out.println(canReach0(nums2, s));
	System.out.println(canReach0(nums3, s));
}

private static boolean canReach0(int[] nums, int s) {
	Map<Integer, Boolean> map = new HashMap<>();
	return dfs(nums, s, map);
}

private static boolean dfs(int[] nums, int s, Map<Integer, Boolean> map) {
	if (s < 0 || s >= nums.length)
		return false;
	if (nums[s] == 0)
		return true;
	if (map.containsKey(s))
		return map.get(s);
	map.put(s, false);
	if (s - nums[s] >= 0) {
		if (dfs(nums, s - nums[s], map))
			return true;
	}
	if (s + nums[s] < nums.length) {
		if (dfs(nums, s + nums[s], map))
			return true;
	}
	return false;
}

---

 

true
true
true

Answer 3

C++ solution version

 

bool dfsArray(vector num, int s, unordered_map<int, int> m)
{
bool res = false;

 

//end
if(num[s] == 0)
    return true;

cout << "s: " << s << endl;

if(m.find(s) != m.end() )
    return false;

m[s]++;


//Go to right
if(s + num[s] < num.size() )
{
    if(dfsArray(num, s+num[s], m))
        return true;
}

//Go to left
if(s - num[s] >= 0)
{
    if(dfsArray(num, s-num[s] , m))
        return true;
}


return res;

 

}