0 like 0 dislike
703 views
| 703 views

0 like 0 dislike

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)