Pocket Gems interview questions & answers

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

CodingEasyPocket GemsSoftware Engineer

1. Find the Index of the First Occurrence in a String (LeetCode)

Model answer

The task

Given a text string and a pattern string, return the starting index of the pattern’s first occurrence in the text. Return -1 if it does not occur; an empty pattern matches at index 0.

Key idea

Use Knuth–Morris–Pratt (KMP). Its prefix table lets the search reuse information about matched characters instead of restarting from scratch after a mismatch.

Approach

  1. Build a prefix table for the pattern. At each position, it records the length of the longest proper prefix that is also a suffix.
  2. Scan the text while tracking how many pattern characters currently match.
  3. On a mismatch, use the prefix table to find the next viable match length.
  4. Return the match’s starting index when the entire pattern matches; otherwise return -1.
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        # Build the longest-prefix-suffix table for needle.
        lps = [0] * len(needle)
        prefix_len = 0
        i = 1

        while i < len(needle):
            if needle[i] == needle[prefix_len]:
                prefix_len += 1
                lps[i] = prefix_len
                i += 1
            elif prefix_len > 0:
                prefix_len = lps[prefix_len - 1]
            else:
                i += 1

        # Search haystack without rechecking matched characters.
        text_i = 0
        pattern_i = 0

        while text_i < len(haystack):
            if haystack[text_i] == needle[pattern_i]:
                text_i += 1
                pattern_i += 1

                if pattern_i == len(needle):
                    return text_i - pattern_i
            elif pattern_i > 0:
                pattern_i = lps[pattern_i - 1]
            else:
                text_i += 1

        return -1

Complexity:

  • Time: O(n + m), where n and m are the text and pattern lengths.
  • Space: O(m), for the prefix table.

Common follow-ups

  • How would you handle many pattern searches in the same text? Build an index or use a multi-pattern algorithm such as Aho–Corasick.
  • What if the text arrives as a stream? Keep the KMP match state and prefix table between chunks.
  • How would you find all occurrences? After each full match, record its start and reset the pattern index using the final prefix-table value.
CodingMediumPocket GemsSoftware Engineer

2. 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.
CodingMediumPocket GemsSoftware Engineer

3. Kth Largest Element in an Array (LeetCode)

Model answer

The task

Find the value that would appear in position k when the array is sorted from largest to smallest. Duplicate values count as separate positions.

Key idea

The answer is the element at index len(nums) - k in ascending order. Quickselect partitions the array around pivots, then continues only in the partition that contains that index.

Approach

  1. Convert k to its target index in ascending order.
  2. Choose a random pivot to reduce the chance of consistently poor partitions.
  3. Partition into values smaller than, equal to, and greater than the pivot.
  4. Narrow the search to the partition containing the target, or return the pivot if the target lies among the equal values.
import random
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        left, right = 0, len(nums) - 1

        while left <= right:
            pivot = nums[random.randint(left, right)]

            # Three-way partition:
            # nums[left:lt] < pivot
            # nums[lt:gt + 1] == pivot
            # nums[gt + 1:right + 1] > pivot
            lt, i, gt = left, left, right
            while i <= gt:
                if nums[i] < pivot:
                    nums[lt], nums[i] = nums[i], nums[lt]
                    lt += 1
                    i += 1
                elif nums[i] > pivot:
                    nums[i], nums[gt] = nums[gt], nums[i]
                    gt -= 1
                else:
                    i += 1

            if target < lt:
                right = lt - 1
            elif target > gt:
                left = gt + 1
            else:
                return pivot

        raise ValueError("k must be within the array's valid range")

Complexity:

  • Time: O(n) on average, since each partition discards the portions that cannot contain the answer.
  • Space: O(1) auxiliary space; the partitioning is in place.

Common follow-ups

  • What if worst-case time must be bounded? Use a min-heap of size k for O(n log k) time.
  • How do duplicates affect the result? Each occurrence occupies its own rank; the three-way partition handles equal values together.
  • Can the input remain unchanged? Make a copy before partitioning, at the cost of O(n) extra space.
