Juspay interview questions & answers

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

CodingEasyJuspaySoftware Engineer

1. Toggle Light Bulbs (LeetCode)

Model answer

The task

The title suggests tracking the on/off state of bulbs as toggle operations occur, but it does not identify exactly how bulbs or operations are represented. The solution below shows the general parity-tracking idea for bulb labels.

Key idea

A bulb’s final state depends only on whether it was toggled an odd or even number of times. Track the labels with odd toggle counts; toggling a label again removes it from that set.

Approach

  1. Start with an empty set representing bulbs that are on, assuming they begin off.
  2. For each toggle event, add its bulb label if absent; otherwise remove it.
  3. Return the resulting labels in sorted order if an ordered result is needed.
  4. Adapt the input and return format to the specific problem interface.
def bulbs_on_after_toggles(toggle_events: list[int]) -> list[int]:
    """Return labels toggled an odd number of times, assuming all start off."""
    on = set()

    for bulb in toggle_events:
        if bulb in on:
            on.remove(bulb)
        else:
            on.add(bulb)

    return sorted(on)

Complexity:

  • Time: O(n + k log k), for n toggle events and k bulbs left on; sorting takes O(k log k).
  • Space: O(k), for the set of bulbs left on.

Common follow-ups

  • What if some bulbs start on? Initialize the set with those labels before processing toggles.
  • What if the output does not need ordering? Return the set directly, avoiding the sorting cost.
  • What if each event toggles a range of bulbs? Use a suitable range-update technique, such as a difference array for offline range toggles.
CodingMediumJuspaySoftware Engineer

2. 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.
CodingMediumJuspaySoftware Engineer

3. Set Matrix Zeroes (LeetCode)

Model answer

The task

Given a matrix, modify it in place so that any row or column containing a zero is entirely zeroed. The zeroes introduced during modification should not cause additional rows or columns to be selected.

Key idea

Use the first row and first column as marker storage: mark which rows and columns must be cleared. Track separately whether either of those marker areas originally contains a zero, since they also serve as storage.

Approach

  1. Check whether the first row and first column initially contain zeroes.
  2. Scan the rest of the matrix; for every zero, mark its row in the first column and its column in the first row.
  3. Use those markers to zero the corresponding interior cells.
  4. If needed, zero the first row and first column last.
class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        """
        Modify matrix in place.
        """
        rows, cols = len(matrix), len(matrix[0])

        first_row_has_zero = any(matrix[0][c] == 0 for c in range(cols))
        first_col_has_zero = any(matrix[r][0] == 0 for r in range(rows))

        # Record which interior rows and columns need to be zeroed.
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        # Apply the recorded markers to the interior.
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        # Clear the marker row and column if they originally had zeroes.
        if first_row_has_zero:
            for c in range(cols):
                matrix[0][c] = 0

        if first_col_has_zero:
            for r in range(rows):
                matrix[r][0] = 0

Complexity:

  • Time: O(mn), where m and n are the matrix dimensions; the matrix is scanned a constant number of times.
  • Space: O(1) auxiliary space; markers are stored in the matrix itself.

Common follow-ups

  • What if the matrix must not be modified in place? Use separate row and column marker arrays, requiring O(m + n) extra space.
  • What if the matrix is sparse? Store the indices of affected rows and columns while scanning only the available entries.
  • Does the approach work for a one-row or one-column matrix? Yes; the separate first-row and first-column flags handle those cases.
CodingMediumJuspaySoftware Engineer

4. Find Closest Node to Given Two Nodes (LeetCode)

Model answer

The task

Given a directed graph where each node has at most one outgoing edge, find a node reachable from two starting nodes that minimizes the larger of the two travel distances. Break ties by choosing the node with the smallest index; return -1 if there is no shared reachable node.

Key idea

Because each node has at most one outgoing edge, following edges from a start traces a single path and eventually stops or revisits a node. Record the distance to every node on each path, then choose the best node reachable from both.

Approach

  1. Define a helper that follows outgoing edges from a start node.
  2. Record each node’s distance, stopping at -1 or when a node has already been visited.
  3. Run the helper for both starting nodes.
  4. Scan nodes reachable from both and minimize the greater of their distances.
  5. Scan in index order and update only for a strictly smaller distance, preserving the smallest-index tie-break.
from typing import List

