Phone Interview:

1. Merge two sorted lists
2. Merge K Sorted Lists (he didnt expect me to code this out, but instead give the time complexity and space complexity etc of my solution)
3. Give the Breadth First Search of a binary tree
4. Screenshot attached is very similar to this question. Essentially the question was given N computers each with the same specs (same number of CPUs, RAM and CPU specs) and given a list of the amount of memory it takes to run each task how much time would it take to complete all tasks.

My solution was to sort the tasks in size from least memory to most memory. Then take the first and last element from the task list and assign it to the first computer and then the second task and second to last task and assign it to the second computer.

First round On Site Interview:

The interview link wasnt working and then I finally got on after 5 minutes.
Initially they just ask about your favorite projects and what you do at work

This was the first round containing 2 interviewers:

1. Given a list of elements split the list into two subarrays such that the left subarray has all of its elements than the elements in the right subarray.

   Gave the brute force O(n^2) time complexity solution then gave the linear time complexity solution where

   • you iterate over the array from left to right and form a left subarray containing the maximum element so far in the left subrray.
   • You then can iterate from right to left and then keep track of the minimum element. You then can check if the maximum element in the left subarray (using the auxillary array built above) is less than the minimum element so far in the right subarray

2. Asked for me to design AWS S3

   I explained the consistency model of AWS S3 is eventually consistent and how Bloomberg would want a strictly consistent model. I suggested that when a user queries S3 after inserting data he should be blocked from retrieving data until the inserted data arrives in all availabilty zones.

   The interviewer was suggesting maybe we only need to wait till the data gets replicated to 1 avalability zone and then in the background the data gets replicated to other availability zones. I did not completely understand if this is what the interviewer said and I shouldnt have proceeded till I clarified 100%.

   I also explained that when replicating we want to replicate to the availability zones closest to you.

   At this point we ran out of time. I was a bit dissapointed. Not sure if this was going to make a difference

   This took about 12 minutes

Second round of on-site containing 2 interviewers:

1. You are given a list of elements and a lambda function. The lambda function will take two elements and return True if they belong to the same set / group. You should not worry about the implementation of the lambda function. You should return a List of Lists where each sublist are elements in the same set.

   For example if you are given [12, 11,1,3,9,6,8] and lambda_func = lambda a, b: a % 2 == b % 2

   You should return a List of Lists like the following

   [
   	[11, 1, 3, 9],
   	[12, 6,8]
   ]

   I implemented a solution where you iterate over the list and create a dictionary of sets.

   • Iterate over list for each element
     • check if element in dictionary, if it is skip this element
     • if the element is not in dictionary iterate over the keys of dictionary and check if lambda_func(key, element) returns True. If it does then add the element to that set
     • If lambda_func(key, element) returns False for all keys add a new set to your dictionary as we could not find any group that this element is part of

   I needed some assistance for this question

2. Because we had 5 minutes left before I asked I could ask the interviewer questions, this question was very simple

   Find two elements in a list of positive integers that sum to k

Good news, I received the offer!