PhonePe Previous Year Coding Questions

PhonePe is one of India's most competitive fintech companies to crack. The interview process is distinctly structured around three pillars: strong DSA fundamentals, the ability to build clean working systems in real time (machine coding), and at senior levels the capacity to design large-scale distributed systems. Questions are often drawn from real payment infrastructure challenges such as transaction retry logic, rate limiting, and event-driven architectures.

Hiring Process

Step 1: Resume and Profile Shortlisting PhonePe looks for strong academic backgrounds, competitive programming history, and prior experience at product companies. Contributions to high-scale systems are a strong differentiator. Shortlisting is stricter for lateral roles than campus hiring.

Step 2: Online Assessment Conducted on HackerRank or CodeSignal. The assessment runs for 60 to 90 minutes with two to three problems of medium to hard difficulty. Topics include arrays, binary search, trees, graphs, and dynamic programming. Expect at least one problem requiring a non-trivial optimization over a brute force approach.

Step 3: Machine Coding Round A take-home or timed in-person round lasting 90 to 120 minutes. You are asked to build a working application from scratch such as a parking lot, order management system, or rate limiter. Evaluated on object-oriented design, SOLID principles, code readability, test coverage, and whether the code actually runs. This round is unique to PhonePe and is often the hardest gate.

Step 4: Machine Coding Discussion and DSA Round 1 The interviewer walks through your machine coding submission asking design decisions and trade-offs. Then transitions to one or two medium-hard DSA problems to test breadth of problem-solving.

Step 5: DSA Round 2 and System Design One hard DSA problem followed by a system design discussion. For SDE1 the design portion is light. For SDE2 and above expect a full high-level design covering database choices, API contracts, scalability, and fault tolerance, often around payment systems like UPI processing or fraud detection.

Step 6: Hiring Manager Round Behavioral and culture round assessing ownership mindset, handling ambiguity, and the ability to work across teams. PhonePe values engineers who take end-to-end responsibility for their systems.

Tips: The machine coding round is what eliminates most candidates. Practice building complete working systems in under 2 hours using OOP. For DSA focus heavily on binary trees, graph BFS or DFS, binary search, and DP on intervals. Always state brute force first then optimize explicitly with complexity analysis.

Preparation Resources

• LeetCode PhonePe Tagged Problems
• PhonePe Engineering Blog
• Let's Code DSA Roadmap

Part 1 — OA Questions

1. Single Element in a Sorted Array Medium

You are given a sorted array where every element appears exactly twice except for one element that appears exactly once. Return the single element. Your solution must run in O(log n) time and O(1) space.

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Approach: Use binary search on even indices only. At each midpoint (rounded to even), check if the element at mid equals the element at mid plus 1. If yes, the single element is to the right of mid plus 2. If no, it is at mid or to its left. Adjust boundaries accordingly. Complexity: Time O(log n) · Space O(1) Follow-up: What if the array is not sorted but you know only one element appears once while all others appear three times?

2. Minimum Speed to Arrive on Time Medium

You are given n trains running at a fixed integer speed in km per hour. Each train departs at integer hours. Given an array dist where dist[i] is the distance of the ith train and a float hour representing the maximum travel time, return the minimum positive integer speed to arrive on time, or -1 if it is impossible.

Input: dist = [1,3,2], hour = 6
Output: 1

Input: dist = [1,3,2], hour = 2.7
Output: 3

Approach: Binary search on the answer (speed). For a given speed compute the total time by summing ceiling divisions for all trains except the last and adding the exact float division for the last train. Check if total time is within the hour limit. Narrow the binary search range between 1 and 10 million. Complexity: Time O(n log(max_speed)) · Space O(1) Follow-up: What if trains can depart at non-integer hours, removing the ceiling constraint?

3. Maximum Profit in Job Scheduling Hard

You have n jobs where each job has a start time, end time, and profit. You can only work on one job at a time and jobs cannot overlap. Return the maximum profit achievable by scheduling a subset of jobs.

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120 (jobs 0 and 3)

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,200,19]
Output: 320

Approach: Sort jobs by end time. Use DP where dp[i] is the maximum profit considering the first i jobs. For each job use binary search to find the latest non-overlapping job and take the maximum between skipping the current job and taking it plus dp[non_overlapping_index]. Complexity: Time O(n log n) · Space O(n) Follow-up: What if you can work on at most k jobs simultaneously?

4. Subarray Sum Equals K Medium

Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k.

Input: nums = [1,1,1], k = 2
Output: 2

