Paytm interview questions & answers

20 real Paytm interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (25 Paytm questions in total).

CodingEasyPaytmSoftware Engineer

1. Find Indices With Index and Value Difference I (LeetCode)

Model answer

The task

Find two indices whose distance is at least indexDifference and whose values differ by at least valueDifference. Return the indices if such a pair exists, or [-1, -1] otherwise.

Key idea

Sweep the array from left to right. For each current index, keep track of the smallest and largest values among earlier indices that are far enough away; either extreme gives the greatest possible value difference from the current value.

Approach

  1. Visit each index j as the later index of a potential pair.
  2. Add index j - indexDifference to the eligible earlier indices, if it exists.
  3. Track the eligible indices with the minimum and maximum values.
  4. Compare nums[j] with both extremes. Return a qualifying pair, or [-1, -1] if the sweep finds none.
from typing import List

class Solution:
    def findIndices(
        self, nums: List[int], indexDifference: int, valueDifference: int
    ) -> List[int]:
        min_index = max_index = -1

        for j, value in enumerate(nums):
            # This index is now far enough from j to be considered.
            candidate = j - indexDifference
            if candidate >= 0:
                if min_index == -1 or nums[candidate] < nums[min_index]:
                    min_index = candidate
                if max_index == -1 or nums[candidate] > nums[max_index]:
                    max_index = candidate

            # An eligible value extreme gives the largest difference.
            if min_index != -1 and value - nums[min_index] >= valueDifference:
                return [min_index, j]
            if max_index != -1 and nums[max_index] - value >= valueDifference:
                return [max_index, j]

        return [-1, -1]

Complexity:

  • Time: O(n), where n is the array length; each index is processed once.
  • Space: O(1), using only a few indices.

Common follow-ups

  • What if the indices must have an exact distance? Check only the index exactly indexDifference positions away.
  • Can the method return every qualifying pair? Keep a list of results, though the output can require O(n²) space.
  • What if the value difference is zero? The same sweep works; when the index difference is zero, an index may pair with itself.
CodingEasyPaytmSoftware Engineer

2. Number of Unequal Triplets in Array (LeetCode)

Model answer

The task

Count index triples whose three elements have pairwise different values. The indices must be in increasing order.

Key idea

Sort the array so equal values form contiguous groups. Treat each group in turn as the group supplying the middle value: choose one element from a smaller-value group, one from this group, and one from a larger-value group.

Approach

  1. Sort the values.
  2. Track how many elements belong to groups already processed.
  3. For each group, count its size and the number of elements in later groups.
  4. Add left group_size right to the answer.
  5. Update the count of processed elements.
from typing import List

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        values = sorted(nums)
        n = len(values)
        left = 0
        answer = 0
        i = 0

        while i < n:
            # Find the end of the current equal-value group.
            j = i + 1
            while j < n and values[j] == values[i]:
                j += 1

            group_size = j - i
            right = n - j

            # Pick one element from each of three distinct value groups.
            answer += left * group_size * right

            left += group_size
            i = j

        return answer

Complexity:

  • Time: O(n log n), due to sorting.
  • Space: O(n), for the sorted copy of the array.

Common follow-ups

  • Can this avoid sorting? Yes, count frequencies and process distinct values in sorted order; sorting the distinct keys still takes O(u log u), where u is the number of distinct values.
  • What if the array is already sorted? The grouping scan is O(n); an in-place sort may also use less auxiliary space.
  • How would you handle a streaming input? Maintain value frequencies, but exact counting may require ordering values or a data structure that supports prefix and suffix counts.
CodingEasyPaytmSoftware Engineer

3. Remove All Adjacent Duplicates In String (LeetCode)

Model answer

The task

Given a string, repeatedly remove any pair of equal characters that are next to each other. Return the string left after no such pair remains.

Key idea

Process the characters from left to right using a stack. The stack represents the reduced string so far: if the next character matches its top, remove the top; otherwise, add the character.

Approach

  1. Start with an empty stack.
  2. Visit each character in the input string.
  3. If it matches the stack’s top, pop the top.
  4. Otherwise, push the character.
  5. Join the stack to produce the result.

Each decision leaves the processed prefix fully reduced. Removing a pair can expose a new adjacent pair, but the stack handles that naturally when later characters are processed.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []

        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