CodingMediumPocket GemsSoftware Engineer

4. Longest Repeating Character Replacement (LeetCode)

Model answer

The task

Find the length of the longest substring that can be made entirely of one repeated character by changing at most k characters.

Key idea

Use a sliding window and track the most frequent character in it. The number of replacements needed is the window length minus that frequency, so shrink the window whenever this exceeds k.

Approach

  1. Keep a frequency count for characters in the current window.
  2. Expand the right edge one character at a time and update the highest frequency seen.
  3. If the window would need more than k replacements, move its left edge forward.
  4. Record the largest window length.

The maximum frequency is intentionally not recomputed when the window shrinks. It may be stale, but this still gives the correct maximum length: the window only stays large when its length is supported by a frequency seen in a previously valid window.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = {}
        left = 0
        max_frequency = 0
        longest = 0

        for right, char in enumerate(s):
            counts[char] = counts.get(char, 0) + 1
            max_frequency = max(max_frequency, counts[char])

            # Shrink until the window can be made uniform with at most k changes.
            if (right - left + 1) - max_frequency > k:
                counts[s[left]] -= 1
                left += 1

            longest = max(longest, right - left + 1)

        return longest

Complexity:

  • Time: O(n), where n is the string length; each pointer moves at most n times.
  • Space: O(1), since the frequency map has at most 26 entries for uppercase English letters.

Common follow-ups

  • What if the string can contain arbitrary Unicode characters? Use a dictionary for counts; the space then depends on the number of distinct characters.
  • Can the method return the substring as well as its length? Store the best window’s start and end indices whenever the best length increases.
  • What if replacements have different costs? Track the minimum cost to make the window uniform and shrink while that cost exceeds the budget.
CodingMediumPocket GemsSoftware Engineer

5. Word Break (LeetCode)

Model answer

The task

Given a string and a dictionary of words, determine whether the string can be formed by concatenating dictionary words. Words may be reused.

Key idea

Track which string positions are reachable after forming a sequence of words. From each reachable position, follow the dictionary trie through the string; every terminal trie node marks another reachable position.

Approach

  1. Build a trie from the dictionary, marking the end of each word.
  2. Initialize position 0 as reachable.
  3. For each reachable position, walk the trie along the string from that position.
  4. Mark positions reached at the end of a dictionary word.
  5. Return whether the end of the string is reachable.
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        # None marks the end of a word in the trie.
        trie: dict = {}

        for word in wordDict:
            node = trie
            for char in word:
                node = node.setdefault(char, {})
            node[None] = True

        reachable = [False] * (len(s) + 1)
        reachable[0] = True

        for start in range(len(s)):
            if not reachable[start]:
                continue

            node = trie
            end = start

            while end < len(s) and s[end] in node:
                node = node[s[end]]
                end += 1

                if None in node:
                    reachable[end] = True

        return reachable[len(s)]

Complexity:

  • Time: O(nL), where n is the string length and L is the longest dictionary word.
  • Space: O(D + n), where D is the total number of characters across dictionary words.

Common follow-ups

  • How can you return one valid segmentation? Store a predecessor position whenever a position first becomes reachable, then backtrack from the end.
  • How can you return all valid segmentations? Use memoization to collect possible suffix segmentations from each position.
  • What if the dictionary changes frequently? Consider a data structure that supports efficient updates, such as maintaining the trie incrementally.
CodingMediumPocket GemsSoftware Engineer

6. Sort Colors (LeetCode)

Model answer

The task

Rearrange an array containing only 0, 1, and 2 so the values appear in ascending order. Modify the array in place.

Key idea

Use three pointers to divide the array into regions: 0s at the front, 2s at the back, and 1s in between. Each step places one value into its correct region, so the array is processed in one pass without extra storage.

