Work experience: 2.4 years at a semiconductor product based MNC as developer.

Got a message from recruiter on LinkedIn and a phone call was scheduled. After discussing about my work experience over phone, screening interview was scheduled.

Screening round 1: 1 question -> 15/11/21 (45 mins)
Interviewer was from Google Zurich and started with intro.

Question: Given a sorted array Ar and a variable M, find min no of buckets that can be formed, where in each bucket max-min <= M.
Ex:

Ar: [1,2,5,6,7,10,12]
M: 2
Ans: 3 ([1,2],[5,6,7],[10,12]) (here for the last bucket [9,11] or [8,10] is also valid)

Explained a two pointer logic solution. Interviewer was satisfied and then asked to check all the corner cases as well. Then proceded to code.
Time: O(n) where n is size of array
Space: O(1)

Followup question 1: Lets say M is not given but the no of buckets is given. Then how will you found out the optimal value of M. Explained a basic search in range [Min,Max] of the array and for every value cheking how many buckets will be formed. Later optimised to binary search for finding the M in range [Min,Max]. O(n*log(max-min))

Followup question 2: What is the upper bound of Max in this problem and any solution to reduce it. I was not sure what he was asking and thus was not able to answer this. Later he gave an equation for upper bound.

Screening Round 2: 1 question -> 06/12/21 (45 mins)
Interviewer was from Google India and interview started with intro.

Question: Given a unsorted array Ar and a variable k, give the positions k would occupy if Ar was sorted.
Ex:

Ar: [33,11,22,11,22,33,22]
M: 22
Ans: [2,3,4]

Gave 1st solution as basic sort the array and then find the indexes where k are present.
Gave 2nd solution of linear traversal and keeping count of elements smaller than k and equal to k. Answer will be range [small, small + equal -1]. Interviewer seemed happy with logic and then asked to code it.

Time: O(n) where n is size of array
Space: O(1)

Followup question 1: Lets assume k is not given and we have to assume that the value of k is the smallest among the most frequently occuring element and then find its indexes in sorted array. He said to use the function created above.

Gave a O(n) logic for finding the smallest among the most frequently occuring element and called the above created function for that number. He seemed okay with the solution.
Time: O(n)

Followup question 2: For every element in the unsorted array, find their indexes if ar was sorted.
Started with how our findindex function was already taking O(n) for 1 element and if we will run it on n element, its going to take O(n^2). Then gave a better solution of sorting the array and doing a single traversal for getting every element index which will take O(nlogn + n). He gave some edge cases and was trying to make me utter stable sort (which i had completely forgoten at that time). He then gave me hints and finally those edges were cleared.

Update: Onsite Scheduled. Onsite Experience