Input: nums = [1,2,3], k = 3
Output: 2

Approach: Use a running prefix sum and a hash map storing the count of each prefix sum seen so far. For each position check if prefix_sum minus k exists in the map. If it does, all subarrays ending here with that starting prefix contribute to the count. Initialize the map with 0 mapped to 1 for subarrays starting at index 0. Complexity: Time O(n) · Space O(n) Follow-up: What if you need the total number of subarrays with XOR equal to k instead of sum?

5. Longest Subarray of 1s After Deleting One Element Medium

Given a binary array nums, you must delete exactly one element. Return the length of the longest non-empty subarray of 1s after the deletion.

Input: nums = [1,1,0,1]
Output: 3

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5

Approach: Use a sliding window allowing at most one zero inside. When the window contains more than one zero, shrink from the left. The answer is window size minus one (since one element must be deleted, even if all are 1s). Complexity: Time O(n) · Space O(1) Follow-up: Generalize to find the longest subarray of 1s after deleting at most k elements.

6. Find the Duplicate Number Medium

Given an array of n plus 1 integers where each value is between 1 and n inclusive, find the one duplicate number. You must not modify the array and use only O(1) extra space.

Input: nums = [1,3,4,2,2]
Output: 2

Input: nums = [3,1,3,4,2]
Output: 3

Approach: Treat the array as a linked list where index i points to nums[i]. The duplicate creates a cycle. Use Floyd's tortoise and hare algorithm to detect the cycle entry point, which is the duplicate number. Complexity: Time O(n) · Space O(1) Follow-up: What if there could be multiple duplicate numbers and you need to find all of them?

Part 2 — Machine Coding Round

7. Design Snake and Ladder Game Medium

Design and implement a complete Snake and Ladder game. The system should support multiple players, a configurable board size, arbitrary snake and ladder positions, dice rolling, and detect the winner. The code must compile and run with a working demo.

Board: 6x6, players: [Alice, Bob]
Snakes: {26:10, 20:4}, Ladders: {6:25, 11:40}
Turn: Alice rolls 4 from cell 1 -> cell 5, then rolls 1 -> cell 6 -> ladder to 25
Turn: Bob rolls 6 from cell 1 -> cell 7...
Winner: first player to reach cell 36

Approach: Model entities as classes: Board holds the grid and snake or ladder mappings, Player holds position and name, Dice generates random values, Game orchestrates turns. Use BFS for the underlying cell-jump problem. Keep the game loop clean with a play() method that cycles players until someone wins. Complexity: Time O(n^2) for board setup · Space O(n^2) Follow-up: How would you add a web API to allow remote players to join and take turns asynchronously?

8. Design a Parking Lot System Medium

Design a parking lot system supporting multiple floors and vehicle types (bike, car, truck). Implement park(vehicle), unpark(ticket), and getAvailableSlots(vehicleType). Slots are assigned to the nearest available spot.

ParkingLot(floors=2, slotsPerFloor=[10,10])
ticket = park(Car("KA-01")) -> Ticket(floor=0, slot=0)
park(Bike("KA-02")) -> Ticket(floor=0, slot=1) (bikes fill compact spots first)
unpark(ticket) -> fee based on duration
getAvailableSlots(CAR) -> 9

Approach: Use abstract classes for Vehicle and Slot with concrete types. Each floor manages its slots in priority queues sorted by slot number for nearest-first assignment. ParkingLot delegates to floors in order. Ticket stores entry time and slot reference for fee calculation on exit. Complexity: Time O(log n) per park or unpark · Space O(n) Follow-up: Add support for reserved monthly passes and EV charging slots with an additional fee.

9. Design a Rate Limiter Hard

Design a rate limiter that allows at most N requests per user per minute. Implement isAllowed(userId, timestamp) returning true if the request should proceed. The limiter must support thousands of concurrent users with low memory footprint. This is a direct analogy to PhonePe's UPI transaction throttling.

limiter = RateLimiter(maxRequests=3, windowSeconds=60)
isAllowed("user1", 1) -> true (1st request)
isAllowed("user1", 30) -> true (2nd request)
isAllowed("user1", 50) -> true (3rd request)
isAllowed("user1", 55) -> false (4th request within window)
isAllowed("user1", 65) -> true (1st request expired, window slides)

Approach: Use a sliding window log per user: store request timestamps in a deque. On each request remove all timestamps older than the window, check if the remaining count is below the limit, and append the current timestamp. For memory efficiency consider a fixed-window counter or token bucket as trade-off alternatives. Complexity: Time O(N) per request where N is max requests per window · Space O(users * N) Follow-up: How would you distribute this rate limiter across multiple servers so limits are enforced globally?

