Citadel interview questions & answers

20 real Citadel interview questions with full model answers — Product & growth, Coding. Drawn from the same verified bank ChannelPulse drills from (77 Citadel questions in total).

CodingEasyCitadelSoftware Engineer

1. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyCitadelSoftware Engineer

2. Sqrt(x) (LeetCode)

Model answer

The task

Given a nonnegative integer x, return the greatest integer whose square is no larger than x. The result is the integer square root, rounded down.

Key idea

The predicate “m squared is no larger than x” is monotonic: it is true up to the square root and false afterward. Binary search finds the largest value for which it is true.

Approach

  1. Return x directly when it is 0 or 1.
  2. Search candidate roots between 1 and x // 2.
  3. For each midpoint, compare mid with x // mid, avoiding multiplication and its potential overflow in fixed-width languages.
  4. If mid <= x // mid, record it as a valid answer and search higher; otherwise, search lower.
  5. Return the largest valid candidate.
class Solution:
    def mySqrt(self, x: int) -> int:
        # The square root of 0 or 1 is the number itself.
        if x < 2:
            return x

        low, high = 1, x // 2
        answer = 1

        while low <= high:
            mid = (low + high) // 2

            # Equivalent to mid * mid <= x, without multiplying.
            if mid <= x // mid:
                answer = mid
                low = mid + 1
            else:
                high = mid - 1

        return answer

Complexity:

  • Time: O(log x), since binary search halves the search range each iteration.
  • Space: O(1), using a fixed number of variables.

Common follow-ups

  • How would you compute the root using Newton’s method? Repeatedly update a guess with (guess + x / guess) / 2 until it stops decreasing.
  • How would you return a floating-point square root? Continue with a numeric method to the desired precision instead of returning an integer floor.
  • What if the input could be negative? Define the desired behavior first; integer square root is typically restricted to nonnegative inputs.
CodingEasyCitadelSoftware Engineer

3. Moving Average from Data Stream (LeetCode)

Model answer

The task

Design an object that receives values one at a time and returns the average of the most recent size values. Until that many values have arrived, average all values seen so far.

Key idea

Keep the current window in a queue and track its sum. When the window is full, remove its oldest value before adding the new one.

Approach

  1. Store the window size, an empty deque, and a running sum.
  2. For each new value, remove the oldest value if the queue is already full.
  3. Add the new value to both the queue and the running sum.
  4. Return the sum divided by the number of values currently in the queue.
from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        if size <= 0:
            raise ValueError("size must be positive")

        self.size = size
        self.window = deque()
        self.total = 0.0

    def next(self, val: int) -> float:
        if len(self.window) == self.size:
            self.total -= self.window.popleft()

        self.window.append(val)
        self.total += val

        return self.total / len(self.window)

Complexity:

  • Time: O(1) per next call; each value is added and removed at most once.
  • Space: O(size) for the queue holding the current window.

Common follow-ups

  • What if values arrive from multiple threads? Protect updates to the queue and sum with a lock.
  • How would you support changing the window size? Update the size and remove oldest values until the queue fits.
  • What if the stream is too large to keep in memory? The queue already stores only the most recent size values.
  • Can you return the average over a time duration instead of a fixed number of values? Store timestamps and evict entries outside the duration before calculating.
CodingEasyCitadelSoftware Engineer

4. Fizz Buzz (LeetCode)

Model answer

The task

For each integer from 1 through n, produce a string: use "Fizz" for multiples of 3, "Buzz" for multiples of 5, and "FizzBuzz" for multiples of both. Otherwise, use the number’s decimal representation.

Key idea

Check divisibility by both numbers before checking either one separately. Build the result in order with a single pass.

Approach

  1. Create an empty list for the output strings.
  2. Visit each integer from 1 through n.
  3. If it is divisible by both 3 and 5, append "FizzBuzz".
  4. Otherwise, append the matching single word, or the number as a string.
  5. Return the list.