class Solution:
    def closestMeetingNode(
        self, edges: List[int], node1: int, node2: int
    ) -> int:
        def distances(start: int) -> List[int]:
            result = [-1] * len(edges)
            node = start
            distance = 0

            while node != -1 and result[node] == -1:
                result[node] = distance
                distance += 1
                node = edges[node]

            return result

        dist1 = distances(node1)
        dist2 = distances(node2)

        best_node = -1
        best_distance = float("inf")

        for node in range(len(edges)):
            if dist1[node] != -1 and dist2[node] != -1:
                candidate = max(dist1[node], dist2[node])
                if candidate < best_distance:
                    best_distance = candidate
                    best_node = node

        return best_node

Complexity:

  • Time: O(n), since each path and the final scan visit at most n nodes.
  • Space: O(n), for the two distance arrays.

Common follow-ups

  • What if the total distance should be minimized instead? Compare dist1[node] + dist2[node] instead of their maximum.
  • What if each node can have multiple outgoing edges? Use graph traversal to compute shortest-path distances from each start.
  • How are cycles handled? The distance helper stops when it encounters a node already recorded.
CodingMediumJuspaySoftware Engineer

5. Asteroid Collision (LeetCode)

Model answer

The task

Given a sequence of signed asteroid sizes, simulate their movement and collisions. Return the asteroids that remain, in their original order.

Key idea

A collision can happen only when a right-moving asteroid is followed by a left-moving one. Keep surviving asteroids in a stack; resolve each possible collision with the stack’s most recent survivor.

Approach

  1. Start with an empty stack.
  2. Process asteroids from left to right.
  3. While the stack’s top moves right and the current asteroid moves left, compare their sizes.
  4. Remove the smaller asteroid; if they are equal, remove both. Stop resolving if the current asteroid is destroyed.
  5. Add the current asteroid if it survives, then return the stack.
from typing import List

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        survivors: List[int] = []

        for asteroid in asteroids:
            alive = True

            # Only a right-moving survivor can collide with a left-moving one.
            while (
                alive
                and asteroid < 0
                and survivors
                and survivors[-1] > 0
            ):
                top = survivors[-1]

                if top < -asteroid:
                    # The top asteroid is smaller and is destroyed.
                    survivors.pop()
                elif top == -asteroid:
                    # Both asteroids are destroyed.
                    survivors.pop()
                    alive = False
                else:
                    # The current asteroid is smaller and is destroyed.
                    alive = False

            if alive:
                survivors.append(asteroid)

        return survivors

Complexity:

  • Time: O(n), since each asteroid is pushed and popped at most once.
  • Space: O(n) for the stack of surviving asteroids.

Common follow-ups

  • How would you handle zero-sized asteroids? Define their movement and collision behavior, then adjust the collision rules accordingly.
  • Can the result be computed in place? Yes, use the input list’s prefix as the stack, if modifying the input is allowed.
  • What if collisions occur in multiple dimensions? A single stack is no longer sufficient; the model needs spatial positions and directions.
CodingMediumJuspaySoftware Engineer

6. Maximum Score From Removing Substrings (LeetCode)

Model answer

The task

Given a string and scores for removing "ab" and "ba", choose a sequence of removals that maximizes the total score. Each removal deletes two adjacent characters.

Key idea

Remove the higher-scoring pair first. A stack lets us remove each occurrence as soon as its two characters become adjacent; after that pass, remove the other pair from the remaining string.

Approach

  1. Decide which pair has the higher score.
  2. Scan the string with a stack, removing that pair whenever it appears at the top.
  3. Scan the remaining characters the same way for the other pair.
  4. Add both passes’ scores and return the total.
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def remove_pairs(text: str, first: str, second: str, score: int):
            stack = []
            total = 0

            for char in text:
                if stack and stack[-1] == first and char == second:
                    stack.pop()
                    total += score
                else:
                    stack.append(char)

            return "".join(stack), total

        # Remove the more valuable pair before the less valuable one.
        if x >= y:
            remaining, high_score = remove_pairs(s, "a", "b", x)
            _, low_score = remove_pairs(remaining, "b", "a", y)
        else:
            remaining, high_score = remove_pairs(s, "b", "a", y)
            _, low_score = remove_pairs(remaining, "a", "b", x)

        return high_score + low_score

Complexity:

  • Time: O(n), since each character is processed a constant number of times.
  • Space: O(n), for the stacks holding characters that remain after each pass.

