Akuna Capital interview questions & answers

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

CodingEasyAkuna CapitalSoftware Engineer

1. Increasing Decreasing String (LeetCode)

Model answer

The task

Reorder the characters by repeatedly taking the smallest remaining character, then the largest remaining character, alternating those two passes until all characters are used.

Key idea

Count each lowercase letter, then scan the alphabet forward and backward, taking each available letter at most once per pass. A fixed-size frequency table avoids repeatedly sorting the remaining characters.

Approach

  1. Count the occurrences of each letter.
  2. While letters remain, scan from a to z, appending and decrementing each available count.
  3. Scan from z to a the same way.
  4. Stop early if the forward scan used the final letter.
class Solution:
    def sortString(self, s: str) -> str:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord("a")] += 1

        result = []
        remaining = len(s)

        while remaining:
            # Take available letters in increasing order.
            for i in range(26):
                if counts[i]:
                    result.append(chr(ord("a") + i))
                    counts[i] -= 1
                    remaining -= 1

            # The forward pass may have used the final letter.
            if remaining == 0:
                break

            # Take available letters in decreasing order.
            for i in range(25, -1, -1):
                if counts[i]:
                    result.append(chr(ord("a") + i))
                    counts[i] -= 1
                    remaining -= 1

        return "".join(result)

Complexity:

  • Time: O(n), since each pass scans a fixed 26-letter alphabet.
  • Space: O(1) auxiliary space for the frequency table, excluding the O(n) result.

Common follow-ups

  • What if the input includes arbitrary Unicode characters? Use a dictionary of character counts and scan sorted distinct keys in each direction.
  • Can the result be built without storing a frequency table? Yes, but repeatedly searching and removing characters is generally less efficient.
  • What if the alphabet is much larger? A frequency map still counts efficiently, but ordering its distinct keys may add sorting cost.
CodingMediumAkuna CapitalSoftware Engineer

2. Network Delay Time (LeetCode)

Model answer

The task

Given directed, weighted connections between numbered nodes and a starting node, find the time it takes for a signal to reach every node. Return the longest shortest-path distance from the start, or -1 if any node cannot be reached.

Key idea

Use Dijkstra’s algorithm because edge weights are nonnegative. A min-heap processes nodes in order of their currently known travel time, so each node’s shortest distance can be finalized efficiently.

Approach

  1. Build an adjacency list from the connections.
  2. Initialize all distances as unknown, except the start node at distance 0.
  3. Repeatedly pop the smallest tentative distance from a min-heap.
  4. Skip entries that are outdated; otherwise, relax each outgoing edge and push any improved distance.
  5. If any node remains unreachable, return -1; otherwise return the largest distance.
import heapq
from typing import List

class Solution:
    def networkDelayTime(
        self, times: List[List[int]], n: int, k: int
    ) -> int:
        # Each edge is represented as (neighbor, travel_time).
        graph = [[] for _ in range(n + 1)]
        for source, target, weight in times:
            graph[source].append((target, weight))

        distances = [float("inf")] * (n + 1)
        distances[k] = 0
        min_heap = [(0, k)]

        while min_heap:
            elapsed, node = heapq.heappop(min_heap)

            # Ignore a heap entry if a better route was found later.
            if elapsed > distances[node]:
                continue

            for neighbor, weight in graph[node]:
                new_elapsed = elapsed + weight
                if new_elapsed < distances[neighbor]:
                    distances[neighbor] = new_elapsed
                    heapq.heappush(min_heap, (new_elapsed, neighbor))

        reachable_distances = distances[1:]
        if any(distance == float("inf") for distance in reachable_distances):
            return -1

        return max(reachable_distances)

Complexity:

  • Time: O((V + E) log V), where V is the number of nodes and E the number of connections.
  • Space: O(V + E) for the adjacency list, distances, and heap.

Common follow-ups

  • What if edge weights can be negative? Dijkstra is not suitable; use Bellman–Ford and detect reachable negative cycles.
  • What if only one destination’s travel time is needed? Stop when that destination is removed from the heap with its current shortest distance.
  • What if many starting nodes are queried? Consider repeated Dijkstra runs, or an all-pairs shortest-path algorithm if the graph is small.