from typing import List

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        result = []

        for number in range(1, n + 1):
            if number % 15 == 0:
                result.append("FizzBuzz")
            elif number % 3 == 0:
                result.append("Fizz")
            elif number % 5 == 0:
                result.append("Buzz")
            else:
                result.append(str(number))

        return result

Complexity:

  • Time: O(n), since each number is processed once.
  • Space: O(n), for the returned list of strings.

Common follow-ups

  • How would you support a different set of divisors and words? Iterate over divisor-word pairs and combine the words for every divisor that divides the current number.
  • How could you avoid checking divisibility with modulo? Maintain counters for each divisor and reset them when they reach that divisor.
  • What if the output is too large to keep in memory? Yield each string as it is produced, or write it directly to a stream.
CodingEasyCitadelSoftware Engineer

5. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingEasyCitadelSoftware Engineer

6. Climbing Stairs (LeetCode)

Model answer

The task

Count how many distinct ways there are to reach the top of a staircase with n steps when each move advances either one or two steps.

Key idea

To reach step i, the last move must come from step i - 1 or i - 2. Thus the number of ways to reach i is the sum of the ways to reach those two earlier steps. Only the previous two counts are needed, so there is no need to store a full table.

Approach

  1. Set the number of ways to reach step 0 to 1, representing the single empty sequence of moves.
  2. Set the number of ways to reach step 1 to 1.
  3. For each step from 2 through n, add the counts for the preceding two steps.
  4. Return the count for step n.
class Solution:
    def climbStairs(self, n: int) -> int:
        # Ways to reach steps 0 and 1.
        two_back = 1
        one_back = 1

        # Build the count using the two preceding results.
        for _ in range(2, n + 1):
            current = two_back + one_back
            two_back = one_back
            one_back = current

        return one_back

Complexity:

  • Time: O(n), since each step is processed once.
  • Space: O(1), since only two prior counts are retained.

Common follow-ups

  • What if each move can advance 1, 2, or 3 steps? Sum the counts for the previous three steps.
  • What if the result must be returned modulo a number? Apply the modulus after each addition.
  • What if some steps are forbidden? Set their ways count to zero and use dynamic programming for the allowed steps.
CodingEasyCitadelSoftware Engineer

7. Write Python code to calculate variance.

Model answer


def variance(values, sample=False):
    """Calculate population variance, or sample variance if sample=True."""
    count = 0
    mean = 0.0
    sum_squared_deviations = 0.0

    # Welford's algorithm is numerically stable and uses constant extra space.
    for value in values:
        count += 1
        delta = value - mean
        mean += delta / count
        sum_squared_deviations += delta * (value - mean)

    denominator = count - 1 if sample else count
    if denominator <= 0:
        raise ValueError("Need at least one value for population variance, or two for sample variance")

    return sum_squared_deviations / denominator

numbers = [2, 4, 6, 8]
print(variance(numbers))         # Population variance: 5.0
print(variance(numbers, True))   # Sample variance: 6.666666666666667
  • Uses Welford’s algorithm to avoid the numerical instability of computing E[x²] - E[x]².
  • Population variance divides by n; sample variance divides by n - 1.

Complexity: Time O(n); space O(1).

CodingMediumCitadelSoftware Engineer

8. Evaluate Division (LeetCode)

Model answer

The task

Given equations that define ratios between variables, answer queries asking for a ratio between two variables. Return -1.0 when the ratio cannot be determined.

Key idea

Represent each equation as two directed graph edges: from a to b with weight a / b, and from b to a with the reciprocal weight. A path’s edge weights multiply to give the ratio between its endpoints.

Approach

  1. Build a weighted adjacency list from the equations.
  2. For each query, return -1.0 if either variable is unknown.
  3. Otherwise, use DFS to find a path between the variables, multiplying edge weights along the way.
  4. Track visited variables so cycles do not cause repeated exploration.
  5. If the variables are the same and known, the ratio is 1.0.
