Sprinklr interview questions & answers

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

CodingEasySprinklrSoftware Engineer

1. Isomorphic Strings (LeetCode)

Model answer

The task

Determine whether two strings have the same length and whether their characters can be matched one-to-one so that each position in one string corresponds to the same position in the other.

Key idea

Maintain mappings in both directions. A character in the first string must always map to the same character in the second, and two different characters cannot map to the same character.

Approach

  1. Return False if the strings have different lengths.
  2. Create a mapping from the first string to the second.
  3. Create a reverse mapping from the second string to the first.
  4. Scan corresponding characters together.
  5. If either mapping conflicts with the current pair, return False; otherwise, record the pair.
  6. If every pair is consistent, return True.
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        forward = {}
        reverse = {}

        for left, right in zip(s, t):
            if left in forward and forward[left] != right:
                return False
            if right in reverse and reverse[right] != left:
                return False

            forward[left] = right
            reverse[right] = left

        return True

Complexity:

  • Time: O(n), where n is the string length; each position is checked once.
  • Space: O(k), where k is the number of distinct characters stored in the mappings.

Common follow-ups

  • What if the mapping only needs to preserve characters in one direction? Use just one mapping; this does not enforce a one-to-one correspondence.
  • What if the strings are streamed? Process corresponding characters as they arrive, retaining the two mappings.
  • Can the extra space be bounded for a fixed alphabet? Yes; use arrays instead of dictionaries when the character set has a known, small range.
CodingMediumSprinklrSoftware Engineer

2. Choose Edges to Maximize Score in a Tree (LeetCode)

Model answer

The task

Choose a set of weighted tree edges with no shared endpoints, maximizing their total weight. Return the best score.

Key idea

This is maximum-weight matching on a tree. For each node, compare leaving it unmatched to matching it with one child; if it matches a child, that child cannot match any of its own children.

Approach

  1. Build child lists from the parent of each node.
  2. Traverse from the root and record nodes in visitation order.
  3. Process nodes in reverse order so each child’s states are ready.
  4. Track the best score when the node may match a child, and when its parent edge is already chosen.
  5. Return the root’s best score.
from typing import List

class Solution:
    def maximumScore(self, edges: List[List[int]]) -> int:
        n = len(edges)
        children = [[] for _ in range(n)]

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

        # Build a traversal order, then process it bottom-up.
        order = [0]
        for node in order:
            for child, _ in children[node]:
                order.append(child)

        # free[u]: best score in u's subtree if u is not matched to its parent.
        # blocked[u]: best score if u is matched to its parent, so u
        # cannot be matched to any of its children.
        free = [0] * n
        blocked = [0] * n

        for node in reversed(order):
            # If node is blocked, each child is free to choose its own match.
            blocked[node] = sum(free[child] for child, _ in children[node])

            # Start with node unmatched to all children.
            best = blocked[node]

            # Or match node to exactly one child.
            for child, weight in children[node]:
                score = (
                    blocked[node]
                    - free[child]
                    + weight
                    + blocked[child]
                )
                best = max(best, score)

            free[node] = best

        return free[0]

Complexity:

  • Time: O(n), since each node and edge is processed a constant number of times.
  • Space: O(n), for the tree and the dynamic-programming arrays.

Common follow-ups

  • What if all weights are negative? The algorithm can choose no edges, so the score is at least zero.
  • What if the tree is not rooted at node 0? Root it with a traversal before applying the same DP.
  • What if chosen edges may share endpoints? Then this matching constraint no longer applies; the problem’s selection rules determine a different DP.
CodingMediumSprinklrSoftware Engineer

3. Maximum Sum of Two Non-Overlapping Subarrays (LeetCode)

Model answer

The task

Choose two subarrays of specified lengths from an array so that they do not overlap. Return the largest possible sum of their elements.

Key idea

Try both possible left-to-right orders of the subarrays. For each order, scan the possible position of the second subarray while keeping the best sum of a first subarray that ends before it.

Approach

  1. Build prefix sums so any subarray sum can be computed in constant time.
  2. Write a helper for lengths left_len and right_len, where the first subarray must come before the second.
  3. As the second subarray moves right, add the newly eligible first subarray to the running maximum.
  4. Combine that maximum with the current second-subarray sum.
  5. Run the helper with the lengths swapped and take the larger result.
