SDE - Intern

I gave the max-heap based approach, in which I told him to insert every item into the max-heap, and then return the top K. For this, he asked the time Complexity, I answered O(Klog(K*N)). He told me to optimize it further. This time I gave a pointer based approach, i.e., to set a pointer at every category and then check for max among them, then increment count for the pointer of the category in which max was found, and do it till we have found K elements. For this, he asked the time Complexity, I answered O(K*N). He told me to optimize it further by combining the above two approaches, I did it and gave the Time Complexity as O(Klog(N)).

For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. In below code, this sum is stored in ‘max_single’ and returned by the recursive function.

Tip 1 : Revise ER diagrams and practice them
Tip 2 : List all entities and their relationships involved with the app.
Tip 3 : After drawing tables apply normalisation to reduce redundancy.

I didn't knew the solution so I thought of this as given n arrays having m nos in each array and we need to sort all arrays with space cmplexity of the order O(nlogm) but definitely not O(m*n) due to memory constraints.
So this is a common Priority Queue Problem for which I told the approach.

I just did school Mathematics Addition and the interviewer seemed pleased with my approach.

Remember the carry value to be included or not at the end of for loop when you traverse both linked list.
e.g. 237+100 = 337 ( no carry )
but 999+1 = 1000 ( include carry )

Tip 1 : Discuss your Approach loudly with Interviewer.
Tip 2 : Get help if you get stuck. For these type of problems, there is no preparation. They just check our thought process.
Tip 3 : I gave solution of above problem as : Google figures time spent on page and if it is very less then it thinks it is probably misspelled

Tip 1 : Prepare for this round beforehand.( Don't take it lightly )
Tip 2 : Know about company beforehand like what work they do and how you are eligible candidate for the role they are looking for.
Tip 3 : For Sprinklr vs Amazon type questions stick to company you are applying and tell how you feel this is best opportunity for you.

Tip 1 : Prepare for this round beforehand.
Tip 2 : Develop team spirit and have some team work experience ( like SIH)
Tip 3 : HR can try to confuse you but stay calm.