Round 1
Questions:
Q1. Given an array of size n with integers in it. And given two numbers a and b, find the minimum possible score of ELIGIBLE sub-arrays of the given array.
i) The score of a sub-array is calculated as the number of distinct elements within that sub-array
ii) A sub-array is eligible if it contains at least 1 occurrence of a and b each.
vector<int> arr, int n, int a, int b; int ans = n+1; unordered_map<int, int> mp; int i=0; for(int j=0;j<n;j++){ mp[arr[j]]++; if(mp[a] > 0 && mp[b] > 0) ans = min(ans, (int)mp.size()); while(mp[a]>0 && mp[b]>0){ ans = min(ans, (int)mp.size()); mp[arr[i]]--; if(mp[arr[i]] == 0) mp.erase(arr[i]); i++; } } cout<<ans<<endl;
15/15 test cases passed.
Candidate's Approach
The candidate used a variable length sliding window approach to maintain a count of distinct elements in the current sub-array. The solution efficiently checks for the presence of elements a and b and updates the minimum score accordingly.
Interviewer's Feedback
No feedback provided.
Round 2
Questions: Q2. There are multiple delivery centers and delivery warehouses all over the world! The world is represented by a number line from -10^9 to 10^9. There are n delivery centers, with the i-th one at location center[i]. A location x is called a suitable location for a warehouse if it is possible to bring all the products to that point by traveling a distance of no more than d.
At any one time, products can be brought from one delivery center and placed at point x. Given the positions of n delivery centers, calculate the number of suitable locations in the world. That is, calculate the number of points x on the number line (-10^9 ≤ x ≤ 10^9) where the travel distance required to bring all the products to that point is less than or equal to d.
Note: The distance between point x and center[i] is |x - center[i]|, their absolute difference.
bool cal(vector<int> arr, int d, int x){ int sum = 0; for(int i:arr){ sum+=abs(x-i); } return sum<=d; } vector<int> arr, int n, int d; int l1 = -1e9, h1 = arr[n-1]-d; int minx = h1; while(l1<=h1){ int m = (l1+h1)/2; if(cal(arr, d, m)){ minx = m; h1=m-1; }else{ l1 = m+1; } } l1=arr[0]+d, h1=1e9; int maxx = l1; while(l1<=h1){ int m = (l1+h1)/2; if(cal(arr, d, m)){ maxx = m; l1=m+1; }else{ h1 = m-1; } } if(maxx<minx)return 0; return (maxx-minx+1);
Only 12/15 test cases passed.
Candidate's Approach
The candidate attempted to use binary search to find the minimum and maximum suitable locations for the warehouse. However, they faced issues with passing all test cases and sought help to identify the missing elements in their solution.
Interviewer's Feedback
No feedback provided.