PhonePe interview questions & answers

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

CodingEasyPhonePeSoftware Engineer

1. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyPhonePeSoftware Engineer

2. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyPhonePeSoftware Engineer

3. Longest Common Prefix (LeetCode)

Model answer

The task

Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.

Key idea

Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.

Approach

  1. If the list is empty, return an empty string.
  2. Scan each character of the first string from left to right.
  3. For each position, compare that character with the character at the same position in every other string.
  4. If a string is too short or a character differs, return the matching prefix before that position.
  5. If all positions match, return the first string.
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Complexity:

  • Time: O(S), where S is the total number of characters inspected.
  • Space: O(1) auxiliary space, excluding the returned prefix.

Common follow-ups

  • How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
  • Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
  • What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.
CodingMediumPhonePeSoftware Engineer

4. Evaluate Division (LeetCode)

Model answer

The task

Given equations that define ratios between variables, answer queries asking for a ratio between two variables. Return -1.0 when the ratio cannot be determined.

Key idea

Represent each equation as two directed graph edges: from a to b with weight a / b, and from b to a with the reciprocal weight. A path’s edge weights multiply to give the ratio between its endpoints.

Approach

  1. Build a weighted adjacency list from the equations.
  2. For each query, return -1.0 if either variable is unknown.
  3. Otherwise, use DFS to find a path between the variables, multiplying edge weights along the way.
  4. Track visited variables so cycles do not cause repeated exploration.
  5. If the variables are the same and known, the ratio is 1.0.
from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self,
        equations: List[List[str]],
        values: List[float],
        queries: List[List[str]]
    ) -> List[float]:
        graph = defaultdict(list)

        for (numerator, denominator), value in zip(equations, values):
            graph[numerator].append((denominator, value))
            graph[denominator].append((numerator, 1.0 / value))

        def find_ratio(start: str, target: str) -> float:
            if start not in graph or target not in graph:
                return -1.0
            if start == target:
                return 1.0

            stack = [(start, 1.0)]
            visited = {start}

            while stack:
                variable, product = stack.pop()

                for neighbor, edge_value in graph[variable]:
                    if neighbor in visited:
                        continue

                    next_product = product * edge_value
                    if neighbor == target:
                        return next_product

                    visited.add(neighbor)
                    stack.append((neighbor, next_product))

            return -1.0

        return [find_ratio(a, b) for a, b in queries]

Complexity:

  • Time: O(Q(V + E)), where each query may traverse the full graph.
  • Space: O(V + E) for the graph and the DFS state.

Common follow-ups

  • How can repeated queries be sped up? Use weighted union-find to answer each query in near-constant time after preprocessing.
  • How would you handle inconsistent equations? Detect conflicting ratios when connecting variables or revisiting an already-connected pair.
  • What if the graph is very large but queries are few? Keep DFS/BFS per query to avoid more elaborate preprocessing.
CodingMediumPhonePeSoftware Engineer

5. Smallest String With Swaps (LeetCode)

Model answer

The task

Given a string and pairs of indices that may be swapped any number of times, return the lexicographically smallest string reachable through those swaps.

Key idea

Swaps connect indices into independent groups: within each connected component, every character can reach every index. Sort the characters and indices in each group, then place the smallest characters at the smallest indices.

Approach

  1. Initialize a disjoint-set union (DSU), with one set per string index.
  2. For each allowed pair, union its two indices.
  3. Group indices by their DSU root.
  4. For each group, sort its indices and the characters at those indices.
  5. Assign the sorted characters back to the sorted indices.
from collections import defaultdict
from typing import List

class Solution:
    def smallestStringWithSwaps(
        self, s: str, pairs: List[List[int]]
    ) -> str:
        n = len(s)
        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            # Path compression keeps future lookups efficient.
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)
            if root_a == root_b:
                return

            # Union by size keeps the DSU trees shallow.
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            size[root_a] += size[root_b]

        for a, b in pairs:
            union(a, b)

        components = defaultdict(list)
        for i in range(n):
            components[find(i)].append(i)

        result = list(s)
        for indices in components.values():
            indices.sort()
            chars = sorted(s[i] for i in indices)

            for i, char in zip(indices, chars):
                result[i] = char

        return "".join(result)

Complexity:

  • Time: O(n log n + p α(n)), where n is the string length, p is the number of pairs, and α is the inverse Ackermann function.
  • Space: O(n) for the DSU, component groups, and result.