class Solution:
    def maxSumTwoNoOverlap(
        self, nums: list[int], firstLen: int, secondLen: int
    ) -> int:
        # Prefix sums let us get any subarray sum in O(1).
        prefix = [0]
        for value in nums:
            prefix.append(prefix[-1] + value)

        def best_in_order(left_len: int, right_len: int) -> int:
            best_left = prefix[left_len] - prefix[0]
            best_total = float("-inf")

            # The right subarray is [end - right_len, end).
            for end in range(left_len + right_len, len(nums) + 1):
                left_end = end - right_len

                # Include the left subarray that ends immediately before
                # the current right subarray; earlier ones remain eligible.
                left_sum = prefix[left_end] - prefix[left_end - left_len]
                best_left = max(best_left, left_sum)

                right_sum = prefix[end] - prefix[left_end]
                best_total = max(best_total, best_left + right_sum)

            return best_total

        return max(
            best_in_order(firstLen, secondLen),
            best_in_order(secondLen, firstLen),
        )

Complexity:

  • Time: O(n), with two linear scans.
  • Space: O(n), for the prefix-sum array.

Common follow-ups

  • Can the extra space be reduced? Yes; maintain rolling window sums instead of storing all prefix sums.
  • What if there are more than two subarrays? Use dynamic programming over the number of chosen subarrays and positions.
  • Does this work with negative values? Yes; fixed-length sums are compared directly, and the result starts at negative infinity.
CodingMediumSprinklrSoftware Engineer

4. Edit Distance (LeetCode)

Model answer

The task

Given two strings, find the fewest single-character insertions, deletions, or replacements needed to change one into the other.

Key idea

Let dp[j] represent the edit distance between the processed prefix of the first string and the first j characters of the second. For each character pair, either keep matching characters at no cost or choose the cheapest insertion, deletion, or replacement.

Approach

  1. Make the second string the shorter one to keep the DP row small.
  2. Initialize distances for converting the empty first prefix into each prefix of the second string.
  3. Process the first string one character at a time, keeping the previous row’s diagonal value.
  4. Update each cell using the matching-character case or the minimum of the three edit operations.
  5. Return the final row value.
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # Keep the DP row as short as possible.
        if len(word2) > len(word1):
            word1, word2 = word2, word1

        # Distances from an empty prefix of word1 to prefixes of word2.
        dp = list(range(len(word2) + 1))

        for i, char1 in enumerate(word1, start=1):
            # Distance from the current word1 prefix to an empty word2 prefix.
            diagonal = dp[0]
            dp[0] = i

            for j, char2 in enumerate(word2, start=1):
                above = dp[j]

                if char1 == char2:
                    dp[j] = diagonal
                else:
                    # Insert, delete, or replace one character.
                    dp[j] = 1 + min(
                        dp[j - 1],  # Insert
                        above,      # Delete
                        diagonal,   # Replace
                    )

                diagonal = above

        return dp[-1]

Complexity:

  • Time: O(mn), where m and n are the string lengths; each pair of characters is processed once.
  • Space: O(min(m, n)), for the DP row.

Common follow-ups

  • How would you reconstruct the actual edits? Store the full DP table, then backtrack from the final cell.
  • What if insertion, deletion, and replacement have different costs? Use those costs in the recurrence.
  • Can the time be reduced when the strings are very different in length? A length difference greater than the allowed edit limit can rule out a result within that limit.
CodingMediumSprinklrSoftware Engineer

5. Maximum Subarray Sum After One Operation (LeetCode)

Model answer

The task

Choose a non-empty contiguous subarray and square one element in the array. Return the largest subarray sum achievable after that operation.

Key idea

Track the best subarray sum ending at the current position in two states: one where no element has been squared, and one where the operation has been used. Each state can either extend a previous subarray or start a new one.

Approach

  1. Initialize the no-operation state with the first value and the used-operation state with its square.
  2. For each next value, update the no-operation state by extending or starting a subarray.
  3. Update the used-operation state by either squaring the current value, extending a subarray where the operation was already used, or starting with the square.
  4. Keep the largest used-operation state seen; this ensures the returned subarray includes the operation.
from typing import List

