PolicyBazaar Software Developer Interview Questions and Answers

BFS traversal of an undirected and disconnected graph starting from vertex 0.

• Implement BFS algorithm to traverse the graph starting from vertex 0.

• Use a queue to keep track of visited nodes and their neighbors.

• Ensure the traversal starts from vertex 0 and follows the BFS order.

• Output the BFS traversal sequence for each test case in a separate line.

• Handle disconnected components by checking for unvisited nodes.

• Consider the constraints for the number of vertices and edges in the...read more

DFS traversal problem to find connected components in an undirected and disconnected graph.

• Use Depth First Search (DFS) algorithm to traverse the graph and find connected components

• Maintain a visited array to keep track of visited vertices

• Iterate through all vertices and perform DFS on unvisited vertices to find connected components

Calculate the Nth Fibonacci number efficiently using dynamic programming.

• Use dynamic programming to store and reuse previously calculated Fibonacci numbers.

• Start with base cases F(1) and F(2) as 1, then calculate subsequent Fibonacci numbers.

• Optimize the solution to avoid redundant calculations by storing intermediate results.

• Time complexity can be reduced to O(N) using dynamic programming.

Find the height of a Binary Tree given its Inorder and Level Order traversals without constructing it.

• Use the properties of Inorder and Level Order traversals to determine the height of the Binary Tree.

• The height of a Binary Tree is the number of edges on the longest path from the root to a leaf node.

• Consider edge cases like a single node tree or empty tree while calculating the height.

The task is to output the right view of a binary tree, which includes the nodes visible when observed from the right.

• Perform level order traversal of the binary tree.

• For each level, add the rightmost node to the result.

• Print the result as the right view of the binary tree.

• Handle null nodes represented by -1 in the input.