Paytm Interview Questions (2026): Real, With Answers

Based on candidate reports, expect somewhere between 60 and 90 minutes, most commonly 70, with two to three coding problems rather than a huge MCQ bank. The MCQ-plus-coding format (roughly six MCQs on CS fundamentals plus a coding section) shows up more often on-campus and for HackerRank-hosted tests; the off-campus CocoWorks version skews toward pure coding.

Treat it like a timed contest, not a leisurely take-home. You won't get partial credit for a beautifully commented function that times out on the hidden test cases, and the platform typically runs all three problems in one window rather than letting you submit and move on section by section.

Some reports for frontend-adjacent roles mention a machine coding component built in React rather than a plain algorithmic problem, on top of the usual DSA and CS-fundamentals MCQs. That's not universal across every posting, but it's common enough that if your target role touches the web app or merchant dashboard, it's worth having a small React component (something with local state and a couple of edge cases) ready to build from scratch in 30 to 40 minutes, not just recite from memory.

Candidate reports don't consistently describe negative marking on the coding problems themselves, and specifics here vary by which platform hosts your particular test (CocoWorks versus HackerRank), so don't assume either way. What is consistent: submitting all three problems with even partial passing test cases beats spending the full window perfecting one and leaving the other two blank, since graders appear to weight problems independently rather than requiring all three solved to advance.

Glassdoor's aggregate data for the Software Engineer track puts the median time from application to hire at around 5 days across 211 submitted interview reports, which is fast by product-company standards and suggests the assessment-to-interview turnaround specifically is short, often under a week. That's a median across the whole pipeline though, not a guarantee, and reports of the process stretching to two to four weeks for more senior or specialized roles aren't rare either.

Roman numerals are a greedy-decomposition problem once you set up the value table correctly, including the subtractive pairs (900 for CM, 400 for CD, 40 for XL, and so on) as their own entries rather than trying to special-case subtraction logic separately. Walk the table from largest to smallest, and at each value, append the symbol and subtract as many times as it fits before moving to the next entry.

def int_to_roman(num):
  values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
  symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
  result = []
  for value, symbol in zip(values, symbols):
    while num >= value:
      result.append(symbol)
      num -= value
  return "".join(result)

The failure mode interviewers watch for is a candidate hardcoding four separate if-branches for the subtractive cases instead of folding them into the same table-driven loop. It works either way, but the table version is the one that survives a follow-up like "now do the reverse, Roman to integer" without a rewrite.

Split on whitespace, discard the empty tokens that repeated spaces produce, reverse the list of words, and rejoin with a single space. The subtlety interviewers actually test for is handling of leading, trailing, and multiple consecutive spaces, since a naive split on a single space character leaves empty strings in the result if you don't filter them.

def reverse_words(s):
  words = s.split() # split() with no argument collapses runs of whitespace
  return " ".join(reversed(words))

If asked to do it in place on a character array (a common follow-up for languages without a built-in split), the standard approach is to reverse the entire string first, then reverse each individual word back to normal, which gets you the word order flipped while each word's internal characters stay correct.

Sort by start time first, this is the step candidates sometimes skip and then wonder why their merge logic breaks. Once sorted, walk through and compare each interval's start against the current merged interval's end. If the new start is less than or equal to the current end, extend the merge; otherwise close out the current merged interval and start a new one.

def merge_intervals(intervals):
  intervals.sort(key=lambda pair: pair[0])
  merged = [intervals[0]]
  for start, end in intervals[1:]:
    last_end = merged[-1][1]
    if start <= last_end:
      merged[-1][1] = max(last_end, end)
    else:
      merged.append([start, end])
  return merged

Encapsulation bundles data with the methods that operate on it and restricts direct access, a payment service exposing processPayment() while keeping the raw card details private inside the class. Abstraction hides implementation complexity behind a simple interface, a PaymentGateway interface with a single charge() method that different providers implement differently underneath. Inheritance lets a subclass reuse and extend a parent's behavior, a RefundableTransaction extending Transaction. Polymorphism lets the same method call behave differently depending on the actual object type at runtime, calling charge() on a list of mixed gateway objects and having each one run its own provider-specific logic.

