Directi interview questions & answers

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

CodingMediumDirectiSoftware Engineer

1. Min Cost to Connect All Points (LeetCode)

Model answer

The task

Given points in a plane, connect them so every point is reachable from every other point, minimizing the total Manhattan distance of the chosen connections.

Key idea

The points form a complete weighted graph, but explicitly building all edges is unnecessary. Prim’s algorithm can grow a minimum spanning tree by tracking each unconnected point’s cheapest connection to the current tree.

Approach

  1. Start the tree at point 0 with cost 0.
  2. Keep the cheapest known connection cost for each point and mark points as visited when added.
  3. Repeatedly add the unvisited point with the smallest connection cost.
  4. Add that cost to the answer, then update the remaining costs using Manhattan distance from the newly added point.
  5. Return the sum after all points have been added.
from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 1:
            return 0

        # best[i] is the cheapest edge currently known from the tree to i.
        best = [float("inf")] * n
        best[0] = 0
        visited = [False] * n
        total_cost = 0

        for _ in range(n):
            # Select the unvisited point with the cheapest connection.
            current = -1
            for i in range(n):
                if not visited[i] and (
                    current == -1 or best[i] < best[current]
                ):
                    current = i

            visited[current] = True
            total_cost += best[current]

            x1, y1 = points[current]
            for i in range(n):
                if not visited[i]:
                    x2, y2 = points[i]
                    distance = abs(x1 - x2) + abs(y1 - y2)
                    best[i] = min(best[i], distance)

        return total_cost

Complexity:

  • Time: O(n²), from selecting the next point and updating distances for each point.
  • Space: O(n), for the connection costs and visited flags.

Common follow-ups

  • Can Kruskal’s algorithm solve it? Yes; generate all point pairs, sort by distance, and use Union-Find, taking O(n² log n) time and O(n²) space.
  • Can Prim’s algorithm use a heap? Yes, but this dense graph still has O(n²) possible edges; the array-based version is simpler and avoids storing them.
  • What if there is only one point? No connection is needed, so the cost is 0.
  • What if distances use another metric? Replace the Manhattan distance calculation, provided the edge weights remain well-defined.
CodingMediumDirectiSoftware Engineer

2. Minimum Cost to Buy Apples (LeetCode)

Model answer

The task

For each city, find the cheapest way to obtain an apple and bring it there, choosing any city as the place to buy it. Roads are bidirectional, and transporting an apple makes the road cost k + 1 times its listed cost.

Key idea

Run Dijkstra from each destination using these adjusted road costs. For each possible purchase city, add its apple price to the shortest travel cost; the minimum is that destination’s answer.

Approach

  1. Build an undirected adjacency list, converting the road endpoints to zero-based indices.
  2. Multiply each road cost by k + 1.
  3. For each city, run Dijkstra to find the cheapest adjusted travel cost to every other city.
  4. Add each reachable city’s apple price and keep the minimum.
from typing import List
import heapq

class Solution:
    def minCost(
        self, n: int, roads: List[List[int]], appleCost: List[int], k: int
    ) -> List[int]:
        graph = [[] for _ in range(n)]

        for a, b, cost in roads:
            a -= 1
            b -= 1
            adjusted_cost = cost * (k + 1)
            graph[a].append((b, adjusted_cost))
            graph[b].append((a, adjusted_cost))

        answers = []

        for start in range(n):
            distances = [float("inf")] * n
            distances[start] = 0
            heap = [(0, start)]

            while heap:
                distance, city = heapq.heappop(heap)
                if distance != distances[city]:
                    continue

                for neighbor, road_cost in graph[city]:
                    candidate = distance + road_cost
                    if candidate < distances[neighbor]:
                        distances[neighbor] = candidate
                        heapq.heappush(heap, (candidate, neighbor))

            answers.append(
                min(appleCost[city] + distances[city] for city in range(n))
            )

        return answers

Complexity:

  • Time: O(n(m + n) log n), for Dijkstra from each city.
  • Space: O(n + m), for the graph, distances, and heap.

Common follow-ups

  • What if all road costs are equal? Use BFS for each source instead of Dijkstra.
  • Can the algorithm be improved for very large graphs? Discuss exploiting graph structure or using specialized all-pairs shortest-path techniques.
  • What if roads are one-way? Store each road in only its directed orientation.
CodingMediumDirectiSoftware Engineer

3. Largest Submatrix With Rearrangements (LeetCode)

Model answer

The task

