Paytm Previous Year Coding Questions
Paytm (One97 Communications) is India's largest payments and financial services company with 350M+ users. Engineering interviews are known for their focus on data structures applied to fintech contexts — wallet balances, transaction histories, cashback rules, and fraud patterns. The DSA rounds frequently feature problems solvable with stacks, heaps, or monotonic data structures (Largest Rectangle in Histogram, Skyline Problem). The LLD round typically asks candidates to design a Wallet system or a Cashback Engine. The HLD round is domain-specific — UPI payment flows, Paytm Soundbox, and the bank transaction system are recurring topics. Backend roles often require Java knowledge and Spring Boot discussion.
Hiring Process
Step 1: Resume Screening Paytm screens for backend engineering experience, Java/Go knowledge, and familiarity with payments or high-scale systems. Tier-1 college candidates and engineers from fintech or product companies are preferred.
Step 2: Online Assessment (HackerEarth / HackerRank) Duration: 60–90 minutes. 2–3 coding problems (Easy to Hard) and optionally 1 SQL problem. OA problems are often array/DP-heavy. Candidates are expected to pass all test cases.
Step 3: DSA Live Coding Round 1 60 minutes. 2 LeetCode Medium problems. Clean code and edge case handling expected. Interviewers often probe time and space complexity.
Step 4: DSA Live Coding Round 2 60 minutes. A harder problem — stacks, heaps, advanced DP, or monotonic data structures. This is the elimination round.
Step 5: Machine Coding / LLD Round 90 minutes. Build a working system from a product spec. Common: Paytm Wallet, Cashback Engine, Mini Statement. Graded on SOLID principles, clean code, and extensibility.
Step 6: System Design / HLD Round (SDE-2+) 60–90 minutes. Paytm-specific systems: UPI payment flow, Soundbox alert system, merchant settlement, fraud detection. Interviewers probe distributed transactions, idempotency, and consistency guarantees.
Step 7: Hiring Manager Round Behavioural + system depth. Past project walkthrough and architecture discussion. Engineering culture at Paytm values ownership and product thinking.
Tips: Stacks and monotonic queues are the most-tested advanced DSA at Paytm — practice Largest Rectangle in Histogram, Sliding Window Maximum, and The Skyline Problem. For LLD, build a Wallet system with debit/credit, cashback accrual, and redemption logic. For HLD, understand the UPI 2-factor flow (collect vs. pay) and how Paytm acts as a TPAP (Third Party Application Provider) on top of NPCI.
Preparation Resources
Part 1 — OA Questions
1. Spiral Matrix Medium
Given an m×n matrix, return all elements in spiral order.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Approach: Maintain four boundaries: top, bottom, left, right. Traverse right along top row, then down along right column, then left along bottom row, then up along left column. Shrink the boundary after each pass.
Complexity: Time O(m*n) · Space O(1)
Follow-up: Spiral Matrix II — fill a matrix with 1..n² in spiral order (LeetCode #59).
2. Count Inversions in Array Medium
Count the number of inversions in an array — pairs (i, j) where i < j but arr[i] > arr[j]. Paytm frames this as counting "out-of-order transactions."
Input: arr = [8, 4, 2, 1]
Output: 6
Explanation: (8,4),(8,2),(8,1),(4,2),(4,1),(2,1)
Input: arr = [3, 1, 2]
Output: 2
Approach: Modified merge sort. During the merge step, whenever a right-half element is placed before a left-half element, it contributes (mid - leftPointer + 1) inversions to the count. Total inversion count accumulates across all merge steps.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Count of Smaller Numbers After Self (LeetCode #315) — per-element inversion count.
3. Maximum Sum Circular Subarray Medium
Given a circular integer array, find the maximum sum of a non-empty subarray.
Input: nums = [1,-2,3,-2]
Output: 3
Input: nums = [5,-3,5]
Output: 10
Explanation: Wrap around: 5+5=10.
Approach: Two cases: (1) max subarray is entirely within the array → standard Kadane's. (2) max subarray wraps around → totalSum - minSubarraySum (using Kadane's for minimum). Answer = max of both cases. Edge case: if all elements are negative, return the max element.
Complexity: Time O(n) · Space O(1)
Follow-up: Why does the "all negative" edge case break the wrap-around formula?
4. Top K Frequent Elements Medium
Given an integer array and k, return the k most frequent elements.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Approach: Count frequencies. Min-heap of size k — if the heap has more than k elements, pop the minimum frequency element. Alternatively, bucket sort: index by frequency (0..n), place elements in their frequency bucket, scan backwards for k elements.
Complexity: Time O(n log k) heap · O(n) bucket sort · Space O(n)
Follow-up: Top K Frequent Words with lexicographic tiebreaking (LeetCode #692).
5. Minimum Path Sum Medium
Given an m×n grid of non-negative integers, find a path from top-left to bottom-right that minimises the sum of all numbers along the path.
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: 1→3→1→1→1.
Approach: DP in-place. dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]. Fill first row and column as prefix sums. Answer is dp[m-1][n-1].
Complexity: Time O(m*n) · Space O(1)
Follow-up: Minimum Falling Path Sum — can move to any adjacent column in the next row (LeetCode #931).
6. Group Anagrams Medium
Given an array of strings, group the anagrams together.
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Approach: Hash map keyed by the sorted version of each word (or a character frequency tuple). Append each word to its key's list.
Complexity: Time O(n * k log k) where k = max word length · Space O(n*k)
Follow-up: O(n*k) key using a 26-element frequency count string instead of sorting.
Part 2 — Phone Screen Questions
7. Largest Rectangle in Histogram Hard
Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed.
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: Rectangle with height 5 spanning bars 3–4.
Input: heights = [2,4]
Output: 4
Approach: Monotonic increasing stack of indices. When a bar is shorter than the stack top, pop and compute the area using the popped height and the width from the current index to the new stack top. Append a 0-height sentinel at the end to flush the stack.
Complexity: Time O(n) · Space O(n)
Follow-up: Maximal Rectangle in a binary matrix (LeetCode #85) — apply this per row.
8. Flatten Binary Tree to Linked List Medium
Flatten a binary tree in-place into a linked list in preorder traversal order (using the right pointer).
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Approach: Morris traversal (O(1) space). For each node with a left child, find the rightmost node of the left subtree. Connect that rightmost node's right pointer to the current node's right child. Move the left subtree to the right. Repeat.
Complexity: Time O(n) · Space O(1)
Follow-up: Recursive approach uses O(h) stack space — explain when O(1) iterative is required.
9. Longest Increasing Subsequence Medium
Return the length of the longest strictly increasing subsequence.
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: [2,3,7,101]
Input: nums = [0,1,0,3,2,3]
Output: 4
Approach: Patience sorting with binary search. Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number, binary search for its position in tails and replace or extend. Length of tails is the answer.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Reconstruct the actual LIS (store parent pointers). Russian Doll Envelopes (LeetCode #354) is LIS in 2D.
10. Sort Colors (Dutch National Flag) Medium
Sort an array containing only 0s, 1s, and 2s in-place in one pass without using sort().
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Approach: Dutch National Flag — three pointers: low (boundary of 0s), mid (current), high (boundary of 2s). If mid is 0, swap with low and advance both. If mid is 2, swap with high and decrement high. If mid is 1, just advance mid.
Complexity: Time O(n) · Space O(1)
Follow-up: Sort an array with k distinct values using the same principle.
11. Partition Labels Medium
Partition a string into as many parts as possible so each letter appears in at most one part. Return the size of each part.
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Approach: Record the last occurrence index of each character. Iterate with a window. Extend the window end to max(end, lastOccurrence[char]). When the current index equals the window end, a partition is complete.
Complexity: Time O(n) · Space O(1) (26 letters)
Follow-up: How does this differ from Merge Intervals structurally?
12. Maximum Frequency Stack Hard
Design a stack that always pops the most frequent element, with ties broken by recency.
FreqStack fs
push(5),push(7),push(5),push(7),push(4),push(5)
pop()→5, pop()→7, pop()→5, pop()→4
Approach: Two maps: freq (element → frequency) and group (frequency → stack of elements). Track maxFreq. push: increment freq, push x to group[freq], update maxFreq. pop: pop from group[maxFreq], decrement freq of that element, if group[maxFreq] is empty decrement maxFreq.
Complexity: Time O(1) · Space O(n)
Follow-up: What if you need both pop-max-freq and pop-min-freq?
13. All Nodes Distance K in Binary Tree Medium
Given a binary tree, a target node, and an integer k, return all nodes exactly k distance from the target.
Input: root=[3,5,1,6,2,0,8], target=5, k=2
Output: [7,4,1]
Approach: Convert tree to undirected graph (add parent pointers via DFS). Then BFS from target for k steps, collecting all nodes at distance k.
Complexity: Time O(n) · Space O(n)
Follow-up: What if you need nodes within distance k (not exactly k)?
Part 3 — Onsite Questions
14. Largest Rectangle in Histogram — Maximal Rectangle Hard
Given a binary matrix of '0' and '1', find the largest rectangle containing only '1's.
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Approach: Build a heights array row by row (heights[j] = consecutive '1's ending at current row in column j). Apply Largest Rectangle in Histogram (LeetCode #84) to each row's heights. Track global maximum.
Complexity: Time O(m*n) · Space O(n)
Follow-up: Count the number of rectangles containing only '1's — harder variant requiring O(m²n) DP.
15. The Skyline Problem Hard
Given a list of buildings as [left, right, height], compute the key points of the skyline silhouette.
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Approach: Sweep line with a max-heap. Create events: (left, -height) for starts and (right, height) for ends. Sort events by x, breaking ties so starts come before ends. Maintain a max-heap of active heights. At each event, update the heap; when the max height changes, record a key point.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Why do we negate heights for start events in the sort comparator?
16. Count of Smaller Numbers After Self Hard
Return an array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than nums[i].
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Approach: Modified merge sort with index tracking. During merge, when a right element is placed before a left element, all remaining left elements get +1 inversions. Alternatively: coordinate compress and use a Binary Indexed Tree (BIT/Fenwick tree) — iterate right to left, query prefix sum for count of smaller, then update.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Count of Range Sum (LeetCode #327) uses the same merge sort approach.
17. Recover Binary Search Tree Hard
Two nodes of a BST are swapped by mistake. Recover the tree without changing its structure.
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
(3 and 1 were swapped)
Approach: Morris inorder traversal (O(1) space). Track prev node. Find the two nodes where prev > current (first violation: first = prev, second = current; update second on every violation). Swap their values at the end.
Complexity: Time O(n) · Space O(1)
Follow-up: Why does inorder traversal of a BST always give a sorted sequence — use this invariant.
18. Find the Celebrity Medium
Among n people, a celebrity is known by everyone but knows nobody. Given a knows(a, b) API, find the celebrity in O(n) calls.
Input: knows matrix implicitly via API
Output: celebrity index or -1
Approach: Start with candidate 0. For each person i from 1 to n-1: if candidate knows i, the candidate cannot be the celebrity → update candidate to i. After one pass, verify the final candidate: they must not know anyone and must be known by everyone.
Complexity: Time O(n) API calls · Space O(1)
Follow-up: What if there can be multiple celebrities?
19. Basic Calculator II Medium
Implement a basic calculator to evaluate a string expression with +, -, *, / (integer division, no parentheses).
Input: s = "3+2*2"
Output: 7
Input: s = " 3/2 "
Output: 1
Input: s = " 3+5 / 2 "
Output: 5
Approach: Stack. Track current number and last operator. On '+'/'-': push (±number) to stack. On ''/'/': pop top, compute, push result. At the end, sum the stack.
*Complexity: Time O(n) · Space O(n)
Follow-up: Basic Calculator I with parentheses (LeetCode #224) and Basic Calculator III with both (LeetCode #772).
20. Remove Invalid Parentheses Hard
Remove the minimum number of invalid parentheses to make the input string valid. Return all unique results.
Input: s = "()())()"
Output: ["(())()", "()()()"]
Input: s = "(a)())()"
Output: ["(a)()()", "(a())()"]
Approach: BFS level by level. At each level, try removing one parenthesis from each position. If any resulting string is valid, add to results and don't go deeper. Use a visited set to avoid duplicates.
Complexity: Time O(n * 2^n) worst case · Space O(n * 2^n)
Follow-up: Backtracking approach — precompute the count of misplaced '(' and ')' to prune early.
21. Sudoku Solver Hard
Solve a Sudoku puzzle by filling empty cells ('.') with digits 1–9 such that each row, column, and 3×3 box contains each digit exactly once.
Input: partially filled 9×9 board
Output: completed valid board
Approach: Backtracking. For each empty cell, try digits 1–9. Check validity against row, column, and 3×3 box sets. If valid, place and recurse. On failure, backtrack. Pre-maintain boolean arrays for O(1) validity checks.
Complexity: Time O(9^m) where m = empty cells · Space O(m)
Follow-up: Use constraint propagation (Arc Consistency) to reduce the search space before backtracking.
22. N-Queens Hard
Place n queens on an n×n chessboard such that no two queens attack each other. Return all distinct solutions.
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Approach: Backtracking row by row. At each row, try placing a queen in each column. Check conflicts using three sets: cols, diagonals (row-col), anti-diagonals (row+col). If safe, place and recurse. Remove on backtrack.
Complexity: Time O(n!) · Space O(n)
Follow-up: N-Queens II — only count solutions (LeetCode #52).
23. Burst Balloons Hard
Given balloons with numbers, burst them to maximise coins. Bursting balloon i gives coins nums[i-1]*nums[i]*nums[i+1].
Input: nums = [3,1,5,8]
Output: 167
Explanation: 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 167
Approach: Interval DP. Think of k as the LAST balloon burst in range [i, j]. dp[i][j] = max coins from bursting all balloons between i and j (exclusive). dp[i][j] = max over k of (nums[i]nums[k]nums[j] + dp[i][k] + dp[k][j]). Pad with 1 sentinels on both ends.
**Complexity: Time O(n³) · Space O(n²)
Follow-up: Strange Printer (LeetCode #664) uses the same interval DP thinking.
24. Strange Printer Hard
A printer prints consecutive sequences of the same character per turn. Find the minimum number of turns to print a given string.
Input: s = "aaabbb"
Output: 2
Input: s = "aba"
Output: 2
Approach: Interval DP. dp[i][j] = min turns to print s[i..j]. Base: dp[i][i]=1. If s[i]==s[j], dp[i][j]=dp[i][j-1] (extend the last character's turn). Otherwise dp[i][j] = min over k in [i,j-1] of dp[i][k]+dp[k+1][j].
Complexity: Time O(n³) · Space O(n²)
Follow-up: Minimum Cost to Cut a Stick (LeetCode #1547) — same interval DP pattern.
25. Predict the Winner Medium
Two players pick from either end of an array, optimally maximising their own score. Determine if player 1 can win.
Input: nums = [1,5,2]
Output: false
Input: nums = [1,5,233,7]
Output: true
Approach: dp[i][j] = max score advantage the current player can achieve over the other in range [i,j]. dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]). Player 1 wins if dp[0][n-1] >= 0.
Complexity: Time O(n²) · Space O(n)
Follow-up: Stone Game (LeetCode #877) — same pattern, always player 1 wins if n is even (mathematical insight).
26. Swim in Rising Water Hard
Grid values represent elevation. At time t, you can swim from cell to cell if both cells have elevation ≤ t. Find the minimum t to swim from (0,0) to (n-1,n-1).
Input: grid = [[0,2],[1,3]]
Output: 3
Approach: Modified Dijkstra. Min-heap of (max_elevation_seen, row, col). At each step, pop minimum elevation cell. Relax neighbours by taking max(current max, neighbour elevation). Reach destination when (n-1,n-1) is popped.
Complexity: Time O(n² log n) · Space O(n²)
Follow-up: Binary search on t + BFS/DFS validity check gives the same complexity with simpler code.
27. Minimum Number of Refueling Stops Hard
A car starts at position 0 with startFuel. Stations array gives [position, fuel]. Find the minimum stops to reach target, or -1 if impossible.
Input: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]
Output: 2
Approach: Greedy with max-heap. Drive as far as possible. When you run out of fuel, retroactively refuel at the station with the most fuel you've passed (greedy choice). Pop from max-heap and increment stop count. If heap is empty and target unreached, return -1.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Why is the greedy choice correct here — prove that taking the largest available fuel is always optimal.
28. Frog Jump Hard
A frog on stones can jump k-1, k, or k+1 units where k was its last jump. Determine if it can reach the last stone.
Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: 1,2,2,3,4,4,5 jumps.
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Approach: DP with hash map. Map from stone position → set of jump sizes that can reach it. For each stone, for each jump size k in its set, try k-1, k, k+1 to the next stone. Build iteratively.
Complexity: Time O(n²) · Space O(n²)
Follow-up: Can you solve this with memoised recursion and explain the subproblem structure?
29. Maximum Sum of 3 Non-Overlapping Subarrays Hard
Find the 3 non-overlapping subarrays of length k with maximum total sum. Return their starting indices.
Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: [1,2]+[2,6]+[7,5]=23
Approach: Sliding window sums. Precompute windowSum[i] = sum of nums[i..i+k-1]. Precompute leftBest[i] = index of max window sum in [0..i]. Precompute rightBest[i] = index of max window sum in [i..n-k]. Iterate middle window m from k to n-2k, using leftBest[m-1] and rightBest[m+k] for best left and right.
Complexity: Time O(n) · Space O(n)
Follow-up: Generalise to any number of non-overlapping windows of size k.
30. First Missing Positive Hard
Find the smallest missing positive integer in O(n) time and O(1) space.
Input: nums = [1,2,0]
Output: 3
Input: nums = [3,4,-1,1]
Output: 2
Input: nums = [7,8,9,11,12]
Output: 1
Approach: Use the array itself as a hash map. Phase 1: for each nums[i] in [1,n], place it at index nums[i]-1 (cyclic swap). Phase 2: scan for first i where nums[i] != i+1. Answer is i+1 (or n+1 if all are correct).
Complexity: Time O(n) · Space O(1)
Follow-up: Why is the answer always in [1, n+1]?
31. Candy Hard
Distribute minimum candies to children with ratings such that every child gets at least 1 and higher-rated neighbours get more.
Input: ratings = [1,0,2]
Output: 5
Explanation: [2,1,2]
Input: ratings = [1,2,2]
Output: 4
Explanation: [1,2,1]
Approach: Two passes. Left to right: if ratings[i] > ratings[i-1], candies[i] = candies[i-1]+1. Right to left: if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1]+1). Sum all.
Complexity: Time O(n) · Space O(n)
Follow-up: One-pass O(1) space solution using slope counting.
32. Minimum Window Subsequence Hard
Given strings s and t, find the minimum window in s such that t is a subsequence of that window.
Input: s = "abcdebdde", t = "bde"
Output: "bcde"
Input: s = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", t = "iqas"
Output: "iqas" region of s
Approach: Two-pointer forward scan to find a valid window ending (t fully matched), then backward scan from the end to minimise the window start. Slide the start pointer and repeat.
Complexity: Time O(s*t) · Space O(1)
Follow-up: Minimum Window Substring (LeetCode #76) — differs because order doesn't matter there (multiset match vs. subsequence match).
33. Design Twitter (LLD) Medium
Design a simplified Twitter with postTweet, getNewsFeed (10 most recent from self + followees), follow, and unfollow.
twitter.postTweet(1, 5)
twitter.getNewsFeed(1) → [5]
twitter.follow(1, 2)
twitter.postTweet(2, 6)
twitter.getNewsFeed(1) → [6, 5]
twitter.unfollow(1, 2)
twitter.getNewsFeed(1) → [5]
Approach: User map → set of followees + list of (timestamp, tweetId). getNewsFeed: collect all followed users' tweets, merge with a max-heap on timestamp, return top 10.
Complexity: Time O(n log n) for feed · Space O(tweets + follows)
Follow-up: How does this scale to millions of users? (Fan-out on write vs. fan-out on read.)
34. Design Paytm Wallet (LLD) Medium
Design Paytm's digital wallet. Users can add money, make payments, receive money, and view their mini statement (last N transactions). Concurrent debit operations must not allow the balance to go negative.
Wallet.addMoney(userId, amount, txnId)
Wallet.pay(fromUserId, toUserId, amount, txnId) → success/failure
Wallet.getBalance(userId) → amount
Wallet.getMiniStatement(userId, n) → [Transaction]
Approach: Classes: User (id, walletBalance, transactionHistory), Transaction (id, type: CREDIT/DEBIT, amount, counterparty, timestamp), WalletService. pay() acquires a per-user lock (not global) to prevent concurrent negative-balance issues. Idempotency: store txnId in a processed-set; return cached result on duplicate. getMiniStatement returns last n entries from the user's transaction list (circular buffer or trim on insert). Key Design Principles: Per-user locking for concurrency, immutable transaction records, idempotency on txnId Follow-up: How do you handle distributed wallet operations when users are sharded across multiple DB nodes?
35. Design Cashback Engine (LLD) Medium
Design Paytm's cashback engine that applies cashback rules to transactions. Rules can be flat (₹50 on first UPI payment), percentage-based (2% on bill payments), or capped (5% up to ₹100). Rules have expiry dates and per-user usage limits.
CashbackEngine.registerRule(ruleId, type, value, maxCap, eligibility, expiresAt)
CashbackEngine.computeCashback(userId, txn) → cashbackAmount
CashbackEngine.creditCashback(userId, cashbackAmount, txnId)
Approach: Classes: CashbackRule (id, type, value, cap, eligibilityChecker, expiresAt, usageLimiter), CashbackEngine. computeCashback iterates applicable rules, applies them via Strategy pattern (FlatCashback, PercentCashback), applies cap, checks eligibility (Chain of Responsibility), checks usage limit, returns maximum applicable cashback. creditCashback is an async write to the wallet after the originating transaction settles. Key Design Principles: Strategy for cashback types, Chain of Responsibility for eligibility, Observer to trigger cashback after transaction settles Follow-up: How do you prevent double-crediting cashback if the settlement event is delivered twice?
36. Design UPI Payment System (HLD) Hard
Design Paytm's UPI payment flow. Paytm acts as a TPAP (Third Party Application Provider) on top of NPCI's UPI rails. Support both pay (push) and collect (pull) flows.
Functional: initiateUPIPay(vpa, amount, remarks), initiateCollect(fromVPA, amount), approveCollect(requestId, upiPin)
Non-functional: p99 <2s, 10M TPS on peak days, exactly-once settlement
Approach: Pay flow: Paytm App → Paytm TPAP Server → NPCI UPI Switch → Beneficiary Bank. The TPAP server validates the VPA, generates a UPI transaction ID, sends to NPCI, waits for acknowledgement. NPCI routes to the payer bank for debit, then to beneficiary bank for credit. Paytm gets the final status via callback. Idempotency: unique UPI Txn ID prevents duplicate debits. Collect flow: sender creates a collect request on NPCI; recipient's TPAP notifies them; approval triggers the same pay flow. Status polling: Paytm polls NPCI if callback doesn't arrive within 30s (timeout reconciliation). Key Concepts: NPCI UPI switch as the central router, VPA resolution, TPAP role, debit+credit atomicity via NPCI, timeout reconciliation Follow-up: How does UPI handle the case where debit succeeds but the credit acknowledgement is lost?
37. Design Paytm Soundbox (HLD) Hard
Design the Paytm Soundbox system — a device at merchant outlets that announces payment amounts audibly when a customer pays. The device uses a SIM card with 2G connectivity.
Functional: receivePaymentAlert(merchantId, amount, senderName), announceAudio(text), getDeviceStatus()
Non-functional: <3s announcement latency after payment, works on 2G, 10M devices, at-least-once delivery
Approach: Payment confirmed → Paytm backend publishes event to Kafka → Soundbox Notification Service consumes the event → sends a lightweight push notification (FCM or MQTT over 2G) to the device identified by merchantId. Device maps to a unique device token stored in a Device Registry (MySQL + Redis cache). Audio text generated server-side (short string). Device plays TTS or pre-recorded audio clips. Retry: if device doesn't ACK within 5s, resend (exponential backoff, max 3 retries). Device heartbeat every 30s so the server knows it is online. Key Concepts: MQTT for low-bandwidth push, device registry, at-least-once with ACK, pre-generated audio to save bandwidth, heartbeat for device liveness Follow-up: How do you handle 10M simultaneous payment events during a festival sale spike?
38. Design Search Autocomplete System Hard
Design a search autocomplete system that suggests top-3 previously typed sentences matching the current prefix, ranked by frequency then lexicographic order.
AutocompleteSystem(["i love you","island","ironman","i love leetcode"], [5,3,2,2])
input('i') → ["i love you","island","i love leetcode"]
input(' ') → ["i love you","i love leetcode"]
input('a') → []
input('#') → saves "i a" with frequency 1
Approach: Trie where each node stores top-3 results (sorted). On input: traverse trie for the current prefix, return node's top-3. On '#': insert the complete sentence into the trie, updating frequencies and top-3 at each node along the path.
Complexity: Time O(p + q log q) per character · Space O(n * L)
Follow-up: For a real-time system with millions of queries, use Elasticsearch with prefix queries and Redis for top-k caching.
39. Minimum Cost to Hire K Workers Hard
Each worker has a quality and wage. Hire exactly k workers such that each worker is paid at least wage[i]/quality[i] × totalQuality. Minimise total wage.
Input: quality=[10,20,5], wage=[70,50,30], k=2
Output: 105.0
Approach: For each worker as the "captain" (who sets the wage/quality ratio), all other hired workers must be paid at least their own minimum ratio × their quality. Sort by wage/quality ratio. Slide a max-heap of size k over workers sorted by ratio — maintain a running sum of qualities. Total cost = ratio × qualitySum. Track the minimum.
Complexity: Time O(n log n) · Space O(k)
Follow-up: Why must all workers in the group be paid at the captain's ratio?
40. Reach a Number Medium
On an infinite number line, start at 0. On step i, move exactly i steps left or right. Find the minimum steps to reach target.
Input: target = 3
Output: 2
Explanation: step 1 right (→1), step 2 right (→3).
Input: target = 2
Output: 3
Approach: Work with abs(target). Sum 1+2+...+k until sum >= target. If (sum - target) is even, we can flip one step to subtract that amount — return k. If odd, try k+1 or k+2 (adding 1 changes parity, adding 2 preserves parity vs. target's parity).
Complexity: Time O(sqrt(target)) · Space O(1)
Follow-up: Prove why flipping a step of size d changes the sum by 2d (subtracting 2d from sum).
41. Expression Add Operators Hard
Given a string of digits and a target, insert +, -, or * between digits to form expressions that evaluate to target. Return all valid expressions.
Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Approach: Backtracking with current expression value and last multiplied operand. At each position try +, -, with every prefix as the next operand. For , undo the last operand's addition and apply multiplication: val = val - last + last curr.
*Complexity: Time O(4^n) · Space O(n)
Follow-up: Why must you track the "last" operand separately for multiplication?
42. Cherry Pickup II Hard
Two robots start at the top-left and top-right of a grid. Both move down one row per step, choosing one of three columns each step. Maximise total cherries collected (shared cell counts once).
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Approach: 3D DP: dp[row][col1][col2] = max cherries when robot 1 is at (row,col1) and robot 2 at (row,col2). At each step try all 9 combinations of movements. If col1 == col2, count cherry once.
Complexity: Time O(rows * cols²) · Space O(cols²)
Follow-up: Generalise to k robots — how does the state space grow?
43. Number of Subarrays with Bounded Maximum Medium
Count subarrays where the maximum element is between left and right (inclusive).
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: [2], [2,1], [3]
Approach: Count(atMost(right)) - Count(atMost(left-1)) where atMost(bound) counts subarrays with max ≤ bound. atMost: sliding window where elements > bound reset the window. Each valid position contributes (i - windowStart + 1) subarrays.
Complexity: Time O(n) · Space O(1)
Follow-up: Number of Subarrays with Bounded Sum — same counting trick with prefix sums.
44. Stickers to Spell Word Hard
Given stickers (each with some letters, unlimited supply) and a target word, find the minimum stickers to spell the target. Return -1 if impossible.
Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Approach: Bitmask DP over subsets of target characters covered. dp[mask] = min stickers to cover the characters represented by mask. For each state, try applying each sticker and compute the resulting new mask by greedily matching sticker letters to uncovered target letters.
Complexity: Time O(2^n * |stickers| * n) · Space O(2^n)
Follow-up: Why is bitmask DP appropriate here (n ≤ 15)?
45. Stone Game Medium
Two players pick stones from either end of a row. The player with more stones wins. Can Alex (player 1) always win?
Input: piles = [5,3,4,5]
Output: true
Approach: Alex always wins because the array has an even number of piles and both players play optimally. Alex can always choose either "all even-indexed piles" or "all odd-indexed piles" (whichever has a higher sum) from the start.
Complexity: Time O(1) · Space O(1)
Follow-up: Stone Game II (LeetCode #1140) and Stone Game III (LeetCode #1406) are harder variants requiring actual DP.
46. Recover BST from Preorder Medium
Given a preorder traversal string with dashes indicating depth (e.g., "1-2--3--4-5--6--7"), reconstruct the binary tree.
Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
Approach: Parse (depth, value) pairs. Use a stack where the stack index represents depth. For each node at depth d, pop the stack until size == d, then attach as the left child (if parent has no left) or right child. Push the new node.
Complexity: Time O(n) · Space O(n)
Follow-up: What if the tree is not a BST — does the reconstruction algorithm change?
47. Minimum Cost to Connect Sticks Medium
Connect sticks with minimum cost. The cost of connecting two sticks is their sum; the resulting stick is put back.
Input: sticks = [2,4,3]
Output: 14
Explanation: 2+3=5 (cost 5), 5+4=9 (cost 9) → total 14.
Input: sticks = [1,8,3,5]
Output: 30
Approach: Min-heap (Huffman coding). Always combine the two smallest sticks. Add their sum back to the heap. Accumulate the cost.
Complexity: Time O(n log n) · Space O(n)
Follow-up: This is Huffman coding — prove that greedy always gives the minimum total cost.
48. Design Bank Transaction System (HLD) Hard
Design Paytm Payments Bank's transaction processing system that handles deposits, withdrawals, transfers, and maintains consistent account balances at scale.
Functional: deposit(accountId, amount, txnId), withdraw(accountId, amount, txnId), transfer(fromId, toId, amount, txnId), getBalance(accountId), getMiniStatement(accountId, n)
Non-functional: ACID transactions, 100K TPS, 99.999% uptime
Approach: Account balances stored in MySQL (ACID-compliant). Transfers use DB transactions with SELECT FOR UPDATE to lock both rows and prevent race conditions. Idempotency: txnId stored in a transactions table; duplicate requests return cached result. Scale reads: Redis cache for balance (invalidated on write). Scale writes: shard accounts by accountId % numShards; cross-shard transfers use a two-phase commit or compensating transactions (Saga). Event sourcing: store every transaction as an immutable event; balance derived by replaying events (audit-friendly). Kafka for async downstream: trigger notifications, fraud scoring, reconciliation jobs. Key Concepts: SELECT FOR UPDATE for serialisable balance updates, Saga for cross-shard transfers, event sourcing, idempotency Follow-up: How do you handle a transfer where the debit succeeds but the credit node is down?
49. Arithmetic Slices II — Subsequence Hard
Count the number of arithmetic subsequences of length >= 3.
Input: nums = [2,4,6,8,10]
Output: 7
Approach: dp[i] is a map of {difference → count of arithmetic subsequences ending at i with that difference}. For each i and j < i, difference d = nums[i] - nums[j]. dp[i][d] += dp[j][d] + 1 (extending existing sequences). Add dp[j][d] to the total answer (these are sequences of length ≥ 3 extended to i).
Complexity: Time O(n²) · Space O(n²)
Follow-up: Arithmetic Slices I for contiguous subarrays (LeetCode #413) is O(n) with a simple DP.
50. Design Merchant Settlement System (HLD) Hard
Design Paytm's merchant settlement system that aggregates daily transactions for each merchant and disburses the settlement amount to their bank account at T+1 or T+2.
Functional: processTransaction(merchantId, amount, txnId), triggerSettlement(date), getSettlementReport(merchantId, date)
Non-functional: accurate to the paisa, handles 50M daily transactions, idempotent settlements
Approach: Every payment event published to Kafka. Settlement Aggregation Service consumes events and upserts into a daily aggregation table (merchantId, date, totalAmount, txnCount) using atomic SQL increments. At EOD, a Settlement Job reads the aggregation table, applies MDR (merchant discount rate), computes net payable, and creates payout records. Payout Service sends NEFT/IMPS instructions to the bank via an API. Idempotency: each settlement run is keyed by (merchantId, date); reruns check if a settlement already exists. Reconciliation: next day, the bank confirms payouts; a reconciliation job matches confirmed payouts against records. Key Concepts: Kafka for event ingestion, idempotent aggregation with UPSERT, MDR calculation, bank API integration, reconciliation job Follow-up: How do you handle a merchant refund that arrives after the settlement has already been disbursed?
Preparation Tips
Paytm's interviews heavily feature monotonic stacks and heaps (Largest Rectangle in Histogram, Skyline Problem, Maximum Frequency Stack) — these are the most differentiating DSA topics. Interval DP (Burst Balloons, Strange Printer) appears regularly in the second DSA round and trips up candidates who haven't seen it. For LLD, build a working Paytm Wallet with per-user locking and idempotent transactions. For HLD, understand the UPI flow from the TPAP perspective (how Paytm sits on top of NPCI) and the Soundbox notification architecture — both are Paytm-specific and signal genuine product knowledge to the interviewer.
Join Telegram group to get the latest Paytm OA questions and connect with candidates currently in the Paytm interview process.