Question

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

Answer 1

1.)Largest Possible Square For Cut Sticks:
Given two Integers, cut them so that they form 4 sticks of same length(i.e. a square) and length of the side is maximized.(we can have leftovers).
Ex:
Input: A = 13, B = 11
Output: function will return 5 because we can cut two sticks of length 5 from each of the given sticks.
2.) Minimum operations to make all array elements equal by doing given two operations:
i) increment an element by 1
ii)choose two elements and increase the left one and decrease the right one.
ex:
Arr=[1,2,2,4]
we can make all elements equal to 3 by selecting 2,4 and and making them 3,3 by 2nd operaion.
and we can do first opeartion on remaining element.
3.)I do not remember exact problem statement,but it was a variation of Merge Overlapping Intervals with checking if given interval fully lies in any of the merged intervals.

Answer 2

for question 1) Binary search. i guess this would work. open for suggestions .......

 

    int[] nums = {13,11};
    int range = 0;

    for(int num : nums){
        range += num;
    }
    int lo = 1;
    int hi = range/4;
    int ans = 0;

    while(lo <= hi){
        int mid = lo + (hi-lo)/2;   
        if(check(nums,mid,4)){
            ans = mid;
            lo = mid+1;
        }
        else {
            hi = mid-1;
        }
    }
    System.out.println(ans);
}    

public static boolean check(int[] nums ,int mid, int side){
    int count = 0;
    for(int a : nums){
        count += a/mid;
    }
    return count >= side;
} 

Answer 3

First question, O(1) :

 

public static void main(String[] args) {

    System.out.println(sticksCut(13, 11) + " =? 5");
    System.out.println(sticksCut(10, 21) + " =? 7");
    System.out.println(sticksCut(2, 1) + " =? 0");
    System.out.println(sticksCut(1, 8) + " =? 2");
    System.out.println(sticksCut(5, 4) + " =? 2");
    System.out.println(sticksCut(8, 1) + " =? 2");

  }


public static int sticksCut(int a, int b) {

int option1 = 0, option2 = 0, option3 = 0, option4 = 0, option5 = 0;

option1 = a / 4;

if (a / 3 <= b) option2 = a / 3;

option3 = a / 2 > b / 2 ? b / 2 : a / 2;

if (b / 3 <= a) option4 = b / 3;

option5 = b / 4;

return Math.max(
  option1,
  Math.max(option2, Math.max(option3, Math.max(option4, option5)))
);
}

 

Second question O(nlg(n)):

 

public static void main(String[] args) {
    int[] arr = { 1, 2, 2, 4 };
    int[] arr2 = { 3, 5, 7, 10 };
    int[] arr3 = { 1, 2, 3, 4 };
    int[] arr4 = { 1, 7, 3, 4, 8 };

    System.out.println(minEqual(arr) + " =? 4");
    System.out.println(minEqual(arr2) + " =? 7");
    System.out.println(minEqual(arr3) + " =? 3");
    System.out.println(minEqual(arr4) + " =? 7");
  }

public static int minEqual(int[] arr) {
    int count = 0, temp = 0, min = 0, n = arr.length - 1;

Arrays.sort(arr);

//maximize the first operator
for (int i = 0; i <= n / 2; i++) {
  if (arr[n - i] - arr[i] >= 1) {
    count = ((arr[n - i] - arr[i]) / 2);
    min += count;
    arr[i] += count;
    arr[n - i] -= count;
  }
}

temp = arr[0];
count = 0;

//second operator
for (int i = 0; i <= n; i++) {
  if (temp == arr[i]) count++;
}

return Math.max(count, n - count) + min;
  }