Interviewers specifically ask for real examples because "encapsulation means hiding data" recited from memory tells them nothing about whether you've actually designed a class hierarchy under pressure.

A process has its own isolated memory space; a thread shares memory with every other thread in the same process. That shared memory is exactly why threads are cheaper to create and communicate faster, and exactly why a bug in one thread, a race condition on a shared account balance variable, say, can corrupt state for the whole process instead of staying contained.

For a payments backend specifically, this is why so much of the concurrency discussion in interviews centers on synchronization: multiple threads handling concurrent debit requests against the same wallet balance is a textbook race condition if you don't lock, queue, or use an atomic compare-and-swap around the balance update.

TCP is connection-oriented and guarantees ordered, reliable delivery through acknowledgments and retransmission, at the cost of more overhead. UDP is connectionless and fire-and-forget, faster but with no delivery guarantee.

A payment confirmation has to use TCP, effectively, whatever HTTPS runs on top of. You cannot afford a dropped packet silently losing confirmation that a transaction succeeded. A live status feed showing a merchant's real-time transaction dashboard could tolerate UDP-style best-effort delivery in theory, since a missed update just gets overwritten by the next one a second later, though in practice most teams still run this over TCP-based protocols like WebSockets for simplicity rather than building a custom UDP layer for a marginal latency win.

Functionally, all three register a class as a Spring-managed bean and are interchangeable at the mechanical level, they're all specializations of @Component. The difference is purely semantic and, for @Repository specifically, one real behavioral difference: @Repository additionally enables Spring's exception translation, converting a database-specific exception (a raw SQLException, for instance) into Spring's unified DataAccessException hierarchy. @Service and plain @Component don't do that translation.

The strongest answers describe a direct, private conversation first, understanding whether the issue is workload, unclear scope, or something personal, before escalating to a manager. Escalating immediately without attempting to resolve it peer-to-peer first tends to read as conflict-avoidant in the opposite direction, going straight to authority rather than handling it like a colleague. The nuance interviewers want is knowing when direct conversation genuinely isn't working and escalation becomes the responsible next step, not a first resort.

A strong answer references something concrete about Paytm's actual position, the scale of its payments and wallet volume, a specific product surface (merchant payments, lending, wealth) that maps to your background, rather than a generic "I'm passionate about fintech" line that could apply to any company in the sector. If you genuinely don't have a specific reason beyond "it's a well-known company hiring for my skill set," it's better to be honest about wanting to work on payments infrastructure at scale than to fake a passion you don't have.

Keep this to two or three minutes, structured around the roles and projects most relevant to the job you're interviewing for, not a chronological recitation of your entire resume. The goal is to give the interviewer a clear thread connecting your past work to why this specific role is a logical next step, not to relitigate every job you've held.

Reports consistently mention OOP, operating systems, DBMS, and computer networks as the four pillars tested by MCQ, the same four subjects that resurface later in the live technical round as open-ended questions. The MCQs tend to be conceptual rather than trick questions: expect things like process versus thread, ACID properties, normalization, and TCP versus UDP rather than obscure syntax gotchas.

The overlap between the MCQ round and the live interview is deliberate from an interviewer's side even if it's never stated. A weak MCQ score with a strong live answer on the same topic reads as inconsistent, so it's worth actually studying these fundamentals rather than assuming the MCQ section is disposable.

Split each candidate even-length window into two halves and compare sums directly. The naive version checks every even length and every starting index, recomputing both half-sums each time, which costs O(n^3) in the worst case. Prefix sums cut that down: build a running sum array once, then any subarray sum is a difference of two prefix values in O(1), bringing the whole scan to O(n^2) over all valid windows.

def count_balanced_even_subarrays(arr):
  n = len(arr)
  prefix = [0] * (n + 1)
  for i in range(n):
    prefix[i + 1] = prefix[i] + arr[i]

  count = 0
  for length in range(2, n + 1, 2):
    half = length // 2
    for start in range(0, n - length + 1):
      mid = start + half
      end = start + length
      left_sum = prefix[mid] - prefix[start]
      right_sum = prefix[end] - prefix[mid]
      if left_sum == right_sum:
        count += 1
  return count