10. Design Bounded Blocking Queue Medium

Implement a thread-safe bounded blocking queue with enqueue(element) that blocks when the queue is full and dequeue() that blocks when the queue is empty. Multiple producer and consumer threads should work correctly without race conditions.

queue = BoundedBlockingQueue(capacity=3)
Thread 1 (producer): enqueue(1), enqueue(2), enqueue(3)
Thread 2 (consumer): dequeue() -> 1
Thread 3 (producer): enqueue(4) -- was blocked, now proceeds

Approach: Use a deque protected by a mutex with two condition variables: notFull and notEmpty. Enqueue waits on notFull when at capacity, then inserts and signals notEmpty. Dequeue waits on notEmpty when empty, then removes and signals notFull. This classic producer-consumer pattern is exactly how PhonePe models async payment event queues. Complexity: Time O(1) amortized · Space O(capacity) Follow-up: How would you extend this to support priority-based dequeuing?

11. Design Order Management System Hard

Design an order management system for an e-commerce platform. Implement placeOrder(userId, items), cancelOrder(orderId), getOrderStatus(orderId), and listOrders(userId). Orders transition through states: PLACED, CONFIRMED, SHIPPED, DELIVERED, CANCELLED.

placeOrder("user1", [Item("phone",1), Item("case",2)]) -> Order(id="ORD001", status=PLACED)
getOrderStatus("ORD001") -> PLACED
cancelOrder("ORD001") -> success (only if not yet SHIPPED)
placeOrder("user1", [Item("tablet",1)]) -> Order(id="ORD002")
listOrders("user1") -> [ORD001 CANCELLED, ORD002 PLACED]

Approach: Use a state machine pattern for order transitions. Order class holds state, items, timestamps, and userId. OrderService orchestrates operations and validates state transitions (e.g., cannot cancel a delivered order). Use in-memory maps for userId-to-orders and orderId-to-order lookup. Apply the observer pattern to trigger notifications on state changes. Complexity: Time O(1) per operation · Space O(n) Follow-up: How would you add inventory management so placing an order reserves stock atomically?

12. Design In-Memory Key-Value Store with TTL Medium

Design an in-memory key-value store supporting set(key, value, ttlSeconds), get(key) returning null if expired, and delete(key). Keys should expire automatically after their TTL. Relevant to PhonePe's OTP storage and session caching use cases.

store.set("otp:user1", "482910", 120)
store.get("otp:user1") -> "482910" (within 120 seconds)
store.get("otp:user1") -> null (after 120 seconds)
store.set("session:user2", "token123", 3600)
store.delete("session:user2")
store.get("session:user2") -> null

Approach: Store entries in a hash map with their expiry timestamp. On get, check if the current time exceeds the expiry and return null if so. For lazy expiration clean up stale entries on access. For proactive cleanup maintain a min-heap of expiry times and a background thread that wakes up at the next expiry to remove expired keys. Complexity: Time O(log n) for set with heap · O(1) for get · Space O(n) Follow-up: How would you persist this store across restarts with minimal performance impact?

13. Design Elevator System Medium

Design an elevator system for a building with n floors and k elevators. Implement requestElevator(fromFloor, direction) and selectFloor(elevatorId, floor). The system should assign the nearest available elevator optimally.

Building: 10 floors, 2 elevators
Elevator 1 at floor 3 going UP, Elevator 2 at floor 7 going DOWN
requestElevator(5, UP) -> assigns Elevator 1 (same direction, closer)
requestElevator(2, DOWN) -> assigns Elevator 2 (will come down)
selectFloor(1, 8) -> Elevator 1 adds floor 8 to its queue

Approach: Each elevator maintains two sorted sets of destination floors: one for the current direction and one for the reverse direction (SCAN algorithm). The dispatcher assigns incoming requests using a scoring function based on distance and direction alignment. Model states as IDLE, MOVING_UP, and MOVING_DOWN. Complexity: Time O(log n) per request · Space O(n * k) Follow-up: How would you handle emergency requests that override all existing schedules?

Part 3 — Onsite DSA Questions

14. House Robber III Medium

A thief wants to rob houses arranged in a binary tree. Adjacent nodes (parent and child) cannot both be robbed. Given the root of a binary tree, return the maximum amount that can be robbed.

Input: root = [3,2,3,null,3,null,1]
Output: 7 (rob nodes 3, 3, 1)