Complexity:

  • Time: O(n), since each character is pushed at most once and popped at most once.
  • Space: O(n), for the stack in the worst case.

Common follow-ups

  • What if each character must be removed when it appears in a run of at least k equal characters? Store character counts on the stack and pop a group when its count reaches k.
  • Can this be done in place on a mutable character array? Use a write index as a stack pointer, overwriting the processed prefix.
  • What if removals follow a specified priority or multiple different patterns? Clarify the rules first; a stack may still work, but the match and removal logic may need to change.
CodingEasyPaytmSoftware Engineer

4. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingEasyPaytmSoftware Engineer

5. Reverse Linked List (LeetCode)

Model answer

The task

Given the head of a singly linked list, reverse its links in place and return the new head.

Key idea

Recursively reverse the list starting at the second node. As the recursion unwinds, point each node’s successor back to it, then clear its old forward link.

Approach

  1. If the list has zero or one node, it is already reversed.
  2. Recursively reverse the list after the head and save its new head.
  3. Point the next node back to the current node.
  4. Set the current node’s next pointer to None to finish the reversed list.
  5. Return the saved new head.
class Solution:
    def reverseList(self, head):
        # An empty or single-node list is already reversed.
        if head is None or head.next is None:
            return head

        # Reverse the remainder of the list.
        new_head = self.reverseList(head.next)

        # Put the current node after its former successor.
        head.next.next = head
        head.next = None

        return new_head

Complexity:

  • Time: O(n), where n is the number of nodes.
  • Space: O(n), for the recursive call stack.

Common follow-ups

  • Can you do it iteratively with O(1) extra space? Use previous, current, and next_node pointers to reverse links while traversing.
  • What if the list is empty or has one node? The base case returns it unchanged.
  • Can you reverse only a portion of the list? Track the sublist boundaries and reconnect them after reversing that segment.
CodingMediumPaytmSoftware Engineer

6. Spiral Matrix (LeetCode)

Model answer

The task

Return the matrix values in clockwise spiral order, starting from the top-left corner and moving inward.

Key idea

Track the unvisited rectangle with four boundaries. Visit its top, right, bottom, and left edges in turn, then shrink the rectangle and repeat.

Approach

  1. Return an empty list if the matrix has no rows or columns.
  2. Initialize boundaries for the top, bottom, left, and right edges.
  3. Traverse the top edge, then move the top boundary inward.
  4. Traverse the right edge, then move the right boundary inward.
  5. If rows remain, traverse the bottom edge in reverse; if columns remain, traverse the left edge upward.
  6. Repeat until the boundaries cross.
from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse the top edge from left to right.
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            # Traverse the right edge from top to bottom.
            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            # Traverse the bottom edge only if it has not been visited.
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1

            # Traverse the left edge only if it has not been visited.
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1

        return result

Complexity: Time: O(m × n), where each cell is visited once.

Complexity: Space: O(1) auxiliary space, excluding the output list.

Common follow-ups

  • How would you return the values counterclockwise? Change the traversal order and edge directions while maintaining the same boundary updates.
  • How does this handle a single row or column? The boundary checks prevent an edge from being visited twice.
  • Can the traversal be done without boundary variables? Yes, by marking visited cells and turning when blocked, but that requires O(m × n) extra space.
CodingMediumPaytmSoftware Engineer

7. Find Indices With Index and Value Difference II (LeetCode)

Model answer

The task

Find two positions in an array whose distance is at least indexDifference and whose values differ by at least valueDifference. Return a qualifying pair, or [-1, -1] if none exists.

Key idea

For each right-hand position j, eligible earlier positions satisfy i <= j - indexDifference. Among those positions, only the smallest and largest values matter: either may be far enough from nums[j]. Track their indices as the eligible set grows.

Approach

  1. Scan positions j from left to right.
  2. Add j - indexDifference to the eligible set when it is nonnegative.
  3. Update the indices of the smallest and largest values seen in that set.
  4. Check whether either extreme differs from nums[j] by at least valueDifference; return that pair if so.
  5. If the scan ends without a match, return [-1, -1].
from typing import List