Common follow-ups

  • What if only one swap is allowed? Apply that swap directly; connected components no longer describe all reachable arrangements.
  • Can sorting be avoided for a small character set? Count each character per component and assign characters in order.
  • What if swaps arrive incrementally? Maintain the DSU as pairs arrive; recompute affected component characters when a result is requested.
CodingMediumPhonePeSoftware Engineer

6. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode)

Model answer

The task

Given an integer array and a nonnegative limit, find the length of the longest contiguous subarray whose largest and smallest values differ by at most the limit.

Key idea

Maintain a sliding window and two monotonic deques of indices: one tracks the window’s maximum, the other its minimum. When their difference exceeds the limit, move the window’s left edge until it is valid again.

Approach

  1. Initialize deques for maximum and minimum candidates, plus the window’s left edge and best length.
  2. For each new right-edge index, remove dominated values from the backs of the deques.
  3. Add the new index to both deques.
  4. While the maximum minus minimum exceeds the limit, advance the left edge and discard deque fronts that have left the window.
  5. Record the longest valid window seen.
from collections import deque
from typing import List

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        max_indices = deque()  # Values decrease from front to back.
        min_indices = deque()  # Values increase from front to back.
        left = 0
        best = 0

        for right, value in enumerate(nums):
            # Remove candidates that cannot be the window maximum.
            while max_indices and nums[max_indices[-1]] < value:
                max_indices.pop()
            max_indices.append(right)

            # Remove candidates that cannot be the window minimum.
            while min_indices and nums[min_indices[-1]] > value:
                min_indices.pop()
            min_indices.append(right)

            # Shrink until the window satisfies the limit.
            while nums[max_indices[0]] - nums[min_indices[0]] > limit:
                left += 1
                if max_indices[0] < left:
                    max_indices.popleft()
                if min_indices[0] < left:
                    min_indices.popleft()

            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), because each index enters and leaves each deque at most once.
  • Space: O(n) in the worst case for the deques.

Common follow-ups

  • How would you handle a stream of values? Use the same window logic, storing indices or timestamps to expire old entries.
  • What if values arrive out of order? A simple sliding window no longer suffices; use an ordered structure that supports range extrema and expiration.
  • Can you solve it with heaps? Yes, with min- and max-heaps plus lazy removal, though the deque solution is typically simpler and faster.
CodingMediumPhonePeSoftware Engineer

7. Number of Islands (LeetCode)

Model answer

The task

Given a grid of land and water, count the groups of connected land cells. Cells connect horizontally or vertically, not diagonally.

Key idea

Each group is one island. Scan the grid, and whenever an unvisited land cell is found, count a new island and explore its entire connected region. Mark cells as visited when adding them to the search queue so no cell is processed more than once.

Approach

  1. Return 0 if the grid is empty.
  2. Scan every cell in the grid.
  3. When a land cell is found, increment the island count and start a breadth-first search from it.
  4. During the search, mark each discovered land cell as water and add its in-bounds land neighbors to the queue.
  5. Return the island count after the scan is complete.
from collections import deque
from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        islands = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1":
                    continue

                islands += 1
                grid[row][col] = "0"
                queue = deque([(row, col)])

                while queue:
                    current_row, current_col = queue.popleft()

                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_row = current_row + dr
                        next_col = current_col + dc

                        if (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                            and grid[next_row][next_col] == "1"
                        ):
                            # Mark when enqueuing to avoid duplicate work.
                            grid[next_row][next_col] = "0"
                            queue.append((next_row, next_col))

        return islands

Complexity: Time: O(rows * cols), since each cell is examined at most a constant number of times.

Complexity: Space: O(rows * cols) in the worst case for the BFS queue.

Common follow-ups

  • Preserve the input grid? Track visited cells in a separate set instead of changing land cells to water.
  • Use depth-first search instead? Recursively or iteratively explore the four neighbors; iterative DFS avoids recursion-depth concerns.
  • Count diagonally connected land as part of the same island? Include the four diagonal directions in the neighbor list.
CodingMediumPhonePeSoftware Engineer

8. Detonate the Maximum Bombs (LeetCode)

Model answer

The task

Each bomb has a position and a blast radius. Find the largest number of bombs that can be detonated by choosing one bomb to start, where a blast can trigger another bomb.

Key idea