Input: root = [3,4,5,1,3,null,1]
Output: 9 (rob nodes 4, 5)

Approach: Use postorder DFS returning a pair (robThis, skipThis) at each node. robThis equals the node value plus skipLeft plus skipRight. skipThis equals the maximum of each child's rob or skip value. The answer is the maximum of both values at the root. Complexity: Time O(n) · Space O(h) Follow-up: What if the constraint was that no two nodes within distance k of each other can both be robbed?

15. Kth Ancestor of a Tree Node Medium

Given a tree of n nodes rooted at 0, implement TreeAncestor(n, parent) and getKthAncestor(node, k) returning the kth ancestor of the given node, or -1 if it does not exist.

TreeAncestor(7, [-1,0,0,1,1,2,2])
getKthAncestor(3, 1) -> 1
getKthAncestor(5, 2) -> 0
getKthAncestor(6, 3) -> -1

Approach: Precompute binary lifting table where up[node][j] stores the 2^j-th ancestor of node. Build using up[node][j] = up[up[node][j-1]][j-1]. For a query decompose k in binary and jump through precomputed ancestors. This reduces each query from O(n) to O(log n). Complexity: Time O(n log n) build · O(log n) per query · Space O(n log n) Follow-up: Use binary lifting to find the LCA (Lowest Common Ancestor) of any two nodes efficiently.

16. All Nodes Distance K in Binary Tree Medium

Given the root of a binary tree, a target node, and an integer k, return a list of all node values that are exactly k edges away from the target node.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]

Approach: First build a parent pointer map for every node using DFS. Then run BFS from the target node treating the tree as an undirected graph (using child links and parent pointers). Track visited nodes to avoid backtracking. Return all nodes at BFS level k. Complexity: Time O(n) · Space O(n) Follow-up: What if the tree changes dynamically with insertions and you need to answer distance queries efficiently?

17. Binary Tree Right Side View Medium

Given the root of a binary tree, imagine standing on the right side. Return the values of the nodes you can see ordered from top to bottom.

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Input: root = [1,null,3]
Output: [1,3]

Approach: Run BFS level by level. At each level record the last node's value (the rightmost node visible from the right side). Alternatively use DFS visiting right subtree before left and recording the first node seen at each depth. Complexity: Time O(n) · Space O(n) Follow-up: Return both left and right side views simultaneously in a single traversal.

18. Count Good Nodes in Binary Tree Medium

Given a binary tree, a node X is good if the path from root to X contains no node with a value greater than X. Return the number of good nodes.

Input: root = [3,1,4,3,null,1,5]
Output: 4 (nodes 3, 4, 3, 5)

Input: root = [3,3,null,4,2]
Output: 3

Approach: DFS with a running maximum along the current root-to-node path. At each node if the node value is greater than or equal to the running max it is a good node and increment the count. Pass the updated maximum down to both children. Complexity: Time O(n) · Space O(h) Follow-up: Find all paths from root to leaf where every node on the path is a good node.

19. Flatten Binary Tree to Linked List Medium

Given the root of a binary tree, flatten it into a linked list in-place in preorder traversal order. The right child pointer of each node should point to the next node in the list and the left pointer should be null.

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Approach: Use Morris traversal. For each node that has a left child, find the rightmost node in the left subtree and point it to the current node's right child. Then move the left subtree to the right and set left to null. Repeat for each node until the whole tree is flattened. Complexity: Time O(n) · Space O(1) Follow-up: Flatten the tree in postorder rather than preorder using the same in-place constraint.

20. Path Sum II Medium

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values equals targetSum.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Approach: Use backtracking DFS. Maintain a current path list and a running sum. At each leaf node check if the running sum equals targetSum and if so add a copy of the path to results. On returning from recursion remove the last element from the path and subtract its value from the running sum. Complexity: Time O(n) · Space O(n) Follow-up: Instead of root-to-leaf paths, find all paths (not necessarily starting at root) with a given sum.

21. Candy Hard

There are n children standing in a line with ratings. Give each child at least one candy. Children with a higher rating than their adjacent neighbors must get more candies. Return the minimum total candies needed.

Input: ratings = [1,0,2]
Output: 5 (candies: [2,1,2])

Input: ratings = [1,2,2]
Output: 4 (candies: [1,2,1])