An interviewer usually pushes on whether you can do better than O(n^2). A sliding-window variant that maintains both half-sums incrementally as the window grows gets you to O(n) for a fixed length, but you still pay for the outer loop over lengths, so O(n^2) overall is the realistic answer most candidates land on, and that's fine as long as you can explain why.

This is the classic maximal square DP problem. Define dp[i][j] as the side length of the largest all-1s square whose bottom-right corner sits at (i, j). If the cell itself is 0, dp[i][j] is 0. If it's 1, the square can only be as large as the smallest of the three neighboring squares (top, left, top-left) plus one, because all three have to support a square of at least that size for the current cell to extend them.

def max_square_side(matrix):
  if not matrix or not matrix[0]:
    return 0
  rows, cols = len(matrix), len(matrix[0])
  dp = [[0] * cols for _ in range(rows)]
  best = 0
  for i in range(rows):
    for j in range(cols):
      if matrix[i][j] == 1:
        if i == 0 or j == 0:
          dp[i][j] = 1
        else:
          dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        best = max(best, dp[i][j])
  return best

The insight worth saying out loud, unprompted, is why you take the minimum of the three neighbors rather than the max. A square extending down-right can only be as strong as its weakest supporting edge, so min is the correct operator even though it feels counterintuitive the first time you derive it.

Standard BFS gives you level order but always left to right. Zigzag alternates direction every level. The clean way to do it is to keep the BFS queue exactly as-is and just track a boolean for which direction the current level should read in, reversing the collected level's values before appending them to the result when the flag says right-to-left.

from collections import deque

def zigzag_level_order(root):
  if not root:
    return []
  result, queue, left_to_right = [], deque([root]), True
  while queue:
    level_size = len(queue)
    level = deque()
    for _ in range(level_size):
      node = queue.popleft()
      if left_to_right:
        level.append(node.val)
      else:
        level.appendleft(node.val)
      if node.left:
        queue.append(node.left)
      if node.right:
        queue.append(node.right)
    result.append(list(level))
    left_to_right = not left_to_right
  return result

Using a deque for the level buffer and appending to either end based on direction avoids a separate reverse pass, which is a small but real efficiency win an interviewer notices.

Floyd's cycle detection (slow and fast pointers) answers the first half in O(1) space: advance slow by one node and fast by two, and if they ever meet, a cycle exists. The second half, finding the entry point, uses a mathematical property of the meeting point: reset one pointer to the head, keep the other at the meeting point, and advance both one step at a time. They meet again exactly at the cycle's start.

def detect_cycle_start(head):
  slow = fast = head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      pointer = head
      while pointer != slow:
        pointer = pointer.next
        slow = slow.next
      return pointer
  return None

The hash-set alternative (track visited nodes, return the first repeat) is simpler to derive under pressure and worth mentioning as a fallback, but it costs O(n) space. Interviewers who ask this expect you to know Floyd's exists and roughly why the math works, even if you don't rederive the full proof live.

Standard binary search still applies, you just have to figure out which half of the array is actually sorted before deciding which side to recurse into. At each step, compare the middle element against the two endpoints: whichever half has its endpoints in strictly increasing order is the sorted half, and you can then check in O(1) whether the target falls inside that sorted range.

def search_rotated(nums, target):
  lo, hi = 0, len(nums) - 1
  while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target:
      return mid
    if nums[lo] <= nums[mid]: # left half is sorted
      if nums[lo] <= target < nums[mid]:
        hi = mid - 1
      else:
        lo = mid + 1
    else: # right half is sorted
      if nums[mid] < target <= nums[hi]:
        lo = mid + 1
      else:
        hi = mid - 1
  return -1