class Solution:
    def maxSumAfterOperation(self, nums: List[int]) -> int:
        # Best subarray ending here without using the operation.
        no_operation = nums[0]

        # Best subarray ending here with the operation already used.
        used_operation = nums[0] * nums[0]

        answer = used_operation

        for value in nums[1:]:
            previous_no_operation = no_operation
            previous_used_operation = used_operation

            no_operation = max(value, previous_no_operation + value)

            used_operation = max(
                value * value,                    # Start here and square this value.
                previous_no_operation + value * value,  # Square this value after extending.
                previous_used_operation + value,  # Operation was already used.
            )

            answer = max(answer, used_operation)

        return answer

Complexity:

  • Time: O(n), since each array element is processed once.
  • Space: O(1), since only a fixed number of state values are stored.

Common follow-ups

  • What if the operation can be used at most once? Track an additional best state with no operation and take the maximum across both states.
  • What if the operation is multiplication by a constant instead of squaring? Replace value * value with the transformed value.
  • How would you return the subarray boundaries? Store each state’s starting index and update it whenever a state starts a new subarray.
CodingMediumSprinklrSoftware Engineer

6. Shortest Path with Alternating Colors (LeetCode)

Model answer

The task

Given a directed graph whose edges are red or blue, find the shortest path from node 0 to every node such that consecutive edges on a path have different colors. Return -1 for any node that cannot be reached this way.

Key idea

A node alone is not enough to describe the BFS state: which color was used to arrive determines which edges can be taken next. Track both the node and the last edge color, and explore only edges of the opposite color.

Approach

  1. Store outgoing neighbors separately for red and blue edges.
  2. Start BFS from node 0 with either color as the “last” color, both at distance zero. This allows the first edge to be either color.
  3. From each state, traverse only edges whose color differs from the last color.
  4. Record the shortest distance for each node-and-last-color state.
  5. For each node, return the smaller recorded distance, or -1 if neither state was reached.
from collections import deque
from typing import List

class Solution:
    def shortestAlternatingPaths(
        self,
        n: int,
        redEdges: List[List[int]],
        blueEdges: List[List[int]]
    ) -> List[int]:
        # Color 0 is red; color 1 is blue.
        graph = [[[] for _ in range(n)] for _ in range(2)]

        for source, target in redEdges:
            graph[0][source].append(target)
        for source, target in blueEdges:
            graph[1][source].append(target)

        # dist[node][color] is the shortest distance when arriving
        # at node with the given color as the last edge color.
        dist = [[-1, -1] for _ in range(n)]
        queue = deque()

        # Seed both last-color states so either color may be used first.
        for color in range(2):
            dist[0][color] = 0
            queue.append((0, color))

        while queue:
            node, last_color = queue.popleft()
            next_color = 1 - last_color

            for neighbor in graph[next_color][node]:
                if dist[neighbor][next_color] == -1:
                    dist[neighbor][next_color] = dist[node][last_color] + 1
                    queue.append((neighbor, next_color))

        answer = []
        for red_distance, blue_distance in dist:
            reachable = [d for d in (red_distance, blue_distance) if d != -1]
            answer.append(min(reachable) if reachable else -1)

        return answer

Complexity:

  • Time: O(n + r + b), where r and b are the numbers of red and blue edges.
  • Space: O(n + r + b) for the adjacency lists, distances, and BFS queue.

Common follow-ups

  • What if the graph is undirected? Add each edge in both directions, keeping its color.
  • Can paths start with a required color? Seed only the state that permits that first color.
  • How would you handle more than two colors? Track the last color and explore edges of every different color.
CodingMediumSprinklrSoftware Engineer

7. 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.
CodingMediumSprinklrSoftware Engineer

8. Minimum Time to Revert Word to Initial State I (LeetCode)

Model answer

The task

Each second, remove the first k characters of the word and append k arbitrary characters. Find the fewest seconds after which it is possible for the word to equal its original value again.

Key idea

After t seconds, the portion of the original word that remains is the suffix starting at index t * k. For the result to match the original, that suffix must equal the original word’s prefix of the same length.

Use the Z-function to check these prefix-suffix matches in linear time.

Approach

  1. Compute the Z-array, where z[i] is the length of the match between the word’s prefix and the substring starting at i.
  2. Check indices k, 2k, 3k, ... that are less than the word length.
  3. If z[i] >= n - i, the remaining original characters match the required prefix; return i // k.
  4. If no such index works, return the number of operations needed to remove all original characters.