Approach: Two passes. Left to right: give each child one more candy than the left neighbor if their rating is higher. Right to left: ensure each child has one more candy than the right neighbor if rating is higher, taking the maximum of both passes. Sum all candy counts. Complexity: Time O(n) · Space O(n) Follow-up: Can you solve this in O(1) space using a mathematical observation about ascending and descending runs?

22. Product of Array Except Self Medium

Given an integer array nums, return an array answer where answer[i] equals the product of all elements except nums[i]. You must solve it in O(n) time without using division.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Approach: Build a prefix product array and a suffix product array. For each index multiply prefix[i-1] by suffix[i+1]. Optimize to O(1) space (excluding output) by filling the output with prefix products first then making a single right-to-left pass with a running suffix product. Complexity: Time O(n) · Space O(1) excluding output Follow-up: What if you can use division? Handle the case where zeros appear in the array carefully.

23. Jump Game III Medium

Given an array of non-negative integers arr and start index, you can jump from index i to i plus arr[i] or i minus arr[i]. Return true if you can reach any index with value 0.

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true (5 -> 4 -> 1 -> 3, value 0)

Input: arr = [3,0,2,1,2], start = 2
Output: false

Approach: BFS or DFS from the start index. At each index add both reachable indices (i plus arr[i] and i minus arr[i]) if they are within bounds and not yet visited. Return true when reaching an index with value 0. Marking visited prevents infinite loops. Complexity: Time O(n) · Space O(n) Follow-up: Return the minimum number of jumps needed to reach any zero-valued index.

24. Longest Consecutive Sequence Medium

Given an unsorted array of integers, return the length of the longest consecutive elements sequence. Your algorithm must run in O(n) time.

Input: nums = [100,4,200,1,3,2]
Output: 4 (sequence 1,2,3,4)

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Approach: Insert all numbers into a hash set. For each number check if it is the start of a sequence (number minus 1 is not in the set). If yes, count consecutive increments until the sequence breaks. The maximum count across all sequence starts is the answer. Complexity: Time O(n) · Space O(n) Follow-up: What if you need to return the actual consecutive sequence rather than just its length?

25. Search in Rotated Sorted Array Medium

Given an integer array sorted in ascending order then rotated at an unknown pivot, and a target value, return the index of target or -1 if not present. Must run in O(log n) time.

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Approach: Modified binary search. At each midpoint determine which half is sorted by comparing mid with the left boundary. If left half is sorted and target falls in its range search left, otherwise search right. Repeat for right half. This maintains O(log n) without finding the pivot first. Complexity: Time O(log n) · Space O(1) Follow-up: What if duplicates are allowed in the array?

26. Find Peak Element Medium

A peak element is one that is strictly greater than its neighbors. Given an integer array nums, find a peak element and return its index. The array may contain multiple peaks. Must run in O(log n) time.

Input: nums = [1,2,3,1]
Output: 2 (element 3 is a peak)

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5

Approach: Binary search. At each midpoint compare nums[mid] with nums[mid+1]. If nums[mid+1] is greater, a peak must exist on the right (the array is rising). Otherwise a peak exists at mid or to its left. This guarantees finding a peak because boundaries are treated as negative infinity. Complexity: Time O(log n) · Space O(1) Follow-up: Find a peak in a 2D matrix where a cell is a peak if it is greater than all four adjacent cells.

27. Number of Provinces Medium

There are n cities. Some are directly connected. Given an n by n adjacency matrix isConnected, return the total number of provinces (groups of directly or indirectly connected cities).

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Approach: Use Union-Find. For each pair (i, j) where isConnected[i][j] equals 1, union nodes i and j. Count the number of distinct root nodes after processing all connections. Alternatively use DFS to count connected components. Complexity: Time O(n^2) · Space O(n) Follow-up: If cities are added dynamically, how would you maintain province counts with O(alpha(n)) per update?

28. Pacific Atlantic Water Flow Medium

Given an m by n matrix of heights, water flows to adjacent cells with equal or lower height. The Pacific ocean borders the top and left edges. The Atlantic borders the bottom and right. Return all cells from which water can reach both oceans.

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Approach: Run reverse BFS from all Pacific border cells and all Atlantic border cells separately, moving to adjacent cells with equal or greater height (reverse flow). Cells reachable in both BFS runs can flow to both oceans. Complexity: Time O(m * n) · Space O(m * n) Follow-up: What if some cells are blocked and cannot pass water?

29. Accounts Merge Medium

Given a list of accounts where each account is a name followed by emails, merge accounts that share at least one email. Return merged accounts with emails sorted.