Common follow-ups

  • Can you avoid building a string between passes? Yes; use a stack for each pass and iterate over the first pass’s stack directly.
  • Why remove the higher-scoring pair first? Removing it greedily preserves its value; removing the lower-value pair first can destroy an opportunity to earn the higher score.
  • What if the input contains other characters? The stack naturally keeps them, and only the specified adjacent pairs are removed.
CodingMediumJuspaySoftware Engineer

7. Operations on Tree (LeetCode)

Model answer

The task

Design a tree-locking data structure that lets users lock or unlock individual nodes, and upgrade a node by replacing locks on its descendants with a lock on the node itself. An upgrade is allowed only when the node and all its ancestors are unlocked and at least one descendant is locked.

Key idea

Store each node’s current lock owner, using -1 for unlocked, and build child lists from the parent array. For an upgrade, walk upward to check ancestors and traverse downward to find and clear locked descendants.

Approach

  1. Initialize an owner array with every node unlocked.
  2. Build child lists from the parent array.
  3. For lock, succeed only if the node is unlocked; record the user.
  4. For unlock, succeed only if that user owns the node’s lock.
  5. For upgrade, check the node and its ancestors, then traverse its descendants.
  6. If any descendant is locked, clear all descendant locks and lock the requested node.
class LockingTree:
    def __init__(self, parent: list[int]):
        self.parent = parent
        n = len(parent)
        self.children = [[] for _ in range(n)]

        for node in range(1, n):
            self.children[parent[node]].append(node)

        # -1 means the node is currently unlocked.
        self.owner = [-1] * n

    def lock(self, num: int, user: int) -> bool:
        if self.owner[num] != -1:
            return False

        self.owner[num] = user
        return True

    def unlock(self, num: int, user: int) -> bool:
        if self.owner[num] != user:
            return False

        self.owner[num] = -1
        return True

    def upgrade(self, num: int, user: int) -> bool:
        if self.owner[num] != -1:
            return False

        # Every ancestor must be unlocked.
        ancestor = self.parent[num]
        while ancestor != -1:
            if self.owner[ancestor] != -1:
                return False
            ancestor = self.parent[ancestor]

        # Collect locked descendants. Do not include num itself.
        locked_descendants = []
        stack = self.children[num][:]

        while stack:
            node = stack.pop()
            if self.owner[node] != -1:
                locked_descendants.append(node)
            stack.extend(self.children[node])

        if not locked_descendants:
            return False

        # Replace their locks with a lock on num.
        for node in locked_descendants:
            self.owner[node] = -1
        self.owner[num] = user
        return True

Complexity:

  • Time: lock and unlock are O(1); upgrade is O(n) in the worst case, as it may inspect the tree.
  • Space: O(n) for the child lists and lock-owner array.

Common follow-ups

  • Can upgrades be faster? Maintain locked-descendant counts, but updates must carefully propagate through ancestors.
  • What if the tree changes? Update the child representation and any cached metadata when nodes are added or moved.
  • How would this work concurrently? Protect checks and updates with synchronization so two operations cannot interleave inconsistently.
CodingMediumJuspaySoftware Engineer

8. Longest Subsequence With Decreasing Adjacent Difference (LeetCode)

Model answer

The task

Find the length of the longest subsequence whose absolute adjacent differences never increase as you move from left to right.

Key idea

Track the best subsequence length for each ending value and exact last difference. To extend a sequence with a new difference d, the previous difference must be at least d; a suffix maximum answers that query efficiently.

Approach

  1. Let D be the range of values in nums; differences are between 0 and D.
  2. For each distinct value, store DP states by exact last difference, plus suffix maxima over those states.
  3. For each number, consider every previously seen ending value. Query its suffix maximum at the new difference to find the best valid sequence to extend.
  4. If that ending value has appeared but has no length-2-or-more state to extend, start a pair of length 2.
  5. Apply updates only after checking all prior values, then refresh the suffix maxima for the current ending value.