class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)

        # Compute the Z-array in linear time.
        z = [0] * n
        left = right = 0

        for i in range(1, n):
            if i <= right:
                z[i] = min(right - i + 1, z[i - left])

            while i + z[i] < n and word[z[i]] == word[i + z[i]]:
                z[i] += 1

            if i + z[i] - 1 > right:
                left = i
                right = i + z[i] - 1

        # Find the earliest shift that leaves a matching suffix.
        shift = k
        while shift < n:
            if z[shift] >= n - shift:
                return shift // k
            shift += k

        # All original characters have been removed; the appended
        # characters can be chosen to recreate the word.
        return (n + k - 1) // k

Complexity:

  • Time: O(n), for the Z-array and the shift checks.
  • Space: O(n), for the Z-array.

Common follow-ups

  • What if k is larger than the word length? The answer is one operation.
  • Can rolling hash replace the Z-array? Yes; compare each relevant prefix and suffix, accounting for possible hash collisions.
  • What if the operation retains a different portion of the word? Re-derive which original characters remain after each operation, then check the corresponding match condition.
CodingMediumSprinklrSoftware Engineer

9. Longest Univalue Path (LeetCode)

Model answer

The task

Given a binary tree, find the length of its longest path whose nodes all have the same value. Length is measured in edges, and the path may pass through a node from one child subtree to the other.

Key idea

At each node, compute the longest same-value path that extends downward through exactly one child. A path that turns at the node can combine the valid downward lengths from both children; track the best such path globally.

Approach

  1. Keep a variable for the best path length found so far.
  2. Use depth-first search to compute each node’s longest valid downward extension.
  3. For each child, extend its result by one edge only when the child’s value matches the current node’s value.
  4. Update the global best using the sum of the left and right extensions.
  5. Return the global best after visiting the tree.
# TreeNode is assumed to have attributes val, left, and right.

class Solution:
    def longestUnivaluePath(self, root):
        best = 0

        def dfs(node):
            nonlocal best

            if node is None:
                return 0

            left_length = dfs(node.left)
            right_length = dfs(node.right)

            left_arm = 0
            if node.left is not None and node.left.val == node.val:
                left_arm = left_length + 1

            right_arm = 0
            if node.right is not None and node.right.val == node.val:
                right_arm = right_length + 1

            # A path can join the matching arms at this node.
            best = max(best, left_arm + right_arm)

            # Return only one arm: a parent can extend through one child.
            return max(left_arm, right_arm)

        dfs(root)
        return best

Complexity:

  • Time: O(n), visiting each node once.
  • Space: O(h), for the recursion stack, where h is the tree height.

Common follow-ups

  • What if the answer should count nodes instead of edges? Add one to the returned edge count when a nonempty path is found.
  • How does a skewed tree affect recursion? Its recursion depth is O(n); an iterative postorder traversal avoids recursion-limit issues.
  • What if each node has multiple children? Track the two longest matching downward arms to form the best path through each node.
CodingMediumSprinklrSoftware Engineer