Input: [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"]]

Approach: Use Union-Find on emails. For each account union all emails together. Map each email to its account owner. Group emails by root representative. Sort each group and prepend the owner name. This problem reflects PhonePe's need to deduplicate user accounts linked to the same phone or email. Complexity: Time O(N * alpha(N) + N log N) · Space O(N) Follow-up: What if accounts also have phone numbers as identifiers alongside emails?

30. Shortest Path in Binary Matrix Medium

Given an n by n binary matrix, find the length of the shortest clear path from the top-left corner to the bottom-right corner. A clear path moves through 0-valued cells in any of 8 directions. Return -1 if no such path exists.

Input: grid = [[0,1],[1,0]]
Output: 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Approach: BFS from (0,0) tracking path length. Explore all 8 neighbors of each cell. Mark cells as visited by setting them to 1. Return the distance when reaching the bottom-right corner. Return -1 if BFS exhausts all reachable cells without finding the target. Complexity: Time O(n^2) · Space O(n^2) Follow-up: What if the matrix has weighted cells where each cell has a traversal cost?

31. All Paths From Source to Target Medium

Given a directed acyclic graph of n nodes, return all possible paths from node 0 to node n minus 1. You may return the paths in any order.

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Approach: DFS with backtracking. Maintain a current path list. At each node add it to the path and explore all neighbors. When node n-1 is reached add a copy of the path to results. Backtrack by removing the last node after exploring. Since the graph is acyclic no visited set is needed. Complexity: Time O(2^n * n) in worst case · Space O(n) Follow-up: Find only the shortest path among all paths from source to target.

32. House Robber II Medium

Houses are arranged in a circle so the first and last houses are adjacent. You cannot rob two adjacent houses. Given an array representing the amount of money in each house, return the maximum you can rob.

Input: nums = [2,3,2]
Output: 3

Input: nums = [1,2,3,1]
Output: 4

Approach: Since first and last houses are adjacent you cannot rob both. Split into two subproblems: rob houses 0 to n-2 and rob houses 1 to n-1. Apply the standard linear House Robber DP to each. Return the maximum of both results. Complexity: Time O(n) · Space O(1) Follow-up: Extend to a grid where houses are arranged in a 2D circle.

33. Best Time to Buy and Sell Stock with Cooldown Medium

You are given stock prices where prices[i] is the price on day i. You may buy and sell multiple times but after selling you must wait one day before buying again (cooldown). Return the maximum profit.

Input: prices = [1,2,3,0,2]
Output: 3 (buy day 0, sell day 1, cooldown day 2, buy day 3, sell day 4)

Input: prices = [1]
Output: 0

Approach: Define three states: held (holding a stock), sold (just sold, in cooldown), and rest (no stock, no cooldown). Transitions: held[i] = max(held[i-1], rest[i-1] minus price[i]). sold[i] = held[i-1] plus price[i]. rest[i] = max(rest[i-1], sold[i-1]). Answer is max(sold[n-1], rest[n-1]). Complexity: Time O(n) · Space O(1) Follow-up: What if the cooldown period is k days instead of 1?

34. Maximal Square Medium

Given an m by n binary matrix of '0' and '1', find the largest square containing only 1s and return its area.

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Approach: Build a DP table where dp[i][j] is the side length of the largest square with its bottom-right corner at (i, j). If matrix[i][j] is '1', then dp[i][j] equals 1 plus the minimum of dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. Track the maximum side length and return its square. Complexity: Time O(m * n) · Space O(m * n), reducible to O(n) Follow-up: Find the largest rectangle containing only 1s (not necessarily square).

35. Unique Paths II Medium

A robot starts at the top-left of an m by n grid and tries to reach the bottom-right. It can only move right or down. Some cells contain obstacles. Return the number of unique paths avoiding obstacles.

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Approach: DP where dp[i][j] is the number of ways to reach cell (i, j). Cells with obstacles have 0 paths. For non-obstacle cells dp[i][j] equals dp[i-1][j] plus dp[i][j-1]. Handle boundary conditions carefully. Reduce to O(n) space by using a single row DP array. Complexity: Time O(m * n) · Space O(n) Follow-up: What if the robot can also move up and left but cannot revisit any cell?

36. Target Sum Medium

Given an integer array nums and an integer target, assign a plus or minus sign to each number. Return the number of different ways to assign signs so that the sum equals target.

Input: nums = [1,1,1,1,1], target = 3
Output: 5

Input: nums = [1], target = 1
Output: 1

Approach: Use a hash map DP where keys are running sums and values are the count of ways to reach that sum. For each number update the map by adding and subtracting the number from every existing sum. Final answer is dp[target]. Complexity: Time O(n * sum) · Space O(sum) Follow-up: Reduce to a subset sum problem by observing that the sum of positive numbers minus the sum of negative numbers equals target.

37. Minimum Path Sum Medium

Given an m by n grid filled with non-negative numbers, find a path from the top-left to the bottom-right which minimizes the sum of all numbers along its path. You can only move right or down.

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7 (path 1 -> 3 -> 1 -> 1 -> 1)

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Approach: Modify the grid in-place for O(1) space. For each cell add the minimum of the value from above and from the left. Handle the first row and first column separately as they have only one direction. The bottom-right cell contains the minimum path sum. Complexity: Time O(m * n) · Space O(1) Follow-up: What if you can move in all four directions but cannot revisit cells?

38. Find the Town Judge Easy

In a town of n people, the town judge trusts nobody and everyone else trusts the judge. Given an array of trust pairs, find the town judge or return -1.

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Approach: Compute a trust score for each person as in-degree minus out-degree. The town judge has trust score of n minus 1 (everyone trusts them and they trust nobody). Return the person with score n minus 1, or -1 if none exists. Complexity: Time O(n + E) · Space O(n) Follow-up: What if the judge can trust exactly one person (themselves)?

39. Copy List with Random Pointer Medium

A linked list where each node has a next pointer and a random pointer (which can point to any node or null). Construct a deep copy of the list in O(n) time and O(1) extra space (excluding output).

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: deep copy with same structure

Approach: Three-pass O(1) space approach. Pass 1: insert a copy of each node immediately after the original. Pass 2: set each copy's random pointer to original.random.next. Pass 3: separate the interleaved list into original and copy. The hash map approach is simpler but uses O(n) space. Complexity: Time O(n) · Space O(1) Follow-up: Extend to a doubly linked list with an extra previous pointer.

40. Merge k Sorted Lists Hard

Given an array of k linked lists each sorted in ascending order, merge all into one sorted linked list and return its head.

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Approach: Use a min-heap of size k storing (value, list_index, node) tuples. Initialize with the head of each list. Repeatedly extract the minimum, append to result, and push the next node from the same list. This directly models merging k transaction streams at PhonePe sorted by timestamp. Complexity: Time O(n log k) · Space O(k) Follow-up: Implement using divide-and-conquer by pairwise merging lists instead of a heap.

41. Reverse Nodes in k-Group Hard

Given the head of a linked list, reverse the nodes k at a time and return the modified list. If the remaining nodes are fewer than k, leave them as is.

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Approach: Count k nodes ahead to check if a full group exists. If not, return the head as is. Otherwise reverse k nodes iteratively and recursively call for the remaining list. Connect the tail of the reversed group to the result of the recursive call. Complexity: Time O(n) · Space O(n/k) recursion stack Follow-up: Solve iteratively to eliminate the recursion stack overhead.

42. LRU Cache Medium

Design a data structure for a Least Recently Used cache. Implement get(key) in O(1) and put(key, value) in O(1). When capacity is reached evict the least recently used key. PhonePe uses LRU caching extensively for UPI VPA lookups and merchant data.

cache = LRUCache(2)
put(1,1), put(2,2), get(1) -> 1
put(3,3) (evicts key 2), get(2) -> -1
put(4,4) (evicts key 1), get(1) -> -1, get(3) -> 3, get(4) -> 4

Approach: Combine a hash map for O(1) key lookup with a doubly linked list for O(1) order maintenance. Most recently used nodes go to the head. On get, move the node to head. On put, add to head and if over capacity remove the tail node and its map entry. Complexity: Time O(1) per operation · Space O(capacity) Follow-up: Design an LFU cache where eviction is based on least usage frequency.

43. Implement Trie Medium

Implement a trie with insert(word), search(word), and startsWith(prefix) operations. Relevant to PhonePe's UPI VPA autocomplete and merchant name search.

insert("apple"), search("apple") -> true
search("app") -> false
startsWith("app") -> true
insert("app"), search("app") -> true

Approach: Each trie node contains an array of 26 child pointers and an isEnd flag. Insert walks down creating nodes for new characters and sets isEnd at the final node. Search and startsWith walk the same path, with search also requiring isEnd to be true. Complexity: Time O(L) per operation · Space O(L * n) Follow-up: Design a trie that also stores word frequency and returns the top k most searched prefixes.

44. Find All Disappeared Numbers Easy

Given an array of n integers where each value is between 1 and n, return all integers in the range 1 to n that do not appear in the array. Use O(1) extra space.

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Input: nums = [1,1]
Output: [2]

Approach: Use the input array as a visited marker. For each value v mark the element at index v-1 as negative. After all markings any index that still holds a positive value corresponds to a missing number (index plus 1). Restore the array after if needed. Complexity: Time O(n) · Space O(1) Follow-up: What if the values can be outside the range 1 to n and you need to find all duplicates instead?

45. Minimum Number of Vertices to Reach All Nodes Medium

Given a directed acyclic graph with n nodes and a list of edges, return the smallest set of vertices from which all nodes are reachable.

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[3,5]]
Output: [0,3]

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]