class Solution:
    def findIndices(
        self,
        nums: List[int],
        indexDifference: int,
        valueDifference: int
    ) -> List[int]:
        min_index = -1
        max_index = -1

        for j, value in enumerate(nums):
            # This position now meets the required index distance.
            candidate = j - indexDifference
            if candidate >= 0:
                if min_index == -1 or nums[candidate] < nums[min_index]:
                    min_index = candidate
                if max_index == -1 or nums[candidate] > nums[max_index]:
                    max_index = candidate

            # The eligible set is nonempty; test its value extremes.
            if min_index != -1 and value - nums[min_index] >= valueDifference:
                return [min_index, j]
            if max_index != -1 and nums[max_index] - value >= valueDifference:
                return [max_index, j]

        return [-1, -1]

Complexity:

  • Time: O(n), with one pass through the array.
  • Space: O(1), storing only two indices.

Common follow-ups

  • Can the pair be returned in either order? Yes; the distance and value conditions use absolute differences.
  • What if indexDifference is zero? The current position is eligible, so a position may pair with itself when the value threshold allows it.
  • Can the scan return the lexicographically smallest valid pair? Not necessarily; that requires an explicit ordering strategy rather than returning the first pair found.
CodingMediumPaytmSoftware Engineer

8. LRU Cache (LeetCode)

Model answer

The task

Design a cache with a fixed capacity that supports retrieving and inserting key-value pairs. When an insertion exceeds capacity, evict the item that has gone unused for the longest time.

Key idea

Use a hash map for direct key lookup and a doubly linked list to track recency. Keep the most recently used item at the front; the least recently used item is at the back.

Approach

  1. Create a map from keys to their linked-list nodes.
  2. Use dummy head and tail nodes so items can be added or removed without special cases at the ends.
  3. On a successful get, move the node to the front and return its value; return -1 if the key is absent.
  4. On put, update and promote an existing node, or add a new node at the front.
  5. If the cache is over capacity, remove the node just before the tail and delete its key from the map.
class _Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}

        # Items are stored between these sentinels.
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _make_most_recent(self, node: _Node) -> None:
        self._remove(node)
        self._add_to_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._make_most_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)

        if node is not None:
            node.value = value
            self._make_most_recent(node)
            return

        node = _Node(key, value)
        self.nodes[key] = node
        self._add_to_front(node)

        if len(self.nodes) > self.capacity:
            least_recent = self.tail.prev
            self._remove(least_recent)
            del self.nodes[least_recent.key]

Complexity:

  • Time: O(1) for get and put; map and list operations take constant time.
  • Space: O(capacity); the map and list store at most the cache’s capacity of entries.

Common follow-ups

  • How would you make the cache thread-safe? Protect operations with a lock.
  • What if entries expire after a time-to-live? Track expiration times and remove expired entries during access or with a cleanup mechanism.
  • How would you support eviction by frequency instead of recency? Track access counts and organize entries by frequency.
CodingMediumPaytmSoftware Engineer

9. Smallest Subsequence of Distinct Characters (LeetCode)

Model answer

The task

Given a string, return the lexicographically smallest subsequence that contains every distinct character from the string exactly once. The relative order of the chosen characters must match their order in the original string.

Key idea

Process characters from left to right while maintaining a monotonic stack. If the current character is smaller than the stack’s top, and that top appears again later, remove it so the smaller character can come first.

Track which characters are already in the stack to avoid adding duplicates.

Approach

  1. Record the last index where each character appears.
  2. Scan the string from left to right.
  3. Skip a character if it is already in the stack.
  4. Otherwise, pop larger stack characters whose last occurrence is still ahead.
  5. Push the current character and mark it as present.
  6. Join the stack to form the result.
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # The last position tells us whether a character can be safely removed.
        last_position = {char: i for i, char in enumerate(s)}
        stack = []
        in_stack = set()

        for i, char in enumerate(s):
            if char in in_stack:
                continue

            # Remove a larger character if it will appear again later.
            while (
                stack
                and stack[-1] > char
                and last_position[stack[-1]] > i
            ):
                removed = stack.pop()
                in_stack.remove(removed)

            stack.append(char)
            in_stack.add(char)

        return "".join(stack)

Complexity:

  • Time: O(n), since each character is pushed and popped at most once.
  • Space: O(k), for the stack and set, where k is the number of distinct characters.

