PhonePe Prep

Posted
1 Oct 2025
464 reads

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)

  1. 01

    Burning Tree

    Data Structures & Algorithms · Medium

    Find the minimum time taken to burn the entire binary tree starting from a given target node.

    Open the problem
  2. 02

    Shortest Path to Get All Keys

    Data Structures & Algorithms · Hard

    Given a 2D grid consisting of walls, empty cells, the starting point, keys, and locks. Return the shortest path to get all keys.

    Open the problem
  3. 03

    Maximum Profit in Job Scheduling

    Data Structures & Algorithms · Hard

    Given n jobs where startTime[i], endTime[i], and profit[i] are the start time, end time, and profit of the i-th job, return the maximum profit you can achieve by scheduling jobs such that no two jobs overlap.

    Open the problem
  4. 04

    Determine if Two Strings Are Close

    Data Structures & Algorithms · Medium

    Two 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.

    Open the problem
  5. 05

    Matchsticks to Square

    Data Structures & Algorithms · Medium

    You are given an integer array matchsticks where matchsticks[i] is the length of the i-th matchstick. 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.

    Open the problem
  6. 06

    Kth Smallest Element in a Sorted Matrix

    Data Structures & Algorithms · Medium

    Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix.

    Open the problem
  7. 07

    Burst Balloons

    Data Structures & Algorithms · Hard

    You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it. If you burst balloon i, you will get nums[left] * nums[i] * nums[right] coins. Your goal is to burst all the balloons to get the maximum coins. Assume nums[-1] = nums[n] = 1.

    Open the problem
  8. 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.

  9. 09

    Remove K Digits

    Data Structures & Algorithms · Medium

    Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

    Open the problem
  10. 10

    Codeforces 1037/D - Build Permutation (BFS/DFS Traversal)

    Data Structures & Algorithms

    Problem statement from Codeforces problem 1037/D, related to tree traversals.

    Open the problem
  11. 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. 12

    Sum of Nodes at Deepest Level in Binary Tree

    Data Structures & Algorithms · Medium

    Given a binary tree, find the sum of all nodes at the deepest level.

    Open the problem
  13. 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. 14

    Remove Most Stones with Same Row or Column

    Data Structures & Algorithms · Medium

    You are given an array of stones where stones[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.

    Open the problem
  15. 15

    Trapping Rain Water

    Data Structures & Algorithms · Hard

    Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

    Open the problem
  16. 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. 17

    Nodes at K Distance from Target in Binary Tree

    Data Structures & Algorithms · Medium

    Given the root of a binary tree, the value of a target node, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

    Open the problem
  18. 18

    Min Stack

    Data Structures & Algorithms · Medium

    Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

    Open the problem
  19. 19

    Binary Tree Zigzag Level Order Traversal

    Data Structures & Algorithms · Medium

    Given the root of 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).

    Open the problem
  20. 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. 21

    First Missing Positive

    Data Structures & Algorithms · Hard

    Given an unsorted integer array nums, return the smallest missing positive integer.

    Open the problem
  22. 22

    Longest Increasing Path in a Matrix

    Data Structures & Algorithms · Hard

    Given an m x n integers 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).

    Open the problem
  23. 23

    Complete Binary Tree Inserter

    Data Structures & Algorithms · Medium

    Implement the CBTInserter class. The question specifically asked for an O(log n) solution for insertion, though I could only achieve O(n).

    Open the problem
  24. 24

    Queue Reconstruction by Height

    Data Structures & Algorithms · Medium

    You are given an array of people, people, as people[i] = [hi, ki]. hi is the height of the i-th person, and ki is the number of people in front of the i-th person who have a height greater than or equal to hi. Reconstruct the queue.

    Open the problem
  25. 25

    House Robber III

    Data Structures & Algorithms · Medium

    The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, 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.

    Open the problem
  26. 26

    Kth Ancestor of a Tree Node

    Data Structures & Algorithms · Hard

    Given a tree with n nodes labeled from 0 to n - 1, and parent[i] denotes the parent of i-th node. Find the k-th ancestor of a given node.

    Open the problem
  27. 27

    Bricks Falling When Hit

    Data Structures & Algorithms · Hard

    You are given an m x n grid representing a map of bricks. A brick is at grid[i][j] = 1 and an empty cell is at grid[i][j] = 0. You are also given an array hits, where hits[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.

    Open the problem
  28. 28

    Convex Hull Algorithm

    Data Structures & Algorithms · Hard

    A problem related to finding the convex hull of a set of points.

  29. 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. 30

    Search in Rotated Sorted Array

    Data Structures & Algorithms · Medium

    There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k. Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 otherwise.

    Open the problem
  31. 31

    Binary Tree Maximum Path Sum

    Data Structures & Algorithms · Hard

    A 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 root of a binary tree, return the maximum path sum of any non-empty path.

    Open the problem
  32. 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. 33

    Sum of Distances in Tree

    Data Structures & Algorithms · Hard

    There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given an array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi. Return an array answer of length n where answer[i] is the sum of the distances between node i and all other nodes in the tree.

    Open the problem
  34. 34

    Rotting Oranges

    Data Structures & Algorithms · Medium

    You are given an m x n grid 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.

    Open the problem
  35. 35

    Greedy Meeting Schedule Problem

    Data Structures & Algorithms · Medium

    A greedy problem similar to typical meeting scheduling or interval problems.

  36. 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. 37

    Shortest Path in a Grid with Obstacles Elimination

    Data Structures & Algorithms · Hard

    You are given an m x n integer matrix grid where grid[i][j] is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right. You are also given an integer k. Return the minimum number of steps to walk from (0, 0) to (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is impossible to find such a path, return -1.

    Open the problem
  38. 38

    Maximum Sum BST in Binary Tree

    Data Structures & Algorithms · Hard

    Given a root of a binary tree, return the maximum sum of all nodes in any BST (Binary Search Tree) subtree.

    Open the problem
  39. 39

    Find the Kth Smallest Sum of a Matrix With Sorted Rows

    Data Structures & Algorithms · Hard

    Given an m x n matrix mat where each row is sorted in non-decreasing order, and an integer k, return the k-th smallest sum among all possible arrays that you can form by choosing exactly one element from each row.

    Open the problem
  40. 40

    Number of Islands

    Data Structures & Algorithms · Medium

    Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands.

    Open the problem
  41. 41

    Diameter of Binary Tree

    Data Structures & Algorithms · Easy

    Given the root of 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.

    Open the problem
  42. 42

    Range Sum Query 2D - Immutable

    Data Structures & Algorithms · Medium

    Given 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).

    Open the problem
  43. 43

    Count Ways to Build Good Strings

    Data Structures & Algorithms · Medium

    Given integers low, high, zero, and one. Return the number of 'good' strings, which are binary strings whose length is between low and high (inclusive) and contain zero consecutive '0's and one consecutive '1's.

    Open the problem
  44. 44

    Binary Tree Cameras

    Data Structures & Algorithms · Hard

    You are given the root of 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.

    Open the problem
  45. 45

    Escape the Spreading Fire

    Data Structures & Algorithms · Hard

    You are given a 0-indexed m x n grid of integers fire. 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 time t you 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, return 10^9.

    Open the problem
  46. 46

    Daily Temperatures

    Data Structures & Algorithms · Medium

    Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

    Open the problem
  47. 47

    Longest Increasing Subsequence

    Data Structures & Algorithms · Medium

    Given an integer array nums, return the length of the longest strictly increasing subsequence.

    Open the problem
  48. 48

    Minimum Path Cost in a Grid

    Data Structures & Algorithms · Medium

    You are given an m x n integer grid grid. You are also given an m x n integer matrix moveCost where moveCost[r][c] is the cost to move from a cell (r, c) to any cell in the next row column c'.

    Open the problem
  49. 49

    Simple Bank System

    Data Structures & Algorithms · Medium

    Implement a bank system with operations like transfer, deposit, and withdraw. This is a design problem often involving handling multiple accounts and transactions.

    Open the problem
  50. 50

    Decoded String at Index

    Data Structures & Algorithms · Medium

    You are given an encoded string s and an integer k. To decode the string, this is how it works: if the character is a digit d, the encoded string is repeated d - 1 times. Return the k-th character of the decoded string.

    Open the problem
  51. 51

    Check Array Formation Through Concatenation

    Data Structures & Algorithms · Easy

    You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are also distinct. Return true if arr can be formed by concatenating the arrays in pieces in any order.

    Open the problem
  52. 52

    Frog Jump

    Data Structures & Algorithms · Hard

    A 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.

    Open the problem
  53. 53

    Where Will the Ball Fall

    Data Structures & Algorithms · Medium

    You have a 2-D grid of size m x n representing a box with some slanted walls. A ball will drop from the top of the box. The grid grid[i][j] can be 1 (representing a right-slanted wall) or -1 (representing a left-slanted wall). Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom, or -1 if it gets stuck.

    Open the problem
  54. 54

    Hackerrank - Down to Zero II

    Data Structures & Algorithms

    You are given an integer N. In one move, you can either decrease N by 1 or decrease N to one of its divisors. Find the minimum number of moves to reach 0.

    Open the problem
  55. 55

    Transform String by Character Conversion

    Data Structures & Algorithms · Hard

    Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions. In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

  56. 56

    IPO

    Data Structures & Algorithms · Hard

    Suppose LeetCode will start n projects for you. For each project i, you can choose to start it if you have at least capital[i] capital, and you'll earn profit[i] profit. You are given k projects to perform and your initial capital w. Maximize your final capital.

    Open the problem
  57. 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. 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. 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. 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. 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. 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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at PhonePe recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!