from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self,
        equations: List[List[str]],
        values: List[float],
        queries: List[List[str]]
    ) -> List[float]:
        graph = defaultdict(list)

        for (numerator, denominator), value in zip(equations, values):
            graph[numerator].append((denominator, value))
            graph[denominator].append((numerator, 1.0 / value))

        def find_ratio(start: str, target: str) -> float:
            if start not in graph or target not in graph:
                return -1.0
            if start == target:
                return 1.0

            stack = [(start, 1.0)]
            visited = {start}

            while stack:
                variable, product = stack.pop()

                for neighbor, edge_value in graph[variable]:
                    if neighbor in visited:
                        continue

                    next_product = product * edge_value
                    if neighbor == target:
                        return next_product

                    visited.add(neighbor)
                    stack.append((neighbor, next_product))

            return -1.0

        return [find_ratio(a, b) for a, b in queries]

Complexity:

  • Time: O(Q(V + E)), where each query may traverse the full graph.
  • Space: O(V + E) for the graph and the DFS state.

Common follow-ups

  • How can repeated queries be sped up? Use weighted union-find to answer each query in near-constant time after preprocessing.
  • How would you handle inconsistent equations? Detect conflicting ratios when connecting variables or revisiting an already-connected pair.
  • What if the graph is very large but queries are few? Keep DFS/BFS per query to avoid more elaborate preprocessing.
CodingMediumCitadelSoftware Engineer

9. 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.
CodingMediumCitadelSoftware Engineer

10. Combination Sum (LeetCode)

Model answer

The task

Given positive candidate values and a target, find every distinct combination that sums to the target. A candidate may be used multiple times, but combinations that differ only in order should appear once.

Key idea

Build each combination in nondecreasing candidate order. After choosing a value, recurse from its same index so it can be reused; this ordering prevents permutations from being generated.

Approach

  1. Sort the candidates to process them in ascending order and enable early stopping.
  2. Use backtracking with the current start index, remaining sum, and chosen values.
  3. When the remaining sum is zero, save a copy of the chosen values.
  4. Otherwise, try each candidate from the start index onward.
  5. Stop trying larger candidates once one exceeds the remaining sum.
from typing import List

class Solution:
    def combinationSum(
        self, candidates: List[int], target: int
    ) -> List[List[int]]:
        candidates.sort()
        results: List[List[int]] = []
        current: List[int] = []

        def search(start: int, remaining: int) -> None:
            if remaining == 0:
                results.append(current.copy())
                return

            for index in range(start, len(candidates)):
                value = candidates[index]

                # Later values are no smaller, so none can fit either.
                if value > remaining:
                    break

                current.append(value)
                # Keep index unchanged to allow reusing this candidate.
                search(index, remaining - value)
                current.pop()

        search(0, target)
        return results

Complexity:

  • Time: O(N^d + R·d) as a loose worst-case bound, where N is the number of candidates, d = target / smallest candidate, and R is the number of results. The search explores candidate sequences up to depth d.
  • Space: O(d) auxiliary space for the recursion and current combination, excluding the returned results.

Common follow-ups

  • How would you avoid duplicate combinations if the input can contain repeated values? Deduplicate the sorted candidates before searching.
  • How would you find just one combination? Return immediately when a successful path is found.
  • What if each candidate can be used at most once? Recurse with index + 1 instead of index.
  • How can you handle a very large target? Use dynamic programming or memoization if the goal is counting or checking existence rather than listing every combination.
CodingMediumCitadelSoftware Engineer

11. Design Circular Queue (LeetCode)

Model answer

The task

Implement a fixed-capacity queue that wraps around its storage instead of shifting elements. It must support insertion, removal, checking whether it is empty or full, and reading the front and rear values.

Key idea

Store elements in a fixed-size array and track the front index and number of stored elements. Compute positions modulo the capacity so the queue reuses slots at the beginning of the array after reaching its end.

Approach

  1. Initialize an array of capacity k, a front index of 0, and a size of 0.
  2. On insertion, fail if full; otherwise write at (front + size) % capacity and increase the size.
  3. On removal, fail if empty; otherwise advance the front index modulo capacity and decrease the size.
  4. Read the front at the front index and the rear at (front + size - 1) % capacity.
  5. Return -1 for front or rear queries when the queue is empty.