10. LRU Cache (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

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

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

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

        self._make_most_recent(node)
        return node.value

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

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

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

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

Complexity:

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

Common follow-ups

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

11. Maximum Sum Circular Subarray (LeetCode)

Model answer

The task

Find the largest sum obtainable from a non-empty contiguous portion of an array, where the portion may wrap from the end back to the beginning.

Key idea

A best portion either does not wrap, so ordinary Kadane’s algorithm finds it, or wraps, so it consists of the whole array minus a minimum-sum contiguous portion. If every value is negative, use the ordinary maximum instead of subtracting the minimum, which would incorrectly produce zero.

Approach

  1. Scan once, tracking the running total, the best non-wrapping sum, and the smallest contiguous sum.
  2. Use Kadane’s recurrence for both the maximum and minimum.
  3. If the maximum sum is negative, return it; otherwise return the larger of the non-wrapping maximum and total minus the minimum.
from typing import List

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        total = 0

        max_ending = min_ending = 0
        max_sum = float("-inf")
        min_sum = float("inf")

        for value in nums:
            total += value

            # Best ordinary subarray ending at this position.
            max_ending = max(value, max_ending + value)
            max_sum = max(max_sum, max_ending)

            # Smallest subarray ending at this position.
            min_ending = min(value, min_ending + value)
            min_sum = min(min_sum, min_ending)

        # If all values are negative, wrapping would select an empty remainder.
        if max_sum < 0:
            return max_sum

        # A wrapping subarray is the array with a minimum-sum portion removed.
        return max(max_sum, total - min_sum)

Complexity:

  • Time: O(n), one pass through the array.
  • Space: O(1), only a fixed number of running values.

Common follow-ups

  • How would you return the actual subarray boundaries? Track the start and end indices during Kadane’s scans, including the removed minimum segment.
  • What if the array is updated repeatedly? A segment tree can maintain maximum and minimum subarray information for range updates or queries.
  • Can this be solved with a monotonic queue? Yes; prefix sums over a doubled array can find a maximum-length-limited circular segment, with a deque maintaining candidate prefix minima.
CodingMediumSprinklrSoftware Engineer

12. All Nodes Distance K in Binary Tree (LeetCode)

Model answer

The task

Return the values of all nodes exactly k edges from a given target node in a binary tree. The nodes may be reached through child links or by moving to a parent.

Key idea

Add parent links to the tree, turning it into a graph where each node has at most three neighbors. Then use breadth-first search from the target, stopping after k layers.

Approach

  1. Traverse the tree and record each node’s parent.
  2. Start BFS at the target, marking it visited.
  3. For each node, consider its left child, right child, and parent.
  4. After k layers, return the values in the queue.
from collections import deque
from typing import List

class Solution:
    def distanceK(self, root, target, k: int) -> List[int]:
        if root is None or k < 0:
            return []

        # Record each node's parent so the tree can be traversed in both directions.
        parent = {root: None}
        stack = [root]

        while stack:
            node = stack.pop()

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

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

        if target not in parent:
            return []

        queue = deque([target])
        visited = {target}
        distance = 0

        while queue and distance < k:
            for _ in range(len(queue)):
                node = queue.popleft()

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

            distance += 1

        return [node.val for node in queue] if distance == k else []

Complexity:

  • Time: O(n), to build parent links and perform BFS.
  • Space: O(n), for the parent map, queue, and visited set.

Common follow-ups

  • What if node values are duplicated? Identify nodes by object identity, not by value.
  • Can the tree remain unchanged? Yes; the parent map is stored separately.
  • What if many targets are queried? Build the parent map once and reuse it.
CodingMediumSprinklrSoftware Engineer

13. Sum of Subarray Minimums (LeetCode)

Model answer

The task

Find the sum of the minimum value in every contiguous subarray of arr, returning the result modulo \(10^9+7\).

Key idea

Count how many subarrays have each element as their minimum, then add that element’s contribution. A monotonic stack finds the nearest smaller boundaries in linear time; popping equal values gives duplicate minima a consistent tie-break.

Approach

  1. Scan left to right with a stack of indices whose values are increasing.
  2. When the current value is less than or equal to the stack top, pop that index. The current index is its next less-than-or-equal boundary.
  3. The new stack top, if present, is its previous strictly smaller boundary.
  4. Multiply the number of choices for the left and right endpoints by the popped value, and add that contribution.
  5. Use a final sentinel step to process every remaining index, then take the sum modulo \(10^9+7\).
from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        stack = []
        total = 0

        # The final iteration acts as a sentinel to flush the stack.
        for right in range(n + 1):
            while stack and (
                right == n or arr[stack[-1]] >= arr[right]
            ):
                index = stack.pop()
                left = stack[-1] if stack else -1

                # Choose a start after left and an end before right.
                count = (index - left) * (right - index)
                total += arr[index] * count

            if right < n:
                stack.append(right)

        return total % mod

Complexity:

  • Time: O(n), since each index is pushed and popped at most once.
  • Space: O(n) for the monotonic stack.

Common follow-ups

  • Why pop on equality? It assigns subarrays with tied minima to one occurrence consistently, preventing double counting.
  • What if the exact sum is needed? Return total without applying the modulus.
  • What if we need the minimum of each fixed-size sliding window? Use a monotonic deque, removing indices that leave the window or are dominated by a newer value.
CodingMediumSprinklrSoftware Engineer

14. Find K Pairs with Smallest Sums (LeetCode)

Model answer

The task

Given two ascending arrays and an integer k, return up to k pairs—one value from each array—with the smallest pair sums.

Key idea

Treat each value in the first array as the start of a sorted row of pairs, ordered by the second array. A min-heap can repeatedly select the smallest pair not yet returned and advance within that row.

Approach

  1. Return an empty list if either array is empty or k is nonpositive.
  2. Add the first pair from each of the first min(k, len(nums1)) rows to a min-heap.
  3. Pop the smallest-sum pair and add its values to the result.
  4. If that pair has a next value in nums2, push the next pair from the same row.
  5. Stop after returning k pairs or when the heap is empty.
import heapq
from typing import List

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

        # Each heap entry is (pair sum, index in nums1, index in nums2).
        row_count = min(k, len(nums1))
        heap = [
            (nums1[i] + nums2[0], i, 0)
            for i in range(row_count)
        ]
        heapq.heapify(heap)

        pairs = []
        while heap and len(pairs) < k:
            _, i, j = heapq.heappop(heap)
            pairs.append([nums1[i], nums2[j]])

            next_j = j + 1
            if next_j < len(nums2):
                heapq.heappush(
                    heap,
                    (nums1[i] + nums2[next_j], i, next_j),
                )

        return pairs

Complexity:

  • Time: O(r + t log r), where r = min(k, len(nums1)) and t is the number of pairs returned.
  • Space: O(r) for the heap, excluding the output.

Common follow-ups

  • What if the arrays are not sorted? Sort them first, accounting for the sorting cost.
  • Why initialize only k rows? No pair from a later row can rank ahead of all k first pairs from earlier rows, since the arrays are sorted.
  • How would you handle a very large k? The heap approach still avoids storing all pair combinations; it stores at most one candidate per row.
CodingMediumSprinklrSoftware Engineer

15. Subarray Sum Equals K (LeetCode)

Model answer

The task

Count the contiguous subarrays whose elements sum to a given target k. The array may contain negative numbers, so subarray sums do not necessarily grow as the subarray gets longer.

Key idea

For each position, let prefix be the sum of all elements seen so far. A subarray ending here sums to k exactly when an earlier prefix sum equals prefix - k. Keep counts of earlier prefix sums in a hash table.

Approach

  1. Start with prefix sum 0 occurring once, representing the empty prefix.
  2. Scan the array and add each value to the running prefix sum.
  3. Add the number of times prefix - k has appeared to the answer.
  4. Record the current prefix sum for future positions.
from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Counts of prefix sums seen so far.
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1

        prefix_sum = 0
        subarray_count = 0

        for value in nums:
            prefix_sum += value

            # Each matching earlier prefix identifies one subarray
            # ending at the current position.
            subarray_count += prefix_counts[prefix_sum - k]

            # Record this prefix only after counting, so the match
            # refers to an earlier position.
            prefix_counts[prefix_sum] += 1

        return subarray_count

Complexity: Time: O(n), where n is the number of elements; each element is processed once.

Complexity: Space: O(n) in the worst case, for the distinct prefix sums stored.

Common follow-ups

  • Why not use a sliding window? Negative values break the monotonic behavior of window sums that sliding-window techniques rely on.
  • What if all values are nonnegative? A sliding window can be used, though prefix sums still provide a straightforward solution.
  • Can this count subarrays for many target values? The prefix-frequency scan is target-specific; repeated queries may need a different strategy depending on the input size and query count.
CodingMediumSprinklrSoftware Engineer

16. House Robber III (LeetCode)

Model answer

The task

Given a binary tree where each node holds a nonnegative amount, choose nodes to maximize the total without choosing both a node and its parent.

Key idea

For each subtree, track two values: the best total if its root is robbed, and the best total if its root is skipped. This lets each parent combine its children’s results without needing to revisit nodes.

Approach

  1. Use depth-first search to compute the two values for each node.
  2. If the node is robbed, its children must be skipped.
  3. If the node is skipped, each child can be robbed or skipped, whichever yields more.
  4. Return the larger of the two values for the tree’s root.
# LeetCode provides the TreeNode class.

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
            # Return (best total if robbed, best total if skipped).
            if node is None:
                return 0, 0

            left_robbed, left_skipped = dfs(node.left)
            right_robbed, right_skipped = dfs(node.right)

            # Rob this node only if both children are skipped.
            robbed = node.val + left_skipped + right_skipped

            # If skipping this node, choose the best option per child.
            skipped = (
                max(left_robbed, left_skipped)
                + max(right_robbed, right_skipped)
            )

            return robbed, skipped

        return max(dfs(root))

Complexity:

  • Time: O(n), where n is the number of nodes, since each node is processed once.
  • Space: O(h), for the recursion stack, where h is the tree height.

Common follow-ups

  • What if the tree is highly unbalanced? The recursion stack can grow to O(n); an iterative postorder traversal avoids recursion-depth issues.
  • What if some node values are negative? The same recurrence works; skipping a negative-valued node can be better than robbing it.
  • Can the result be computed with less memory? The two values per node are already constant-size; the recursion stack is the main extra space.
CodingMediumSprinklrSoftware Engineer

17. 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.
CodingMediumSprinklrSoftware Engineer

18. 132 Pattern (LeetCode)

Model answer

The task

Determine whether an integer array contains three elements in order whose values form a “132” pattern: the first is smallest, the second is largest, and the third lies between them.

Key idea

Scan from right to left, treating each element as a possible middle (largest) value. A decreasing stack tracks candidates for the final value, while second stores the largest valid final value found so far.

Approach

  1. Initialize an empty stack and set second to negative infinity.
  2. Visit each value from right to left.
  3. If the value is less than second, it can be the first element of a valid pattern.
  4. Otherwise, pop stack values smaller than the current value. Each popped value can serve as the final element, so update second with it.
  5. Push the current value and continue. If no match is found, return False.
class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        stack: list[int] = []
        second = float("-inf")

        # Scan right to left: stack values are candidates for the third element.
        for value in reversed(nums):
            if value < second:
                return True

            # The current value can be the middle element.
            # Popped values are smaller candidates to its right.
            while stack and stack[-1] < value:
                second = stack.pop()

            stack.append(value)

        return False

Complexity:

  • Time: O(n), since each value is pushed and popped at most once.
  • Space: O(n), for the monotonic stack.

Common follow-ups

  • Can this be solved with binary search? Yes; maintain candidates while scanning and use an ordered structure to find a value in the required range.
  • What if the pattern must be strictly increasing/decreasing as specified? Use strict comparisons, as above; duplicates do not form a valid pattern.
  • How would you return the indices, not just whether a pattern exists? Store indices alongside stack values and track the indices associated with second.
CodingMediumSprinklrSoftware Engineer

19. Number of Same-End Substrings (LeetCode)

Model answer

The task

Given a string and multiple inclusive index ranges, count for each range how many of its substrings begin and end with the same character.

Key idea

For any one character occurring k times in a range, it contributes k * (k + 1) // 2 substrings: each occurrence can pair with itself or a later occurrence. Prefix character counts let us find each character’s frequency in a range quickly.

Approach

  1. Build prefix counts for each lowercase letter, where each prefix includes the characters before its ending index.
  2. For each query [left, right], subtract the prefix counts at left from those at right + 1.
  3. For each letter, add count * (count + 1) // 2 to the answer.
  4. Return the answers in query order.
from typing import List

class Solution:
    def sameEndSubstringCount(
        self, s: str, queries: List[List[int]]
    ) -> List[int]:
        n = len(s)
        alphabet_size = 26

        # prefix[i][c] counts letter c in s[:i].
        prefix = [[0] * alphabet_size for _ in range(n + 1)]

        for i, char in enumerate(s):
            prefix[i + 1] = prefix[i].copy()
            prefix[i + 1][ord(char) - ord("a")] += 1

        answers = []
        for left, right in queries:
            total = 0
            for letter in range(alphabet_size):
                count = prefix[right + 1][letter] - prefix[left][letter]
                total += count * (count + 1) // 2
            answers.append(total)

        return answers

Complexity:

  • Time: O(26n + 26q), for building prefix counts and answering q queries.
  • Space: O(26n), for the prefix-count table.

Common follow-ups

  • What if the alphabet is larger? Use a mapping of characters to prefix counts, or track only characters present in the string.
  • Can memory be reduced? Store prefix counts only for relevant characters; the straightforward table uses O(26n) space.
  • What if queries use half-open ranges? Use prefix[right] - prefix[left] for [left, right).
CodingMediumSprinklrSoftware Engineer

20. 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.

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