CodingMediumAkuna CapitalSoftware Engineer

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

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

            if root_a == root_b:
                return

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

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

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

        return components - 1

Complexity:

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

Common follow-ups

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

4. Map Sum Pairs (LeetCode)

Model answer

The task

Design a data structure that stores string-to-integer values. It must support inserting or updating a key and returning the sum of all values whose keys begin with a given prefix.

Key idea

Keep the current value for each complete key in a hash map. In a trie, store at each node the total value of all keys passing through it; when a key is updated, adjust each node on its path by only the change in value.

Approach

  1. Initialize a hash map for key values and a trie root.
  2. On insertion, compute the difference between the new value and the key’s previous value.
  3. Add that difference to the root and every trie node along the key’s path, creating missing nodes.
  4. To sum a prefix, follow its characters in the trie.
  5. Return that node’s stored total, or zero if the path does not exist.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.total = 0

class MapSum:
    def __init__(self):
        self.values = {}
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        # Adjust aggregates by the change, so reinserting a key replaces its value.
        delta = val - self.values.get(key, 0)
        self.values[key] = val

        node = self.root
        node.total += delta

        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.total += delta

    def sum(self, prefix: str) -> int:
        node = self.root

        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]

        return node.total

Complexity:

  • Time: O(L) for insertion, where L is the key length; O(P) for a prefix query, where P is the prefix length.
  • Space: O(N), for trie nodes across all stored keys and the key-value map.

Common follow-ups

  • How would you support deleting a key? Subtract its stored value along the trie path, then remove it from the map.
  • How would you reclaim unused trie nodes? Prune nodes bottom-up when they have no children and a zero aggregate.
  • What if values can be negative? The same delta-based aggregates work without changes.
CodingMediumAkuna CapitalSoftware Engineer

5. Can Make Palindrome from Substring (LeetCode)

Model answer

The task

For each query, determine whether the characters in the specified substring can be rearranged and changed in at most k positions to form a palindrome.

Key idea

A substring’s letter frequencies are summarized for this purpose by which counts are odd. Prefix bitmasks let us find that set of letters for any substring with one XOR. Each pair of odd counts needs one replacement to make both counts even, so the minimum replacements is half the number of odd counts, rounded down.

Approach

  1. Build a prefix bitmask where bit c records the parity of character c’s count so far.
  2. For each inclusive range [left, right], XOR its two prefix masks to get the substring’s odd-count letters.
  3. Count the set bits and check whether half that count, rounded down, is at most k.
  4. Return the result for every query.
from typing import List