class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.values = [0] * k
        self.front_index = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        rear_index = (self.front_index + self.size) % self.capacity
        self.values[rear_index] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.front_index = (self.front_index + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.values[self.front_index]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        rear_index = (self.front_index + self.size - 1) % self.capacity
        return self.values[rear_index]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Complexity:

  • Time: O(1) per operation; each operation updates or reads a constant number of values.
  • Space: O(k); the fixed-size array stores up to k elements.

Common follow-ups

  • How can the queue distinguish full from empty without a size field? Reserve one array slot, or track a separate full flag.
  • What changes for a dynamically growing queue? Allocate a larger array when full and copy elements in queue order.
  • How would you make it thread-safe? Protect operations with a lock, or use a suitable concurrent queue implementation.
CodingMediumCitadelSoftware Engineer

12. Course Schedule II (LeetCode)

Model answer

The task

Return an ordering of all courses that satisfies the prerequisite relationships. If no such ordering exists because the relationships contain a cycle, return an empty list.

Key idea

Model each course as a graph node, with an edge from a prerequisite to the course that depends on it. Kahn’s topological-sort algorithm repeatedly takes courses with no remaining prerequisites; if it cannot take every course, the graph contains a cycle.

Approach

  1. Build an adjacency list and count each course’s prerequisites as its indegree.
  2. Add all zero-indegree courses to a queue.
  3. Remove courses from the queue, adding each to the result and reducing the indegree of its dependent courses.
  4. Add a dependent course to the queue when its indegree reaches zero.
  5. Return the result if it includes every course; otherwise, return an empty list.
from collections import deque
from typing import List

class Solution:
    def findOrder(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> List[int]:
        # Edges point from prerequisite to dependent course.
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1

        ready = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )
        order = []

        while ready:
            course = ready.popleft()
            order.append(course)

            for dependent in graph[course]:
                indegree[dependent] -= 1
                if indegree[dependent] == 0:
                    ready.append(dependent)

        # A cycle prevents all courses from being added.
        return order if len(order) == numCourses else []

**Complexity:**

- Time: O(V + E), where V is the number of courses and E is the number of prerequisite relationships.
- Space: O(V + E) for the graph, indegrees, queue, and result.

**Common follow-ups**

- How can DFS solve this? Use three node states—unvisited, visiting, and visited—to detect cycles while building a topological order.
- How can the algorithm return the number of courses that can be completed? Return the length of the processed order.
- How can you choose the smallest-numbered available course at each step? Use a min-heap instead of a queue, giving O((V + E) log V) time.
CodingMediumCitadelSoftware Engineer

13. Next Permutation (LeetCode)

Model answer

The task

Rearrange the array in place to produce the next lexicographically greater ordering of its values. If no greater ordering exists, wrap around to the smallest ordering.

Key idea

The suffix after the rightmost position where the sequence increases is in descending order, so it is already the largest arrangement of those values. Swap that position with the smallest value in the suffix that is still larger, then reverse the suffix to make it as small as possible.

Approach

  1. Scan from right to left to find the rightmost index whose value is smaller than the value after it.
  2. If such an index exists, scan from the end to find the rightmost value larger than the pivot, then swap them.
  3. Reverse the portion after the pivot. This also handles the case where no pivot exists: the whole array becomes ascending.
  4. Mutate the input list directly.
from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)

        # Find the rightmost position that can be increased.
        pivot = n - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            # The suffix is descending; its rightmost value greater
            # than the pivot is the smallest value that can replace it.
            successor = n - 1
            while nums[successor] <= nums[pivot]:
                successor -= 1

            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        # Reverse the suffix to make it the smallest possible ordering.
        left, right = pivot + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Complexity:

  • Time: O(n), with a constant number of linear scans.
  • Space: O(1), since the rearrangement is done in place.