from typing import List

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        if not nums:
            return 0

        values = sorted(set(nums))
        value_id = {value: i for i, value in enumerate(values)}
        max_diff = max(nums) - min(nums)
        width = max_diff + 1

        # best[value][d]: best length ending at value with exact last difference d.
        best = [[0] * width for _ in values]

        # suffix[value][d]: best length with last difference at least d.
        suffix = [[0] * width for _ in values]

        seen = [False] * len(values)
        answer = 1

        for x in nums:
            x_id = value_id[x]
            updates = [0] * width

            # Use only states formed before this occurrence of x.
            for y_id, y in enumerate(values):
                if not seen[y_id]:
                    continue

                diff = abs(x - y)
                previous_length = suffix[y_id][diff]

                # Extend a valid sequence, or start a new pair.
                candidate = max(2, previous_length + 1)
                updates[diff] = max(updates[diff], candidate)

            for diff, length in enumerate(updates):
                best[x_id][diff] = max(best[x_id][diff], length)

            running = 0
            for diff in range(max_diff, -1, -1):
                running = max(running, best[x_id][diff])
                suffix[x_id][diff] = running

            seen[x_id] = True
            answer = max(answer, max(updates, default=0))

        return answer

Complexity:

  • Time: O(n(U + D) + UD), where U is the number of distinct values and D is the value range.
  • Space: O(UD) for the DP and suffix-max tables.

Common follow-ups

  • What if the value range is large? Use a range-maximum structure per ending value to avoid allocating a dense table over all differences.
  • Can equal adjacent values be used? Yes; their absolute difference is 0, which satisfies the non-increasing condition.
  • How can the actual subsequence be returned? Store predecessor value/difference choices when recording each improved DP state.
CodingMediumJuspaySoftware Engineer

9. Container With Most Water (LeetCode)

Model answer

The task

Given nonnegative heights arranged along a line, choose two positions to form a container with the greatest possible area. Its area is the distance between the positions multiplied by the shorter of their two heights.

Key idea

Start with the widest possible pair, at the two ends. The shorter side limits the area, so moving the taller side inward cannot improve that limiting height and only reduces the width. Move the shorter side instead, hoping to find a taller boundary.

Approach

  1. Set pointers to the first and last positions.
  2. Compute the area using their distance and the shorter height; update the best area.
  3. Move the pointer at the shorter height inward by one position.
  4. Repeat until the pointers meet.
  5. Return the greatest area seen.
from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        best_area = 0

        while left < right:
            width = right - left
            limiting_height = min(height[left], height[right])
            best_area = max(best_area, width * limiting_height)

            # The shorter side limits this container's area.
            # Moving the taller side inward cannot improve that limit.
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return best_area

Complexity:

  • Time: O(n), because each pointer moves inward at most n times.
  • Space: O(1), since only a few variables are used.

Common follow-ups

  • What if heights can be negative? A negative height does not describe a valid container; clarify the input rules, or treat invalid heights as unusable.
  • Why is it safe to discard the shorter side? With the same shorter boundary, every inward pair has less width, so it cannot produce a larger area.
  • Can this be done with extra memory? Not usefully for this objective; the two-pointer scan already processes the candidates in linear time with constant space.
CodingMediumJuspaySoftware Engineer

10. Gas Station (LeetCode)

Model answer

The task

Given circular arrays of fuel available and fuel required for each leg, find a starting station from which a vehicle can complete the full loop, or return -1 if no such start exists.

Key idea

If the total fuel is less than the total cost, no start can work. Otherwise, when the running fuel balance becomes negative, none of the stations in the current candidate segment can be a valid start, so begin a new candidate at the next station.

Approach

  1. Track the total fuel surplus across all stations.
  2. Track the surplus from the current candidate start.
  3. At each station, add its fuel minus its travel cost to both totals.
  4. If the candidate’s running surplus drops below zero, discard that segment and set the next station as the candidate.
  5. Return the candidate if the total surplus is nonnegative; otherwise, return -1.
class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total_surplus = 0
        current_surplus = 0
        start = 0

        for i in range(len(gas)):
            surplus = gas[i] - cost[i]
            total_surplus += surplus
            current_surplus += surplus

            # No station in the current segment can be a valid start.
            if current_surplus < 0:
                start = i + 1
                current_surplus = 0

        return start if total_surplus >= 0 else -1

Complexity:

  • Time: O(n), where n is the number of stations; each station is processed once.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • Why can the candidate segment be discarded after the balance goes negative? Starting at any station within that segment leaves less fuel by the time it reaches the failure point, so it cannot succeed.
  • What if multiple valid starts exist? The algorithm returns one valid start; uniqueness is not guaranteed.
  • Can this be solved without storing prefix sums? Yes. The running surplus and total surplus are sufficient, as shown above.
CodingMediumJuspaySoftware Engineer

11. Minimum Cost Homecoming of a Robot in a Grid (LeetCode)

Model answer

The task