class Solution:
    def canMakePaliQueries(
        self, s: str, queries: List[List[int]]
    ) -> List[bool]:
        # prefix[i] stores character-count parities for s[:i].
        prefix = [0]
        mask = 0

        for char in s:
            mask ^= 1 << (ord(char) - ord("a"))
            prefix.append(mask)

        answers = []
        for left, right, k in queries:
            odd_mask = prefix[right + 1] ^ prefix[left]
            odd_count = odd_mask.bit_count()

            # Each replacement can resolve two odd-count letters.
            answers.append(odd_count // 2 <= k)

        return answers

Complexity:

  • Time: O(n + q), for the prefix masks and one constant-time parity check per query.
  • Space: O(n), for the prefix masks.

Common follow-ups

  • What if queries use half-open ranges? Use prefix[right] ^ prefix[left].
  • What if the alphabet is larger? Assign one bit per possible character, or use parity arrays if a compact bitmask is impractical.
  • Can queries be answered without storing every prefix mask? Not generally in constant time; storing them supports fast arbitrary range queries.
CodingMediumAkuna CapitalSoftware Engineer

6. Delete and Earn (LeetCode)

Model answer

The task

Choose values to earn points, where taking a value earns its value once for every occurrence and removes all occurrences of the neighboring values. Return the maximum points possible.

Key idea

Combine equal values into one total reward: taking value x earns x * count[x]. Values x and x + 1 then conflict, so the problem becomes the same as choosing non-adjacent entries in a sequence.

Approach

  1. Count how many times each value occurs.
  2. Build a reward for each possible value from zero through the maximum.
  3. Iterate through those rewards, tracking the best total using values up to the previous and second-previous positions.
  4. At each value, either skip it or take its reward and add the best total from two positions earlier.
from collections import Counter
from typing import List

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

        counts = Counter(nums)
        max_value = max(nums)

        # best_two_back and best_one_back track the best totals
        # before the current value and at the previous value.
        best_two_back = 0
        best_one_back = 0

        for value in range(max_value + 1):
            take = best_two_back + value * counts[value]
            skip = best_one_back
            current_best = max(take, skip)

            best_two_back = best_one_back
            best_one_back = current_best

        return best_one_back

Complexity:

  • Time: O(n + M), for counting the input and scanning values up to maximum value M.
  • Space: O(n + M), for the frequency map and the value range.

Common follow-ups

  • What if values are very large and sparse? Sort the distinct values and apply the recurrence only to them, accounting for gaps.
  • Can the DP use less space? Yes; the solution already keeps only two previous totals.
  • What if taking a value conflicts with values within distance k? Track the best total from k + 1 positions earlier.
CodingMediumAkuna CapitalSoftware Engineer

7. Shortest and Lexicographically Smallest Beautiful String (LeetCode)

Model answer

The task

Given a binary string and a positive integer k, return the shortest substring containing exactly k ones. If several shortest substrings exist, return the lexicographically smallest; return an empty string if none exists.

Key idea

Record the positions of all ones. Any shortest valid substring must begin and end at ones, and its ones must be a group of k consecutive ones in that position list.

Approach

  1. Collect the indices of every '1'.
  2. If there are fewer than k, return an empty string.
  3. For each group of k consecutive ones, use its first and last positions as substring boundaries.
  4. Keep the shortest candidate; break equal-length ties by lexicographic order.
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # A shortest valid substring starts and ends at a one.
        ones = [i for i, ch in enumerate(s) if ch == "1"]

        if len(ones) < k:
            return ""

        best = ""

        # Each window of k consecutive ones defines a tight candidate.
        for i in range(len(ones) - k + 1):
            left = ones[i]
            right = ones[i + k - 1]
            candidate = s[left:right + 1]

            if (
                not best
                or len(candidate) < len(best)
                or (len(candidate) == len(best) and candidate < best)
            ):
                best = candidate

        return best

Complexity:

  • Time: O(n²) in the worst case, due to comparing candidate substrings.
  • Space: O(n) for the recorded one positions.

Common follow-ups

  • What if no substring contains k ones? Return the empty string.
  • Why only consider consecutive groups of ones? Any valid substring’s ones form such a group; extra boundary characters can only make it longer.
  • How would you handle many queries with different k values? Reuse the recorded one positions, then scan the relevant groups for each query.
CodingMediumAkuna CapitalSoftware Engineer

8. Maximum Star Sum of a Graph (LeetCode)

Model answer

The task

Given vertex values and undirected edges, find the greatest sum of a center vertex and at most k of its neighbors. A star may contain just its center.

Key idea

For any chosen center, negative-valued neighbors can only reduce the sum, so ignore them. The best neighbors are the up to k positive values that are largest.

Approach

  1. Build an adjacency list for the undirected graph.
  2. For each vertex, collect the positive values of its neighbors.
  3. Sort those values in descending order.
  4. Add the center’s value to the first k neighbor values.
  5. Track the maximum sum across all centers.
from typing import List

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        n = len(vals)
        neighbors = [[] for _ in range(n)]

        for u, v in edges:
            neighbors[u].append(vals[v])
            neighbors[v].append(vals[u])

        best = float("-inf")

        for center in range(n):
            # Only positive neighbors can improve the sum.
            positive = [value for value in neighbors[center] if value > 0]
            positive.sort(reverse=True)

            star_sum = vals[center] + sum(positive[:k])
            best = max(best, star_sum)

        return best

Complexity:

  • Time: O(n + m log m), where m is the number of edges; sorting each adjacency list is the dominant work.
  • Space: O(n + m) for the adjacency list and temporary neighbor values.

Common follow-ups

  • What if k is larger than a vertex’s degree? Select all its positive neighbors; slicing naturally handles this.
  • Can sorting be avoided when k is small? Keep only the largest k positive neighbor values with a min-heap.
  • What if the graph is directed? Define which direction counts as a neighbor, then build the adjacency list accordingly.
CodingMediumAkuna CapitalSoftware Engineer

9. Reduce Array Size to The Half (LeetCode)

Model answer

The task

Given an integer array, choose values to remove along with all their occurrences. Return the fewest distinct values to choose so that at least half the array’s elements are removed.

Key idea

Removing a value with a higher frequency makes more progress. Sort the frequencies from largest to smallest and take them until the removed count reaches half the array.

Approach

  1. Count how often each distinct value appears.
  2. Sort those frequencies in descending order.
  3. Add frequencies to a running total, counting each chosen value.
  4. Return the count as soon as the total removed reaches at least half the array.
from collections import Counter
from typing import List

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        frequencies = sorted(Counter(arr).values(), reverse=True)
        target = len(arr) // 2

        removed = 0
        chosen = 0

        for frequency in frequencies:
            removed += frequency
            chosen += 1
            if removed >= target:
                return chosen

        return chosen

Complexity:

  • Time: O(n + u log u), for counting n elements and sorting u distinct frequencies.
  • Space: O(u), for storing the frequencies.

Common follow-ups

  • Can sorting be avoided? Use a max-heap of frequencies; repeatedly remove the largest. This is useful when only a few values need to be chosen.
  • What if frequencies arrive as a stream? Maintain frequency counts as values arrive, then select the largest counts once the input ends.
  • What if the target is a different fraction of the array? Replace len(arr) // 2 with the required number of elements to remove.
CodingHardAkuna CapitalSoftware Engineer

10. Create Sorted Array through Instructions (LeetCode)

Model answer

The task

Process the values in order, inserting each into a growing sorted collection. For each insertion, add the smaller of the counts of existing values strictly less than and strictly greater than the new value; return the total modulo \(10^9+7\).

Key idea

Coordinate-compress the values so they map to a compact range of ranks. A Fenwick tree stores how many values have been inserted at each rank, letting us count smaller and greater values efficiently; querying through the current rank includes duplicates, so they are not counted as greater.

Approach

  1. Sort the distinct input values and assign each a 1-based rank.
  2. Initialize a Fenwick tree to track inserted ranks.
  3. For each value, query the count at ranks below its rank.
  4. Compute the greater count as the number already inserted minus the count at or below its rank.
  5. Add the smaller of those counts to the answer, then update the tree with the new rank.
class Solution:
    def createSortedArray(self, instructions: list[int]) -> int:
        mod = 10**9 + 7

        # Map each distinct value to a compact, 1-based rank.
        ranks = {value: i + 1 for i, value in enumerate(sorted(set(instructions)))}
        tree = [0] * (len(ranks) + 1)

        def query(index: int) -> int:
            """Count inserted values at ranks 1 through index."""
            total = 0
            while index > 0:
                total += tree[index]
                index -= index & -index
            return total

        def update(index: int) -> None:
            """Record one insertion at this rank."""
            while index < len(tree):
                tree[index] += 1
                index += index & -index

        answer = 0

        for inserted, value in enumerate(instructions):
            rank = ranks[value]

            smaller = query(rank - 1)
            at_or_below = query(rank)
            greater = inserted - at_or_below

            answer = (answer + min(smaller, greater)) % mod
            update(rank)

        return answer

Complexity:

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

Common follow-ups

  • What if values arrive online and cannot be compressed ahead of time? Use a dynamic segment tree over the value domain or an ordered multiset.
  • How are duplicates handled? Querying through the current rank counts equal values as neither strictly smaller nor strictly greater.
  • Can the tree support range counts? Subtract two prefix queries to obtain the count over any rank interval.
CodingHardAkuna CapitalSoftware Engineer

11. Constrained Subsequence Sum (LeetCode)

Model answer

The task

Find the largest sum of a non-empty subsequence of nums whose chosen indices increase and whose consecutive indices differ by at most k.

Key idea

Let dp[i] be the best sum of a valid subsequence ending at index i. The best preceding index is the one with the largest dp value in the previous k positions, or no preceding index if all those values are negative.

A monotonic deque keeps those candidate values in decreasing order, so the best one is available at the front.

Approach

  1. Iterate through the array from left to right.
  2. Remove deque indices that are more than k positions behind the current index.
  3. Add the front candidate’s positive value to nums[i]; if there is no positive candidate, start a new subsequence.
  4. Remove candidates from the back whose dp values are no better than the current value.
  5. Add the current index and track the largest dp value.
from collections import deque
from typing import List

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        # Indices in the deque have dp values in decreasing order.
        candidates = deque()
        best_sum = float("-inf")

        for i, value in enumerate(nums):
            # Keep only indices that can precede i.
            while candidates and candidates[0] < i - k:
                candidates.popleft()

            # Extend the best positive subsequence, or start anew.
            current = value
            if candidates and nums_dp[candidates[0]] > 0:
                current += nums_dp[candidates[0]]

            # Remove candidates dominated by this one.
            while candidates and nums_dp[candidates[-1]] <= current:
                candidates.pop()

            nums_dp[i] = current
            candidates.append(i)
            best_sum = max(best_sum, current)

        return best_sum

Complexity:

  • Time: O(n), since each index enters and leaves the deque at most once.
  • Space: O(n) for the dynamic-programming values and deque.

Common follow-ups

  • How would you return the chosen subsequence? Store a parent index for each dp entry and trace back from the best endpoint.
  • Can the deque be replaced with a heap? Yes, using a max-heap with indices and lazy removal, typically taking O(n log n) time.
  • What if the subsequence may be empty? Initialize the answer to 0 instead of requiring a non-empty result.
CodingHardAkuna CapitalSoftware Engineer

12. Critical Connections in a Network (LeetCode)

Model answer

The task

Given an undirected network, find every connection whose removal would make the network less connected. Return those connections as pairs of node IDs.

Key idea

A DFS assigns each node a discovery time and tracks the earliest discovery time reachable from its subtree using tree edges and back edges. A DFS tree edge is a bridge exactly when the child subtree cannot reach the parent or any ancestor through a back edge.

Approach

  1. Build an adjacency list that stores each edge’s unique ID alongside its neighboring node.
  2. Run DFS from each unvisited node, recording discovery times and low-link values.
  3. Skip only the exact edge used to enter a node, so parallel edges are handled correctly.
  4. After visiting a child, mark its tree edge as a bridge if the child’s low-link value exceeds the parent’s discovery time.
  5. Return all marked edges.
from typing import List
import sys

class Solution:
    def criticalConnections(
        self, n: int, connections: List[List[int]]
    ) -> List[List[int]]:
        sys.setrecursionlimit(max(1000, 2 * n + 10))

        # Store edge IDs so parallel edges are distinguished.
        graph = [[] for _ in range(n)]
        for edge_id, (u, v) in enumerate(connections):
            graph[u].append((v, edge_id))
            graph[v].append((u, edge_id))

        discovery = [-1] * n
        low = [0] * n
        bridges = []
        time = 0

        def dfs(node: int, parent_edge: int) -> None:
            nonlocal time
            discovery[node] = low[node] = time
            time += 1

            for neighbor, edge_id in graph[node]:
                if edge_id == parent_edge:
                    continue

                if discovery[neighbor] == -1:
                    dfs(neighbor, edge_id)
                    low[node] = min(low[node], low[neighbor])

                    if low[neighbor] > discovery[node]:
                        bridges.append([node, neighbor])
                else:
                    # A back edge reaches an already discovered node.
                    low[node] = min(low[node], discovery[neighbor])

        for node in range(n):
            if discovery[node] == -1:
                dfs(node, -1)

        return bridges

Complexity:

  • Time: O(V + E), since each node and edge is processed a constant number of times.
  • Space: O(V + E), for the adjacency list and DFS state.

Common follow-ups

  • How would you find articulation points too? Use the same low-link values; apply the articulation-point conditions for DFS roots and non-roots.
  • What if the graph is disconnected? Start DFS from every unvisited node, as in this solution.
  • What if there are parallel edges? Track edge IDs and skip only the exact parent edge, not every edge to the parent.
CodingHardAkuna CapitalSoftware Engineer

13. Minimum Number of Taps to Open to Water a Garden (LeetCode)

Model answer

The task

Each tap waters a contiguous interval of the garden. Find the fewest taps whose intervals cover the entire garden, or return -1 if that cannot be done.

Key idea

Treat each tap as an interval and group intervals by their left endpoint. Then use the greedy strategy for covering a line: among intervals reachable with the taps chosen so far, extend coverage as far as possible.

Approach

  1. Convert each tap into a clamped interval [left, right].
  2. For each left, store the farthest right any tap starting there can reach.
  3. Sweep from left to right, tracking the current coverage boundary and the farthest boundary reachable.
  4. Whenever the sweep reaches the current boundary, choose another tap to extend coverage.
  5. If no tap extends coverage, return -1.
class Solution:
    def minTaps(self, n: int, ranges: list[int]) -> int:
        if n == 0:
            return 0

        # farthest[left] is the furthest right endpoint of any
        # tap interval whose left endpoint is left.
        farthest = [0] * (n + 1)

        for i, radius in enumerate(ranges):
            left = max(0, i - radius)
            right = min(n, i + radius)
            farthest[left] = max(farthest[left], right)

        taps = 0
        current_end = 0
        next_end = 0

        for position in range(n):
            next_end = max(next_end, farthest[position])

            # A new tap is needed to extend coverage.
            if position == current_end:
                if next_end == current_end:
                    return -1

                taps += 1
                current_end = next_end

                if current_end >= n:
                    return taps

        return -1

Complexity:

  • Time: O(n), for building intervals and scanning positions.
  • Space: O(n), for the farthest-reach array.

Common follow-ups

  • How can the chosen taps be returned? Store the tap index that provides each farthest reach and record the choices during the sweep.
  • How would you solve it with dynamic programming? Set dp[x] to the minimum taps needed to cover through position x, relaxing each interval’s reachable range.
  • What if taps can be added or removed between queries? Use an interval data structure, such as a segment tree, to update and query reach efficiently.
CodingHardAkuna CapitalSoftware Engineer

14. Dice Roll Simulation (LeetCode)

Model answer

The task

Count length-n sequences of dice rolls where each face has its own limit on how many times it can appear consecutively. Return the count modulo \(10^9+7\).

Key idea

Track the number of valid sequences ending with each face and each possible streak length. A new streak of length one can follow any sequence that ended with a different face; longer streaks extend the same face’s previous streak.

Approach

  1. Store DP counts by face and streak length, using rolling arrays for consecutive roll counts.
  2. Initialize each face as a possible first roll with streak length one.
  3. For each additional roll, compute the count of sequences that can start a new streak for each face.
  4. Extend existing streaks by one, respecting that face’s limit.
  5. Sum the final DP counts modulo \(10^9+7\).
from typing import List

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7

        if n == 0:
            return 1

        # dp[face][streak] counts sequences ending with this face
        # repeated streak times. Index 0 is unused.
        dp = [[0] * (limit + 1) for limit in rollMax]

        for face in range(6):
            dp[face][1] = 1

        total = 6

        for _ in range(2, n + 1):
            next_dp = [[0] * (limit + 1) for limit in rollMax]

            for face in range(6):
                same_face_total = sum(dp[face])
                next_dp[face][1] = (total - same_face_total) % mod

                # Extend the current face's streak, if it remains within its limit.
                for streak in range(2, rollMax[face] + 1):
                    next_dp[face][streak] = dp[face][streak - 1]

            dp = next_dp
            total = sum(sum(face_counts) for face_counts in dp) % mod

        return total

Complexity:

  • Time: O(n × (6 + sum(rollMax))) — each roll processes the face limits and totals.
  • Space: O(sum(rollMax)) — only the current and next DP states are stored.

Common follow-ups

  • How would you reduce memory? Keep only the current and next roll states, as this solution does.
  • What if all faces share the same limit? Use the same DP, with equal-sized streak arrays.
  • How would you support a different modulus? Replace mod with the requested value.
CodingHardAkuna CapitalSoftware Engineer

15. Number of Different Subsequences GCDs (LeetCode)

Model answer

The task

Count the distinct values that can be the GCD of a nonempty subsequence of the given positive integers. The subsequence need not be contiguous.

Key idea

For a candidate GCD g, consider all input values divisible by g. Their combined GCD is achievable: if it equals g, those values themselves form a subsequence with GCD g. Check each candidate up to the largest input value.

Approach

  1. Mark which values occur in the input and find the maximum value.
  2. Try each integer g from 1 through that maximum.
  3. Visit the multiples of g that occur in the input, accumulating their GCD.
  4. Stop checking this candidate once the accumulated GCD reaches g.
  5. Count every candidate that passes the check.
from math import gcd
from typing import List

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        maximum = max(nums)
        present = [False] * (maximum + 1)

        for value in nums:
            present[value] = True

        answer = 0

        for candidate in range(1, maximum + 1):
            current_gcd = 0

            # Every value considered is a multiple of candidate.
            for value in range(candidate, maximum + 1, candidate):
                if present[value]:
                    current_gcd = gcd(current_gcd, value)

                    # The GCD cannot decrease below candidate.
                    if current_gcd == candidate:
                        answer += 1
                        break

        return answer

Complexity:

  • Time: O(M log² M), where M is the maximum input value; there are O(M log M) multiple checks, with GCD operations taking O(log M) in the worst case.
  • Space: O(M) for the presence array.

Common follow-ups

  • Why can we combine all multiples of a candidate? If their GCD is the candidate, those values are already a valid nonempty subsequence.
  • Can the candidate be larger than the maximum input value? No; a GCD cannot exceed any value in its subsequence.
  • What if the input contains duplicates? Duplicates do not change a GCD, so marking presence is sufficient.
  • Could this use a set instead of an array? Yes, but the array offers constant-time membership checks when values are bounded.
CodingHardAkuna CapitalSoftware Engineer

16. Minimize Malware Spread (LeetCode)

Model answer

The task

Given an undirected graph and a set of initially infected nodes, remove one initial infection to minimize how many nodes eventually become infected. If several choices are equally good, return the smallest node index.

Key idea

Infection spreads through each connected component. Removing an infection helps only when it is the sole initially infected node in its component; in that case, it saves the entire component.

Approach

  1. Use disjoint-set union (DSU) to find the graph’s connected components.
  2. Count the initial infections in each component.
  3. For each initial node, consider its component size only if that component has exactly one initial infection.
  4. Choose the node that saves the largest component; break ties by choosing the smallest index.
  5. If no node saves a component, return the smallest initially infected node.
from typing import List

class Solution:
    def minMalwareSpread(
        self, graph: List[List[int]], initial: List[int]
    ) -> int:
        n = len(graph)
        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # Path halving
                x = parent[x]
            return x

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

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

        # Build connected components from the adjacency matrix.
        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j] == 1:
                    union(i, j)

        infected_count = [0] * n
        for node in initial:
            infected_count[find(node)] += 1

        # Sorting ensures the smallest index wins ties.
        answer = min(initial)
        best_saved = 0

        for node in sorted(initial):
            root = find(node)
            if infected_count[root] == 1 and size[root] > best_saved:
                best_saved = size[root]
                answer = node

        return answer

