Question

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

Answer 1

I recently gave Microsoft Online Assessment for SE-2 on Codility.

 

There were two questions:

 

1. An easy debugging question - a minor change in the if condition resolved the bug
2. Below Coding question - could not solve
   
   
   
   

Answer 2

here is code in java. we are doing below given steps

 

1. identifying range for each crane and after that sort it in by range end. merge all overlapping interval to create disjoint range. after that check which range has start point and check if end point is also in that range. if both are in same range return true otherwise return false. Time complexity is nlogn.

 

// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
int[] A = new int[]{1 , 4, 2};
int[] P = new int[]{10, 4, 5};
System.out.println(solution(A , P , 200, 1));
}

 

public static boolean solution(int[] A , int[] P , int B , int E){
    List<int[]> range = new ArrayList<>();
    
    for(int i = 0 ; i < A.length ; i++){
        range.add(new int[]{ A[i] - P[i] , A[i] + P[i]});
    }
    
    Collections.sort(range , (a , b) -> a[1] - b[1]);
    
    List<int[]> disjoint = new ArrayList<>();
    
    for(int i = 0 ; i < range.size() ; i++){
        
        int start  = range.get(i)[0];
        int end = range.get(i)[1];
        while( i < range.size() -1 && end >= range.get(i+1)[0]){
            start = Math.min(start , range.get(i+1)[0]);
            end = range.get(i+1)[1];
            i++;
        }
        
        disjoint.add(new int[]{start , end});
    }
    
    int lo = 0 , hi = disjoint.size() -1;
    
    while(lo <= hi){
        int mid = (lo + hi + 1)/2;
        int[] tmp = disjoint.get(mid);
        if(B >= tmp[0] && B <= tmp[1]){
            if(E >= tmp[0] && E <= tmp[1]){
                return true;
            }else{
                return false;
            }
            
        }else if(B >= tmp[0]){
            lo = mid+1;
        }else{
            hi = mid-1;
        }
    }
    
    return false;
}

 

}

Answer 3

Fully working sol^n. Don't know if I should return true or false in the case when B and E are equal.

 

class Solution {
    public boolean solution(int[] A, int[] P, int B, int E) {
        if(B == E) return true;
        int[][] intervals = new int[P.length][];

        for(int i = 0 ; i < P.length ; i++)
            intervals[i] = new int[]{ P[i] - A[i] , P[i] + A[i]};

        int[][] merged = merge(intervals);
        int low = 0, high = merged.length - 1;
        int start = Math.min(B, E), end = Math.max(B, E);

        while (low < high) {
            int mid = (low + high) >>> 1;
            if (merged[mid][0] == start) return end <= merged[mid][1];
            if (merged[mid][0] < start) low = mid + 1;
            else high = mid;
        }
        return checkInterval(merged[low], start, end);
    }

    public boolean checkInterval(int[] interval, int start, int end) {
        return start >= interval[0] && end <= interval[1];
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int [][]{};
        Arrays.sort(intervals, (int [] a, int [] b) -> a[0] - b[0]);
        ArrayList list = new ArrayList();
        int i = intervals[0][0];
        int j = intervals[0][1];
        boolean first = true;
        for (int[] set : intervals) {
            if (first) {
                first = false;
                continue;
            }
            if (set[0] <= j) {
                j = Math.max(j, set[1]);
            } else {
                list.add(new int[]{i, j});
                i = set[0];
                j = set[1];
            }
        }
        list.add(new int[]{i, j});
        return list.toArray(new int[list.size()][2]);
    }
}

Answer 4

def solve(a,p,b,e):
    if b>e:
        b,e = e,b

    intervals = []

    for i,j in zip(a,p):
        intervals.append([j-i,j+i])

    intervals.sort(key = lambda x:x[0])
    merged = [intervals[0]]
   
    for interval in intervals[1:]:
        if merged[-1][1]>=interval[0]:
            merged[-1][1] = max(merged[-1][1],interval[1])
        else:
            merged.append(interval)
    
    print(merged)

    flag = True
    for i in merged:
        if i[0]<=b<=i[1] and i[0]<=e<=i[1]:
            print("TRUE")
            flag = False
            break
    if flag:
        print("FALSE")