Find the least cost for a robot to travel from its starting cell to its home cell. Each vertical move pays the cost of the row it enters, and each horizontal move pays the cost of the column it enters.

Key idea

The row and column moves can be handled independently: every route must cross the same rows and columns between the two positions. Moving directly toward home along each axis avoids unnecessary steps.

Approach

  1. Set the row and column directions based on the start and home positions.
  2. Step through each row between them, adding the cost of each entered row.
  3. Step through each column between them, adding the cost of each entered column.
  4. Return the total.
from typing import List

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int],
    ) -> int:
        total = 0

        start_row, start_col = startPos
        home_row, home_col = homePos

        row_step = 1 if home_row > start_row else -1
        row = start_row
        while row != home_row:
            row += row_step
            total += rowCosts[row]

        col_step = 1 if home_col > start_col else -1
        col = start_col
        while col != home_col:
            col += col_step
            total += colCosts[col]

        return total

Complexity:

  • Time: O(|Δrow| + |Δcol|), for the steps between the positions.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if the robot may move only right or down? The same method works when the destination is reachable using those directions; otherwise it is unreachable.
  • What if some moves are blocked? The direct-axis argument no longer necessarily holds; use shortest-path search on the grid.
  • How would you return the path as well as the cost? Record each visited cell while stepping toward home.
  • What if each move has an additional direction-dependent cost? Add that cost during the corresponding axis traversal.
CodingMediumJuspaySoftware Engineer

12. Merge Intervals (LeetCode)

Model answer

The task

Given a collection of intervals, combine every pair that overlaps and return the resulting non-overlapping intervals. The result should be ordered by starting point.

Key idea

Sort intervals by their start. Then scan once, keeping the most recently merged interval; each next interval either extends it or starts a new one.

Approach

  1. Sort the intervals by their start value.
  2. Initialize the result with the first interval, if any.
  3. For each remaining interval, compare its start with the end of the last result interval.
  4. If they overlap, update that end to the larger of the two ends.
  5. Otherwise, append the interval as a new result.
from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        intervals.sort(key=lambda interval: interval[0])
        merged = [intervals[0]]

        for start, end in intervals[1:]:
            # The intervals overlap, so extend the last merged interval.
            if start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                # No overlap: this interval begins a new merged range.
                merged.append([start, end])

        return merged

Complexity: Time: O(n log n), dominated by sorting n intervals.

Complexity: Space: O(n) for the merged result; sorting may also use up to O(n) space.

Common follow-ups

  • What if intervals that only touch at an endpoint should remain separate? Use start < merged[-1][1] as the overlap test.
  • How would you merge intervals as they arrive in sorted order? Skip sorting and apply the same scan, processing each interval once.
  • What if intervals are inserted one at a time into an already merged collection? Use binary search to find the insertion point, then merge neighboring overlaps.
CodingMediumJuspaySoftware Engineer

13. Maximum Product Subarray (LeetCode)

Model answer

The task

Given an integer array, find the largest product of any nonempty contiguous subarray.

Key idea

A negative number can turn a very small product into the largest one, so track both the maximum and minimum product ending at the current position. Update both for each number, then keep the best maximum seen overall.

Approach

  1. Initialize the ending maximum, ending minimum, and overall answer to the first number.
  2. For each remaining number, save the old ending maximum.
  3. Update the ending maximum and minimum from the number alone or from multiplying it by either saved product.
  4. Update the overall answer with the new ending maximum.
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        # The best subarray must include at least one element.
        ending_max = ending_min = answer = nums[0]

        for value in nums[1:]:
            previous_max = ending_max

            # Multiplication by a negative can swap the roles of max and min.
            ending_max = max(value, value * previous_max, value * ending_min)
            ending_min = min(value, value * previous_max, value * ending_min)

            answer = max(answer, ending_max)

        return answer

Complexity:

  • Time: O(n), processing each array element once.
  • Space: O(1), storing only a fixed number of values.

Common follow-ups

  • How would you return the subarray’s indices too? Track the start index associated with each ending maximum and save its range whenever the overall best improves.
  • What changes if the array may be empty? Define the desired empty-input result, then check for emptiness before accessing the first element.
  • How would you handle floating-point values? Use the same recurrence, while accounting for precision and the desired comparison tolerance.
CodingMediumJuspaySoftware Engineer

14. Node With Highest Edge Score (LeetCode)

Model answer

The task

Given a directed graph where each node has one outgoing edge, find the node with the largest edge score. A node’s score is the sum of the indices of all nodes that point to it; ties go to the smallest node index.

