PubMatic SDE-2 Interview Questions and Answers

Round duration - 90 Minutes
Round difficulty - Medium

It was a zoom call with a SDE-2 person, after 15 mins into my background he jumped directly to the questions
 

Q1. 
Binary Tree Zigzag Traversal Problem Statement
Given a Binary Tree comprised of 'N' nodes with integer values, your task is to print the zigzag traversal of the tree.
Note:
The zigzag pattern implies th...read more
Ans. 
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.
Answered by AI
Add your answer
Q2. 
Convert Binary Tree to Mirror Tree
Convert a given binary tree into its mirror tree, where the left and right children of all non-leaf nodes are interchanged.
Input:
An integer ‘T’ denoting the number o...read more
Ans. 
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 travers...read more
Answered by AI
Add your answer
Q3. 
Time to Burn Tree Problem
You are given a binary tree consisting of 'N' unique nodes and a start node where the burning will commence. The task is to calculate the time in minutes required to completely b...read more
Ans. 
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
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

Again this was a Problem Solving round taken by a SDE-2 

Q1. 
Topological Sort Problem Statement
Given a Directed Acyclic Graph (DAG) consisting of V vertices and E edges, your task is to find any topological sorting of this DAG. You need to return an array of size ...read more
Ans. 
Implement a function to find any topological sorting of a Directed Acyclic Graph (DAG).
• Use Depth First Search (DFS) to find the topological ordering of the vertices.

• Start by visiting a vertex and recursively visit its adjacent vertices before adding it to the result array.

• Maintain a visited array to keep track of visited vertices and avoid cycles.

• Once all vertices are visited, reverse the result array to get the topolo...read more
Answered by AI
Add your answer

Round duration - 100 Minutes
Round difficulty - Hard

This round was with a SDE-3(Principal Engineer)

Q1. 
Trailing Zeros in Factorial Problem
Find the number of trailing zeroes in the factorial of a given number N.
Input:
The first line contains an integer T representing the number of test cases.
Each of the...read more
Ans. 
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.
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Hard

This round was scheduled with a SDE-3/SDE-4(Senior Principal Engineer):
He directly started with questions after my introduction of 5mins
 

Round duration - 90 Miinutes
Round difficulty - Medium

Discussion with Hiring Manager
 

Q1. 
Loot Houses Problem Statement
A thief is planning to steal from several houses along a street. Each house has a certain amount of money stashed. However, the thief cannot loot two adjacent houses. Determi...read more
Ans. 
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...read more
Answered by AI
Add your answer

Round duration - 75 Minutes
Round difficulty - Easy

This round was with VP in Redwood City , it was scheduled around 11:00 pm IST