PhonePe Prep
- Posted
- 1 Oct 2025
Summary
This post summarizes my interview experience at PhonePe, detailing the various Data Structures & Algorithms and System Design questions I encountered across multiple technical rounds.
How it went
My interview journey at PhonePe involved several intense rounds, primarily focusing on Data Structures & Algorithms (DSA) and System Design.
DSA Rounds
The DSA rounds were comprehensive, covering a wide array of topics. I was presented with problems such as "Burning Tree" and "Shortest Path to Get All Keys". I also tackled LeetCode 1235: Maximum Profit in Job Scheduling and 1657: Determine if Two Strings Are Close. During Matchsticks to Square, I initially struggled due to misinterpreting the input format, but once I understood, my approach was satisfactory to the interviewer. For Kth Smallest Element in a Sorted Matrix, I started with a min-heap solution, and after a hint, optimized it using binary search.
Other notable DSA problems included Burst Balloons (a hard DP problem) and The Celebrity Problem. In a subsequent PS/DS round, I was asked to solve Remove K Digits and a problem from Codeforces. I also faced a custom question: "Find the minimum number of swaps to make a string palindrome", for which I used a greedy approach. Another question involved finding "the sum of all nodes at the deepest level in a binary tree".
I encountered a complex problem on maximizing total damage with spell casting, where I had to consider sliding window or dynamic programming, and removing the most stones in the same row or column, which required graph theory and Union-Find. Classic problems like Trapping Rain Water, Left View of a Binary Tree, and finding nodes at 'k' distance from a target node were also asked. I implemented a Min Stack and was tasked with printing the level order traversal of a tree with alternate direction changes, which I solved easily. Another monotonic stack problem was given, and despite modifications, I managed to solve the first two versions.
Additional problems included First Missing Positive, Longest Increasing Path in a Matrix, and an O(log n) optimization challenge for the Complete Binary Tree Inserter (which I could only solve in O(n)). Queue Reconstruction by Height, House Robber III, Kth Ancestor of a Tree Node, and Bricks Falling When Hit were also part of the technical assessments. I was also asked a question related to the Convex Hull Algorithm and how to generate random points within a circle with equal probability distribution.
System Design Rounds
The System Design rounds were equally challenging. I was asked to design a Search Autocomplete feature, where I successfully implemented a Trie-based solution and discussed scalability and optimizations. One of the final rounds was to design Instagram, where I focused on posting, immediate visibility, feed generation, and likes/comments. I covered NFRs, scale, HLD, and trade-offs, though I felt I could have elaborated more on the likes/comments service. I also had to design a service for delayed triggers, a generic online game (like Ludo/Chess) where I had to drive the discussion from FNRs to tech stack and matching logic, and Payment Gateway Integration. Another iteration of Design Instagram highlighted the interviewer's disagreement with a message queue for feed publishing/fetching at massive scale. Lastly, I designed Twitter, covering tweet posting, follow-following, timelines, and profiles, emphasizing LLD and HLD aspects.
Questions asked (62)
- 01
Burning Tree
Data Structures & Algorithms · Medium
Open the problemFind the minimum time taken to burn the entire binary tree starting from a given target node.
- 02
Shortest Path to Get All Keys
Data Structures & Algorithms · Hard
Open the problemGiven a 2D grid consisting of walls, empty cells, the starting point, keys, and locks. Return the shortest path to get all keys.
- 03
Maximum Profit in Job Scheduling
Data Structures & Algorithms · Hard
Open the problemGiven
njobs wherestartTime[i],endTime[i], andprofit[i]are the start time, end time, and profit of thei-thjob, return the maximum profit you can achieve by scheduling jobs such that no two jobs overlap. - 04
Determine if Two Strings Are Close
Data Structures & Algorithms · Medium
Open the problemTwo strings are considered 'close' if you can attain one from the other using two types of operations: 1. Swap any two existing characters. 2. Transform every occurrence of one existing character into another existing character, and vice versa. Return true if they are close, false otherwise.
- 05
Matchsticks to Square
Data Structures & Algorithms · Medium
Open the problemYou are given an integer array
matchstickswherematchsticks[i]is the length of thei-thmatchstick. You want to use all the matchsticks to form one square. You should not break any single matchstick, but you can link them up, and each matchstick must be used exactly one time. Return true if you can make this square, and false otherwise. - 06
Kth Smallest Element in a Sorted Matrix
Data Structures & Algorithms · Medium
Open the problemGiven an
n x nmatrix where each of the rows and columns is sorted in ascending order, return thek-thsmallest element in the matrix. - 07
Burst Balloons
Data Structures & Algorithms · Hard
Open the problemYou are given
nballoons, indexed from0ton - 1. Each balloon is painted with a number on it. If you burst ballooni, you will getnums[left] * nums[i] * nums[right]coins. Your goal is to burst all the balloons to get the maximum coins. Assumenums[-1] = nums[n] = 1. - 08
The Celebrity Problem
Data Structures & Algorithms · Medium
In a group of N people, a celebrity is someone who is known by everyone else but does not know anyone. Find the celebrity if one exists.
- 09
Remove K Digits
Data Structures & Algorithms · Medium
Open the problemGiven a non-negative integer
numrepresented as a string, removekdigits from the number so that the new number is the smallest possible. - 10
Codeforces 1037/D - Build Permutation (BFS/DFS Traversal)
Data Structures & Algorithms
Open the problemProblem statement from Codeforces problem 1037/D, related to tree traversals.
- 11
Minimum Swaps to Make String Palindrome
Data Structures & Algorithms · Medium
Given a string, find the minimum number of swaps required to make it a palindrome.
- 12
Sum of Nodes at Deepest Level in Binary Tree
Data Structures & Algorithms · Medium
Open the problemGiven a binary tree, find the sum of all nodes at the deepest level.
- 13
Maximize Total Damage with Spell Casting
Data Structures & Algorithms
A problem about maximizing total damage with spell casting. I had to devise a strategy, possibly using sliding window or dynamic programming, to balance choices and constraints.
- 14
Remove Most Stones with Same Row or Column
Data Structures & Algorithms · Medium
Open the problemYou are given an array of
stoneswherestones[i] = [ri, ci]represents the location of a stone on a 2D plane. You can remove a stone if and only if it shares the same row or column as another stone that has not been removed. Return the maximum number of stones that you can remove. - 15
Trapping Rain Water
Data Structures & Algorithms · Hard
Open the problemGiven
nnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. - 16
Left View of a Binary Tree
Data Structures & Algorithms · Medium
Given a binary tree, print the nodes in 'left view' order (first node at each level from the left side).
- 17
Nodes at K Distance from Target in Binary Tree
Data Structures & Algorithms · Medium
Open the problemGiven the
rootof a binary tree, the value of atargetnode, and an integerk, return an array of the values of all nodes that have a distancekfrom thetargetnode. - 18
Min Stack
Data Structures & Algorithms · Medium
Open the problemDesign a stack that supports
push,pop,top, and retrieving the minimum element in constant time. - 19
Binary Tree Zigzag Level Order Traversal
Data Structures & Algorithms · Medium
Open the problemGiven the
rootof a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). - 20
Monotonic Stack Problem with Modifications
Data Structures & Algorithms
A problem solvable using a monotonic stack. The interviewer modified the question multiple times during the interview. I solved the initial problem and its first modification.
- 21
First Missing Positive
Data Structures & Algorithms · Hard
Open the problemGiven an unsorted integer array
nums, return the smallest missing positive integer. - 22
Longest Increasing Path in a Matrix
Data Structures & Algorithms · Hard
Open the problemGiven an
m x nintegers matrix, return the length of the longest increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., no wrap-around is allowed). - 23
Complete Binary Tree Inserter
Data Structures & Algorithms · Medium
Open the problemImplement the
CBTInserterclass. The question specifically asked for an O(log n) solution for insertion, though I could only achieve O(n). - 24
Queue Reconstruction by Height
Data Structures & Algorithms · Medium
Open the problemYou are given an array of people,
people, aspeople[i] = [hi, ki].hiis the height of thei-thperson, andkiis the number of people in front of thei-thperson who have a height greater than or equal tohi. Reconstruct the queue. - 25
House Robber III
Data Structures & Algorithms · Medium
Open the problemThe thief has found himself a new place for his thievery again. There is only one entrance to this area, called
root. Besides theroot, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were robbed on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. - 26
Kth Ancestor of a Tree Node
Data Structures & Algorithms · Hard
Open the problemGiven a tree with
nnodes labeled from0ton - 1, andparent[i]denotes the parent ofi-th node. Find thek-th ancestor of a given node. - 27
Bricks Falling When Hit
Data Structures & Algorithms · Hard
Open the problemYou are given an
m x ngrid representing a map of bricks. A brick is atgrid[i][j] = 1and an empty cell is atgrid[i][j] = 0. You are also given an arrayhits, wherehits[i] = [rowi, coli]indicates a brick (if exists) at that position is removed. We need to find the number of bricks that will fall after each hit. - 28
Convex Hull Algorithm
Data Structures & Algorithms · Hard
A problem related to finding the convex hull of a set of points.
- 29
Generate Random Points in Circle with Equal Probability
Other · Medium
Write a function that generates random points within a circle with equal probability distribution.
- 30
Search in Rotated Sorted Array
Data Structures & Algorithms · Medium
Open the problemThere is an integer array
numssorted in ascending order (with distinct values). Prior to being passed to your function,numsis possibly rotated at an unknown pivot indexk. Given the arraynumsafter the rotation and an integertarget, return the index oftargetif it is innums, or-1otherwise. - 31
Binary Tree Maximum Path Sum
Data Structures & Algorithms · Hard
Open the problemA path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. The path does not necessarily need to pass through the root. The path sum is the sum of the node's values in the path. Given the
rootof a binary tree, return the maximum path sum of any non-empty path. - 32
Max Integers to Add Without Negative Sum
Data Structures & Algorithms · Medium
Given an array of integers, count the maximum number of integers you can add such that at any point, the cumulative sum from left to right never goes negative. The question was presented in a scenario.
- 33
Sum of Distances in Tree
Data Structures & Algorithms · Hard
Open the problemThere is an undirected connected tree with
nnodes labeled from0ton - 1andn - 1edges. You are given an arrayedgesof lengthn - 1, whereedges[i] = [ai, bi]indicates that there is an edge between nodesaiandbi. Return an arrayanswerof lengthnwhereanswer[i]is the sum of the distances between nodeiand all other nodes in the tree. - 34
Rotting Oranges
Data Structures & Algorithms · Medium
Open the problemYou are given an
m x ngrid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no fresh oranges remain. If this is impossible, return -1. - 35
Greedy Meeting Schedule Problem
Data Structures & Algorithms · Medium
A greedy problem similar to typical meeting scheduling or interval problems.
- 36
Monotonic Stack (Next Greater Element variant)
Data Structures & Algorithms · Medium
A problem that can be solved using a monotonic stack, similar to finding the next greater element.
- 37
Shortest Path in a Grid with Obstacles Elimination
Data Structures & Algorithms · Hard
Open the problemYou are given an
m x ninteger matrixgridwheregrid[i][j]is either0(empty) or1(obstacle). You can move up, down, left, or right. You are also given an integerk. Return the minimum number of steps to walk from(0, 0)to(m - 1, n - 1)given that you can eliminate at mostkobstacles. If it is impossible to find such a path, return-1. - 38
Maximum Sum BST in Binary Tree
Data Structures & Algorithms · Hard
Open the problemGiven a
rootof a binary tree, return the maximum sum of all nodes in anyBST(Binary Search Tree) subtree. - 39
Find the Kth Smallest Sum of a Matrix With Sorted Rows
Data Structures & Algorithms · Hard
Open the problemGiven an
m x nmatrixmatwhere each row is sorted in non-decreasing order, and an integerk, return thek-th smallest sum among all possible arrays that you can form by choosing exactly one element from each row. - 40
Number of Islands
Data Structures & Algorithms · Medium
Open the problemGiven an
m x n2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. - 41
Diameter of Binary Tree
Data Structures & Algorithms · Easy
Open the problemGiven the
rootof a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. - 42
Range Sum Query 2D - Immutable
Data Structures & Algorithms · Medium
Open the problemGiven a 2D matrix
matrix, handle multiple queries of the following type: Calculate the sum of the elements inside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2). - 43
Count Ways to Build Good Strings
Data Structures & Algorithms · Medium
Open the problemGiven integers
low,high,zero, andone. Return the number of 'good' strings, which are binary strings whose length is betweenlowandhigh(inclusive) and containzeroconsecutive '0's andoneconsecutive '1's. - 44
Binary Tree Cameras
Data Structures & Algorithms · Hard
Open the problemYou are given the
rootof a binary tree. We install cameras on some nodes of the tree. Each camera at a node can monitor itself, its parent, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree. - 45
Escape the Spreading Fire
Data Structures & Algorithms · Hard
Open the problemYou are given a
0-indexedm x ngrid of integersfire. You are in a cell(0, 0)and a fire starts at a cell(fireRow, fireCol). You want to reach a safe cell(m - 1, n - 1)before the fire reaches it. Return the maximum timetyou can wait before starting your journey, such that you can still reach the safe cell. If it is impossible to ever reach the safe cell, return-1. If you can always reach the safe cell regardless of how long you wait, return10^9. - 46
Daily Temperatures
Data Structures & Algorithms · Medium
Open the problemGiven an array of integers
temperaturesrepresents the daily temperatures, return an arrayanswersuch thatanswer[i]is the number of days you have to wait after thei-thday to get a warmer temperature. If there is no future day for which this is possible, keepanswer[i] == 0instead. - 47
Longest Increasing Subsequence
Data Structures & Algorithms · Medium
Open the problemGiven an integer array
nums, return the length of the longest strictly increasing subsequence. - 48
Minimum Path Cost in a Grid
Data Structures & Algorithms · Medium
Open the problemYou are given an
m x ninteger gridgrid. You are also given anm x ninteger matrixmoveCostwheremoveCost[r][c]is the cost to move from a cell(r, c)to any cell in the next row columnc'. - 49
Simple Bank System
Data Structures & Algorithms · Medium
Open the problemImplement a bank system with operations like
transfer,deposit, andwithdraw. This is a design problem often involving handling multiple accounts and transactions. - 50
Decoded String at Index
Data Structures & Algorithms · Medium
Open the problemYou are given an encoded string
sand an integerk. To decode the string, this is how it works: if the character is a digitd, the encoded string is repeatedd - 1times. Return thek-th character of the decoded string. - 51
Check Array Formation Through Concatenation
Data Structures & Algorithms · Easy
Open the problemYou are given an array of distinct integers
arrand an array of integer arrayspieces, where the integers inpiecesare also distinct. Return true ifarrcan be formed by concatenating the arrays inpiecesin any order. - 52
Frog Jump
Data Structures & Algorithms · Hard
Open the problemA frog is trying to cross a river. The river is divided into some number of units, and at each unit, there may or may not be a stone. The frog can only jump on stones. Given a list of stone positions (in units) in sorted ascending order, determine if the frog can reach the last stone.
- 53
Where Will the Ball Fall
Data Structures & Algorithms · Medium
Open the problemYou have a 2-D grid of size
m x nrepresenting a box with some slanted walls. A ball will drop from the top of the box. The gridgrid[i][j]can be1(representing a right-slanted wall) or-1(representing a left-slanted wall). Return an arrayanswerof sizenwhereanswer[i]is the column that the ball falls out of at the bottom, or-1if it gets stuck. - 54
Hackerrank - Down to Zero II
Data Structures & Algorithms
Open the problemYou are given an integer
N. In one move, you can either decreaseNby 1 or decreaseNto one of its divisors. Find the minimum number of moves to reach 0. - 55
Transform String by Character Conversion
Data Structures & Algorithms · Hard
Given two strings
str1andstr2of the same length, determine whether you can transformstr1intostr2by doing zero or more conversions. In one conversion you can convert all occurrences of one character instr1to any other lowercase English character. - 56
IPO
Data Structures & Algorithms · Hard
Open the problemSuppose
LeetCodewill startnprojects for you. For each projecti, you can choose to start it if you have at leastcapital[i]capital, and you'll earnprofit[i]profit. You are givenkprojects to perform and your initial capitalw. Maximize your final capital. - 57
Design Search Autocomplete Feature
System Design
Design a search autocomplete feature. I used a Trie data structure and implemented a working solution. The discussion covered scalability, handling different scenarios, and optimization of memory and time complexity.
- 58
Design Instagram
System Design
Design Instagram, focusing on core features like posting content, immediate post visibility, feed generation, and likes/comments. I covered non-functional requirements, set scale expectations, and outlined a high-level design, detailing each service and its trade-offs.
- 59
Design Delayed Trigger Service
System Design
Design a service that registers triggers with specified delays from other services and sends a response once the delay for that trigger is completed.
- 60
Design an Online Game (e.g., Ludo/Chess/SnakeNladder)
System Design
Design an online multiplayer game like Ludo or Chess. I had to lead the discussion, covering functional and non-functional requirements, high-level design, APIs, tech stack choices, implementation details, exception handling, fault tolerance, and database choices. I also explained core logic for features like player matching (e.g., Noob vs. Noob) and presented multiple approaches with their trade-offs.
- 61
Design Payment Gateway Integration
System Design
Design a system for payment gateway integration. The interviewers were looking for very specific details in the design.
- 62
Design Twitter
System Design
Design Twitter, focusing on functionalities such as posting tweets, follow/following mechanisms, user timelines, and user profiles. The interview emphasized both Low-Level Design (LLD) and High-Level Design (HLD).
How they prepared
My preparation primarily involved in-depth study of Data Structures and Algorithms, practicing a wide range of LeetCode problems, and gaining a solid understanding of System Design principles. I focused on common patterns and complex problem-solving techniques relevant to both domains.