Common follow-ups

  • Why choose the rightmost pivot? It preserves the longest possible prefix, making the next ordering as close as possible.
  • How are duplicate values handled? The strict comparisons skip equal values and still select the correct next ordering.
  • What if the input is already in descending order? No pivot exists, so reversing the full array produces the smallest ordering.
  • How would you return a new list instead? Copy the input first, then apply the same in-place algorithm to the copy.
CodingMediumCitadelSoftware Engineer

14. Binary Tree Zigzag Level Order Traversal (LeetCode)

Model answer

The task

Return the values of a binary tree grouped by depth, alternating the direction in which each level is read: left-to-right, then right-to-left.

Key idea

Use breadth-first search so nodes are processed one level at a time. Keep the queue order unchanged, but collect each level in the appropriate direction.

Approach

  1. Return an empty list if the tree is empty.
  2. Initialize a queue with the root and mark the first level as left-to-right.
  3. For each level, process exactly the number of nodes currently in the queue.
  4. Add each node’s children to the queue in normal left-to-right order.
  5. Collect level values from the left or right end as appropriate, then switch direction.
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        if root is None:
            return []

        result = []
        queue = deque([root])
        left_to_right = True

        while queue:
            level_values = deque()

            # The queue length at the start gives this level's node count.
            for _ in range(len(queue)):
                node = queue.popleft()

                if left_to_right:
                    level_values.append(node.val)
                else:
                    level_values.appendleft(node.val)

                # Keep the queue in standard breadth-first order.
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            result.append(list(level_values))
            left_to_right = not left_to_right

        return result

Complexity:

  • Time: O(n), where n is the number of nodes; each node is processed once.
  • Space: O(n), including the returned levels; the queue holds at most one level’s nodes.

Common follow-ups

  • Can you implement this recursively? Yes; group nodes by depth and place each value at the appropriate end for that depth.
  • What if the traversal should start right-to-left? Initialize the direction flag to False.
  • How can you reduce per-level collection overhead? Use a list and place values at calculated indices instead of using a deque.
  • What happens for an empty tree or a single-node tree? The empty tree returns an empty list; a single node returns one level.
CodingMediumCitadelSoftware Engineer

15. Knight Probability in Chessboard (LeetCode)

Model answer

The task

Find the probability that a knight, starting at a given cell on an n × n board, remains on the board after making exactly k random moves. Each of the knight’s eight possible moves is equally likely.

Key idea

Track the probability of being at each cell after each move. For each cell, distribute its probability equally among its valid destinations; probability assigned to off-board destinations is discarded.

Approach

  1. Initialize a probability table with probability 1.0 at the starting cell and 0.0 elsewhere.
  2. Repeat for each of the k moves, creating a fresh table for the next move.
  3. For each cell with nonzero probability, send one eighth of it to each valid knight destination.
  4. Sum the final table; this is the probability of still being on the board.
class Solution:
    def knightProbability(
        self, n: int, k: int, row: int, column: int
    ) -> float:
        moves = (
            (2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2),
        )

        # Probability of occupying each cell after the current number of moves.
        probability = [[0.0] * n for _ in range(n)]
        probability[row][column] = 1.0

        for _ in range(k):
            next_probability = [[0.0] * n for _ in range(n)]

            for r in range(n):
                for c in range(n):
                    current = probability[r][c]
                    if current == 0.0:
                        continue

                    share = current / 8.0
                    for dr, dc in moves:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n:
                            next_probability[nr][nc] += share

            probability = next_probability

        return sum(map(sum, probability))

Complexity:

  • Time: O(k · n²), processing each cell and its eight moves per step.
  • Space: O(n²), storing the current and next probability tables.

Common follow-ups

  • How can memory use be reduced? Keep only the current and next tables, as this solution does.
  • What if moves have different probabilities? Distribute each cell’s probability using the corresponding move weights.
  • What if k is extremely large? Represent transitions as a matrix and use exponentiation by squaring.
CodingMediumCitadelSoftware Engineer

