PubMatic SDE-2 Interview Questions, Process, and Tips

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. Brute force
We can use level order traversal (recursive) to explore all levels of the tree. Also, at each level nodes should be printed in alternating order. 
 
For example - First level of tree should be printed in left to right manner, Second level of tree should be printed in right to left manner, Third again in left to right order and so on.
 
So, we will use a Direction variable whose value will toggle a...read more
Answered Anonymously
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. Recursive approach.
The idea is to traverse the binary tree and swap the left and right subtrees.
 
The steps are as follows:
 
1. Call mirror function as mirror(node->left)  to access the left subtree.
2. Call mirror function as mirror(node->right) to access the right subtree.
3. Swap left and right subtrees using:
• ‘TEMP’ = leftSubtree
• leftSubtree = rightSubtree
• rightSubtree = ‘TEMP’
Space Complexity: O(n)Explanation...read more
Answered Anonymously
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. Using BFS
The idea is to first create an undirected graph of the given binary tree and then doing a bfs traversal of the undirected graph starting from the start node. We will keep a variable ‘count’ that will be incremented at each level of bfs traversal. ‘count-1’ is the required time needed to burn the whole tree.
 
Algorithm
 
• Initialize an unordered map ‘M’ that maps from integer to array of integers that sto...read more
Answered Anonymously
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. Modify Depth First Search
In the Depth First Search (DFS), we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a  stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of the stack. Note that a vertex is pushed to stack on...read more
Answered Anonymously
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. Find the factorial of the number
• Calculate the factorial of N.
• Initialise FACT = 1 to store factorial of N, iterate 1 <= i <= N and do FACT = FACT * i.
• Count the number of trailing zeroes in FACT. Initialise ZEROES = 0.
• Repeatedly divide the FACT by 10, if the remainder is 0, increase ZEROES by 1. If the remainder > 0, stop and return ZEROES.
Space Complexity: O(1)Explanation:
O(1), as we are using constant extra m...read more
Answered Anonymously
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. Recursive Approach
Suppose that the robber is at the ith house. The robber has two options:
• If he decides to rob this house, then he cannot rob the next house, so he’ll have to go to the house after that.
• If he decides not to rob this house, he has no restriction over choosing the next house.
You will follow the same for the rest of the houses. Thus, if maxLoot(i) is the maximum loot possible when we’re at the ith house, t...read more
Answered Anonymously
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