Complexity:

  • Time: O(n² α(n) + m log m), where n is the number of nodes, m the number of initial infections, and α the inverse Ackermann function.
  • Space: O(n) for the DSU and component infection counts.

Common follow-ups

  • What if removing a node also removes its edges? That is a different variant; recompute spread after excluding the node, often using DFS/BFS per candidate.
  • What if multiple initial infections can be removed? The choice may involve selecting components and becomes an optimization problem over the removal budget.
  • Can the graph be processed from an edge list? Yes; union the endpoints of each edge instead of scanning the adjacency matrix.
CodingHardAkuna CapitalSoftware Engineer

17. Cherry Pickup (LeetCode)

Model answer

The task

Given a square grid with cherries and impassable cells, find the maximum cherries collectable on a trip from the top-left to the bottom-right and back. A cherry can be collected only once, and neither leg may pass through an impassable cell.

Key idea

Treat the two legs as two travelers moving from the top-left to the bottom-right at the same time. After the same number of moves, both travelers are on the same diagonal, so their positions can be tracked by their row indices. Dynamic programming finds the best total cherries while counting a shared cell only once.

Approach

  1. Let dp[r1][r2] be the best total after the current number of moves, with the travelers in rows r1 and r2.
  2. Derive each column from the move count and row.
  3. For each pair of valid, non-thorn cells, consider the four combinations of previous rows.
  4. Add the cherries at both positions, counting them once if the travelers coincide.
  5. Return the best value at the destination, or zero if no valid round trip exists.
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if n == 0 or grid[0][0] == -1:
            return 0

        neg = float("-inf")
        dp = [[neg] * n for _ in range(n)]
        dp[0][0] = grid[0][0]

        # Both travelers make one move per step.
        for steps in range(1, 2 * n - 1):
            curr = [[neg] * n for _ in range(n)]

            # A row is possible only if its corresponding column is in bounds.
            low = max(0, steps - (n - 1))
            high = min(n - 1, steps)

            for r1 in range(low, high + 1):
                c1 = steps - r1
                if grid[r1][c1] == -1:
                    continue

                for r2 in range(low, high + 1):
                    c2 = steps - r2
                    if grid[r2][c2] == -1:
                        continue

                    best_previous = neg
                    # Each traveler either moved right (same row) or down
                    # (previous row was one less).
                    for p1 in (r1, r1 - 1):
                        for p2 in (r2, r2 - 1):
                            if 0 <= p1 < n and 0 <= p2 < n:
                                best_previous = max(
                                    best_previous, dp[p1][p2]
                                )

                    if best_previous == neg:
                        continue

                    cherries = grid[r1][c1]
                    if r1 != r2:  # Different rows mean different cells.
                        cherries += grid[r2][c2]

                    curr[r1][r2] = best_previous + cherries

            dp = curr

        return max(0, dp[n - 1][n - 1])