Key idea

Accumulate each source node’s index into the score of its destination. Then scan scores in increasing node order, updating the answer only when a strictly larger score is found.

Approach

  1. Create a score array initialized to zero.
  2. For each node, add its index to the score of its destination.
  3. Scan nodes from smallest to largest.
  4. Keep the current best node, replacing it only when a score is strictly higher.
class Solution:
    def edgeScore(self, edges: list[int]) -> int:
        n = len(edges)
        scores = [0] * n

        # Each node contributes its index to the score of its destination.
        for node, destination in enumerate(edges):
            scores[destination] += node

        best_node = 0
        for node in range(1, n):
            # Strict comparison preserves the smaller index on ties.
            if scores[node] > scores[best_node]:
                best_node = node

        return best_node

Complexity:

  • Time: O(n), for accumulating scores and scanning them.
  • Space: O(n), for the score array.

Common follow-ups

  • What if ties should choose the largest index? Scan from largest to smallest and keep the first maximum.
  • Can scores be computed without a separate array? Yes, but scores still need to be stored somewhere; the array is the straightforward approach.
  • What if nodes can have multiple outgoing edges? Add each source index to the score of every destination, taking care to match the intended scoring rule.
CodingHardJuspaySoftware Engineer

15. Longest Cycle in a Graph (LeetCode)

Model answer

The task

Given a directed graph where each node has at most one outgoing edge, find the number of nodes in its longest cycle. Return -1 if the graph has no cycle.

Key idea

Follow outgoing edges from each unvisited node, tracking the nodes on the current walk and their positions in it. If the walk reaches a node already on that walk, the cycle length is the current path length minus that node’s position.

Approach

  1. Keep each node in one of three states: unvisited, on the current walk, or fully processed.
  2. Start a walk from every unvisited node, recording each visited node’s position in the walk.
  3. Stop when the walk reaches -1 or a node that has already been visited.
  4. If it reaches a node still on the current walk, calculate the cycle length and update the maximum.
  5. Mark every node on the walk as fully processed before starting another walk.
from typing import List

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        # 0: unvisited, 1: on the current walk, 2: fully processed
        state = [0] * len(edges)
        longest = -1

        for start in range(len(edges)):
            if state[start] != 0:
                continue

            path = []
            position = {}
            node = start

            # Follow outgoing edges until the walk ends or reaches a visited node.
            while node != -1 and state[node] == 0:
                state[node] = 1
                position[node] = len(path)
                path.append(node)
                node = edges[node]

            # A state-1 node belongs to this walk, so the walk has found a cycle.
            if node != -1 and state[node] == 1:
                cycle_length = len(path) - position[node]
                longest = max(longest, cycle_length)

            # This walk is complete; future walks can skip all its nodes.
            for visited_node in path:
                state[visited_node] = 2

        return longest

Complexity:

  • Time: O(n), because each node is processed at most once.
  • Space: O(n), for visit states and the current walk’s path and positions.

Common follow-ups

  • How would you find the cycle itself? Keep the path and return the segment starting at the repeated node’s recorded position.
  • Can strongly connected components solve this? Yes, but the single-outgoing-edge structure makes direct walks simpler.
  • What if nodes can have multiple outgoing edges? A walk is no longer sufficient; use a general directed-cycle algorithm such as DFS or SCC decomposition.
CodingHardJuspaySoftware Engineer

16. Largest Color Value in a Directed Graph (LeetCode)

Model answer

The task

Given a color for each graph node and directed edges, find the largest number of occurrences of any one color along a directed path. If the graph contains a cycle, return -1.

Key idea

Process nodes in topological order and use dynamic programming to track, for each node and color, the greatest count of that color on a path ending there. Topological sorting also reveals whether the graph has a cycle: if some nodes are never processed, one exists.

Approach

  1. Build an adjacency list and calculate each node’s indegree.
  2. Initialize a DP table with one count per node and color; each node contributes its own color.
  3. Add all zero-indegree nodes to a queue.
  4. Process each queued node, updating the best answer and propagating its counts to its neighbors.
  5. If fewer than all nodes were processed, return -1; otherwise return the best count.