Approach

  1. Set low to the start and high to the end of the array.
  2. Scan with current, starting at the beginning.
  3. If the current value is 0, swap it with low, then advance both pointers.
  4. If it is 1, advance current.
  5. If it is 2, swap it with high and move high left. Do not advance current, since the swapped-in value still needs inspection.
  6. Stop when current passes high.
class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """Sort nums in place; return no value."""
        low = 0
        current = 0
        high = len(nums) - 1

        while current <= high:
            if nums[current] == 0:
                nums[low], nums[current] = nums[current], nums[low]
                low += 1
                current += 1
            elif nums[current] == 1:
                current += 1
            else:  # nums[current] == 2
                nums[current], nums[high] = nums[high], nums[current]
                high -= 1

Complexity:

  • Time: O(n), where n is the number of values; each pointer moves only across the array.
  • Space: O(1), since the rearrangement is in place.

Common follow-ups

  • What if there are k distinct values? Use counting or a generalized partitioning strategy; the best approach depends on whether extra passes or storage are allowed.
  • Must the sort be stable? This in-place partitioning is not stable; preserving the order of equal values may require extra space or a different algorithm.
  • What if values outside 0, 1, and 2 appear? Validate or define their placement, then adapt the partitioning logic accordingly.
CodingMediumPocket GemsSoftware Engineer

7. 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.
CodingMediumPocket GemsSoftware Engineer

8. Clone Graph (LeetCode)

Model answer

The task

Given a reference to a node in an undirected graph, return a deep copy of the graph. The copy must preserve each node’s value and connections while using entirely new node objects.

Key idea

Keep a map from each original node to its clone. When visiting a node, create and record its clone before exploring its neighbors; this both prevents revisiting cycles and preserves shared connections.

Approach

  1. If the input node is None, return None.
  2. Start a depth-first search from the input node.
  3. For each node, return its existing clone if it has already been copied.
  4. Otherwise, create and record a clone, then recursively copy each neighbor.
  5. Return the clone of the starting node.
# LeetCode provides the Node class.
class Solution:
    def cloneGraph(self, node):
        if node is None:
            return None

        clones = {}

        def copy(current):
            if current in clones:
                return clones[current]

            # Record the clone before traversing neighbors to handle cycles.
            cloned = Node(current.val)
            clones[current] = cloned

            for neighbor in current.neighbors:
                cloned.neighbors.append(copy(neighbor))

            return cloned

        return copy(node)

Complexity:

  • Time: O(V + E), visiting each reachable node and edge once.
  • Space: O(V), for the clone map and recursion stack.

Common follow-ups

  • What if the graph is disconnected? Run the traversal from every unvisited node.
  • Can this be done iteratively? Yes; use a queue and the same original-to-clone map.
  • What if node values are not unique? Use node objects as map keys, not their values.
  • How can you verify the result is a deep copy? Check that corresponding nodes differ by identity while their values and adjacency structure match.
CodingMediumPocket GemsSoftware Engineer

9. Find All Duplicates in an Array (LeetCode)

Model answer

The task

Return every value that occurs twice in an array whose values are in the range 1 through the array length. Each value occurs at most twice.

Key idea

Use each value as an index into the array. Negate the value at that index to mark it as seen; if it is already negative, the current value is a duplicate. This avoids a separate tracking structure, but modifies the input array.

Approach

  1. Create an empty list for duplicates.
  2. For each number, use its absolute value to compute its corresponding index.
  3. If the value at that index is negative, add the number to the result.
  4. Otherwise, negate the value at that index to mark it as seen.
  5. Return the result.
from typing import List

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        duplicates = []

        for value in nums:
            index = abs(value) - 1

            if nums[index] < 0:
                duplicates.append(abs(value))
            else:
                nums[index] = -nums[index]

        return duplicates

Complexity:

  • Time: O(n), where n is the array length; each element is processed once.
  • Space: O(1) auxiliary space, excluding the list of returned duplicates.

