PubMatic SDE-2 Interview Questions and Answers

Implement a function to print the zigzag traversal of a Binary Tree.

• Traverse the Binary Tree level by level, alternating the direction of traversal for each level.

• Use a queue to keep track of nodes at each level and a flag to switch the direction of traversal.

• Print the values of nodes in the zigzag order as described in the problem statement.

Calculate the time in minutes required to completely burn a binary tree starting from a given node.

• Start burning from the given node and spread fire to adjacent nodes each minute

• Track the time taken for each node to burn completely

• Return the maximum time taken to burn the entire tree

Count the number of trailing zeros in the factorial of a given number.

• Count the number of factors of 5 in the factorial of the given number N.

• Divide N by 5, then by 25, then by 125, and so on, and sum up the quotients to get the total number of trailing zeros.

• Example: For N=10, 10/5=2, so there are 2 factors of 5 in 10!, hence 2 trailing zeros.

Determine the maximum amount of money a thief can steal from houses without looting two consecutive houses.

• Use dynamic programming to keep track of the maximum money that can be stolen up to each house.

• At each house, the thief can either choose to steal from the current house or skip it and steal from the previous house.

• The maximum amount of money that can be stolen without looting two consecutive houses is the maximum of the two options.

Convert a binary tree into its mirror tree by interchanging left and right children of non-leaf nodes.

• Traverse the tree in a recursive manner and swap the left and right children of each node.

• Use a temporary variable to swap the children of each node.

• Ensure to modify the tree in place without creating a new tree.

• Example: For the input tree 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the mirror tree will have inorder traversal as 7 4 2 1 6 3 5.