16. 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.
CodingMediumCitadelSoftware Engineer

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

18. 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.
CodingMediumCitadelSoftware Engineer

19. Time Based Key-Value Store (LeetCode)

Model answer

The task

Design a key-value store that records values with timestamps. A lookup for a key and time returns the value from the latest timestamp not later than the requested time, or an empty string if none exists.

Key idea

Keep each key’s timestamps and values in parallel, ordered by timestamp. Since timestamps for a key arrive in increasing order, writes append in constant time, and lookups use binary search.

Approach

  1. Map each key to a pair of lists: timestamps and corresponding values.
  2. On set, append the timestamp and value to that key’s lists.
  3. On get, use binary search to find the first timestamp greater than the requested time.
  4. Return the value immediately before that position, or an empty string if the position is zero or the key is missing.
from bisect import bisect_right

class TimeMap:
    def __init__(self):
        # Each key maps to its ordered timestamps and matching values.
        self.data: dict[str, tuple[list[int], list[str]]] = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = ([], [])

        timestamps, values = self.data[key]
        timestamps.append(timestamp)
        values.append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""

        timestamps, values = self.data[key]
        # The insertion position is just after the latest eligible timestamp.
        index = bisect_right(timestamps, timestamp) - 1

        if index < 0:
            return ""
        return values[index]

Complexity:

  • Time: set is O(1); get is O(log n), where n is the number of entries for that key.
  • Space: O(N), storing all N key-value-timestamp entries.

Common follow-ups

  • What if timestamps arrive out of order? Insert each record at its sorted position, which takes O(n) per write, or use a balanced search tree.
  • How would you reduce memory usage? Expire old records when they can no longer be queried, or compress retained history if the API permits.
  • How would you handle many concurrent reads and writes? Protect updates with synchronization, or use immutable snapshots for read-heavy workloads.
Product & growthMediumCitadelGroup Product Manager

20. How would you prioritize development projects, down to the level of individual user stories?

Model answer

Clarify the objective I would prioritize against the product and company outcomes, not the apparent urgency or volume of requests. First I’d confirm the planning horizon, strategic goals, customer segments, capacity, and any contractual, regulatory, or reliability commitments. If we lack alignment on the outcome, story-level ranking will create false precision.

Build a decision hierarchy

  1. Portfolio: Allocate capacity across strategic bets, customer commitments, reliability, and discovery. Make the opportunity cost visible; for example, a quarter spent on a major enterprise capability is a quarter not spent on self-serve growth.
  2. Initiatives: Compare opportunities using customer impact, business value, confidence, effort, and risk. A useful lightweight score is impact × confidence ÷ effort, adjusted for strategic fit and time criticality. Use it to structure discussion, not to override judgment.
  3. Features and stories: Define the user outcome and acceptance criteria, then order the smallest independently valuable slices. Check dependencies, risk, and learning value—not just story-point efficiency.

Prioritize at story level For each story, ask: Which user problem does this solve? Is it necessary for the MVP or a dependency? What evidence supports it? What is the cost of delay, and what is the smallest safe release? For example, in an integration setup initiative, I might prioritize a clear authentication error and recovery path before adding support for a second provider, if research shows failed authentication blocks most users. I would still include accessibility, instrumentation, and security requirements as part of “done,” not as optional polish.

Make trade-offs explicit I’d use a shared backlog with a clear rationale, confidence level, owner, and outcome metric. I’d reserve capacity for unplanned work based on actual historical interruption, and protect critical reliability work. I’d avoid treating a scoring model as objective truth: strategic bets may have uncertain near-term returns, and high-risk work may deserve an early spike rather than a full commitment.

Review and learn At planning, commit to outcomes and a bounded set of work; during delivery, re-rank when customer evidence, dependencies, or estimates change. After release, compare results with the hypothesis and use the learning to update the roadmap. I’d track the target outcome, guardrails such as quality and support burden, and delivery predictability—so prioritization improves both customer value and organizational focus.

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