SDE - 1

BFS is a traversing algorithm we start traversing from a selected node (starting node) and traverse the graph layer wise thus exploring the neighbor nodes (nodes which are directly connected to source node). And then move towards the next-level neighbor nodes.
Pseudocode :
BFS (G, s) 
Q.push( s ) //Inserting s in queue Q until all its neighbor vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue, whose neighbor will be visited now
u = Q.pop( )
//processing all the neighbors of u 
for all neighbors v of u in Graph G
if v is not visited 
Q.push( v ) //Stores v in Q to further visit its neighbor
mark w as visited.

The DFS algorithm is a recursive algorithm based on the idea of backtracking. It starts with the initial node of the graph G, and then goes to deeper and deeper until we find the goal node or the node which has no children.
Pseudocode :
DFS(G, s):
mark s as visited
for all neighbors v of s in Graph G:
if v is not visited:
DFS-recursive(G, v)

The recursive approach involves direct implementation of mathematical recurrence formula. 
F(n) = F(n-1)+F(n-2)
Pseudocode :
fibonacci(n):
if(n<=1)
return n;
return fibonacci(n-1) + fibonacci(n-2)

This is an exponential approach. 
It can be optimized using dynamic programming. Maintain an array that stores all the calculated fibonacci numbers so far and return the nth fibonacci number at last. This approach will take O(n) time complexity and O(n) auxiliary space.

A level order traversal based solution can be presented here. For each level, we need to print the first node i.e. the leftmost node of that level.
Steps :
1. Make a queue of node type and push the root node in the queue. 
2. While the queue is not empty, do :
2.1 Determine the current size of the queue. 
2.2 Run a for loop to traverse all nodes of the current level and do :
2.2.1 Remove the topmost node from the queue. 
2.2.2 If i==0 (first node of that level) , print it. 
2.2.3 Push the left and right child of the node if they exist. 

Time Complexity : O(n), where n is number of nodes in binary tree

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 ]

This problem can be solved using recursion. Recursively calculate height of left and right subtrees for each node node and assign height to the node as max of the heights of two children plus 1
Algorithm :
height()
1. If tree is empty , return -1
2. Else
(a) Get the height of left subtree recursively i.e. call height( tree->left-subtree)
(a) Get the height of right subtree recursively i.e. call height( tree->right-subtree)
(c) Get the max of height of left and right subtrees and add 1 to it for the current node.
max_depth = max(height of left subtree, height of right subtree) + 1
(d) Return max_depth

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.