Treat bombs as vertices in a directed graph: add an edge from bomb i to bomb j when j lies within i’s blast radius. For each possible starting bomb, traverse the graph and count how many vertices are reachable.

Approach

  1. For every ordered pair of distinct bombs, compare their squared distance with the first bomb’s squared radius.
  2. Add a directed edge when the second bomb is within range.
  3. Run DFS from each bomb, using a fresh visited set for each start.
  4. Track the largest number of visited bombs.
from typing import List

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        graph = [[] for _ in range(n)]

        # Build the directed graph using squared distances,
        # avoiding unnecessary square-root calculations.
        for i, (x1, y1, radius) in enumerate(bombs):
            for j, (x2, y2, _) in enumerate(bombs):
                if i == j:
                    continue

                dx = x1 - x2
                dy = y1 - y2
                if dx * dx + dy * dy <= radius * radius:
                    graph[i].append(j)

        def reachable_count(start: int) -> int:
            visited = {start}
            stack = [start]

            while stack:
                bomb = stack.pop()
                for neighbor in graph[bomb]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)

            return len(visited)

        return max(reachable_count(i) for i in range(n))

Complexity:

  • Time: O(n³) in the worst case; graph construction takes O(n²), and DFS from all starts takes O(n(n + E)).
  • Space: O(n²) for the graph and O(n) for each traversal’s visited set and stack.

Common follow-ups

  • Can the graph be undirected? No; each bomb has its own radius, so reachability may work in only one direction.
  • Can you reduce repeated traversal work? Strongly connected component condensation can help identify groups that always trigger one another, though counting reachable bombs still requires tracking reachable component sizes.
  • What if coordinates are very large? Squared-distance comparisons avoid floating-point precision issues; use integer types large enough for the squared values.
CodingMediumPhonePeSoftware Engineer

9. Amount of Time for Binary Tree to Be Infected (LeetCode)

Model answer

The task

Given a binary tree and the value of its starting node, find how many minutes it takes for the infection to reach every node. Each minute, infection spreads from an infected node to its parent and children.

Key idea

Treat the tree as an undirected graph: each node is connected to its children and parent. A breadth-first search from the starting node visits nodes in increasing order of infection time.

Approach

  1. Traverse the tree and record each node’s parent.
  2. Find the node whose value matches start.
  3. Run BFS from that node, tracking visited nodes to avoid revisiting through parent links.
  4. Count BFS levels; the last level reached is the time needed to infect all nodes.
from collections import deque
from typing import Optional

# Assumes TreeNode has attributes val, left, and right.
class Solution:
    def amountOfTime(self, root: Optional["TreeNode"], start: int) -> int:
        if root is None:
            return 0

        parent = {}
        start_node = None
        stack = [root]

        # Record parent links and locate the starting node.
        while stack:
            node = stack.pop()

            if node.val == start:
                start_node = node

            if node.left:
                parent[node.left] = node
                stack.append(node.left)

            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        # Visit each node once, expanding one infection minute at a time.
        queue = deque([start_node])
        visited = {start_node}
        minutes = -1

        while queue:
            minutes += 1
            for _ in range(len(queue)):
                node = queue.popleft()

                for neighbor in (node.left, node.right, parent.get(node)):
                    if neighbor is not None and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

        return minutes

Complexity:

  • Time: O(n), since each node is processed a constant number of times.
  • Space: O(n), for parent links, the BFS queue, and the visited set.

Common follow-ups

  • What if the start value is absent? Return an error or a designated sentinel, depending on the API.
  • Can the parent map be avoided? Yes; use DFS to compute distances from the start while tracking paths, though the bookkeeping is less direct.
  • What if the tree is extremely deep? The iterative traversals avoid recursion-depth limits.
CodingMediumPhonePeSoftware Engineer

10. Make Lexicographically Smallest Array by Swapping Elements (LeetCode)

Model answer

The task

Rearrange an array by repeatedly swapping elements whose values differ by at most a given limit. Return the lexicographically smallest array that can be formed.

Key idea

Treat each array position as connected to positions holding values within the swap limit. Because swaps can be chained, sorted values belong to the same swappable group whenever each neighboring pair in sorted order differs by at most the limit.

Within each group, assign its smallest values to its smallest original indices.