from collections import deque
from typing import List

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        alphabet_size = 26

        graph = [[] for _ in range(n)]
        indegree = [0] * n

        for source, target in edges:
            graph[source].append(target)
            indegree[target] += 1

        # dp[node][color] is the greatest count of that color on a
        # path ending at node.
        dp = [[0] * alphabet_size for _ in range(n)]
        for node, color in enumerate(colors):
            dp[node][ord(color) - ord("a")] = 1

        queue = deque(node for node in range(n) if indegree[node] == 0)
        processed = 0
        best = 0

        while queue:
            node = queue.popleft()
            processed += 1
            best = max(best, max(dp[node]))

            for neighbor in graph[node]:
                neighbor_color = ord(colors[neighbor]) - ord("a")

                for color in range(alphabet_size):
                    dp[neighbor][color] = max(
                        dp[neighbor][color],
                        dp[node][color] + (color == neighbor_color),
                    )

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

        return best if processed == n else -1

Complexity:

  • Time: O(26(n + m)), where n is the number of nodes and m is the number of edges.
  • Space: O(26n + n + m) for the DP table, graph, and indegrees.

Common follow-ups

  • What if colors come from a larger alphabet? Coordinate-compress the colors and track one DP entry per distinct color.
  • How could the algorithm return an actual path? Store predecessor information for each node and color, then reconstruct the path for the best state.
  • What if paths may revisit nodes? Clarify the path definition; allowing repeated visits in a cyclic graph can make the maximum unbounded.
CodingHardJuspaySoftware Engineer

17. Sliding Window Maximum (LeetCode)

Model answer

The task

Given an integer array and a window width k, return the maximum value in each contiguous window as it moves from left to right.

Key idea

Keep a deque of indices whose values are in decreasing order. Its front is the index of the current window’s maximum; indices that leave the window or are dominated by a newer, larger value can be discarded.

Approach

  1. Create a deque of indices and a list for the answers.
  2. For each index, remove indices from the front if they are outside the current window.
  3. Remove indices from the back while their values are no greater than the current value.
  4. Append the current index; it is now a candidate maximum for this and future windows.
  5. Once the first full window has been processed, append the value at the deque’s front.
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0:
            return []

        # Store indices in decreasing order of their corresponding values.
        candidates = deque()
        result = []

        for i, value in enumerate(nums):
            # Remove the maximum candidate if it is outside this window.
            while candidates and candidates[0] <= i - k:
                candidates.popleft()

            # A newer value at least as large makes older candidates useless.
            while candidates and nums[candidates[-1]] <= value:
                candidates.pop()

            candidates.append(i)

            # The first complete window ends at index k - 1.
            if i >= k - 1:
                result.append(nums[candidates[0]])

        return result

Complexity:

  • Time: O(n), because each index is added to and removed from the deque at most once.
  • Space: O(k), for the deque of candidate indices, excluding the output.

Common follow-ups

  • How would you find window minima instead? Reverse the deque’s ordering, removing smaller values from the back.
  • What if equal values should preserve the earliest index? Remove only strictly smaller values from the back.
  • How can this be handled as a streaming input? Maintain the same bounded deque and emit a maximum whenever a full window has arrived.
CodingHardJuspaySoftware Engineer

18. Minimum Number of Operations to Make Array Continuous (LeetCode)

Model answer

The task

Find the fewest array elements that must be changed so the resulting array contains distinct consecutive integers.

Key idea

A set of n consecutive integers spans n - 1. Keep as many existing distinct values as possible inside a range of that width; replace every other element. Sorting the unique values lets a sliding window find the largest such group.

Approach

  1. Sort the distinct values, since duplicates cannot occupy separate positions in the final array.
  2. Use two pointers to maintain a window whose largest and smallest values differ by at most n - 1.
  3. For each right endpoint, advance the left endpoint until the window fits.
  4. Track the largest window and return n minus its size.
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        values = sorted(set(nums))

        best = left = 0
        for right, value in enumerate(values):
            while value - values[left] >= n:
                left += 1
            best = max(best, right - left + 1)

        return n - best

Complexity:

  • Time: O(n log n), for sorting the distinct values.
  • Space: O(n), for storing the distinct values.

Common follow-ups

  • What if the input is already continuous? The window contains n distinct values, so the answer is 0.
  • Why remove duplicates first? A continuous result must contain n distinct values, so duplicates cannot increase the number of values we can keep.
  • Can the scan be made faster? The two-pointer scan is already O(n) after sorting; sorting is the dominant cost.
CodingHardJuspaySoftware Engineer

19. Shortest Path in a Weighted Tree (LeetCode)

Model answer

The task

