SDE - Intern

Step 1 : sort boxTypes so that boxes with the most units appear first.
Step 2 : Iterate through the boxes in sorted order.
Step 3 : Instead of counting down one by one how many boxes to take, we can calculate how many boxes of the current type to take by taking min(truckSize, numberOfBoxes). This is because the truck can fit at most truckSize more boxes, but we have numberOfBoxes left.
Step 4 : Decrease the remaining truckSize by subtracting the number of boxes we included.

Step 1 : Create a descending order map, and insert first k elements. our map's first element will;point to the greatest element in the map.
Step 2 : In the second for loop, as its a sliding window, I'm removing the first elem(
a[k-i]) and adding the current upcoming elem (a[i]) into the window.
Step 3 : for that I'm decreasing the element's frequency in the map. also note that decreasing the freq to 0 wont delete the elem from the map, so I'm using m.erase to delete the elem , and incrementing the frequency of the curr elem. and deriving the greatest elem in the map again using it->first.

Tip 1: These questions should be explained according to Amazon's Leadership principles

 

Step 1 : Initially, I gave the naive approach of traversing the tree in Inorder and while traversing, keep track of the count of the nodes visited. If the count becomes k, print the node and end the program. Complexity of this code is O(n) time and O(h) auxiliary space which I explained too and further asked if it is required to improve before starting to implement it.
Step 2 : Then I was asked to solve the problem in O(1) auxiliary space. I thought for a while and explained to him the Morris Traversal to traverse the tree in constant space O(1) space sol. He got a rough idea and asked me to implement it and then I walked him through the code by explaining each section of code with help of an example and he was satisfied.

Step 1 : Initially, I explained an array-based approach similar to this one:Method 3 of https://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/ 
So each time the find answer function is called we will have to traverse the fi[256] array each time to return the answer.
Step 2 : Then he asked me to try a different approach for a situation in which the Find Answer function is called very frequently and hence to improve the time complexity for that function. So I explained to him a new approach which was queue-based. I also explained improvement in time complexity by using queue and then asked me to implement it and so I did and again explained each section of code with 2 test examples by dry-running it.

Step 1 : I gave the recursive approach, he told me to code.
Step 2 : After that he told me to dry run the approach for {a,b,c}, i tried to make the recursion tree on the editor but it was all messy after a few steps. He then shared a whiteboard link for that, it was taking lot of time doing there so finally he shared his whatsapp and told to do it on paper and send him the image, around 35 minutes were passed until then, i shared him a tree but it was incomplete but i explained how i am moving ahead and generating output. He was convinced and we moved to the next question.

Step 1 : I had solved this question before and after some time told him the O(n) approach. He told me to code. I did so explaining each step along. I had two nested for loops in the code, so he inquired about how the approach is linear in time. 
Step 2 : We had some discussion on the code and I had to explain some parts to him again. He suggested some changes too. I deleted 4-5 lines for making those changes and for 5 minute or so was lost bringing it back due to connection issues and stuff. He told me that he had to keep a backup of the code and the changes so I should comment the unnecessary parts and not remove it. 
Step 3 : After that time was almost over and he asked if I had any questions for him. I asked about the work culture, and about the responsibilities an intern takes.