Approach

  1. Sort the array values while retaining their original indices.
  2. Scan the sorted pairs and split them into groups at gaps larger than limit.
  3. For each group, collect its original indices and sort those indices.
  4. Assign the group’s sorted values to those indices in order.
  5. Return the rearranged array.
class Solution:
    def lexicographicallySmallestArray(
        self, nums: list[int], limit: int
    ) -> list[int]:
        # Sorting by value reveals which values can be linked by swaps.
        pairs = sorted((value, index) for index, value in enumerate(nums))
        result = [0] * len(nums)

        start = 0
        while start < len(pairs):
            end = start + 1

            # Consecutive sorted values with small enough gaps are connected.
            while (
                end < len(pairs)
                and pairs[end][0] - pairs[end - 1][0] <= limit
            ):
                end += 1

            group = pairs[start:end]
            indices = sorted(index for _, index in group)
            values = [value for value, _ in group]

            # Put the smallest group value at the earliest group index.
            for index, value in zip(indices, values):
                result[index] = value

            start = end

        return result

Complexity:

  • Time: O(n log n), dominated by sorting the values and group indices.
  • Space: O(n) for the sorted pairs, result, and group data.

Common follow-ups

  • Why can a chain of swaps connect values farther apart than the limit? Each adjacent pair in the chain can be swapped, so transitive connectivity makes the entire group mutually rearrangeable.
  • Can union-find solve it? Yes. Sort values, union neighboring sorted entries whose gap is within the limit, then sort values and indices within each component.
  • What happens when the limit is zero? Only equal values connect, so values can move among positions holding that same value.
CodingMediumPhonePeSoftware Engineer

11. Simple Bank System (LeetCode)

Model answer

The task

Design a bank that stores account balances and supports transfers, deposits, and withdrawals. Each operation succeeds only when the account numbers are valid and the source account has enough money.

Key idea

Store balances in a list, using account number minus one as the index. Check validity and available funds before changing any balance.

Approach

  1. Copy the initial balances into the bank’s state.
  2. Use a helper to check whether an account number is in range.
  3. For a transfer, validate both accounts and the source balance, then update both.
  4. For a deposit or withdrawal, validate the account; for withdrawal, also check funds.
  5. Return True when an operation is completed and False otherwise.
class Bank:
    def __init__(self, balance: list[int]):
        # Account numbers are 1-based; list indices are 0-based.
        self.balance = balance[:]

    def _valid_account(self, account: int) -> bool:
        return 1 <= account <= len(self.balance)

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        if not self._valid_account(account1) or not self._valid_account(account2):
            return False

        source = account1 - 1
        destination = account2 - 1

        if self.balance[source] < money:
            return False

        self.balance[source] -= money
        self.balance[destination] += money
        return True

    def deposit(self, account: int, money: int) -> bool:
        if not self._valid_account(account):
            return False

        self.balance[account - 1] += money
        return True

    def withdraw(self, account: int, money: int) -> bool:
        if not self._valid_account(account):
            return False

        index = account - 1
        if self.balance[index] < money:
            return False

        self.balance[index] -= money
        return True

Complexity:

  • Time: O(1) per operation; each uses a fixed number of list accesses and checks.
  • Space: O(n); the bank stores one balance per account.

Common follow-ups

  • How would you make operations thread-safe? Protect each operation with a lock, or use finer-grained locks per account.
  • How would you support millions of accounts? Store balances in a database or key-value store and update them transactionally.
  • What if transfers must be atomic across multiple services? Use a transactional mechanism or a ledger-based design with reconciliation.
CodingMediumPhonePeSoftware Engineer

12. 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.
CodingMediumPhonePeSoftware Engineer

13. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumPhonePeSoftware Engineer

14. Minimum Number of Days to Make m Bouquets (LeetCode)

Model answer

The task

Given each flower’s blooming day, find the earliest day when it is possible to make m bouquets, each using k adjacent flowers. A flower can be used in only one bouquet.

Key idea

Feasibility is monotonic: if the bouquets can be made by some day, they can also be made on any later day. Binary-search the day, checking feasibility by scanning the flowers and counting runs of bloomed flowers.

Approach

  1. If there are fewer than m * k flowers, return -1.
  2. Search between the earliest and latest bloom days.
  3. For a candidate day, scan in order and count consecutive flowers that have bloomed.
  4. Each time a run reaches length k, form a bouquet and reset the run.
  5. If the scan makes at least m bouquets, search earlier days; otherwise, search later ones.