The title and tags suggest finding distances between nodes in a weighted tree, potentially while edge weights change. The exact query and update requirements are unclear, so the solution below covers the common dynamic version: update an edge weight and query the path distance between two nodes.

Key idea

A tree path distance is root_distance[u] + root_distance[v] - 2 * root_distance[lca(u, v)]. Changing an edge affects the root distance of every node in the child endpoint’s subtree, so a Fenwick tree can apply that change to a subtree and retrieve each node’s current root distance.

Approach

  1. Root the tree at node 0; record parent, depth, initial root distance, and Euler-tour subtree intervals.
  2. Build a binary-lifting table to find lowest common ancestors.
  3. Store each edge’s child endpoint, so an edge update becomes a range addition over that child’s subtree.
  4. Use a Fenwick tree for subtree range additions and point queries.
  5. Compute a distance query with the LCA formula and the current root distances.
class Fenwick:
    """Supports range additions and point queries over [0, n)."""

    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, index, delta):
        i = index + 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def range_add(self, left, right, delta):
        """Add delta to every position in [left, right)."""
        self._add(left, delta)
        if right < self.n:
            self._add(right, -delta)

    def point_query(self, index):
        total = 0
        i = index + 1
        while i:
            total += self.bit[i]
            i -= i & -i
        return total

class WeightedTreeDistance:
    def __init__(self, n, edges):
        """
        edges contains (u, v, weight) triples.
        Nodes are numbered 0 through n - 1.
        """
        self.n = n
        self.edges = [list(edge) for edge in edges]
        graph = [[] for _ in range(n)]

        for edge_id, (u, v, weight) in enumerate(self.edges):
            graph[u].append((v, edge_id))
            graph[v].append((u, edge_id))

        self.parent = [0] * n
        self.depth = [0] * n
        self.base_distance = [0] * n
        self.tin = [0] * n
        self.tout = [0] * n
        self.edge_child = [-1] * len(edges)

        # Enter/exit events produce contiguous Euler-tour subtree intervals.
        clock = 0
        stack = [(0, 0, -1, 0, False)]
        while stack:
            node, parent, edge_id, distance, exiting = stack.pop()
            if exiting:
                self.tout[node] = clock
                continue

            self.parent[node] = parent
            self.depth[node] = 0 if node == parent else self.depth[parent] + 1
            self.base_distance[node] = distance
            self.tin[node] = clock
            clock += 1

            stack.append((node, parent, edge_id, distance, True))
            for neighbor, next_edge in reversed(graph[node]):
                if neighbor == parent:
                    continue
                self.edge_child[next_edge] = neighbor
                next_distance = distance + self.edges[next_edge][2]
                stack.append((neighbor, node, next_edge, next_distance, False))

        levels = max(1, n.bit_length())
        self.up = [self.parent[:]]
        for _ in range(1, levels):
            previous = self.up[-1]
            self.up.append([previous[previous[node]] for node in range(n)])

        self.changes = Fenwick(n)

    def _lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a

        difference = self.depth[a] - self.depth[b]
        bit = 0
        while difference:
            if difference & 1:
                a = self.up[bit][a]
            difference >>= 1
            bit += 1

        if a == b:
            return a

        for level in range(len(self.up) - 1, -1, -1):
            if self.up[level][a] != self.up[level][b]:
                a = self.up[level][a]
                b = self.up[level][b]
        return self.parent[a]

    def update_edge(self, edge_id, new_weight):
        u, v, old_weight = self.edges[edge_id]
        child = self.edge_child[edge_id]
        delta = new_weight - old_weight
        self.edges[edge_id][2] = new_weight
        self.changes.range_add(self.tin[child], self.tout[child], delta)

    def distance(self, u, v):
        ancestor = self._lca(u, v)

        def root_distance(node):
            return self.base_distance[node] + self.changes.point_query(self.tin[node])

        return root_distance(u) + root_distance(v) - 2 * root_distance(ancestor)

Complexity:

  • Time: O(n log n) preprocessing; O(log n) per update or distance query.
  • Space: O(n log n) for the ancestor table and tree data.

Common follow-ups

  • What if edge weights never change? Use the initial root distances and LCA formula; no Fenwick tree is needed.
  • What if the tree has negative edge weights? The same path-sum method works; a tree has a unique path.
  • What if queries ask for the actual path, not just its distance? Find the LCA, then collect each endpoint’s ancestors and join the two path portions.

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