Common follow-ups

  • How would you avoid modifying the input? Use a set to track seen values, at the cost of O(n) extra space.
  • What if values are not restricted to 1 through n? Use a hash set, since values can no longer safely serve as array indices.
  • What if some values occur more than twice? The marking method still reports each value after its first occurrence as a duplicate; use a frequency map if counts are needed.
  • Can the output be sorted? Sort the result before returning it, adding O(k log k) time for k duplicates.
CodingMediumPocket GemsSoftware Engineer

10. Inorder Successor in BST (LeetCode)

Model answer

The task

Given a node p in a binary search tree, find the next node after it in inorder order. Return None if there is no successor.

Key idea

If p has a right subtree, its successor is the leftmost node there. Otherwise, the successor is the nearest ancestor whose value is greater than p’s value.

Approach

  1. If p has a right child, move to that subtree.
  2. Keep moving left; return the last node reached.
  3. Otherwise, search from the root, tracking the smallest node greater than p.
  4. Move left when the current value exceeds p’s value; otherwise, move right.
  5. Return the tracked candidate, or None if none exists.
class Solution:
    def inorderSuccessor(self, root: "TreeNode", p: "TreeNode") -> "TreeNode":
        # The successor is the smallest node in p's right subtree.
        if p.right:
            node = p.right
            while node.left:
                node = node.left
            return node

        # Otherwise, find the closest ancestor greater than p.
        successor = None
        node = root
        while node:
            if p.val < node.val:
                successor = node
                node = node.left
            else:
                node = node.right

        return successor

Complexity:

  • Time: O(h), where h is the tree height.
  • Space: O(1), using only a few references.

Common follow-ups

  • What if nodes have parent pointers? Walk upward until first moving up from a left child; that parent is the successor.
  • What if p is the maximum node? It has no successor, so return None.
  • What if duplicate values are allowed? Define a duplicate ordering rule and use it consistently when searching.
CodingMediumPocket GemsSoftware Engineer

11. Top K Frequent Words (LeetCode)

Model answer

The task

Given a list of words and an integer k, return the k most frequent words. Rank words by decreasing frequency, breaking ties by alphabetical order.

Key idea

Count each word, then put one entry per distinct word in a min-heap. Store entries as (-frequency, word) so the heap returns higher frequencies first, and alphabetical order first when frequencies tie.

Approach

  1. Count how many times each word occurs.
  2. Build a heap with one (-count, word) entry per distinct word.
  3. Pop the heap k times and collect the words.
  4. Return the collected words in pop order.
from collections import Counter
import heapq
from typing import List

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        counts = Counter(words)

        # Negative counts make the min-heap return the highest frequencies first.
        # The word provides alphabetical tie-breaking.
        heap = [(-count, word) for word, count in counts.items()]
        heapq.heapify(heap)

        return [heapq.heappop(heap)[1] for _ in range(k)]

Complexity:

  • Time: O(n + u + k log u), where n is the number of words and u is the number of distinct words.
  • Space: O(u), for the frequency map and heap.

Common follow-ups

  • Can you avoid sorting or heap operations? Use frequency buckets, then visit words alphabetically within each frequency.
  • What if k is close to the number of distinct words? Sorting all distinct words may be simpler, with O(u log u) time.
  • What if words arrive as a stream? Exact counts may require retaining counts for all distinct words; bounded-memory approaches can instead estimate frequent words.
CodingHardPocket GemsSoftware Engineer

12. Alien Dictionary (LeetCode)

Model answer

The task

Infer a character order consistent with a list of words already sorted in an unknown alphabet. Return one valid order, or an empty string if the list is inconsistent.

Key idea

For each adjacent pair of words, their first differing characters reveal a precedence rule. These rules form a directed graph; a topological sort produces a valid character order if and only if the graph has no cycle.

Approach

  1. Add every character to the graph, including characters with no ordering rules.
  2. Compare adjacent words and add an edge from the first differing character in the earlier word to the one in the later word.
  3. If the earlier word is a strict extension of the later word, return "" because that ordering is impossible.
  4. Use Kahn’s algorithm to process zero-indegree characters and build an order.
  5. If not all characters are processed, the rules contain a cycle; return "".