if __name__ == '__main__':
    # a = [1,4,2]
    # p = [10,4,7]
    # b = 11
    # e = 1

    # a = [2,1]
    # p = [5,1]
    # b = 2
    # e = 6

    a = [2,1]
    p = [5,1]
    b = 3
    e = 6

    solve(a,p,b,e)

Answer 5

#include
#include<bits/stdc++.h>
using namespace std;

 

bool solve(vector& A, vector& P, int start, int end){
vector<vector> intervals;
for(int i=0; i<P.size(); i++){
intervals.push_back(vector{P[i]-A[i], P[i]+A[i]});
}
sort(intervals.begin(), intervals.end());
vector<vector> ans;
for(vector interval : intervals){
if(ans.empty() || ans.back()[1]<interval[0]){
ans.push_back(interval);
}
else{
ans.back()[1] = max(ans.back()[1], interval[1]);
}
}

 

for(vector<int> v : ans){
	bool flag1 = false, flag2 = false;
	if(start >= v[0] && start <= v[1]){
		flag1 = true;
	}
	if(end >= v[0] && end <= v[1]){
		flag2 = true;
	}
	if(flag1 && flag2){
		return true;
	}
}
return false;

 

}

 

int main() {
vector A = {1, 4, 2};
vector P = {10, 4, 7};
int b = 11;
int e = 1;
cout << solve(A, P, b, e) << " ";
return 0;
}

Answer 6

This question is similar to https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/

Basic idea (already described in other comments) is to convert this problem into merge intervals using [P[K] - A[K], P[K] + A[K]]

This way, if there is a follow up question of minimum crane moves we can return the number of merged intervals on the fly

Answer 7

I had the exact same online assessment question. I did it with the merge intervals approach. My solution passed all 5 example test cases but when I submitted it, it only passed 3/7 cases. Can't figure out why. Can someone help? Would really appreciate it.

 

public class Solution {
	public static class Range{
		int start;
		int end;
		public Range(int start, int end) {
			this.start = start;
			this.end = end;
		}
		public boolean containsBoth(int B, int E) {
			if(B >= start && B <= end && E >=start && E <= end) {
				return true;
			}
			return false;
		}
		public String toString() {
			return "[" + String.valueOf(start) + "," + String.valueOf(end) + "]";
		}
	}
	public boolean solution(int[] A, int[] P, int B, int E) {
        // write your code in Java SE 8
		List<Range> ranges = new ArrayList<>();
		
		for(int i=0; i<A.length; i++) {
			Range r = new Range(P[i]-A[i], P[i]+A[i]);
			ranges.add(r);
		}
		Collections.sort(ranges, (r1, r2) -> Integer.compare(r1.start, r2.start));
		
		System.out.println(ranges);
		
		//merge overlapped ranges
		List<Range> merged = new ArrayList<>();
		Range cur = ranges.get(0);
		for(int i=1; i<ranges.size(); i++) {
			Range next = ranges.get(i);
			if(cur.end >= next.start && cur.end <= next.end) {//merge
				cur.end = next.end;
			}
			else {//break
				merged.add(cur);
				cur = next;
			}
		}
		
		if(merged.size() == 0 || cur.end != merged.get(merged.size()-1).end) {
			merged.add(cur);
		}
		
		System.out.println(merged);
		
		for(Range r : merged) {
			if(r.containsBoth(B, E)) {
				return true;
			}
		}
		return false;
    }
	public static void main(String[] args) {
		int[] A = new int[] {2, 1};
		int[] P = new int[] {5, 1};
		System.out.println(new Solution().solution(A, P, 2, 6));
		
		A = new int[] {2,1};
		P = new int[] {5,1};
		System.out.println(new Solution().solution(A, P, 3, 6));
		
		A = new int[] {5,5,1};
		P = new int[] {3,3,6};
		System.out.println(new Solution().solution(A, P, 4, 8));
		
		A = new int[] {1,4,2};
		P = new int[] {10,4,7};
		System.out.println(new Solution().solution(A, P, 11, 1));
	}

}