Put every number in a hash set, then for each number that is the start of a run (meaning number minus one isn't in the set), walk forward counting how long the consecutive run goes. Skipping numbers that aren't a run's start is what keeps this O(n) overall instead of O(n^2), since every number only ever gets counted as part of exactly one run's forward walk.

def longest_consecutive(nums):
  num_set = set(nums)
  longest = 0
  for num in num_set:
    if num - 1 not in num_set:
      length = 1
      while num + length in num_set:
        length += 1
      longest = max(longest, length)
  return longest

Sliding window with a hash map tracking the last seen index of each character. Expand the right edge one character at a time; if that character was already seen inside the current window, jump the left edge forward to one past its last occurrence rather than resetting the window entirely, since anything before that repeat is still valid.

def longest_unique_substring(s):
  last_seen = {}
  left = longest = 0
  for right, char in enumerate(s):
    if char in last_seen and last_seen[char] >= left:
      left = last_seen[char] + 1
    last_seen[char] = right
    longest = max(longest, right - left + 1)
  return longest

Atomicity means a transaction either fully completes or fully rolls back, no partial state. Consistency means the database moves from one valid state to another, respecting constraints. Isolation means concurrent transactions don't see each other's uncommitted changes. Durability means once committed, a transaction survives a crash.

A debit-and-credit wallet transfer is the cleanest example of why atomicity matters specifically: debiting sender A and crediting receiver B has to happen as one atomic unit. If the debit commits and the credit fails, or the process crashes between the two statements, A loses money that never reaches B, a real, money-losing bug rather than an abstract database concern.

First normal form requires atomic columns, no repeating groups, so a single transaction row can't have a comma-separated list of item IDs stuffed into one column. Second normal form removes partial dependencies on a composite key, so if a transaction_items table is keyed by (transaction_id, item_id), a column like merchant_name that only depends on transaction_id, not the full composite key, needs to move to a separate transactions table. Third normal form removes transitive dependencies, so if merchant_city depends on merchant_id rather than directly on the transaction, merchant_city belongs in a merchants table, not duplicated across every transaction row.

In practice, most production payment schemas deliberately denormalize some of this back for read performance, a transaction row often does carry a snapshot of merchant_name at the time of the transaction, since merchants change their display name and a historical transaction record shouldn't silently change with it. Knowing when to break the normal form on purpose is as important as being able to recite it.

HTTPS is HTTP layered on top of TLS, which encrypts the connection and verifies the server's identity via a certificate. The handshake starts with the client sending supported cipher suites and a random value, the server responds with its certificate and its own random value, the client verifies the certificate against a trusted certificate authority, both sides derive a shared session key using that exchanged randomness, and from that point on all traffic is symmetrically encrypted with the fast session key rather than the slower asymmetric keys used only to establish it.

For a payments company specifically, this isn't abstract security trivia. Every card detail, every OTP, every wallet balance travels over this connection, and an interviewer asking this wants to hear that you understand why the handshake exists, not just that "HTTPS is HTTP with a padlock."

A deadlock is a state where two or more processes or threads are each waiting on a resource the other holds, and none of them can proceed. It requires all four of: mutual exclusion (a resource can only be held by one thread at a time), hold and wait (a thread holding one resource is waiting for another), no preemption (a resource can't be forcibly taken away), and circular wait (a cycle of threads each waiting on the next).

// classic deadlock: two threads lock two accounts in opposite order
synchronized (accountA) {
  synchronized (accountB) {
    transfer(accountA, accountB, amount);
  }
}
// meanwhile, another thread does:
synchronized (accountB) {
  synchronized (accountA) {
    transfer(accountB, accountA, amount);
  }
}

The fix that actually applies to a wallet transfer scenario is enforcing a consistent lock ordering, always lock the account with the lower ID first regardless of which direction the transfer runs, which breaks the circular wait condition and prevents this exact deadlock from ever occurring.

An inner join keeps only rows that match on both sides, a left join keeps every row from the left table regardless of a match, filling unmatched right-side columns with NULL, and a full outer join keeps every row from both sides, matched or not. In a transactions dataset, an inner join between transactions and refunds silently hides every transaction that hasn't been refunded, which is fine if that's genuinely what you want to report, but a common bug is using an inner join when you actually meant a left join and then wondering why your "total transaction count" report undercounts.

An index is a separate data structure, usually a B-tree, that lets the database find rows matching a query condition without scanning the whole table, turning an O(n) table scan into something closer to O(log n). The tradeoff is that every insert, update, or delete now has to also update every index on that table, so a transactions table with five indexes pays that write cost five times over on every new transaction.

For a table that sees heavy write volume, like a live transactions ledger, the honest answer is to index selectively, the columns you actually query on frequently (user_id, transaction_date, status), not every column that might someday be useful, because over-indexing a write-heavy table is a real, measurable performance mistake, not a theoretical one.

@Transactional wraps a method in a database transaction, committing if the method returns normally and rolling back if it throws. The common trap: by default, Spring only rolls back on unchecked exceptions (RuntimeException and its subclasses), not checked exceptions. If your payment method throws a checked IOException from a downstream call and you haven't explicitly configured rollbackFor, the transaction commits anyway despite the exception, leaving a half-completed operation on the books.

@Transactional(rollbackFor = Exception.class)
public void processPayment(PaymentRequest request) throws PaymentGatewayException {
  walletRepository.debit(request.getUserId(), request.getAmount());
  ledgerRepository.recordEntry(request);
  gatewayClient.notify(request); // if this throws a checked exception,
  // rollbackFor ensures the debit above still gets rolled back too
}

The other common trap: calling a @Transactional method from another method within the same class doesn't go through Spring's proxy, so the annotation is silently ignored. It only works when the call comes in from outside the bean, through the proxy Spring wraps around it.

synchronized is the simplest option, a built-in keyword that locks on an object monitor, but it can't be interrupted while waiting and offers no way to check whether the lock is currently held without blocking. ReentrantLock gives you more control, tryLock with a timeout, interruptible locking, fairness policies, at the cost of having to remember to unlock it manually in a finally block, since it isn't scoped automatically like synchronized. AtomicLong skips locking entirely and uses compare-and-swap at the hardware level, which is faster than either for a single simple counter but doesn't generalize to protecting multiple related fields together.

private final AtomicLong requestCount = new AtomicLong(0);

public void recordRequest() {
  requestCount.incrementAndGet(); // no lock needed, CAS handles it
}

For a wallet balance specifically, a single AtomicLong isn't enough on its own, because a real debit also needs to check sufficient balance before decrementing, and that check-then-act sequence needs an actual lock or a compare-and-swap loop that retries on conflict, not just an atomic increment.

The core insight is that a Wallet shouldn't expose a raw setBalance method at all, every balance change should go through a method that also produces a corresponding Transaction record, so balance and transaction history can never drift apart. Transfer between two wallets should be a single service method that debits one, credits the other, and writes both transaction records inside one atomic operation, not two independent calls the caller has to remember to pair up correctly.

class Wallet {
  private String userId;
  private BigDecimal balance;

  void debit(BigDecimal amount) {
    if (balance.compareTo(amount) < 0) throw new InsufficientBalanceException();
    balance = balance.subtract(amount);
  }
  void credit(BigDecimal amount) {
    balance = balance.add(amount);
  }
}

class WalletTransferService {
  @Transactional
  public void transfer(Wallet from, Wallet to, BigDecimal amount) {
    from.debit(amount);
    to.credit(amount);
    transactionRepository.save(new Transaction(from, to, amount));
  }
}

Using BigDecimal rather than double for money is worth stating explicitly even if nobody asks. Floating point rounding on currency amounts is exactly the kind of bug that looks fine in a demo and causes a reconciliation mismatch in production months later.

Strong consistency for the authorization path (can this transaction actually go through), eventual consistency is acceptable, even expected, for the balance number just sitting on a home screen. A user opening the app and seeing a balance that's a few seconds stale isn't dangerous, since no money moves just from viewing a number. The danger only exists at the moment of authorizing a new debit, which is exactly why that specific read has to hit the source of truth directly rather than a cache or a locally-stored value.

The structure that actually reads well here is: state the disagreement plainly, without softening it into false agreement after the fact, explain the specific evidence or reasoning you brought to the conversation, describe what happened when you raised it (did they change course, did you, did you find a middle path), and be honest if the outcome wasn't what you wanted. An answer where you were right, they listened, and everyone lived happily ever after is the least believable version of this story, and interviewers who've heard hundreds of these can usually tell.

What they're actually screening for is whether you raise disagreement constructively and with evidence, rather than either staying silent to avoid conflict or digging in without being willing to update your position when shown you were wrong.

Walk through the actual sequence: how you found out, how you triaged severity versus panicking and trying to fix everything at once, what the immediate mitigation was versus the eventual root-cause fix, and what changed afterward so the same class of bug doesn't recur. That last part, the follow-up prevention, is the piece candidates skip most often, and it's usually the part that actually distinguishes a strong answer, since anyone can describe firefighting, fewer people describe what they changed structurally afterward.

The honest version of this story usually involves you being at least partially wrong about something initially, or the stakeholder raising a real constraint you hadn't considered, before you found common ground. A version where you simply presented data and they instantly agreed is worth being suspicious of in your own preparation, since real disagreements at work rarely resolve that cleanly, and an interviewer will often probe for the messier, more honest middle.

Pick something with genuine stakes, not a sanitized near-miss, and be specific about your own role in why it fell short, not just external factors. The learning has to be concrete and something you've actually applied since, a specific process change, a different way you scope estimates now, not a vague "I learned to communicate better."

This overlaps with the behavioral round's version of the same question but tends to be asked more briefly here, looking for a general disposition rather than a fully detailed story. A short, honest answer describing that you raise disagreement directly and privately, with evidence, and defer to the decision once made even if you disagreed, generally lands better than an elaborate story that starts feeling rehearsed.

The trick is binary searching on the partition point of the smaller array rather than merging anything. You want to split both arrays such that everything on the left of both partitions is less than or equal to everything on the right, and the left side has exactly half (or half plus one, for odd totals) of the combined elements. Binary search over the smaller array's partition index, and compute the matching partition in the other array algebraically from the total length.

def find_median_sorted_arrays(a, b):
  if len(a) > len(b):
    a, b = b, a
  m, n = len(a), len(b)
  lo, hi = 0, m
  while lo <= hi:
    i = (lo + hi) // 2
    j = (m + n + 1) // 2 - i
    a_left = a[i - 1] if i > 0 else float("-inf")
    a_right = a[i] if i < m else float("inf")
    b_left = b[j - 1] if j > 0 else float("-inf")
    b_right = b[j] if j < n else float("inf")
    if a_left <= b_right and b_left <= a_right:
      if (m + n) % 2 == 0:
        return (max(a_left, b_left) + min(a_right, b_right)) / 2
      return max(a_left, b_left)
    elif a_left > b_right:
      hi = i - 1
    else:
      lo = i + 1

This one shows up more at senior levels. Most mid-level candidates aren't expected to derive it cold, and saying so honestly, then walking through the merge-based O(m+n) approach cleanly, is a perfectly respectable fallback that plenty of successful candidates give.

A hash map alone gets you O(1) lookup but no ordering, and a plain doubly linked list gets you ordering but O(n) lookup. Combine them: the hash map stores key to node references, and a doubly linked list maintains recency order, with the node at the tail being most recently used and the node at the head being the eviction candidate. Every get or put moves the touched node to the tail in O(1) using the map to find it directly, no traversal.

class Node:
  def __init__(self, key, value):
    self.key, self.value = key, value
    self.prev = self.next = None

class LRUCache:
  def __init__(self, capacity):
    self.capacity = capacity
    self.map = {}
    self.head = Node(0, 0)
    self.tail = Node(0, 0)
    self.head.next, self.tail.prev = self.tail, self.head

  def _remove(self, node):
    node.prev.next, node.next.prev = node.next, node.prev

  def _add_to_tail(self, node):
    node.prev, node.next = self.tail.prev, self.tail
    self.tail.prev.next = node
    self.tail.prev = node

  def get(self, key):
    if key not in self.map:
      return -1
    node = self.map[key]
    self._remove(node)
    self._add_to_tail(node)
    return node.value

  def put(self, key, value):
    if key in self.map:
      self._remove(self.map[key])
    node = Node(key, value)
    self.map[key] = node
    self._add_to_tail(node)
    if len(self.map) > self.capacity:
      lru = self.head.next
      self._remove(lru)
      del self.map[lru.key]

This one is a favorite for fintech companies specifically, because caching layers in a payments stack are everywhere, rate limiters, idempotency key stores, session caches, and the LRU pattern generalizes to all of them.

Reduce every person to a single net balance first (total owed minus total owing), then the problem becomes: given a list of net balances that sum to zero, pair up positives and negatives to clear them in the fewest transfers. Backtracking over the non-zero balances, at each step matching the current person against every other unsettled person and recursing, finds the minimum, since the search space is small once you've collapsed to net balances instead of raw pairwise debts.

def min_transactions(balances):
  non_zero = [b for b in balances if b != 0]

  def backtrack(index):
    while index < len(non_zero) and non_zero[index] == 0:
      index += 1
    if index == len(non_zero):
      return 0
    best = float("inf")
    for j in range(index + 1, len(non_zero)):
      if non_zero[j] * non_zero[index] < 0:
        non_zero[j] += non_zero[index]
        best = min(best, 1 + backtrack(index + 1))
        non_zero[j] -= non_zero[index]
    return best

  return backtrack(0)

The reason this fits a Paytm interview specifically is obvious once you say it out loud: split-payment and settlement features between wallet users are a real product surface, not an abstract graph exercise.

Optimistic locking with a version column is the standard database-level answer: every wallet row carries a version number, and an update statement checks that version hasn't changed since it was read, failing (and triggering a retry) if a concurrent update won the race. Pessimistic row-level locking (SELECT... FOR UPDATE) is the alternative, simpler to reason about but it holds a lock for the duration of the transaction, which hurts throughput under high concurrency on a hot wallet.

UPDATE wallets
SET balance = balance - 100, version = version + 1
WHERE user_id = 'u123' AND version = 7 AND balance >= 100;
-- if 0 rows affected, someone else updated first, retry with fresh version

At scale, a single wallet that gets extremely high concurrent traffic, a large merchant's collection account, for instance, becomes a genuine hotspot even with optimistic locking, since every request still contends on the same row. That's usually solved by sharding the balance into multiple sub-buckets that sum to the true total, spreading contention across several rows instead of one, and reconciling to a single number only when reading the balance back.

User ID is the natural shard key for a wallet-centric system, since almost every query, checking a balance, listing a user's transaction history, is scoped to a single user anyway, meaning a well-chosen hash-based shard on user_id keeps most queries hitting a single shard rather than fanning out across all of them.

The genuine complication is any query that needs to aggregate across users, a merchant's total daily revenue across every customer who paid them, for instance, since that merchant's transactions are scattered across every shard by user_id. That's usually solved with a separate read-optimized aggregation store, a data warehouse or an OLAP layer fed by change-data-capture off the sharded transactional database, rather than trying to make the transactional shards themselves serve both patterns well.

A sliding window log or a token bucket both work; the token bucket tends to be the cleaner interview answer because it's easier to reason about and code live. Each user gets a bucket with a fixed capacity that refills at a steady rate. A request consumes one token if available; if the bucket is empty, the request is rejected.

class TokenBucket {
  private final int capacity;
  private double tokens;
  private final double refillRatePerSecond;
  private long lastRefillTimestamp;

  public synchronized boolean tryConsume() {
    refill();
    if (tokens >= 1) {
      tokens -= 1;
      return true;
    }
    return false;
  }

  private void refill() {
    long now = System.currentTimeMillis();
    double elapsedSeconds = (now - lastRefillTimestamp) / 1000.0;
    tokens = Math.min(capacity, tokens + elapsedSeconds * refillRatePerSecond);
    lastRefillTimestamp = now;
  }
}

A per-user rate limiter needs one bucket instance per user ID, typically held in a concurrent map, and interviewers usually follow up asking how you'd evict stale buckets for inactive users so the map doesn't grow unbounded over time.

Publish a transaction-completed event onto a message bus the moment the transaction commits, and have separate consumers for each notification channel, push notification, SMS, in-app feed, subscribe independently to that same event. Decoupling this way means a slow or failing SMS provider doesn't block or delay the push notification, and adding a new channel later (email receipts, say) means adding a new consumer, not touching the transaction-processing code path at all.

At high volume, the practical concern shifts to backpressure: if the SMS provider's API starts rate-limiting you, its consumer's queue backs up, but that shouldn't cascade into slowing down the push notification consumer or, worse, the transaction processing service itself. Each consumer needs its own independent queue and its own retry and dead-letter handling.

The join itself is usually a LEFT JOIN from your internal transactions table out to the bank's settlement records, matched on a shared reference ID (typically the UTR or bank reference number), so unmatched internal transactions surface as NULLs on the bank side rather than silently disappearing. That's the whole point of reconciliation: finding the transactions that exist on one side but not the other.

SELECT t.transaction_id, t.amount, t.status, s.settlement_amount, s.settled_at
FROM transactions t
LEFT JOIN bank_settlements s
 ON t.utr_reference = s.utr_reference
 AND t.transaction_date = s.transaction_date
WHERE s.utr_reference IS NULL
 AND t.status = 'completed';

The pipeline around that query usually runs as a scheduled batch job: extract yesterday's internal transactions and the bank's settlement file (often a flat file dropped overnight), load both into staging tables, run the reconciliation join, and route the mismatches to an exceptions queue for manual review rather than silently retrying, since a mismatched payment record is exactly the kind of thing you don't want auto-resolved without a human checking it.

The client sends a unique idempotency key with the request, and the server checks it against a store before processing. If the key has been seen before with a completed result, return that cached result immediately without touching the payment logic at all. If the key is new, process the payment and store the key alongside the result before returning.

class IdempotencyService {
  Optional<PaymentResponse> checkExisting(String idempotencyKey) {
    return idempotencyRepository.findByKey(idempotencyKey)
     .map(IdempotencyRecord::getResponse);
  }

  @Transactional
  PaymentResponse processWithIdempotency(String key, PaymentRequest request) {
    return checkExisting(key).orElseGet(() -> {
      PaymentResponse response = paymentService.charge(request);
      idempotencyRepository.save(new IdempotencyRecord(key, response));
      return response;
    });
  }
}

The trap here is a race condition: two identical requests with the same key arriving within milliseconds of each other, before either has finished writing its idempotency record. The real fix needs a unique constraint on the idempotency key column at the database level, so the second concurrent insert fails fast with a constraint violation rather than both requests slipping through the "not found" check simultaneously and both charging the card.

Break it into an API layer handling requests, a wallet service owning balance logic, a ledger service that's the append-only source of truth for every debit and credit, a transaction processing queue to decouple the API response from downstream settlement work, and a reconciliation job that periodically checks the ledger against the wallet balances to catch drift.

The part candidates skip most often: the ledger has to be append-only and the wallet balance table is technically a derived, cached view of the ledger, not the other way around. If the balance ever disagrees with the sum of ledger entries, the ledger wins, since it's the audit trail a regulator or a support ticket dispute will actually reference. Treating the balance column as the primary source of truth, with the ledger as an afterthought log, is the design mistake interviewers are specifically listening for.

The honest answer starts with what you should never cache: the authoritative wallet balance used to authorize a debit. That read always has to go to the database, because a cache serving a stale higher balance could authorize a payment the user can't actually cover. What's safe to cache is read-heavy, less time-sensitive data: user profile info, transaction history for display, merchant metadata, rate limit counters that tolerate brief staleness.

Where caching genuinely helps on the write-critical path is idempotency key lookups and rate-limit counters, both of which are naturally short-lived and where a cache miss just falls back to the database rather than causing incorrect financial behavior. The distinction between "cache this for speed" and "never cache this, it's a money-safety boundary" is exactly what separates a candidate who's thought about payments specifically from one reciting generic caching advice.

Put the outbound call to the bank behind a message queue rather than calling it synchronously inline with the user-facing request, so a slow bank response doesn't hold open an HTTP connection to the user. The consumer that actually calls the bank needs an idempotency key on every attempt (so a retried call after a timeout doesn't risk a duplicate charge on the bank's side too), an exponential backoff between retries, and a dead-letter queue for requests that exhaust retries, routed to manual reconciliation rather than silently dropped.

The genuinely hard part is a timeout that doesn't tell you whether the bank actually processed the payment or not. In that ambiguous case, the safe default is to query the bank's status-check API before blindly retrying the charge itself, since retrying a charge you're not sure failed is how double-charges happen in production, not in theory.