Round 1(1 hour)
This round was coding based and the interviewer asked 2 coding questions. Both questions were of medium level difficulty.
Q1. Given some array of strings. Find minimum size of subset of strings to make the count > 50% of the size of the array.
E.g: [“shoes”, “face”, “pizza”, “covid”, “shoes”, “covid”, “covid”, “face”, “shoes”]
Answer is [“covid”, “shoes”]. Explanation: Frequency of the strings is as follows:
Shoes: 3, Covid: 3, “face”: 2, “pizza”: 1
So 3(shoes) + 3(coivid) = 6 makes greater than (9(size of the array)/2) i.e the size of the array.
Hint: Sort them by decreasing order of frequency.
I initially approached this question with dp approach(practiced dp a lot day before). My dp approach was creating the dp[sum][size] and then finding the solution analyzing the values. Interviewer asked me to code and I did code it. Then he said you made the problem complicated, it is an easy problem. The solution hit me instantly and again he asked me to code it.
(15 minutes remaining now.)
Q2. He explained me the problem. You are given an array and the only operations are to pick the elements from beginning or from the end. Obtain the maximum possible using exactly the k-operations.
E.g: arr = {1, 7, 8, 3, 4, 4}, k = 3
Answer would be 1+7+8 = 16.
Again I approached the problem using dp :P. I told him the recursion relation dp[i][j][k] = max(arr[i] + dp[i+1][j][k-1], arr[j] + dp[i][j-1][k-1]). He agreed and asked me to come up with an optimized approach. I took like 2 minutes but couldn’t come up with anything. He suggested me to think using the property. I got the hint and obtained the solution i.e. we can only pick continuous elements from left or from right. Answer is max of (left[x] + right[k-x]) for 0 <= x <= k.
Contact Us