DocuSign interview questions & answers

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

CodingEasyDocuSignSoftware Engineer

1. Count Binary Substrings (LeetCode)

Model answer

The task

Count nonempty substrings of a binary string that contain the same number of 0s and 1s, with all the 0s and 1s grouped into consecutive runs.

Key idea

For each pair of neighboring runs, the number of valid substrings they contribute is the length of the shorter run. Track the previous run’s length and the current run’s length, adding the smaller whenever a run ends.

Approach

  1. Start with the first run and set both run lengths to one.
  2. Scan the string from left to right.
  3. If the current character matches the previous one, extend the current run.
  4. Otherwise, add the smaller run length to the answer, then shift the current run into the previous-run count and start a new run.
  5. Add the final pair’s contribution after the scan.
class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        previous_run = 0
        current_run = 1
        total = 0

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                current_run += 1
            else:
                total += min(previous_run, current_run)
                previous_run = current_run
                current_run = 1

        # Account for the final pair of neighboring runs.
        total += min(previous_run, current_run)
        return total

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(1), using only a few counters.

Common follow-ups

  • How would you return the actual substrings? Track each run boundary and enumerate the valid lengths, though output size can be large.
  • What if the input alphabet has more than two characters? The equal-sized neighboring-run rule applies to adjacent runs of two different characters; clarify the exact validity condition first.
  • How would you handle a stream of characters? Maintain the two run counts and update the total when a run transition is observed; finalize the last pair when the stream ends.
CodingEasyDocuSignSoftware Engineer

2. Logger Rate Limiter (LeetCode)

Model answer

The task

Build a logger that decides whether to print each message. A message is allowed if it has not been printed in the previous 10 seconds.

Key idea

Store the timestamp of the last time each message was accepted. Allow a message when it has never been printed or at least 10 seconds have elapsed since its last accepted print.

Approach

  1. Create a hash map from message text to its last accepted timestamp.
  2. For each request, look up the message’s previous timestamp.
  3. If there is no previous timestamp, or the elapsed time is at least 10 seconds, record the current timestamp and return True.
  4. Otherwise, return False without changing the stored timestamp.
class Logger:
    def __init__(self):
        # Message text -> timestamp of its last accepted print.
        self.last_printed = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        previous = self.last_printed.get(message)

        if previous is None or timestamp - previous >= 10:
            self.last_printed[message] = timestamp
            return True

        return False

Complexity:

  • Time: O(1) average per request for hash-map operations.
  • Space: O(m), where m is the number of distinct messages stored.

Common follow-ups

  • What if requests arrive out of timestamp order? Store timestamp history per message and check whether any accepted print falls within the relevant interval.
  • How can memory use be reduced for a chronological stream? Evict entries older than the rate-limit window, using a queue or time-ordered structure.
  • How would this work across multiple servers? Use shared, atomic state in a distributed store, with a consistent rate-limit operation.
CodingEasyDocuSignSoftware Engineer

3. Merge Two Sorted Lists (LeetCode)

Model answer

The task

Given the heads of two sorted singly linked lists, combine their nodes into one sorted list. Return the head of the merged list.

Key idea

At each step, append the smaller of the two current nodes, then advance that list. A dummy node simplifies handling the merged list’s head.

Approach

  1. Create a dummy node and set a pointer to it.
  2. While both lists have nodes, compare their values.
  3. Link the smaller node after the pointer and advance its source list.
  4. Advance the pointer.
  5. Link any remaining nodes and return the node after the dummy.
# LeetCode provides the ListNode class.
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        tail = dummy

        # Repeatedly attach the smaller current node.
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        # At most one list remains; it is already sorted.
        tail.next = list1 if list1 else list2
        return dummy.next

Complexity:

  • Time: O(m + n), where m and n are the lengths of the lists.
  • Space: O(1) extra space; the existing nodes are relinked.

Common follow-ups

  • How would you implement this recursively? Choose the smaller head and recursively merge the rest; this uses O(m + n) call-stack space.
  • What if the lists are sorted in descending order? Adjust the comparison or reverse the merged result, depending on the desired output order.
  • What if one list is empty? The remaining list is returned directly.
CodingMediumDocuSignSoftware Engineer