Approach: A node can be excluded from the starting set only if it has at least one incoming edge (it can be reached from another node). Therefore return all nodes with in-degree 0. No DFS or BFS needed. Complexity: Time O(V + E) · Space O(V) Follow-up: What if cycles are allowed? Describe how strongly connected components change the answer.

46. Count Sorted Vowel Strings Medium

Given an integer n, return the number of strings of length n consisting only of vowels (a, e, i, o, u) that are lexicographically sorted.

Input: n = 1
Output: 5 (a, e, i, o, u)

Input: n = 2
Output: 15

Input: n = 33
Output: 66045

Approach: DP where dp[i][j] represents the count of valid strings of length i ending with the j-th vowel. dp[i][j] equals the sum of dp[i-1][k] for all k from j to 4. Reduce to O(1) space using the mathematical formula: C(n + 4, 4) which is stars and bars combinatorics. Complexity: Time O(1) with formula · O(n) with DP · Space O(1) Follow-up: Count strings of length n using exactly k distinct vowels.

47. Design Hit Counter Medium

Design a hit counter that counts hits in the past 5 minutes (300 seconds). Implement hit(timestamp) and getHits(timestamp). Relevant to PhonePe's transaction-per-second monitoring.

hit(1), hit(2), hit(3), getHits(4) -> 3
hit(300), getHits(300) -> 4
getHits(301) -> 3

