Question

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

Answer 1

3 questions - 1h:55min

 

1. You are given 4 integers. Match them with the coordinates of two points and return the maximum possible square distance between the points.
2. https://leetcode.com/problems/count-good-nodes-in-binary-tree/
3. Given an array with revenue and expenses of a company (revenues are positive items in array, expenses are negative items) you can relocate expenses to the end of the array to make sure that in each point in time, the sum does not become negative. Return min number of relocations needed

Answer 2

Q1: O(24)

 

int ans;
public int maxDistance(int[] nums) {
 ans = 0;
 backtrack(nums, 0);
 return ans;  
}

private void backtrack(int[] nums, int pos) {
 int n = nums.length;
 if(pos==4) {
  int diff1 = nums[0]-nums[1];
  int diff2 = nums[2]-nums[3];
  ans = Math.max(ans, diff1*diff1 + diff2*diff2);
  return;
 }
 for(int i=pos; i<n; i++) {
  swap(nums, pos, i);
  backtrack(nums, pos+1); 
  swap(nums, pos, i);
 }
}

 

Q2: O(dfs)

 

class Solution {
    int ans;
    public int goodNodes(TreeNode root) {
        ans = 0;
        dfs(root, Integer.MIN_VALUE);
        return ans;
    }
    
    private void dfs(TreeNode node, int max) {
        if(node==null) return;
        if(node.val>=max) {
            ans++;
            max = node.val;
        }
        dfs(node.left, max);
        dfs(node.right, max);
    }
}

 

Q3: nlogn greedy

 

public int minRelocations(int[] items) {
 int sum = 0, ans = 0;
 PriorityQueue<Integer> largestExpenses = new PriorityQueue<>();
 for(int item : items) {
  sum+=item;
  if(item<0) largestExpenses.offer(item);
  if(sum<0) {
   sum-=largestExpenses.poll();
   ans++;
  }
 }
 return ans;
}