Common follow-ups

  • What if the alphabet is fixed and small? Replace the last-position dictionary with an array indexed by character.
  • Why can a character be popped only when it appears later? Otherwise, popping it would make it impossible to include it in the result.
  • What if the input is a stream with no known end? The algorithm needs future-occurrence information, so an unbounded stream generally requires buffering or additional guarantees.
CodingMediumPaytmSoftware Engineer

10. String Compression (LeetCode)

Model answer

The task

Compress consecutive runs of identical characters in a character array, modifying it in place. Keep one character per run and append the run’s count as decimal digits when it is greater than one; return the length of the compressed prefix.

Key idea

Use one pointer to scan each run and another to write the compressed result. Since the write pointer never moves ahead of the read pointer, writing the result cannot overwrite characters that are still needed.

Approach

  1. Start read and write pointers at the beginning of the array.
  2. For each run, remember its character and count its length.
  3. Write the character at the next output position.
  4. If the run has multiple characters, write its count one digit at a time.
  5. Return the final write position.
from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        read = 0
        write = 0
        n = len(chars)

        while read < n:
            char = chars[read]
            run_start = read

            while read < n and chars[read] == char:
                read += 1

            count = read - run_start
            chars[write] = char
            write += 1

            if count > 1:
                # Find the highest power of ten in the count.
                divisor = 1
                while divisor <= count // 10:
                    divisor *= 10

                # Write the count's digits from most to least significant.
                while divisor > 0:
                    digit = (count // divisor) % 10
                    chars[write] = str(digit)
                    write += 1
                    divisor //= 10

        return write

Complexity:

  • Time: O(n), since each character is scanned once and the output has at most O(n) digits.
  • Space: O(1) auxiliary space; the array is modified in place.

Common follow-ups

  • What if counts use a different base? Find the digits in that base and write them from most significant to least.
  • What if the input cannot be modified? Build and return a separate output sequence.
  • What if runs are streamed and the input is unbounded? Retain the current character and count, emitting each run when it ends.
CodingMediumPaytmSoftware Engineer

11. Remove Duplicate Letters (LeetCode)

Model answer

The task

Return a subsequence of the input string that contains every distinct character exactly once. Among all such subsequences, choose the lexicographically smallest.

Key idea

Build the answer from left to right using a monotonic stack. If the stack’s last character is larger than the current one and appears again later, remove it so the smaller character can come first without losing that character entirely.

Approach

  1. Record the last index of each character.
  2. Scan the string from left to right, skipping characters already in the stack.
  3. While the stack ends in a larger character that occurs again later, pop it and mark it as absent.
  4. Push the current character and mark it present.
  5. Join the stack to form the result.
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # The final position tells us whether a character can be added later.
        last_index = {char: i for i, char in enumerate(s)}
        stack = []
        in_stack = set()

        for i, char in enumerate(s):
            if char in in_stack:
                continue

            # Remove larger characters when they can be included again later.
            while (
                stack
                and stack[-1] > char
                and last_index[stack[-1]] > i
            ):
                in_stack.remove(stack.pop())

            stack.append(char)
            in_stack.add(char)

        return "".join(stack)

Complexity:

  • Time: O(n), since each character is pushed and popped at most once.
  • Space: O(k), for the stack and membership data, where k is the number of distinct characters.

Common follow-ups

  • What if the input alphabet is fixed and small? Use an array for last positions and membership instead of dictionaries and sets.
  • Why must a popped character appear later? Otherwise, removing it would make it impossible to include it in the result.
  • How would you adapt the solution to return the largest valid subsequence? Reverse the comparison used when deciding whether to pop.
  • Can the result be built online without knowing future characters? Not with this greedy rule; it relies on knowing whether a character appears again.
CodingMediumPaytmSoftware Engineer

12. Linked List Cycle II (LeetCode)

Model answer

The task

Given the head of a singly linked list, return the node where a cycle begins, or None if the list has no cycle. Return the node itself, not its value.

Key idea

Floyd’s two-pointer algorithm detects a cycle in constant extra space. If the pointers meet, resetting one to the head and moving both one step at a time makes them meet again at the cycle’s entry.

Approach

  1. Start a slow pointer and a fast pointer at the head.
  2. Move slow by one node and fast by two, stopping if fast reaches the end.
  3. If they meet, a cycle exists.
  4. Reset one pointer to the head, then advance both one step at a time.
  5. Return their meeting node; if the fast pointer reached the end, return None.
from typing import Optional

# Assumes the usual ListNode definition:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        # First phase: determine whether a cycle exists.
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                # Second phase: locate the cycle's entry.
                entry = head
                while entry is not slow:
                    entry = entry.next
                    slow = slow.next
                return entry

        return None

Complexity:

  • Time: O(n), where n is the number of nodes visited.
  • Space: O(1), using only two pointers.

Common follow-ups

  • How can this be solved with a hash set? Store visited node references and return the first node encountered twice; this uses O(n) extra space.
  • Why does resetting one pointer find the entry? The cycle geometry makes the distance from the head to the entry equal the distance from the meeting point to the entry along the cycle.
  • What if the list is empty or has one node? The loop ends without a meeting unless that single node points to itself.
CodingMediumPaytmSoftware Engineer

13. Car Pooling (LeetCode)

Model answer

The task

Determine whether all requested passenger pickups and drop-offs can be handled without exceeding the vehicle’s capacity. A trip occupies the vehicle from its pickup location up to, but not including, its drop-off location.

Key idea

Treat each pickup as an increase in passengers and each drop-off as a decrease. Sort these events by location, processing drop-offs before pickups at the same location so passengers leaving free seats for those boarding.

Approach

  1. Create a positive event for each trip’s pickup and a negative event for its drop-off.
  2. Sort events by location, then by passenger change; negative changes come first at a shared location.
  3. Sweep through the events, updating the number of passengers in the vehicle.
  4. Return False as soon as the count exceeds capacity; otherwise return True.
from typing import List

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        events = []

        for passengers, start, end in trips:
            events.append((start, passengers))  # Pick up passengers.
            events.append((end, -passengers))   # Drop off passengers.

        # At the same location, process drop-offs before pickups.
        events.sort()

        onboard = 0
        for _, change in events:
            onboard += change
            if onboard > capacity:
                return False

        return True

Complexity:

  • Time: O(n log n), to sort the 2n pickup and drop-off events.
  • Space: O(n), to store those events.

Common follow-ups

  • What if trips arrive one at a time? Maintain ordered events and recheck affected locations; a balanced search tree can support updates.
  • What if locations are small, bounded integers? Use a difference array and scan locations in order.
  • What if the vehicle starts with passengers already onboard? Include their count in the initial occupancy and account for their drop-off events.
  • What if capacity changes along the route? Check the occupancy against the applicable capacity at each location.
CodingMediumPaytmSoftware Engineer

14. Search in Rotated Sorted Array (LeetCode)

Model answer

The task

Given an ascending array that has been rotated at an unknown position, find the index of a target value, or return -1 if it is absent. The values are distinct.

Key idea

At each binary-search step, at least one half of the current range is still sorted. Check whether the target falls within that half; if so, keep it, otherwise search the other half.

Approach

  1. Initialize two pointers at the ends of the array.
  2. While the pointers have not crossed, inspect the middle value.
  3. If it matches the target, return its index.
  4. If the left half is sorted, check whether the target lies within its bounds and discard the other half if it does.
  5. Otherwise, use the sorted right half in the same way.
  6. Return -1 if the range becomes empty.
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            # The left half is sorted.
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Otherwise, the right half is sorted.
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Complexity:

  • Time: O(log n), because each step discards about half the remaining range.
  • Space: O(1), since the search uses only a fixed number of variables.

Common follow-ups

  • What changes if duplicates are allowed? If the endpoints and midpoint are equal, discard one endpoint; worst-case time can become O(n).
  • How would you find the rotation pivot? Binary-search for the minimum element, then search the appropriate sorted portion.
  • How would you return all matching indices with duplicates? First locate a match, then scan outward across adjacent equal values.
CodingMediumPaytmSoftware Engineer

15. Maximum Transactions Without Negative Balance (LeetCode)

Model answer

The task

Given signed transaction amounts in their original order, choose as many as possible so the balance never falls below zero. Skipped transactions do not affect the balance.

Key idea

Keep every transaction unless doing so makes the balance negative. If it does, undo the selected negative transaction with the greatest loss; removing that transaction restores the most balance while discarding just one transaction.

Approach

  1. Initialize the balance, selected count, and a min-heap of selected negative transactions.
  2. Process transactions from left to right, adding each amount to the balance and count.
  3. Push each negative amount onto the heap.
  4. If the balance is negative, remove the most negative amount from the heap, undo its effect on the balance, and decrement the count.
  5. Return the count.
import heapq
from typing import List

def maximum_transactions(transactions: List[int]) -> int:
    balance = 0
    selected = 0
    losses = []  # Negative amounts; the smallest is the largest loss.

    for amount in transactions:
        balance += amount
        selected += 1

        if amount < 0:
            heapq.heappush(losses, amount)

        if balance < 0:
            largest_loss = heapq.heappop(losses)
            balance -= largest_loss  # Undo this negative transaction.
            selected -= 1

    return selected

Complexity:

  • Time: O(n log n), due to heap operations for negative transactions.
  • Space: O(n) in the worst case, for the heap.

Common follow-ups

  • What if transactions can be reordered? The greedy strategy changes; sorting or a different optimization model may apply.
  • What if the initial balance is positive? Initialize balance to that amount.
  • How would you return the selected transactions too? Store each transaction’s index in the heap and track which indices are removed.
  • What if the balance must stay strictly positive? Check for balance <= 0 instead of balance < 0.
CodingMediumPaytmSoftware Engineer

16. Search a 2D Matrix (LeetCode)

Model answer

The task

Determine whether a target value appears in a matrix whose rows are sorted, with each row’s values ordered after the preceding row’s values.

Key idea

The matrix can be treated as one sorted, row-major sequence. Binary search that virtual sequence, converting each midpoint back to its row and column.

Approach

  1. Return False if the matrix has no rows or columns.
  2. Set the binary-search range to indices from 0 through rows * cols - 1.
  3. Convert each midpoint to (row, col) using division and remainder by the column count.
  4. Compare the corresponding matrix value with the target and narrow the range.
  5. Return False if the search range becomes empty.
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        rows = len(matrix)
        cols = len(matrix[0])
        left, right = 0, rows * cols - 1

        while left <= right:
            mid = (left + right) // 2

            # Map the virtual 1D index to its matrix coordinates.
            row, col = divmod(mid, cols)
            value = matrix[row][col]

            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Complexity:

  • Time: O(log(m × n)), where m × n is the number of matrix elements.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if each row is sorted, but rows are not ordered relative to one another? Binary-search each row, taking O(m log n) time.
  • What if rows and columns are each sorted, but the matrix is not globally ordered row by row? Start at a corner and eliminate a row or column at each step, taking O(m + n) time.
  • How do duplicates affect the search? They do not affect correctness; the search can return upon finding any matching occurrence.
CodingMediumPaytmSoftware Engineer

17. Ugly Number II (LeetCode)

Model answer

The task

Return the nth positive integer whose prime factors are limited to 2, 3, and 5.

Key idea

Every such number is formed by multiplying a smaller such number by 2, 3, or 5. Build the sequence in increasing order, keeping a pointer for each multiplier; choosing the smallest next candidate avoids duplicates and ensures the sequence stays sorted.

Approach

  1. Store the sequence so far, starting with 1.
  2. Keep three indices pointing to values whose multiples by 2, 3, and 5 are candidates for the next number.
  3. Append the smallest of those three candidates.
  4. Advance every pointer whose candidate equals the appended number, so duplicates such as 6 are skipped.
  5. Return the final value in the sequence.
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # The first ugly number is 1.
        ugly = [1]

        i2 = i3 = i5 = 0

        while len(ugly) < n:
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5

            next_value = min(next2, next3, next5)
            ugly.append(next_value)

            # Advance all matching pointers to avoid duplicates.
            if next_value == next2:
                i2 += 1
            if next_value == next3:
                i3 += 1
            if next_value == next5:
                i5 += 1

        return ugly[-1]

Complexity:

  • Time: O(n) — each sequence value is generated once.
  • Space: O(n) — stores the sequence up to the requested position.

Common follow-ups

  • How could a min-heap solve it? Repeatedly pop the smallest candidate and push its multiples by 2, 3, and 5, using a set to prevent duplicates.
  • How would you handle other allowed prime factors? Maintain one pointer per factor and choose the minimum next candidate across them.
  • Can the sequence be generated as a stream? Yes; keep the generated values and pointers, producing each next value on demand.
CodingMediumPaytmSoftware Engineer

18. Min Stack (LeetCode)

Model answer

The task

Design a stack that supports pushing and removing values, inspecting the top value, and retrieving the minimum value currently stored. Each operation should take constant time.

Key idea

Alongside each value, store the minimum seen at that point in the stack. The top entry then contains enough information to answer a minimum query without scanning the stack.

Approach

  1. Keep a list of (value, minimum_so_far) pairs.
  2. On push, compare the new value with the current minimum and store the smaller one.
  3. On pop, remove the top pair.
  4. Return the value or minimum from the top pair for top and getMin.
class MinStack:
    def __init__(self):
        # Each entry is (value, minimum among entries up to this one).
        self.stack = []

    def push(self, val: int) -> None:
        current_min = val
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity:

  • Time: O(1) per operation; each method accesses or updates only the top entry.
  • Space: O(n); each stack entry stores its value and the minimum so far.

Common follow-ups

  • Can you reduce the extra space? Store only values and keep a second stack of minimums, pushing a minimum when it is no greater than the current one.
  • How should duplicate minimums be handled? Track duplicates in the minimum stack too, so popping one leaves the other available.
  • What if the stack can be empty when queried? Define the API’s empty-stack behavior, such as raising an exception or returning a sentinel.
CodingMediumPaytmSoftware Engineer

19. Longest Nice Subarray (LeetCode)

Model answer

The task

Find the length of the longest contiguous part of an integer array where every pair of distinct elements has a bitwise AND of zero.

Key idea

Maintain a sliding window whose elements have no set bit in common. The window’s bitwise OR records all bits currently in use; a conflict with the next value means we must shrink the window until it disappears.

Approach

  1. Track the window’s left edge, its combined bitmask, and the best length found.
  2. For each new value, remove values from the left while its bits overlap the window mask.
  3. Add the new value to the mask and update the best length.
  4. When removing a value, XOR it out: within a valid window, no other value uses any of its set bits.
class Solution:
    def longestNiceSubarray(self, nums: list[int]) -> int:
        left = 0
        used_bits = 0
        best = 0

        for right, value in enumerate(nums):
            # Shrink until value shares no set bits with the window.
            while used_bits & value:
                used_bits ^= nums[left]
                left += 1

            used_bits |= value
            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), since each element enters and leaves the window at most once.
  • Space: O(1), using a fixed number of integer variables.

