SDE - 1

BFS can be used to solve this question.
Steps :
1. Traverse the whole tree in level order fashion using BFS along with storing the last processed node (curr).
2. Keep a tag at the end of each level to know that a particular level has ended.
3. Whenever a level ends store the last processed node value to the resultant list.
Time Complexity : O(n) [ Since, each node is traversed exactly once ]
Space Complexity : O(w) [ 'w' is the maximum width of the tree ]

The groups can be made by grouping nodes on the same level together (A node and any of it’s ancestors cannot be on the same level). So the minimum number of groups will be the maximum depth of the tree.
Steps :
1. For every node create a list of its children. 
2. For every node, check if the node is root. If it is, perform dfs starting with this node. 
3. For every such node. find the maximum depth of the tree starting with this node.
Return the maximum depth of all the depths.

The brute force solution is to traverse the array and to search elements one by one. Run a nested loop, outer loop for row and inner loop for the column
Check every element with x and if the element is found then print “element found”. If the element is not found, then print “element not found”.

Efficient Approach : The idea here is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases : 
1. The given number > the current number: This will ensure that all the elements in the current row are smaller than the given number as the pointer is already at the right-most elements and the row is sorted. Thus, the entire row gets eliminated and continues the search for the next row. 
2. The given number < the current number: This will ensure that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continues the search for the previous column, i.e. the column on the immediate left.
3. The given number == the current number: This will end the search.

• Algorithm: 
1. Let the given element be x, create two variable i = 0, j = n-1 as index of row and column
2. Run a loop until i = n
3. Check if the current element is greater than x then decrease the count of j. Exclude the current column.
4. Check if the current element is less than x then increase the count of i. Exclude the current row.
5. If the element is equal, then print the position and end.

This can be solved using recursion. The basic idea is to subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit. Keep checking for left or right child path sum equal to target sum – value at current node. 
Time complexity : o(n)

Recursion can be used here. 

Steps : 
1. Compare the head of both linked lists.
2. Find the smaller node among the two head nodes. The current element will be the smaller node among two head nodes.
3. The rest elements of both lists will appear after that.
4. Now run a recursive function with parameters, the next node of the smaller element, and the other head.
5. The recursive function will return the next smaller element linked with rest of the sorted element. Now point the next of current element to that, i.e curr_ele->next=recursivefunction()
6. Handle some corner cases. 
• If both the heads are NULL return null.
• If one head is null return the other.
• Time complexity:O(n) 
• Auxiliary Space:O(n)

Tip 1 : Be sure to do your homework on the organization and its culture before the interview.
Tip 2 : Employers want to understand how you use your time and energy to stay productive and efficient. Be sure to emphasize that you adhere to deadlines and take them seriously.
Tip 3 : Talk about a relevant incident that made you keen on the profession you are pursuing and follow up by discussing your education.