from collections import defaultdict, deque
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Include characters that do not appear in any precedence rule.
        graph = {char: set() for word in words for char in word}
        indegree = {char: 0 for char in graph}

        # Adjacent words are enough to infer all necessary ordering rules.
        for first, second in zip(words, words[1:]):
            limit = min(len(first), len(second))

            for i in range(limit):
                if first[i] != second[i]:
                    before, after = first[i], second[i]
                    # Avoid counting duplicate rules more than once.
                    if after not in graph[before]:
                        graph[before].add(after)
                        indegree[after] += 1
                    break
            else:
                # A longer word cannot precede its own strict prefix.
                if len(first) > len(second):
                    return ""

        queue = deque(char for char in graph if indegree[char] == 0)
        order = []

        while queue:
            char = queue.popleft()
            order.append(char)

            for neighbor in graph[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        # Unprocessed characters indicate a cycle.
        return "".join(order) if len(order) == len(graph) else ""

Complexity:

  • Time: O(C + V + E), where C is the total input length, V the number of distinct characters, and E the number of inferred rules.
  • Space: O(V + E) for the graph, indegrees, and queue.

Common follow-ups

  • How can you tell whether the ordering is unique? Check whether the queue ever contains more than one character.
  • What if there are multiple valid orders? Any topological ordering is acceptable; changing the queue policy can choose a different one.
  • Can you return a cycle when the input is inconsistent? Track DFS parents or predecessor links during topological processing to reconstruct one.
CodingHardPocket GemsSoftware Engineer

13. Non-negative Integers without Consecutive Ones (LeetCode)

Model answer

The task

Count the integers from zero through n whose binary representations contain no adjacent 1 bits.

Key idea

For any fixed prefix, the number of valid suffixes of length i follows a Fibonacci recurrence: a valid suffix either starts with 0, or starts with 10. Scan n from its most significant bit, counting valid numbers that first become smaller at each 1 bit.

Approach

  1. Precompute dp[i], the number of valid bit strings of length i.
  2. Scan the bits of n from left to right.
  3. Whenever a bit is 1, add dp[i]: these are the valid numbers that use 0 there and any valid i-bit suffix.
  4. If two adjacent bits of n are 1, stop; n itself and all later prefixes are invalid.
  5. If no adjacent ones are found, include n in the count.
class Solution:
    def findIntegers(self, n: int) -> int:
        bit_count = n.bit_length()

        # dp[i] counts valid binary strings of length i.
        dp = [0] * (bit_count + 1)
        dp[0] = 1
        if bit_count >= 1:
            dp[1] = 2

        for i in range(2, bit_count + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        total = 0
        previous_bit_was_one = False

        for i in range(bit_count - 1, -1, -1):
            if (n >> i) & 1:
                # Count numbers that first become smaller at this bit.
                total += dp[i]

                if previous_bit_was_one:
                    return total

                previous_bit_was_one = True
            else:
                previous_bit_was_one = False

        # n itself is valid.
        return total + 1

Complexity:

  • Time: O(log n), for the bit scan and DP construction.
  • Space: O(log n), for the DP table.

Common follow-ups

  • How would you count valid numbers in a range [a, b]? Use count(b) - count(a - 1).
  • Can the DP table use constant space? Yes; generate the needed Fibonacci values with rolling variables.
  • What happens when n is zero? The scan is empty, and the method returns one for the number zero.
CodingHardPocket GemsSoftware Engineer

14. Shortest Palindrome (LeetCode)

Model answer

The task

Given a string, prepend the fewest characters needed to make it a palindrome. Return the resulting string.

Key idea

Only the longest prefix of the original string that is already a palindrome can remain in place. KMP prefix-function matching finds its length by comparing the string with its reverse.

Approach

  1. Build a sequence from the string, a unique separator, and the reversed string.
  2. Compute the KMP prefix-function for that sequence.
  3. Its final value is the length of the longest palindromic prefix.
  4. Reverse the unmatched suffix and prepend it to the original string.
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        # Use a unique object as a separator, so it cannot match any character.
        separator = object()
        sequence = list(s) + [separator] + list(reversed(s))

        # Compute the KMP prefix-function.
        prefix = [0] * len(sequence)
        for i in range(1, len(sequence)):
            j = prefix[i - 1]

            while j > 0 and sequence[i] != sequence[j]:
                j = prefix[j - 1]

            if sequence[i] == sequence[j]:
                j += 1

            prefix[i] = j

        # The final prefix-function value is the longest palindromic prefix length.
        palindrome_length = prefix[-1]
        unmatched_suffix = s[palindrome_length:]

        return unmatched_suffix[::-1] + s

Complexity:

  • Time: O(n), for building the sequence and computing the prefix-function.
  • Space: O(n), for the sequence and prefix-function arrays.

Common follow-ups

  • Can you solve it with rolling hash? Yes; compare prefix and suffix hashes while carefully handling collisions.
  • How would you avoid extra sequence space? Compute the KMP prefix-function incrementally over the combined sequence.
  • What if the goal is to append characters instead? Find the longest palindromic suffix and append the reverse of the unmatched prefix.
CodingHardPocket GemsSoftware Engineer

15. Basic Calculator III (LeetCode)

Model answer

The task

Evaluate an arithmetic expression containing integers, +, -, *, /, parentheses, and optional whitespace. Division should truncate toward zero.

Key idea

Use recursive descent with separate parsing levels for expressions, terms, unary signs, and parenthesized values. This naturally enforces precedence and lets parentheses recurse; implement division explicitly to avoid Python’s floor-rounding behavior.

Approach

  1. Keep a cursor into the expression and skip whitespace whenever reading a token.
  2. Parse an expression as terms combined by + or -.
  3. Parse a term as unary values combined by * or /.
  4. Parse repeated unary signs, then either an integer or a parenthesized expression.
  5. For division, divide absolute values and restore the sign to truncate toward zero.
class Solution:
    def calculate(self, s: str) -> int:
        i = 0
        n = len(s)

        def skip_spaces() -> None:
            nonlocal i
            while i < n and s[i].isspace():
                i += 1

        def parse_primary() -> int:
            nonlocal i
            skip_spaces()

            if s[i] == "(":
                i += 1
                value = parse_expression()
                skip_spaces()
                i += 1  # Consume ')'.
                return value

            value = 0
            while i < n and s[i].isdigit():
                value = value * 10 + int(s[i])
                i += 1
            return value

        def parse_unary() -> int:
            nonlocal i
            sign = 1
            skip_spaces()

            while i < n and s[i] in "+-":
                if s[i] == "-":
                    sign = -sign
                i += 1
                skip_spaces()

            return sign * parse_primary()

        def trunc_div(a: int, b: int) -> int:
            quotient = abs(a) // abs(b)
            return -quotient if (a < 0) != (b < 0) else quotient

        def parse_term() -> int:
            nonlocal i
            value = parse_unary()

            while True:
                skip_spaces()
                if i == n or s[i] not in "*/":
                    return value

                op = s[i]
                i += 1
                right = parse_unary()

                if op == "*":
                    value *= right
                else:
                    value = trunc_div(value, right)

        def parse_expression() -> int:
            nonlocal i
            value = parse_term()

            while True:
                skip_spaces()
                if i == n or s[i] not in "+-":
                    return value

                op = s[i]
                i += 1
                right = parse_term()
                value = value + right if op == "+" else value - right

        return parse_expression()

Complexity:

  • Time: O(n), where n is the expression length.
  • Space: O(d), for recursive calls up to parenthesis nesting depth d.

Common follow-ups

  • How would you support exponentiation? Add a parsing level with the correct precedence and associativity.
  • How would you report malformed input? Validate tokens and closing parentheses, then raise a parsing error.
  • What if nesting is extremely deep? Replace recursive parenthesis parsing with an explicit stack.

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