Complexity:

  • Time: O(n³), for O(n²) row pairs across O(n) move steps.
  • Space: O(n²), for the two rolling DP tables.

Common follow-ups

  • How would you handle larger, sparse grids? Store only reachable states or use sparse maps when few cells are open.
  • What if cells have arbitrary rewards? Add both cell values, still counting a shared cell once.
  • What if there are more than two travelers? Track each traveler’s position, though the state size grows quickly.
CodingHardAkuna CapitalSoftware Engineer

18. Minimum Initial Energy to Finish Tasks (LeetCode)

Model answer

The task

Given tasks with an energy cost and a minimum energy requirement, choose their order to minimize the energy needed at the start. Energy decreases by each task’s cost after completing it.

Key idea

Sort tasks by decreasing minimum - actual. Tasks with a larger gap should be done earlier: they need a high energy buffer compared with the energy they consume. For a fixed order, the required starting energy is the largest of energy_spent_so_far + task_minimum.

Approach

  1. Sort tasks by minimum - actual, descending.
  2. Track the total energy spent before each task.
  3. For each task, update the answer with spent + minimum.
  4. Add the task’s actual cost to spent.
  5. Return the largest required starting energy encountered.
from typing import List

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        # Prioritize tasks with the largest minimum-energy buffer.
        tasks.sort(key=lambda task: task[1] - task[0], reverse=True)

        spent = 0
        required = 0

        for actual, minimum in tasks:
            # Before this task, we must have spent + minimum energy available.
            required = max(required, spent + minimum)
            spent += actual

        return required

Complexity:

  • Time: O(n log n), for sorting the tasks.
  • Space: O(n), for the sorting implementation.

Common follow-ups

  • Why does this sorting order work? Comparing two adjacent tasks shows that placing the larger minimum - actual first never increases the required starting energy.
  • Can the result exceed the sum of all task costs? Yes; a task’s minimum requirement can force extra initial energy beyond the total cost.
  • What if tasks must remain in their original order? The greedy sort is no longer allowed; scan in order and apply the same spent + minimum calculation.

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