4. Number of Islands (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

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

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

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

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

        return islands

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

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

Common follow-ups

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

5. Find Maximum Area of a Triangle (LeetCode)

Model answer

The task

Given points in the plane, choose three that form a triangle with at least one horizontal or vertical side. Return twice the greatest possible area, or -1 if no positive-area triangle can be formed.

Key idea

For a vertical side, points sharing an x-coordinate define the possible base; only the lowest and highest y-coordinates matter. The third point should be as far away horizontally as possible, which is determined by the global minimum and maximum x-coordinates. Apply the symmetric argument for horizontal sides.

Approach

  1. Group points by x-coordinate and by y-coordinate, tracking the minimum and maximum coordinate in each group.
  2. Track the global minimum and maximum x- and y-coordinates.
  3. For each x-group, multiply its y-span by the farther global x-extreme distance.
  4. For each y-group, multiply its x-span by the farther global y-extreme distance.
  5. Return the largest product, or -1 if it is zero.
from collections import defaultdict
from typing import List

class Solution:
    def maxArea(self, coords: List[List[int]]) -> int:
        # For each x, store the lowest and highest y.
        by_x = defaultdict(lambda: [float("inf"), float("-inf")])

        # For each y, store the leftmost and rightmost x.
        by_y = defaultdict(lambda: [float("inf"), float("-inf")])

        min_x = min_y = float("inf")
        max_x = max_y = float("-inf")

        for x, y in coords:
            by_x[x][0] = min(by_x[x][0], y)
            by_x[x][1] = max(by_x[x][1], y)
            by_y[y][0] = min(by_y[y][0], x)
            by_y[y][1] = max(by_y[y][1], x)

            min_x = min(min_x, x)
            max_x = max(max_x, x)
            min_y = min(min_y, y)
            max_y = max(max_y, y)

        best = 0

        # Use a vertical side as the base.
        for x, (low_y, high_y) in by_x.items():
            height = high_y - low_y
            width = max(abs(x - min_x), abs(x - max_x))
            best = max(best, height * width)

        # Use a horizontal side as the base.
        for y, (left_x, right_x) in by_y.items():
            width = right_x - left_x
            height = max(abs(y - min_y), abs(y - max_y))
            best = max(best, width * height)

        return best if best > 0 else -1

Complexity:

  • Time: O(n), for grouping and scanning the points.
  • Space: O(n), for the coordinate groups.

Common follow-ups

  • Why are global extremes sufficient? For a fixed base, the farthest possible third-point distance along the perpendicular axis is at one of that axis’s global extremes.
  • Can the actual area be fractional? Yes; the returned product is twice the area, so it remains an integer.
  • What if the side may have any orientation? This grouping method no longer suffices; consider enumerating point triples or using a specialized geometric optimization.
CodingMediumDocuSignSoftware Engineer

6. Insert Delete GetRandom O(1) (LeetCode)

Model answer

The task

Design a collection that supports adding and removing values, plus returning a uniformly random stored value. Each operation should take average O(1) time.

Key idea

Store values in a list for constant-time random indexing, and map each value to its index for fast lookup. To remove an item without shifting the list, swap it with the last item and then pop.

Approach

  1. Keep a list of stored values and a dictionary from value to its list index.
  2. For insertion, return False if the value is already present; otherwise append it and record its index.
  3. For removal, return False if absent. Otherwise, move the last value into the removed value’s slot, update its index, then pop and delete the removed value from the dictionary.
  4. For random selection, choose a uniformly random index in the list.
  5. Assume random selection is called only when the collection is nonempty.
import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index_by_value = {}

    def insert(self, val: int) -> bool:
        if val in self.index_by_value:
            return False

        self.index_by_value[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_by_value:
            return False

        index = self.index_by_value[val]
        last_value = self.values[-1]

        # Fill the removed value's slot with the last value.
        self.values[index] = last_value
        self.index_by_value[last_value] = index

        self.values.pop()
        del self.index_by_value[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)

Complexity:

  • Time: O(1) average per operation; dictionary operations are expected O(1).
  • Space: O(n), for the list and index map storing n values.

Common follow-ups

  • How would you support duplicates? Store each value’s set of indices and update that set during swaps.
  • What if random selection must be weighted? Maintain cumulative weights and use binary search, or use a dynamic weighted-sampling structure.
  • What happens if getRandom is called when empty? Define a clear error or sentinel behavior; the implementation assumes at least one value exists.
CodingMediumDocuSignSoftware Engineer

7. Implement Trie (Prefix Tree) (LeetCode)

Model answer

The task

Design a prefix tree that supports inserting strings, checking whether a complete string has been inserted, and checking whether any inserted string begins with a given prefix.

Key idea

Represent each character as an edge to a child node. Mark the node at the end of each inserted string, so a path can indicate a prefix without necessarily representing a complete word.

Approach

  1. Give each node a map from characters to child nodes and a flag indicating whether a word ends there.
  2. For insertion, create any missing nodes along the string’s path.
  3. Mark the final node as the end of a word.
  4. For both searches, follow the path character by character; if a child is missing, return False.
  5. A full-word search also checks the final node’s end-of-word flag; a prefix search only checks that the path exists.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, text: str):
        node = self.root

        for char in text:
            if char not in node.children:
                return None
            node = node.children[char]

        return node

Complexity:

  • Time: O(L) per operation, where L is the length of the word or prefix being processed.
  • Space: O(S) for the trie, where S is the total number of characters stored across distinct paths.

Common follow-ups

  • How would you delete a word? Clear its end-of-word flag, then remove nodes that are no longer needed.
  • How would you support case-insensitive matching? Normalize strings consistently, such as by converting them to lowercase.
  • How can you reduce memory use for sparse or large alphabets? Use compact child storage, such as a radix trie or a sorted edge list.
CodingMediumDocuSignSoftware Engineer

8. 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.
CodingMediumDocuSignSoftware Engineer

9. Spiral Matrix IV (LeetCode)

Model answer

The task

Build an m-by-n matrix by placing linked-list values in clockwise spiral order, starting at the top-left. Any cells left after the list ends should contain -1.

Key idea

Track the unfilled rectangle using four boundaries: top, bottom, left, and right. Fill its edges in clockwise order, shrinking a boundary after each edge so no cell is visited twice.

Approach

  1. Create an m-by-n matrix initialized to -1.
  2. Set the four boundaries to the edges of the matrix.
  3. Traverse the top row, then the right column, bottom row, and left column, advancing the list pointer as each cell is filled.
  4. Shrink the corresponding boundary after each traversal.
  5. Stop when the list is exhausted or the boundaries no longer enclose any cells.
from typing import List, Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def spiralMatrix(
        self, m: int, n: int, head: Optional[ListNode]
    ) -> List[List[int]]:
        matrix = [[-1] * n for _ in range(m)]

        top, bottom = 0, m - 1
        left, right = 0, n - 1
        node = head

        while node is not None and top <= bottom and left <= right:
            # Fill the top edge from left to right.
            for col in range(left, right + 1):
                if node is None:
                    break
                matrix[top][col] = node.val
                node = node.next
            top += 1

            # Fill the right edge from top to bottom.
            for row in range(top, bottom + 1):
                if node is None:
                    break
                matrix[row][right] = node.val
                node = node.next
            right -= 1

            # Fill the bottom edge from right to left, if it remains.
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    if node is None:
                        break
                    matrix[bottom][col] = node.val
                    node = node.next
                bottom -= 1

            # Fill the left edge from bottom to top, if it remains.
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    if node is None:
                        break
                    matrix[row][left] = node.val
                    node = node.next
                left += 1

        return matrix

Complexity:

  • Time: O(mn) in the worst case, where every matrix cell is visited.
  • Space: O(mn) for the returned matrix; O(1) auxiliary space.

Common follow-ups

  • What if the list has more values than cells? Stop once the matrix is full.
  • Can the matrix be filled in counterclockwise order? Change the traversal order and boundary updates.
  • How can you avoid boundary-condition errors? Test single-row, single-column, and partially filled matrices.
CodingMediumDocuSignSoftware Engineer

10. Search Suggestions System (LeetCode)

Model answer

The task

Given a list of products and a search word, return up to three lexicographically smallest products matching each prefix of the search word.

Key idea

Sort the products once. For each prefix, binary-search for its insertion point; matching products, if any, appear consecutively from that position.

Approach

  1. Sort the product names lexicographically.
  2. Build each prefix of the search word in turn.
  3. Use binary search to find the first product not less than that prefix.
  4. Check at most the next three products, keeping only those that start with the prefix.
  5. Append those matches to the result.
from bisect import bisect_left
from typing import List

class Solution:
    def suggestedProducts(
        self, products: List[str], searchWord: str
    ) -> List[List[str]]:
        products.sort()
        suggestions = []
        prefix = ""

        for char in searchWord:
            prefix += char
            start = bisect_left(products, prefix)

            matches = []
            for product in products[start:start + 3]:
                if product.startswith(prefix):
                    matches.append(product)

            suggestions.append(matches)

        return suggestions

Complexity:

  • Time: O(n log n · L + m² log n), where n is the number of products, L is their maximum length, and m is the search-word length. This accounts for string comparisons during sorting and binary searches.
  • Space: O(n · L) for the sorted product list if sorting requires a copy; the returned suggestions also use space for their output.

Common follow-ups

  • How can you avoid sorting all products? Use a trie that stores the three smallest matching products at each prefix node.
  • What if more than three suggestions are required? Check the requested number of consecutive products after the binary-search position.
  • What if products change frequently? A trie or another update-friendly index may be preferable to re-sorting.
  • How do duplicate product names behave? They appear as separate suggestions; deduplicate the sorted list if only unique names should be returned.
CodingMediumDocuSignSoftware Engineer

11. 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.
CodingMediumDocuSignSoftware Engineer

12. Top K Frequent Elements (LeetCode)

Model answer

The task

Given an integer array and a value k, return the k values that occur most often. Their order does not matter.

Key idea

Count each value’s occurrences, then group values by frequency. Since no frequency can exceed the array length, scan these groups from highest frequency down until k values are collected.

Approach

  1. Build a frequency map from each value to its count.
  2. Create buckets indexed by frequency.
  3. Put each distinct value into the bucket for its count.
  4. Scan buckets from highest to lowest, collecting values until there are k.
from collections import defaultdict
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count occurrences of each value.
        frequency = defaultdict(int)
        for value in nums:
            frequency[value] += 1

        # Bucket each value by its frequency.
        buckets = [[] for _ in range(len(nums) + 1)]
        for value, count in frequency.items():
            buckets[count].append(value)

        # Collect values from most frequent to least frequent.
        result = []
        for count in range(len(nums), 0, -1):
            for value in buckets[count]:
                result.append(value)
                if len(result) == k:
                    return result

        return result

Complexity:

  • Time: O(n), where n is the array length; counting and scanning the buckets take linear time.
  • Space: O(n), for the frequency map and buckets.

Common follow-ups

  • How would you solve it with a heap? Keep a size-k heap of distinct values, giving O(n + m log k) time, where m is the number of distinct values.
  • What if results must be ordered by frequency? Sort the selected values by their counts, or collect them in descending bucket order.
  • What if the data arrives as a stream? Maintain approximate counts with a streaming frequency sketch, or use a bounded candidate structure when exact counts are not feasible.
CodingMediumDocuSignSoftware Engineer

13. Integer to Roman (LeetCode)

Model answer

The task

Convert a positive integer into its standard Roman numeral representation, using subtractive forms such as IV and CM where appropriate.

Key idea

Process Roman numeral values from largest to smallest, including the six subtractive combinations as single entries. At each value, emit it as many times as possible, then continue with the remainder.

Approach

  1. List the values and their Roman numeral symbols in descending order.
  2. For each value, use integer division to determine how many times it fits in the remaining number.
  3. Append that many copies of its symbol.
  4. Subtract the represented amount and continue.
  5. Join the symbols to form the result.
class Solution:
    def intToRoman(self, num: int) -> str:
        # Include subtractive pairs alongside the ordinary symbols.
        values = [
            (1000, "M"),
            (900, "CM"),
            (500, "D"),
            (400, "CD"),
            (100, "C"),
            (90, "XC"),
            (50, "L"),
            (40, "XL"),
            (10, "X"),
            (9, "IX"),
            (5, "V"),
            (4, "IV"),
            (1, "I"),
        ]

        result = []

        for value, symbol in values:
            count, num = divmod(num, value)
            result.append(symbol * count)

        return "".join(result)

Complexity:

  • Time: O(1) for the standard bounded integer range; each of the fixed 13 values is checked.
  • Space: O(1) auxiliary space; the result uses O(1) space for the bounded output.

Common follow-ups

  • How would you convert a Roman numeral back to an integer? Scan symbols and subtract a value when it is less than the next symbol.
  • What if the input can exceed the standard Roman numeral range? Define an extension convention, such as overlines for thousands, before adapting the mapping.
  • How would you validate a Roman numeral string? Parse it, convert it to an integer, then convert that integer back and compare with the original.
CodingMediumDocuSignSoftware Engineer

14. House Robber II (LeetCode)

Model answer

The task

Choose non-adjacent houses to maximize the amount collected, with the first and last houses also considered adjacent because the street is circular.

Key idea

A valid selection cannot include both ends of the circle. Solve two linear versions: one that excludes the first house, and one that excludes the last. For each version, use the standard linear house-robber recurrence.

Approach

  1. If there are no houses, return 0.
  2. If there is only one house, return its value.
  3. Define a helper that finds the best total in a half-open range using two rolling values.
  4. Run the helper on the ranges excluding the first and last houses, respectively.
  5. Return the larger result.
class Solution:
    def rob(self, nums: list[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        def rob_range(start: int, end: int) -> int:
            # prev_two: best total before the previous house
            # prev_one: best total through the previous house
            prev_two = 0
            prev_one = 0

            for i in range(start, end):
                current = max(prev_one, prev_two + nums[i])
                prev_two, prev_one = prev_one, current

            return prev_one

        # Exclude the first house, or exclude the last house.
        return max(
            rob_range(1, len(nums)),
            rob_range(0, len(nums) - 1),
        )

Complexity:

  • Time: O(n), since each of the two ranges is processed once.
  • Space: O(1), using only a fixed number of rolling values.

Common follow-ups

  • What if the houses form a line instead of a circle? Run the linear recurrence once over the entire list.
  • Can you return which houses to rob? Store decisions during the recurrence, then backtrack to reconstruct the chosen indices.
  • What if values can be negative? If robbing no houses is allowed, initialize the result so choosing nothing remains an option.
CodingMediumDocuSignSoftware Engineer

15. Design Authentication Manager (LeetCode)

Model answer

The task

Implement an authentication manager that creates tokens with a fixed lifetime, renews valid tokens, and reports how many remain valid at a given time.

Key idea

Keep a hash map from token IDs to nodes in a doubly linked list ordered by expiration time. Since operation times are nondecreasing and every token has the same lifetime, newly created or renewed tokens go at the end; expired tokens can be removed from the front.

Approach

  1. Store each token’s expiration time in a list node, and map its ID to that node.
  2. Before each operation, remove all front nodes whose expiration time is at or before the current time.
  3. For generation, remove any existing node with that ID, then append the new expiration.
  4. For renewal, update only if the token remains in the map after expiration cleanup.
  5. Return the map size for a count request.
class _Node:
    def __init__(self, token_id=None, expiry=0):
        self.token_id = token_id
        self.expiry = expiry
        self.prev = None
        self.next = None

class AuthenticationManager:
    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.tokens = {}

        # Sentinels make insertion and removal uniform.
        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
        del self.tokens[node.token_id]

    def _append(self, node: _Node) -> None:
        last = self.tail.prev
        last.next = node
        node.prev = last
        node.next = self.tail
        self.tail.prev = node
        self.tokens[node.token_id] = node

    def _expire(self, currentTime: int) -> None:
        while self.head.next != self.tail:
            node = self.head.next
            if node.expiry > currentTime:
                break
            self._remove(node)

    def generate(self, tokenId: str, currentTime: int) -> None:
        self._expire(currentTime)

        # Replacing an existing ID is safe, even if IDs are normally unique.
        if tokenId in self.tokens:
            self._remove(self.tokens[tokenId])

        self._append(_Node(tokenId, currentTime + self.ttl))

    def renew(self, tokenId: str, currentTime: int) -> None:
        self._expire(currentTime)
        if tokenId in self.tokens:
            self._remove(self.tokens[tokenId])
            self._append(_Node(tokenId, currentTime + self.ttl))

    def countUnexpiredTokens(self, currentTime: int) -> int:
        self._expire(currentTime)
        return len(self.tokens)

Complexity:

  • Time: O(1) amortized per operation; each token node is removed at most once.
  • Space: O(n), for the currently stored tokens.

Common follow-ups

  • What if operation times are not nondecreasing? Use a min-heap keyed by expiration, with lazy deletion for renewed tokens.
  • What if each token has a different lifetime? Store its calculated expiration; use a min-heap if list ordering can no longer be guaranteed.
  • How should duplicate token IDs behave? Define whether generation replaces the old token or rejects the request.
CodingMediumDocuSignSoftware Engineer

16. Task Scheduler (LeetCode)

Model answer

The task

Find the fewest time slots needed to run all tasks when identical task types must be separated by at least n slots. A slot may be left idle.

Key idea

The most frequent task types determine the minimum schedule length. Put copies of a most frequent type into frames of length n + 1; other tasks can fill the gaps. If there are enough other tasks to fill every gap, no idle slots are needed.

Approach

  1. Count how many times each task type appears.
  2. Find the largest frequency, max_freq.
  3. Count how many types occur exactly max_freq times.
  4. Compute the frame-based length: (max_freq - 1) * (n + 1) + max_count.
  5. Return the larger of that length and the total number of tasks.
from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequencies = Counter(tasks)
        max_freq = max(frequencies.values())
        max_count = sum(
            frequency == max_freq
            for frequency in frequencies.values()
        )

        # The most frequent tasks establish the frame-based schedule.
        frame_length = (max_freq - 1) * (n + 1) + max_count

        # Other tasks may fill idle slots, but cannot reduce below task count.
        return max(len(tasks), frame_length)

Complexity:

  • Time: O(m + k), to count m tasks and scan k task types.
  • Space: O(k), for the task-frequency counts.

Common follow-ups

  • What if n is zero? The formula returns the task count, since no cooldown is required.
  • What if several task types share the highest frequency? Include all of them in the last frame, as max_count does.
  • How could you construct an actual schedule? Greedily run the most frequent available task, tracking cooldowns with a max-heap and a queue.
  • What if tasks have different cooldowns? The simple formula no longer applies; model each task’s next available time and schedule with a priority queue.
CodingMediumDocuSignSoftware Engineer

17. Accounts Merge (LeetCode)

Model answer

The task

Combine accounts that belong to the same person when they share an email address. Return each merged account with its name and unique email addresses in sorted order.

Key idea

Treat each email as a node. Emails appearing in the same account are connected, and connected components represent merged accounts. Union-Find efficiently builds those components as accounts are processed.

Approach

  1. Create a Union-Find set for each distinct email, and remember the account name associated with each email.
  2. For each account, union its first email with every other email in that account.
  3. Group emails by their final Union-Find root.
  4. Sort each group’s emails and assemble the results.
  5. Sort the result groups for deterministic output.
from typing import List

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent: dict[str, str] = {}
        rank: dict[str, int] = {}
        name_by_email: dict[str, str] = {}

        def add(email: str, name: str) -> None:
            if email not in parent:
                parent[email] = email
                rank[email] = 0
                name_by_email[email] = name

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

        def union(first: str, second: str) -> None:
            root_first = find(first)
            root_second = find(second)

            if root_first == root_second:
                return

            # Union by rank keeps the sets shallow.
            if rank[root_first] < rank[root_second]:
                root_first, root_second = root_second, root_first

            parent[root_second] = root_first
            if rank[root_first] == rank[root_second]:
                rank[root_first] += 1

        for account in accounts:
            name = account[0]
            emails = account[1:]

            for email in emails:
                add(email, name)

            # All emails in this account belong to the same component.
            for email in emails[1:]:
                union(emails[0], email)

        emails_by_root: dict[str, List[str]] = {}
        for email in parent:
            root = find(email)
            emails_by_root.setdefault(root, []).append(email)

        merged = []
        for emails in emails_by_root.values():
            emails.sort()
            merged.append([name_by_email[emails[0]], *emails])

        # The outer result order is not essential, but sorting makes it stable.
        merged.sort()
        return merged

Complexity:

  • Time: O(E α(E) + E log E), where E is the number of distinct emails; sorting dominates.
  • Space: O(E) for the Union-Find structure and grouped output.

Common follow-ups

  • Could DFS solve this instead? Yes; build an email graph and find its connected components.
  • What if two unrelated people have the same name? They remain separate unless their accounts share an email.
  • How would you handle very large datasets? Partition by email or use distributed connected-components processing, then combine components that cross partitions.
CodingMediumDocuSignSoftware Engineer

18. Find Peak Element (LeetCode)

Model answer

The task

Given an array whose neighboring values are distinct, return the index of any element that is greater than its neighbors. Treat positions outside the array as having value negative infinity.

Key idea

Compare the middle element with the one immediately to its right. If the middle is larger, a peak exists at or to its left; otherwise, a peak exists to its right. This lets binary search discard half the search range each iteration.

Approach

  1. Set left and right to the array’s endpoints.
  2. While the range has more than one element, inspect its midpoint and the next element.
  3. If the midpoint is larger, keep the left half, including the midpoint.
  4. Otherwise, keep the right half, starting after the midpoint.
  5. Return the remaining index.
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            # A descending step means a peak is at mid or somewhere to its left.
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                # An ascending step means a peak exists to the right of mid.
                left = mid + 1

        return left

Complexity:

  • Time: O(log n), since the search range is halved each iteration.
  • Space: O(1), since only a fixed number of variables are used.

Common follow-ups

  • How would you return all peak indices? Scan the array and compare each value with its neighbors, using negative infinity at the boundaries.
  • What if adjacent values may be equal? The binary-search reasoning may no longer identify a peak in logarithmic time; handle plateaus explicitly or scan in O(n).
  • How would you find a peak in a two-dimensional grid? Use binary search across columns, finding a column maximum each step and comparing it with its horizontal neighbors.
CodingMediumDocuSignSoftware Engineer

19. Meeting Rooms II (LeetCode)

Model answer

The task

Given meeting time intervals, find the minimum number of rooms needed so that no overlapping meetings share a room.

Key idea

Process meetings in start-time order. Track each occupied room by the time its meeting ends; a room is available when its meeting ends no later than the next meeting starts.

Approach

  1. Sort intervals by start time.
  2. Keep a min-heap of end times for meetings using rooms.
  3. For each meeting, remove the earliest end time if that room is available.
  4. Add the current meeting’s end time to the heap.
  5. The largest heap size reached is the minimum room count.
import heapq
from typing import List

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

        intervals.sort(key=lambda meeting: meeting[0])
        room_end_times = []

        for start, end in intervals:
            # Reuse the room whose meeting finishes first, if available.
            if room_end_times and room_end_times[0] <= start:
                heapq.heappop(room_end_times)

            heapq.heappush(room_end_times, end)

        return len(room_end_times)

Complexity:

  • Time: O(n log n), for sorting and heap operations across n meetings.
  • Space: O(n), for the heap in the worst case.

Common follow-ups

  • What if a meeting ending at time t overlaps one starting at t? Change the availability check from <= to <.
  • How can you return a room assignment for every meeting? Store (end_time, room_id) in the heap and reuse the freed room ID.
  • How would you handle meetings arriving online? Maintain the end-time heap as meetings arrive; each new meeting can reuse a room or add one.
CodingMediumDocuSignSoftware Engineer

20. Group Anagrams (LeetCode)

Model answer

The task

Partition the input strings into groups so that strings in the same group contain the same characters with the same frequencies. The order of the groups does not matter.

Key idea

Sort the characters of each string to create a canonical key. Anagrams produce the same key, so a hash table can collect them together.

Approach

  1. Create a mapping from canonical keys to lists of original strings.
  2. For each string, sort its characters and use the result as its key.
  3. Append the string to the list for that key.
  4. Return all grouped lists.
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for word in strs:
            # Anagrams have identical sorted-character representations.
            key = "".join(sorted(word))
            groups[key].append(word)

        return list(groups.values())

Complexity:

  • Time: O(n · k log k), where n is the number of strings and k is the maximum string length.
  • Space: O(n · k) to store the grouped strings and their keys.

Common follow-ups

  • Can this be faster for a fixed alphabet? Use a character-frequency tuple as the key, computing it in O(k) per string.
  • Does this work with uppercase letters or Unicode? Yes; sorting characters works for any Python strings.
  • Can groups be returned in a deterministic order? Sort the groups, or their keys, before returning them.
  • What if memory is limited? Consider processing input in batches or grouping externally by canonical key.

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