Approach: Use two circular arrays of size 300: one for timestamps and one for counts. On hit write to the bucket at timestamp mod 300. On getHits sum all buckets whose stored timestamp falls within the last 300 seconds. Complexity: Time O(1) hit · O(300) getHits · Space O(1) Follow-up: Handle concurrent hits from multiple threads.

48. Maximum Width of Binary Tree Medium

Given the root of a binary tree, return the maximum width of any level. Width is defined as the length between the leftmost and rightmost non-null nodes at that level including null nodes in between.

Input: root = [1,3,2,5,3,null,9]
Output: 4 (level 3: nodes 5,3,null,9)

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7

Approach: BFS level by level assigning column indices. Left child of a node at index i gets index 2i and right child gets index 2i plus 1. Normalize indices at each level by subtracting the leftmost index to prevent integer overflow. Width at each level is rightmost minus leftmost plus 1. Complexity: Time O(n) · Space O(n) Follow-up: What if null nodes at the edges of a level are excluded from the width calculation?

49. Task Scheduler Medium

Given a list of task types and a cooldown n meaning the same task type cannot repeat within n intervals, return the minimum total intervals to complete all tasks. Directly models PhonePe's payment retry throttling.

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8 (A B _ A B _ A B)

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

Approach: Count the most frequent task frequency f. The minimum schedule has f minus 1 full cycles of size n plus 1, followed by a partial last cycle. Answer is max(total tasks, (f-1) (n+1) + count of tasks with frequency f). *Complexity: Time O(n) · Space O(1) Follow-up: Return one valid schedule that achieves the minimum total intervals.

50. Reorganize String Medium

Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or an empty string if it is not possible.

Input: s = "aab"
Output: "aba"

Input: s = "aaab"
Output: ""

Approach: Count character frequencies. If any frequency exceeds (n plus 1) divided by 2 return empty. Use a max-heap. Each step pop the two highest-frequency characters, append them, decrement counts, and push back if still positive. This ensures no two same characters are adjacent. Complexity: Time O(n log k) · Space O(k) Follow-up: What if you need the lexicographically smallest valid rearrangement?

Preparation Tips

Join the Let's Code Telegram group for PhonePe interview discussions, machine coding round reviews, and referral opportunities from PhonePe engineers.

Useful Resources

• Let's Code DSA Roadmap
• System Design Interview Guide
• LeetCode PhonePe Tag
• PhonePe Engineering Blog