class Solution:
    def minDays(self, bloomDay: list[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1

        def can_make(day: int) -> bool:
            bouquets = 0
            consecutive = 0

            for bloom in bloomDay:
                if bloom <= day:
                    consecutive += 1
                    if consecutive == k:
                        bouquets += 1
                        consecutive = 0
                        if bouquets == m:
                            return True
                else:
                    consecutive = 0

            return False

        low, high = min(bloomDay), max(bloomDay)

        while low < high:
            mid = (low + high) // 2
            if can_make(mid):
                high = mid
            else:
                low = mid + 1

        return low

Complexity:

  • Time: O(n log R), where R is the range from the minimum to maximum bloom day; each feasibility check scans the array.
  • Space: O(1), excluding the input; the scan uses only a few counters.

Common follow-ups

  • Can bouquets use non-adjacent flowers? Yes; then count all bloomed flowers and divide by k.
  • What if the input is empty? The product check returns -1 when m and k are positive.
  • Can the search bounds be improved? The minimum and maximum bloom days are already tight bounds on the answer.
  • How would you support many queries with different m and k? The feasibility scan remains simple, but repeated binary searches may motivate preprocessing or a specialized query strategy.
CodingMediumPhonePeSoftware Engineer

15. Split Array into Consecutive Subsequences (LeetCode)

Model answer

The task

Given a sorted integer array, determine whether every value can be assigned to a consecutive, strictly increasing subsequence of length at least three.

Key idea

Process values from smallest to largest. For each value, extend an existing subsequence ending just before it if possible; otherwise, start a new length-three subsequence. Extending first preserves scarce values that may be needed to start future subsequences.

Approach

  1. Count how many times each value remains unused.
  2. Track how many subsequences currently end at each value.
  3. For each value, skip it if already used; otherwise consume one copy.
  4. Extend a subsequence ending at value - 1 when possible.
  5. If none can be extended, require two remaining copies of the next consecutive values to start a subsequence.
  6. Return False if neither option works; otherwise all values are assigned successfully.
from collections import Counter, defaultdict
from typing import List

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        remaining = Counter(nums)
        ending = defaultdict(int)

        for value in nums:
            if remaining[value] == 0:
                continue

            remaining[value] -= 1

            # Extend a subsequence that ends at the previous value.
            if ending[value - 1] > 0:
                ending[value - 1] -= 1
                ending[value] += 1

            # Otherwise, start a new subsequence of length three.
            elif remaining[value + 1] > 0 and remaining[value + 2] > 0:
                remaining[value + 1] -= 1
                remaining[value + 2] -= 1
                ending[value + 2] += 1

            else:
                return False

        return True

Complexity:

  • Time: O(n) on average; each array value is processed once, with hash-table operations.
  • Space: O(n) for the frequency and ending-count maps.

Common follow-ups

  • What if the input is unsorted? Sort it first; the overall time becomes O(n log n).
  • Can the algorithm use a min-heap? Yes; heaps can track available subsequences by ending value and length.
  • What if subsequences must have length at least k? When starting one, check that the next k - 1 consecutive values are available.
  • What edge cases matter? Gaps or too few copies can make assignment impossible; the greedy checks reject these immediately.
CodingMediumPhonePeSoftware Engineer

16. Number of Operations to Make Network Connected (LeetCode)

Model answer

The task

Given computers labeled from 0 to n - 1 and cables connecting pairs of computers, find the fewest cable moves needed to make the network connected. A move can reuse a cable that is not needed to connect its current components; return -1 if there are too few cables.

Key idea

A connected network needs at least n - 1 cables. If that condition holds, the answer is the number of connected components minus one: each move can connect two components. Union-Find tracks those components while processing the cables.

Approach

  1. If there are fewer than n - 1 cables, return -1.
  2. Initialize each computer as its own component.
  3. For each cable, union the components of its endpoints.
  4. Return the number of remaining components minus one.
class Solution:
    def makeConnected(self, n: int, connections: list[list[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        parent = list(range(n))
        size = [1] * n
        components = n

        def find(x: int) -> int:
            # Path halving keeps the trees nearly flat.
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: int, b: int) -> None:
            nonlocal components
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return

            # Attach the smaller tree beneath the larger one.
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a

            parent[root_b] = root_a
            size[root_a] += size[root_b]
            components -= 1

        for a, b in connections:
            union(a, b)

        return components - 1

Complexity:

  • Time: O((n + m) α(n)), where m is the number of cables; Union-Find operations are nearly constant amortized time.
  • Space: O(n), for the parent and size arrays.

Common follow-ups

  • Why is n - 1 cables the minimum? A connected graph on n vertices requires at least n - 1 edges.
  • Can this be solved with graph traversal? Yes. Build adjacency lists, count connected components with DFS or BFS, then subtract one after checking the cable count.
  • What if cables have different costs? The problem changes: choose the cheapest useful connections, typically with a minimum spanning tree approach.
CodingMediumPhonePeSoftware Engineer

17. Matchsticks to Square (LeetCode)

Model answer

The task

Determine whether all the matchsticks can be divided into four groups with equal total length. Each stick must be used whole and exactly once.

Key idea

The total length must divide evenly by four, and no stick can be longer than the target side length. A bitmask DP tracks which sticks have been used; for each reachable mask, it stores the current side’s partial length.

Approach

  1. Reject if there are fewer than four sticks or the total is not divisible by four.
  2. Set the target side length to one quarter of the total; reject if any stick exceeds it.
  3. Start with an empty mask and a partial side length of zero.
  4. For each reachable mask, try adding every unused stick that fits.
  5. Return whether the mask using every stick ends with a partial length of zero.
class Solution:
    def makesquare(self, matchsticks: list[int]) -> bool:
        n = len(matchsticks)
        total = sum(matchsticks)

        if n < 4 or total % 4 != 0:
            return False

        target = total // 4
        if max(matchsticks) > target:
            return False

        # dp[mask] is the length of the side currently being built.
        # -1 means this set of used sticks is unreachable.
        dp = [-1] * (1 << n)
        dp[0] = 0

        for mask in range(1 << n):
            current_side = dp[mask]
            if current_side == -1:
                continue

            for i, length in enumerate(matchsticks):
                bit = 1 << i

                if mask & bit:
                    continue
                if current_side + length > target:
                    continue

                next_mask = mask | bit

                # A full side is completed at target, so the next side
                # starts with length zero.
                dp[next_mask] = (current_side + length) % target

        return dp[(1 << n) - 1] == 0

Complexity:

  • Time: O(n · 2ⁿ), considering each unused stick for each mask.
  • Space: O(2ⁿ), for the DP array.

Common follow-ups

  • How would backtracking solve it? Sort sticks largest-first, assign each to a side that still has room, and skip equivalent side sums.
  • How would you form k equal groups? Replace four with k, and use a target of total // k.
  • How can backtracking be pruned further? Stop trying other sides after a failed placement into an empty side or a side already at the same sum.
CodingMediumPhonePeSoftware Engineer

18. Queue Reconstruction by Height (LeetCode)

Model answer

The task

Reorder people, each described by a height and a count of people at least as tall who must stand ahead of them. Return an arrangement that satisfies every count.

Key idea

Process people from shortest to tallest. For each person, the unfilled positions will eventually be occupied by people at least as tall as them, so their count tells us which unfilled position to choose. A Fenwick tree tracks unfilled positions and finds the requested one efficiently.

Approach

  1. Sort by increasing height, breaking ties by decreasing count.
  2. Initialize a Fenwick tree with every queue position marked empty.
  3. For each person, select the (count + 1)-th empty position.
  4. Put the person there and mark the position filled.
  5. Return the completed queue.
from typing import List

class FenwickTree:
    def __init__(self, n: int) -> None:
        # Initially, every position is empty.
        # For an all-ones array, each Fenwick node stores its low bit.
        self.n = n
        self.tree = [0] + [i & -i for i in range(1, n + 1)]

    def add(self, index: int, delta: int) -> None:
        """Add delta to the value at the zero-based index."""
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def kth(self, k: int) -> int:
        """Return the zero-based index of the k-th available position."""
        index = 0
        bit = 1 << (self.n.bit_length() - 1)

        while bit:
            next_index = index + bit
            if next_index <= self.n and self.tree[next_index] < k:
                index = next_index
                k -= self.tree[next_index]
            bit >>= 1

        return index

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        n = len(people)
        queue = [None] * n
        empty_positions = FenwickTree(n)

        # Shorter people are placed first; for equal heights, place
        # the larger required count first.
        people.sort(key=lambda person: (person[0], -person[1]))

        for height, count in people:
            position = empty_positions.kth(count + 1)
            queue[position] = [height, count]
            empty_positions.add(position, -1)

        return queue

Complexity:

  • Time: O(n log n), from sorting and Fenwick tree operations.
  • Space: O(n), for the queue and Fenwick tree.

Common follow-ups

  • Can this be done without a Fenwick tree? Yes; inserting each person into a list takes O(n²) time in the worst case.
  • Why sort equal heights by decreasing count? It ensures each person with the same height is placed consistently with the required number ahead.
  • What if the input is invalid? Verify the returned arrangement by counting qualifying people before each person.
CodingMediumPhonePeSoftware Engineer

19. Most Stones Removed with Same Row or Column (LeetCode)

Model answer

The task

Given stones at distinct grid coordinates, remove as many as possible while each removal is allowed only when another stone remains in the same row or column. Return the maximum number removable.

Key idea

Treat stones as connected when they share a row or column. Within each connected component, all but one stone can be removed, so the answer is the number of stones minus the number of components.

Approach

  1. Use union-find to group stones that share a row or column.
  2. Represent rows and columns as different kinds of nodes, so a row coordinate cannot be confused with a column coordinate.
  3. For each stone, union its row node with its column node.
  4. Count the distinct components containing stones and subtract that count from the total.
from typing import List

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}
        size = {}

        def find(node):
            if node not in parent:
                parent[node] = node
                size[node] = 1
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        def union(a, b):
            root_a = find(a)
            root_b = find(b)
            if root_a == root_b:
                return
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            size[root_a] += size[root_b]

        # A row node and a column node are distinct even if their values match.
        for row, col in stones:
            union(("row", row), ("col", col))

        # Count components represented by stones.
        components = {
            find(("row", row))
            for row, _ in stones
        }

        return len(stones) - len(components)

Complexity:

  • Time: O(n α(n)), where n is the number of stones and α is the inverse Ackermann function.
  • Space: O(n), for the union-find nodes and component set.

Common follow-ups

  • How would you solve it with DFS? Build adjacency between stones sharing a row or column, then count connected components.
  • What if the grid coordinates can be negative? The tagged tuple nodes already support negative coordinates.
  • What if stones arrive as a stream? Maintain union-find incrementally; track the component count as new row-column unions are added.
CodingMediumPhonePeSoftware Engineer

20. Loud and Rich (LeetCode)

Model answer

The task

Given directed “richer than” relationships and each person’s quietness score, find for every person the quietest person among them and everyone known to be richer than them.

Key idea

Process people in topological order, from richer to poorer. Each person carries the quietest candidate found among themselves and their richer ancestors; pass that candidate along to poorer neighbors.

Approach

  1. Build a graph with an edge from each richer person to the person they outrank.
  2. Compute each person’s indegree.
  3. Initialize each person’s answer to themselves.
  4. Process zero-indegree people first. For each edge, update the poorer person’s answer if the current person’s candidate is quieter.
  5. Add a neighbor to the queue when all its richer people have been processed.
from collections import deque
from typing import List

class Solution:
    def loudAndRich(
        self, richer: List[List[int]], quiet: List[int]
    ) -> List[int]:
        n = len(quiet)
        graph = [[] for _ in range(n)]
        indegree = [0] * n

        # Edges point from richer people to poorer people.
        for rich, poor in richer:
            graph[rich].append(poor)
            indegree[poor] += 1

        # Each person is initially their own quietest known candidate.
        answer = list(range(n))
        queue = deque(
            person for person in range(n) if indegree[person] == 0
        )

        while queue:
            rich = queue.popleft()

            for poor in graph[rich]:
                if quiet[answer[rich]] < quiet[answer[poor]]:
                    answer[poor] = answer[rich]

                indegree[poor] -= 1
                if indegree[poor] == 0:
                    queue.append(poor)

        return answer

Complexity:

  • Time: O(n + m), where n is the number of people and m is the number of relationships.
  • Space: O(n + m) for the graph, indegrees, queue, and answers.

Common follow-ups

  • Can DFS with memoization solve it? Yes; recursively combine each person’s richer neighbors, memoizing the quietest candidate.
  • What if relationships can contain cycles? The topological approach requires a DAG; cycles need to be detected or handled under a different problem definition.
  • What if quietness scores tie? Either tied person is valid if the requirement allows any quietest person.

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