Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
703 views
in Online Assessments by Expert (46,090 points) | 703 views

2 Answers

0 like 0 dislike
Best answer

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
by Expert (46,090 points)
0 like 0 dislike

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;
}
by Expert (46,090 points)