Given a binary matrix, choose a column order that makes some all-ones rectangle as large as possible. Return the maximum possible area.

Key idea

For each cell, count consecutive ones ending at that row in its column. Sorting these heights from largest to smallest reveals the best rectangle ending at that row: the first k heights support a rectangle of height equal to the kth height and width k.

Approach

  1. Track each column’s consecutive-one height as rows are processed.
  2. Reset a column’s height to zero when its current cell is zero; otherwise increment it.
  3. Sort a copy of the heights in descending order for the current row.
  4. For each sorted height at index i, consider area height * (i + 1).
  5. Keep the largest area across all rows.
from typing import List

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

        columns = len(matrix[0])
        heights = [0] * columns
        best_area = 0

        for row in matrix:
            for col, value in enumerate(row):
                heights[col] = heights[col] + 1 if value == 1 else 0

            # Sorting a copy keeps heights aligned with their original columns
            # for processing the next row.
            sorted_heights = sorted(heights, reverse=True)

            for index, height in enumerate(sorted_heights):
                best_area = max(best_area, height * (index + 1))

        return best_area

Complexity:

  • Time: O(m n log n), sorting up to n heights for each of m rows.
  • Space: O(n), for the heights and sorted copy.

Common follow-ups

  • What if columns cannot be rearranged? Use each row’s heights with a histogram maximum-rectangle algorithm.
  • What if rows may also be rearranged? The consecutive-height method no longer directly applies; the permitted rearrangements determine a different problem.
  • Can the method stop early? Not generally; later rows can create taller rectangles or new best areas.
CodingMediumDirectiSoftware Engineer

4. Find the Winner of an Array Game (LeetCode)

Model answer

The task

Given an array of distinct values and a target number of consecutive wins, determine which value becomes the winner. A round compares the current front two values; the winner stays at the front.

Key idea

There’s no need to simulate moving values through the array. Scan once, keeping the current champion and its consecutive-win count. If the scan ends before anyone reaches the target, the champion is the maximum value seen, which will win thereafter.

Approach

  1. Start with the first value as champion and zero wins.
  2. Compare each subsequent value with the champion.
  3. If the new value is larger, make it champion and set its win count to one.
  4. Otherwise, increment the champion’s win count.
  5. Return as soon as the count reaches k; if the scan ends, return the champion.
from typing import List

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        champion = arr[0]
        consecutive_wins = 0

        for value in arr[1:]:
            if value > champion:
                champion = value
                consecutive_wins = 1
            else:
                consecutive_wins += 1

            if consecutive_wins == k:
                return champion

        # If no champion reached k wins, the maximum encountered wins next.
        return champion

Complexity:

  • Time: O(n), where n is the array length; each value is checked at most once.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if k is very large? The scan still works; once all values are visited, the maximum is the eventual winner.
  • Can the array be left unchanged? Yes. The algorithm only reads values and tracks the champion.
  • What if values are not distinct? Define tie handling explicitly; the code treats a tie as a win for the current champion.
CodingMediumDirectiSoftware Engineer

5. Number of Sub-arrays With Odd Sum (LeetCode)

Model answer

The task

Count the contiguous subarrays whose elements add up to an odd number. Return the count modulo \(10^9 + 7\).

Key idea

A subarray sum is odd exactly when its two prefix sums have different parity. As we scan the array, keep counts of the even and odd prefix sums seen so far; each new prefix pairs with all earlier prefixes of the opposite parity.

Approach

  1. Start with an even prefix count of one, representing the empty prefix.
  2. Track the parity of the running sum as each value is processed.
  3. Add the count of previously seen prefixes with opposite parity to the answer.
  4. Record the current prefix parity and return the answer modulo \(10^9 + 7\).
class Solution:
    def numOfSubarrays(self, arr: list[int]) -> int:
        mod = 10**9 + 7

        # The empty prefix has an even sum.
        even_prefixes = 1
        odd_prefixes = 0
        parity = 0
        answer = 0

        for value in arr:
            parity ^= value & 1

            if parity == 0:
                answer += odd_prefixes
                even_prefixes += 1
            else:
                answer += even_prefixes
                odd_prefixes += 1

        return answer % mod

Complexity:

  • Time: O(n), with one pass through the array.
  • Space: O(1), using a fixed number of counters.

Common follow-ups

  • What if the target parity were even? Count pairs of prefix sums with the same parity instead.
  • What if the target sum were a specific value rather than a parity? Track prefix-sum frequencies and count earlier sums equal to the current sum minus the target.
  • Can the array contain negative values? Yes; parity still works using each value modulo 2.
