SDE - Intern

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

The question boils down to finding the number of connected components in an undirected graph. Now comparing the connected components of an undirected graph with this problem, the node of the graph will be the “1’s” (land) in the matrix. 
BFS or DFS can be used to solve this problem. In each BFS call, a component or a sub-graph is visited. We will call BFS on the next un-visited component. The number of calls to BFS function gives the number of connected components. A cell in 2D matrix has 8 neighbors. So for each cell, we process all its 8 neighbors. We keep track of the visited 1s so that they are not visited again using a visited matrix.
Time Complexity : O(m*n) where m*n is the size of the given matrix
Space Complexity : O(min(m,n))

Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices v1,v2,v3.....vn in such a way, that if there is an edge directed towards vertex vj from vertex vi , then vi comes before vj. Modified DFS can be used to solve topological sort problem. A stack can be used to implement it. Steps :
1. Make a stack to store the nodes and a Boolean array to mark all visited nodes initialized to false. 
2. Now, create a recursive helper function and call it for every unvisited node to store Topological Sort starting from all vertices one by one. 
3. In the helper function, mark the current node as visited and recur for all the unvisited vertices adjacent to this vertex. At last, Push current vertex to stack which stores result.
4. After all the nodes are processed, print the contents of the stack.
Time Complexity : O(V+E)
Space Complexity : O(V)

A direct approach is to traverse the entire linked list and calculate its length. Traverse the list again and return the (length-N+1) node. But this approach involves two traversals of the linked list. 
To further optimize the solution, the question can be solved in one traversal only. Two pointers can be used here. Steps :
1. Initialize both the slow pointer and the fast pointer to the head node.
2. First, move fast pointer to n nodes from the head node.
3. Now, move both the pointers one by one until the fast pointer reaches the end of the list.
4. Now, the slow pointer will point to the nth node from the end. This is because when we started advancing pointers 'fast' and 'slow', difference between them was of 'n' nodes which is maintained while advancing these pointers.
Return the slow pointer.
Time Complexity : O(n)