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
You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.
Note:
In zigzag ord...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 by CodingNinjas
View 3 more answers
Q2. Convert binary tree to mirror tree
Given a binary tree, convert this binary tree into its mirror tree.
A binary tree is a tree in which each parent node has at most two children.
Mirror of a Tree: Mirr...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 by CodingNinjas
View 1 more answer
Q3. Time to Burn Tree
You have been given a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task i...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 by CodingNinjas
View 1 more answer

Round duration - 90 Minutes
Round difficulty - Medium

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

Q1. Technical Questions
Started off by asking Java Fundamentals, OOPS,DesignPatters(Singleton,Factory,Cascade), HashMap Internals,Collections, Fail Fast-Fail Safe Iterators
Then jumped off to Problem Solving - E...read more
Add your answer
Q2. Topological Sort
A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.
Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’...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 by CodingNinjas
View 1 more answer

Round duration - 100 Minutes
Round difficulty - Hard

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

Q1. Technical Questions
He took a deep dive into my resume and asked a lot of questions around my projects asking my roles and responsibilities in each project/product/team. Asked about Kadane's Algorithm.
After...read more
Add your answer
Q2. Trailing Zeros in Factorial
You are given an integer N, you need to find the number of trailing zeroes in N! (N factorial).
Note:
1. Trailing zeros in a number can be defined as the number of continuous...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 by CodingNinjas
View 1 more 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
 

Q1. Technical Questions
Question 1 : A scenario/story where Bitonic Sequence was to be implemented.
Question 2 : Design a Scheduler for scheduling n jobs with input give at the runtime , input can be t...read more
Add your answer

Round duration - 90 Miinutes
Round difficulty - Medium

Discussion with Hiring Manager
 

Q1. Basic HR Questions
My Aspirations, Problems I have solved, How do I motivate myself, Disappointment faced, Situations where your solution was accepted other than your peers and How did you convince the mana...read more
Add your answer
Q2. Technical Questions
Deep-Discussion on my projects , My Approach on there use cases /or the problem they were facing , Questions on Spark(Broadcast Join Scenario), Questions on Mapreduce (Scenario Based)
Que...read more
Add your answer
Q3. Loot Houses
A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.
Input Format :
The first line of...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 by CodingNinjas
View 2 more answers

Round duration - 75 Minutes
Round difficulty - Easy

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

Q1. Basic HR Questions
Manager Relationships, Difficult problem solved, Normal day routine, How do I manage a stressful situaiton, Leadership skills, Why I want to join there company, What will happen If I get ...read more
Add your answer
Q2. Technical Questions
Discussion on my resume, Work exp, Team Size, Duration of Projects, Counter Question: Why did you switch 2 companies with your experience and why do you want to switch and come here(Desp...read more
Add your answer