CodingHardDirectiSoftware Engineer

6. Find Longest Awesome Substring (LeetCode)

Model answer

The task

Given a string of decimal digits, find the length of its longest contiguous substring whose digits can be rearranged into a palindrome.

Key idea

A substring can be rearranged into a palindrome when at most one digit occurs an odd number of times. Track the parity of each digit’s count using a 10-bit mask for every prefix.

Approach

  1. Start with mask 0 before the string, at index -1.
  2. Scan the string, flipping the bit for each digit.
  3. For each prefix mask, check whether it has appeared before; equal masks indicate all counts in between are even.
  4. Also check masks differing by one bit; those substrings have exactly one odd count.
  5. Record each mask’s first index and update the longest valid length.
class Solution:
    def longestAwesome(self, s: str) -> int:
        # The empty prefix has even counts for every digit.
        first_index = {0: -1}
        mask = 0
        longest = 0

        for index, char in enumerate(s):
            digit = ord(char) - ord("0")
            mask ^= 1 << digit

            # Equal prefix parities mean every digit count is even.
            if mask in first_index:
                longest = max(longest, index - first_index[mask])

            # A single differing bit permits one odd digit count.
            for bit in range(10):
                candidate = mask ^ (1 << bit)
                if candidate in first_index:
                    longest = max(
                        longest,
                        index - first_index[candidate],
                    )

            # Keep the earliest prefix to maximize substring length.
            if mask not in first_index:
                first_index[mask] = index

        return longest

Complexity:

  • Time: O(n), checking 10 possible one-bit differences per character.
  • Space: O(1), at most 2¹⁰ distinct parity masks.

Common follow-ups

  • What if the alphabet has k symbols? Use a k-bit mask and check k one-bit differences per position.
  • What if up to r counts may be odd? Check masks differing in up to r bits; this is practical when r is small.
  • Can the substring itself be returned? Store the start and end indices whenever the best length increases.
CodingHardDirectiSoftware Engineer

7. Maximum XOR of Two Non-Overlapping Subtrees (LeetCode)

Model answer

The task

The title doesn’t specify what value is assigned to a subtree. The general problem is to choose two disjoint rooted subtrees whose integer scores have the largest XOR.

Key idea

In a depth-first preorder, each subtree occupies a contiguous interval. Process subtree intervals from left to right; a previous interval is disjoint from the current one exactly when it has ended before the current interval starts. A binary trie finds the best XOR among those eligible scores.

Approach

  1. Assume the tree and each subtree’s score are supplied; the score might be a sum, XOR, or another defined value.
  2. Compute preorder entry and exclusive exit positions for every node.
  3. Keep prior intervals in a min-heap by exit position.
  4. Before querying a node, move all ended intervals into a binary trie.
  5. Query the trie for the best XOR, then add the current interval to the heap.
import heapq
from typing import List, Optional

class BinaryTrie:
    """Binary trie for nonnegative integers of a fixed bit width."""

    def __init__(self, bit_count: int) -> None:
        self.bit_count = bit_count
        self.root = [None, None]

    def insert(self, value: int) -> None:
        node = self.root
        for bit in range(self.bit_count - 1, -1, -1):
            branch = (value >> bit) & 1
            if node[branch] is None:
                node[branch] = [None, None]
            node = node[branch]

    def best_xor(self, value: int) -> int:
        """Return the largest XOR with any value already in the trie."""
        node = self.root
        result = 0
        for bit in range(self.bit_count - 1, -1, -1):
            branch = (value >> bit) & 1
            preferred = 1 - branch
            if node[preferred] is not None:
                result |= 1 << bit
                node = node[preferred]
            else:
                node = node[branch]
        return result

def max_xor_disjoint_subtrees(
    children: List[List[int]],
    score: List[int],
    root: int = 0,
) -> int:
    """Return the maximum XOR of two disjoint subtree scores, or -1 if none."""
    n = len(children)
    if n < 2:
        return -1

    # Iterative DFS computes preorder positions and exclusive subtree ends.
    tin = [-1] * n
    tout = [-1] * n
    order = []
    stack = [(root, False)]
    timer = 0

    while stack:
        node, exiting = stack.pop()
        if exiting:
            tout[node] = timer
            continue

        tin[node] = timer
        timer += 1
        order.append(node)
        stack.append((node, True))
        for child in reversed(children[node]):
            stack.append((child, False))

    max_score = max(score)
    bit_count = max(1, max_score.bit_length())
    trie = BinaryTrie(bit_count)
    ended = []  # (exclusive end position, subtree score)
    answer = -1

    for node in order:
        while ended and ended[0][0] <= tin[node]:
            _, previous_score = heapq.heappop(ended)
            trie.insert(previous_score)

        if trie.root[0] is not None or trie.root[1] is not None:
            answer = max(answer, trie.best_xor(score[node]))

        heapq.heappush(ended, (tout[node], score[node]))

    return answer

