SDE - 1

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)).

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 normalization to reduce redundancy.

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.

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.