Common follow-ups

  • What if the condition allows at most k shared bits? Track bit frequencies in the window and define how conflicts are counted.
  • Can the window be replaced with binary search on length? Yes, but checking every window is typically less efficient than this direct sliding window.
  • Why is XOR safe when removing an element? The window invariant guarantees its set bits appear nowhere else in the window.
CodingMediumPaytmSoftware Engineer

20. Minimize Maximum of Array (LeetCode)

Model answer

The task

You may repeatedly move one unit from an array position to the position immediately before it. Find the smallest possible value of the array’s maximum element after any number of moves.

Key idea

For each prefix, its total must remain within that prefix: units can move left, but not right. So the maximum must be at least the ceiling of that prefix’s average. The largest such lower bound is achievable by distributing each prefix as evenly as possible.

Approach

  1. Scan the array from left to right, maintaining the prefix sum.
  2. For each prefix of length i + 1, compute the ceiling of its average.
  3. Track the largest of these values.
  4. Return that value as the minimum achievable maximum.
from typing import List

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        prefix_sum = 0
        answer = 0

        for i, value in enumerate(nums):
            prefix_sum += value
            length = i + 1

            # Integer arithmetic for ceil(prefix_sum / length).
            required_max = (prefix_sum + length - 1) // length
            answer = max(answer, required_max)

        return answer

Complexity:

  • Time: O(n), for one pass through the array.
  • Space: O(1), using only a few variables.

Common follow-ups

  • Can this be solved with binary search? Yes. Binary-search a candidate maximum and check whether each prefix has enough capacity under that limit.
  • Why are prefix averages a lower bound? A prefix’s sum cannot be sent to later positions, so its values must fit within the prefix.
  • Why is the largest prefix bound achievable? Moving excess units left greedily balances each prefix without changing its total or requiring units to move right.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions