SDE - 2

Naive Approach:

Step 1: we will create an array of size = sum of size of the three arrays.
Step 2: Then we will loop through all the three arrays and add them inside the newly created array.
Step 3: We will sort the array.

The interviewer asked me to optimize the solution

Optimized approach:

Step 1: First we will sort two arrays, using two pointer approach where first pointer will traverse through the first array and second pointer will traverse through the second array.
Step 2: We compare the values present in the arrays pointed by there respective pointers and then whichever was smaller we will add them in the temp array and moved that respective pointer one step ahead.
Step 3: After second step , we have merged two sorted arrays, now we will follow the first and second step on the temporary array and the third array and add the results in the final array.

The interviewer asked me can i optimize it more:

Step 1: This time i used three pointers approach. the pointers pointing to the elements of the first, second and third array respectively.
Step 2: Now we will compare all the three elements and whichever is the smallest we will add that in the result array and then the respective pointer we will increment
Step 3: Now if any of the array is exhausted we will follow the same procedure in the previous method, where we merged two sorted arrays.

Now, the interviewer was satisfied

The time was left so i jumped to the optimized solution directly.

Step 1: Create a min heap of size k.
Step 2: Insert all the first elements of all the k arrays.
Step 3: we remove the minimum from the min heap and then add the next element from the array from which the element was taken. If the array doesn’t have any more elements, then we will not do anything.
Step 4: We will keep on doing step 3 until the heap is empty.

Tip 1 : First explain the definition
Tip 2 : Try to give one example where this will perfectly fit

Tip 1 : Understand the question first, don't assume anything. Ask questions to the interviewer
Tip 2 : Explain the DB structure first and then move to the high level design
Tip 3 : You should know the terms load balancing, consistent hashing, messaging queues etc.
Tip 4 : When asked for Low Level Design, go with the class/uml diagram and list out the dependencies and accordingly explain the class structures
Tip 5 : While writing any endpoints make sure, you add proper exceptions and comments.