Complexity:

  • Time: O(n(B + log n)), for trie queries and heap operations; B is the score bit width.
  • Space: O(nB), for the trie, heap, and traversal data.

Common follow-ups

  • How are subtree scores computed? Use the problem’s specified aggregate in a postorder traversal.
  • What if the input is a forest? Start a traversal from each root, assigning non-overlapping preorder ranges.
  • What if scores can be negative? Define the intended signed or fixed-width XOR semantics before choosing the trie representation.
CodingHardDirectiSoftware Engineer

8. Difference Between Maximum and Minimum Price Sum (LeetCode)

Model answer

The task

Given a tree with a price at each node, find the largest difference between the prices of two trips that start at the same node. A trip’s price is the sum of the prices visited after its starting node.

Key idea

For a fixed start, the cheapest trip contributes zero, so we need the greatest path sum when one endpoint’s price is omitted. Root the tree arbitrarily and use DP to consider paths going down one branch or joining two branches.

For each node, track the best downward path including its endpoint, and the best downward path with its endpoint omitted. Combining these states from different child subtrees considers paths whose highest point is the current node.

Approach

  1. Build the adjacency list and create a parent-before-child traversal order from node 0.
  2. Process nodes in reverse order so each child’s DP values are ready.
  3. For each child, use its two states as the contributions from a path branch.
  4. Update the answer for paths using one branch, then combine each branch with a previously processed branch.
  5. Store the best downward states for the current node.
class Solution:
    def maxOutput(self, n: int, edges: list[list[int]], price: list[int]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        # Build a traversal order and parent links iteratively.
        parent = [-1] * n
        order = [0]
        for node in order:
            for nei in graph[node]:
                if nei == parent[node]:
                    continue
                parent[nei] = node
                order.append(nei)

        # full[u]: best downward path starting at u, including its endpoint.
        # trim[u]: best downward path from u with the endpoint omitted.
        full = [0] * n
        trim = [0] * n
        answer = 0

        for u in reversed(order):
            best_trim_branch = None
            best_full_branch = None
            best_child_full = 0
            best_child_trim = None

            for v in graph[u]:
                if parent[v] != u:
                    continue

                best_child_full = max(best_child_full, full[v])

                # A path from a descendant in v's subtree to u,
                # omitting the descendant's price.
                answer = max(answer, trim[v] + price[u])

                # A path from u down into v's subtree omits u's price.
                answer = max(answer, full[v])

                # Join this branch to an already-seen, distinct branch.
                if best_trim_branch is not None:
                    answer = max(
                        answer,
                        best_trim_branch + price[u] + full[v]
                    )
                if best_full_branch is not None:
                    answer = max(
                        answer,
                        trim[v] + price[u] + best_full_branch
                    )

                best_trim_branch = (
                    trim[v] if best_trim_branch is None
                    else max(best_trim_branch, trim[v])
                )
                best_full_branch = (
                    full[v] if best_full_branch is None
                    else max(best_full_branch, full[v])
                )
                best_child_trim = (
                    trim[v] if best_child_trim is None
                    else max(best_child_trim, trim[v])
                )

            full[u] = price[u] + best_child_full

            # A downward path with its endpoint omitted needs at least
            # one child; otherwise the only possible contribution is zero.
            trim[u] = (
                price[u] + best_child_trim
                if best_child_trim is not None
                else 0
            )

        return answer

Complexity:

  • Time: O(n), since each node and edge is processed a constant number of times.
  • Space: O(n), for the adjacency list, traversal order, and DP arrays.

Common follow-ups

  • What if the tree is very deep? Use iterative traversal, as above, to avoid recursion-depth limits.
  • Why can the tree be rooted arbitrarily? Every path has a highest node in any chosen rooting, so it is considered at that node.
  • What if only paths with distinct endpoints count? Keep the single-branch cases, which represent paths with at least one edge; for a one-node tree the answer remains zero.

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