IXL interview questions & answers

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

CodingEasyIXLSoftware Engineer

1. Palindrome Linked List (LeetCode)

Model answer

The task

Determine whether a singly linked list reads the same from front to back and back to front. Return a boolean without relying on access to nodes by index.

Key idea

Find the midpoint with slow and fast pointers, then reverse the second half. Compare the two halves node by node; reverse the second half again afterward to restore the original list.

Approach

  1. Advance slow by one node and fast by two until fast reaches the end.
  2. For an odd-length list, move the start of the second half past the middle node.
  3. Reverse the second half in place.
  4. Compare corresponding values from the head and reversed second half.
  5. Restore the second half before returning the result.
class Solution:
    def isPalindrome(self, head):
        def reverse(node):
            previous = None
            while node:
                following = node.next
                node.next = previous
                previous = node
                node = following
            return previous

        slow = fast = head

        # Find the midpoint. For odd length, fast ends on the final node.
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Skip the middle node when the list has odd length.
        second_half_start = slow.next if fast else slow
        reversed_half = reverse(second_half_start)

        # Compare the first half with the reversed second half.
        left = head
        right = reversed_half
        is_palindrome = True

        while right:
            if left.val != right.val:
                is_palindrome = False
                break
            left = left.next
            right = right.next

        # Restore the list to its original structure.
        reverse(reversed_half)
        return is_palindrome

Complexity:

  • Time: O(n), to find the midpoint, reverse, compare, and restore.
  • Space: O(1), using only a few pointers.

Common follow-ups

  • What if the list must not be modified, even temporarily? Use a stack to store values, which takes O(n) extra space.
  • How can recursion solve it? Recursively compare nodes from the ends, using O(n) call-stack space.
  • What about empty or single-node lists? Both are palindromes; the code handles them directly.
CodingEasyIXLSoftware Engineer

2. Range Addition II (LeetCode)

Model answer

The task

Given an initially zero-filled m × n matrix and a list of operations, each operation increments a top-left rectangle. Return how many cells have the largest value after all operations.

Key idea

The cells with the maximum value are exactly those incremented by every operation. Their shared area has height equal to the smallest operation height and width equal to the smallest operation width.

Approach

  1. Start with the full matrix dimensions as the shared area.
  2. For each operation, shrink the shared height and width to that operation’s dimensions.
  3. Return the area of the remaining shared rectangle.
  4. If there are no operations, the whole matrix has the same value.
from typing import List

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        # With no operations, every cell is tied for the maximum.
        min_height = m
        min_width = n

        for height, width in ops:
            min_height = min(min_height, height)
            min_width = min(min_width, width)

        return min_height * min_width

Complexity:

  • Time: O(k), where k is the number of operations.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What is the maximum cell value? It is the number of operations, assuming each operation increments by one.
  • What if operations increment by arbitrary amounts? The shared area still identifies maximum cells only when all increments are positive and each operation covers a top-left rectangle.
  • What if the matrix is too large to store? This solution already avoids storing it, using constant extra space.
CodingEasyIXLSoftware Engineer

3. 1-bit and 2-bit Characters (LeetCode)

Model answer

The task

Given a sequence of bits encoded using 0 for a one-bit character and 10 or 11 for a two-bit character, determine whether the final character is one-bit.

Key idea

Decode from left to right, advancing one position for a 0 and two positions for a 1. If decoding reaches the final bit, that bit starts a one-bit character; if it jumps past it, the final bit belongs to a two-bit character.

Approach

  1. Set an index to the start of the sequence.
  2. While the index is before the final bit, advance by one or two according to the current bit.
  3. Return whether the index lands exactly on the final bit.
from typing import List

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        index = 0
        last = len(bits) - 1

        # Decode characters until reaching or passing the final bit.
        while index < last:
            index += 1 if bits[index] == 0 else 2

        return index == last

Complexity:

  • Time: O(n), where n is the number of bits scanned.
  • Space: O(1), using only an index.

Common follow-ups

  • What if the sequence is empty? The stated encoding assumes a nonempty sequence; otherwise, define the desired result explicitly.
  • Can the scan stop early? Yes. The loop already stops as soon as it reaches or passes the final bit.
  • Does the algorithm require the input to be validly encoded? Yes; it relies on each 1 beginning a two-bit character.
CodingMediumIXLSoftware Engineer

4. Basic Calculator II (LeetCode)

Model answer

The task

Evaluate a string containing nonnegative integers, spaces, and the operators +, -, *, and /. Multiplication and division take precedence over addition and subtraction, and division truncates toward zero.

Key idea

Scan the expression once, applying each operator when the next operator is reached. Keep addition and subtraction terms in a stack; immediately combine multiplication and division with the stack’s last term. Summing the stack at the end gives the result.

Approach

  1. Accumulate consecutive digits into the current number, ignoring spaces.
  2. On an operator—or a final sentinel—apply the previous operator to that number.
  3. For + and -, push the signed number; for * and /, update the top stack value.
  4. Implement division with absolute values and a sign check, since Python’s // rounds negative results down.
  5. Return the sum of the stack.
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        number = 0
        previous_operator = "+"

        # A final sentinel ensures the last number is processed.
        for char in s + "+":
            if char.isdigit():
                number = number * 10 + int(char)
            elif char == " ":
                continue
            else:
                if previous_operator == "+":
                    stack.append(number)
                elif previous_operator == "-":
                    stack.append(-number)
                elif previous_operator == "*":
                    stack[-1] *= number
                else:  # Division, truncated toward zero.
                    left = stack[-1]
                    quotient = abs(left) // abs(number)
                    stack[-1] = -quotient if (left < 0) != (number < 0) else quotient

                previous_operator = char
                number = 0

        return sum(stack)

Complexity:

  • Time: O(n), where n is the expression length.
  • Space: O(n) in the worst case for the stack of additive terms.

Common follow-ups

  • Support parentheses? Use a recursive descent parser or an operator/value stack to handle nested expressions.
  • Support unary operators? Track whether the parser expects an operand, then handle leading or repeated signs accordingly.
  • Reduce auxiliary space? Maintain a running total and the current term instead of storing all additive terms.
  • Handle malformed expressions? Validate token order, parentheses, and division by zero while parsing.
CodingMediumIXLSoftware Engineer

5. Course Schedule (LeetCode)

Model answer

The task

Given a number of courses and prerequisite pairs, decide whether it’s possible to complete every course. A prerequisite pair means one course must be taken before another.

Key idea

Represent courses as a directed graph, with an edge from each prerequisite to the course that depends on it. A cycle means the courses in that cycle depend on one another, so not all courses can be completed.

Use Kahn’s topological-sort algorithm: repeatedly take courses with no remaining prerequisites and remove their outgoing edges.

Approach

  1. Create an adjacency list and count each course’s prerequisites (its indegree).
  2. Add every course with indegree zero to a queue.
  3. Remove courses from the queue, counting each as completed.
  4. Decrease the indegree of each dependent course; enqueue it when its indegree reaches zero.
  5. Return whether the number completed equals the total number of courses.
from collections import deque
from typing import List

class Solution:
    def canFinish(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> bool:
        # Edges point from prerequisite to the course that depends on it.
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

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

        # Begin with courses that have no prerequisites.
        ready = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )

        completed = 0

        while ready:
            course = ready.popleft()
            completed += 1

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

        return completed == numCourses

Complexity:

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

Common follow-ups

  • How can you return a valid course order? Record courses as they are removed from the queue; return the order if it includes every course.
  • How can DFS detect a cycle? Track nodes as unvisited, visiting, or finished; reaching a visiting node reveals a cycle.
  • What if there are no courses? The algorithm returns True, since zero courses can all be completed.
CodingMediumIXLSoftware Engineer

6. Fraction to Recurring Decimal (LeetCode)

Model answer

The task

Convert a fraction given by an integer numerator and nonzero integer denominator into its decimal string. If the decimal digits repeat, enclose the repeating part in parentheses.

Key idea

Long division generates the decimal digits. A remainder that appears again means the digits since its first appearance repeat, so store each remainder’s position in the output.

Approach

  1. Return "0" if the numerator is zero.
  2. Determine the sign, then use absolute values for the division.
  3. Append the integer part and a decimal point if a remainder remains.
  4. Before generating each fractional digit, check whether its remainder has been seen. If so, insert parentheses at its recorded position.
  5. Otherwise, record the remainder’s position, multiply it by 10, and continue long division.
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        # Apply the sign once, then perform long division on positive values.
        negative = (numerator < 0) != (denominator < 0)
        numerator = abs(numerator)
        denominator = abs(denominator)

        integer_part, remainder = divmod(numerator, denominator)
        result = ("-" if negative else "") + str(integer_part)

        if remainder == 0:
            return result

        result += "."
        # Map each remainder to the index where its next digit will be written.
        seen = {}

        while remainder != 0:
            if remainder in seen:
                repeat_start = seen[remainder]
                result = result[:repeat_start] + "(" + result[repeat_start:] + ")"
                break

            seen[remainder] = len(result)
            remainder *= 10
            digit, remainder = divmod(remainder, denominator)
            result += str(digit)

        return result

Complexity:

  • Time: O(k), where k is the number of fractional digits generated before termination or repetition.
  • Space: O(k), for the output and stored remainders.

Common follow-ups

  • How would you handle a very large denominator? Use the same remainder-cycle method; the number of distinct remainders is bounded by the denominator.
  • What if the denominator is zero? Reject the input or raise an exception; the fraction is undefined.
  • Can the result be streamed? Yes, emit digits as generated, but buffer them if parentheses must be inserted retroactively.
CodingMediumIXLSoftware Engineer

7. Fraction Addition and Subtraction (LeetCode)

Model answer

The task

Parse an expression made of signed fractions and return its value as a reduced fraction. The result should have a positive denominator.

Key idea

Accumulate the fractions using a common denominator, reducing by the greatest common divisor after each addition. Scan the string directly so signs are handled as part of each fraction.

Approach

  1. Start with the accumulated value 0/1.
  2. Read each fraction’s sign, numerator, and denominator from the expression.
  3. Add it to the accumulated fraction using cross-multiplication.
  4. Reduce the new numerator and denominator by their GCD.
  5. Format the reduced result as "numerator/denominator".
from math import gcd

class Solution:
    def fractionAddition(self, expression: str) -> str:
        total_num = 0
        total_den = 1
        i = 0

        while i < len(expression):
            # Read the sign; a missing sign means positive.
            sign = 1
            if expression[i] in "+-":
                if expression[i] == "-":
                    sign = -1
                i += 1

            # Read the numerator.
            start = i
            while i < len(expression) and expression[i].isdigit():
                i += 1
            numerator = int(expression[start:i])

            # Skip the slash, then read the denominator.
            i += 1
            start = i
            while i < len(expression) and expression[i].isdigit():
                i += 1
            denominator = int(expression[start:i])

            # Add this signed fraction to the running total.
            total_num = total_num * denominator + sign * numerator * total_den
            total_den *= denominator

            # Keep the running fraction reduced.
            common = gcd(abs(total_num), total_den)
            total_num //= common
            total_den //= common

        return f"{total_num}/{total_den}"

Complexity:

  • Time: O(n) parsing steps, plus the cost of integer arithmetic and GCD operations.
  • Space: O(1) auxiliary variables, excluding the integers used to store the running fraction.

Common follow-ups

  • How would you handle whitespace? Skip whitespace while scanning before reading each token.
  • How would you support negative denominators? Move the sign to the numerator before reducing.
  • Can you reduce only once at the end? Yes, but intermediate integers may grow much larger.
CodingMediumIXLSoftware Engineer

8. Design Snake Game (LeetCode)

Model answer

The task

Implement a snake game that moves in a grid, consumes food, and grows. Return the number of foods eaten after each move, or -1 once the snake hits a wall or itself.

Key idea

Track the snake’s body in a deque and its occupied cells in a set. The set makes collision checks constant time; when the snake is not eating, its tail vacates a cell on the same move, so moving into that cell is allowed.

Approach

  1. Store the body from tail to head, plus a set of occupied cells.
  2. For each move, compute the new head and check whether it is in bounds.
  3. Determine whether the move eats the next food.
  4. Check for self-collision, allowing the current tail cell if the snake is not growing.
  5. Remove the tail when not eating, then add the new head and return the food count.
from collections import deque

class SnakeGame:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0
        self.dead = False

        # Body is ordered from tail to head.
        self.body = deque([(0, 0)])
        self.occupied = {(0, 0)}

        self.directions = {
            "U": (-1, 0),
            "D": (1, 0),
            "L": (0, -1),
            "R": (0, 1),
        }

    def move(self, direction: str) -> int:
        if self.dead:
            return -1

        row, col = self.body[-1]
        dr, dc = self.directions[direction]
        new_head = (row + dr, col + dc)
        new_row, new_col = new_head

        # A move beyond the grid ends the game.
        if not (0 <= new_row < self.height and 0 <= new_col < self.width):
            self.dead = True
            return -1

        eating = (
            self.food_index < len(self.food)
            and [new_row, new_col] == self.food[self.food_index]
        )

        tail = self.body[0]
        if new_head in self.occupied and (eating or new_head != tail):
            self.dead = True
            return -1

        # The tail vacates its cell unless the snake grows.
        if not eating:
            self.body.popleft()
            self.occupied.remove(tail)
        else:
            self.food_index += 1

        self.body.append(new_head)
        self.occupied.add(new_head)
        return self.food_index

Complexity:

  • Time: O(1) per move; each move uses constant-time deque and set operations.
  • Space: O(L) for the body and occupied-cell set, where L is the snake’s length.

Common follow-ups

  • How would you support wrapping at the grid edges? Wrap the new row and column modulo the grid dimensions.
  • What if moves arrive concurrently? Protect game state updates with a lock.
  • How could you optimize memory for a very large sparse grid? Store only occupied cells, as this implementation does.
CodingMediumIXLSoftware Engineer

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

10. 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.
CodingMediumIXLSoftware Engineer

11. Merge Intervals (LeetCode)

Model answer

The task

Given a collection of intervals, combine every pair that overlaps and return the resulting non-overlapping intervals. The result should be ordered by starting point.

Key idea

Sort intervals by their start. Then scan once, keeping the most recently merged interval; each next interval either extends it or starts a new one.

Approach

  1. Sort the intervals by their start value.
  2. Initialize the result with the first interval, if any.
  3. For each remaining interval, compare its start with the end of the last result interval.
  4. If they overlap, update that end to the larger of the two ends.
  5. Otherwise, append the interval as a new result.
from typing import List

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

        intervals.sort(key=lambda interval: interval[0])
        merged = [intervals[0]]

        for start, end in intervals[1:]:
            # The intervals overlap, so extend the last merged interval.
            if start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                # No overlap: this interval begins a new merged range.
                merged.append([start, end])

        return merged

Complexity: Time: O(n log n), dominated by sorting n intervals.

Complexity: Space: O(n) for the merged result; sorting may also use up to O(n) space.

Common follow-ups

  • What if intervals that only touch at an endpoint should remain separate? Use start < merged[-1][1] as the overlap test.
  • How would you merge intervals as they arrive in sorted order? Skip sorting and apply the same scan, processing each interval once.
  • What if intervals are inserted one at a time into an already merged collection? Use binary search to find the insertion point, then merge neighboring overlaps.
CodingMediumIXLSoftware Engineer

12. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts (LeetCode)

Model answer

The task

Given a rectangular cake and positions of horizontal and vertical cuts, find the largest rectangular piece that can result. Return its area modulo \(10^9+7\).

Key idea

The largest piece uses the widest gap between consecutive horizontal cut boundaries and the widest gap between consecutive vertical cut boundaries. The maximum area is the product of those two gaps.

Approach

  1. Sort the horizontal cut positions and add the cake’s top and bottom edges as boundaries.
  2. Find the largest distance between consecutive horizontal boundaries.
  3. Repeat for vertical cuts, including the left and right edges.
  4. Multiply the two maximum gaps and take the result modulo \(10^9+7\).
class Solution:
    def maxArea(
        self,
        h: int,
        w: int,
        horizontalCuts: list[int],
        verticalCuts: list[int],
    ) -> int:
        mod = 10**9 + 7

        horizontal = [0] + sorted(horizontalCuts) + [h]
        vertical = [0] + sorted(verticalCuts) + [w]

        max_height = max(
            horizontal[i + 1] - horizontal[i]
            for i in range(len(horizontal) - 1)
        )
        max_width = max(
            vertical[i + 1] - vertical[i]
            for i in range(len(vertical) - 1)
        )

        return (max_height * max_width) % mod

Complexity:

  • Time: O(m log m + n log n), for sorting the two cut lists.
  • Space: O(m + n), for the sorted lists with added boundaries.

Common follow-ups

  • What if cuts arrive unsorted? Sort them before computing consecutive gaps.
  • Why can the two largest gaps be combined? Horizontal and vertical cuts are independent, so their widest intervals intersect in a piece.
  • What if there are no cuts in one direction? The corresponding maximum gap is the full cake dimension.
CodingMediumIXLSoftware Engineer

13. Minimum Number of Steps to Make Two Strings Anagram (LeetCode)

Model answer

The task

Given two equal-length strings, find the fewest characters in the second string that must be replaced so it can be rearranged into the first string.

Key idea

Count each character in both strings. Every character that the second string has in excess of the first can be replaced; the minimum number of replacements equals the total number of missing characters in the second string.

Approach

  1. Count characters in each string.
  2. For every character needed by the first string, compare its count with the count in the second.
  3. Add any positive difference to the answer.
  4. Return the total.
from collections import Counter

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        needed = Counter(s)
        available = Counter(t)

        # Each deficit requires one replacement in t.
        return sum(
            max(0, count - available[char])
            for char, count in needed.items()
        )

Complexity:

  • Time: O(n), to count and compare characters.
  • Space: O(1), since the lowercase English alphabet has a fixed size.

Common follow-ups

  • What if the strings contain arbitrary Unicode characters? Use the same counting approach; space becomes O(k), where k is the number of distinct characters.
  • How would you return the actual replacements? Pair surplus characters in the second string with the characters it is missing.
  • What if insertions and deletions are also allowed? Compare character counts and compute the required edits according to their costs.
CodingMediumIXLSoftware Engineer

14. Find the Derangement of An Array (LeetCode)

Model answer

The task

Count the permutations of n distinct items in which every item is placed somewhere other than its original position. Return the count modulo \(10^9+7\).

Key idea

Let D[n] be the number of valid permutations of n items. The derangement recurrence is D[n] = (n - 1) * (D[n - 1] + D[n - 2]): choose a destination for one item, then account for whether the displaced item returns to its original position.

Approach

  1. Set D[0] = 1 (the empty arrangement) and D[1] = 0.
  2. Iterate from 2 through n, applying the recurrence.
  3. Keep only the previous two values, reducing space to constant.
  4. Return the result modulo \(10^9+7\).
class Solution:
    def findDerangement(self, n: int) -> int:
        mod = 10**9 + 7

        # D[0] and D[1]
        two_back = 1
        one_back = 0

        for size in range(2, n + 1):
            current = (size - 1) * (one_back + two_back) % mod
            two_back, one_back = one_back, current

        return one_back

Complexity:

  • Time: O(n), for one pass through the sizes.
  • Space: O(1), using only two stored recurrence values.

Common follow-ups

  • Can inclusion-exclusion give the count? Yes: \(D_n = n! \sum_{k=0}^{n} (-1)^k/k!\).
  • What if the modulus changes? Use the same recurrence and take each result modulo the requested modulus.
  • What if n is very large? For a single answer, the recurrence takes linear time; for many queries, precompute values up to the largest requested n.
CodingHardIXLSoftware Engineer

15. Find Median from Data Stream (LeetCode)

Model answer

The task

Design a data structure that accepts numbers one at a time and can return the median of all numbers seen so far. The median is the middle value for an odd count, or the average of the two middle values for an even count.

Key idea

Keep the lower half of the values in a max-heap and the upper half in a min-heap. Maintain heap sizes so the lower half has either the same number of elements as the upper half or exactly one more.

Approach

  1. Store the lower half as negated values in Python’s min-heap; store the upper half normally.
  2. Insert each new value into the lower heap.
  3. Move the largest lower-half value to the upper heap to preserve ordering.
  4. If the upper heap becomes larger, move its smallest value back to the lower heap.
  5. Return the lower heap’s top for an odd count, or average the two heap tops for an even count.
import heapq

class MedianFinder:
    def __init__(self):
        # Negated values make this a max-heap.
        self.lower = []
        # A regular min-heap.
        self.upper = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        # Ensure every value in lower is <= every value in upper.
        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        # Keep lower the same size as upper, or one element larger.
        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def findMedian(self) -> float:
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

Complexity:

  • Time: addNum is O(log n) due to heap operations; findMedian is O(1).
  • Space: O(n) to store all numbers across the two heaps.

Common follow-ups

  • How would you support removing values? Use lazy deletion with delayed removals, pruning heap tops as needed.
  • What if numbers arrive in a bounded integer range? A frequency array can track counts and locate the middle ranks.
  • Can this be distributed across machines? Maintain ordered partitions or quantile summaries, then combine counts to find the middle ranks.
CodingHardIXLSoftware Engineer

16. Merge k Sorted Lists (LeetCode)

Model answer

The task

Combine several individually sorted linked lists into one sorted linked list. The result should reuse the input nodes rather than create a new node for every value.

Key idea

Keep the first unmerged node from each nonempty list in a min-heap. Repeatedly take the smallest node, append it to the result, and add its successor to the heap.

Approach

  1. Add each nonempty list’s head to the heap.
  2. Include a unique counter in each heap entry so equal values never require comparing nodes.
  3. Pop the smallest node and append it to the result.
  4. If that node has a successor, push the successor into the heap.
  5. Return the node after a dummy head.
import heapq
from typing import Optional

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

class Solution:
    def mergeKLists(
        self, lists: list[Optional[ListNode]]
    ) -> Optional[ListNode]:
        heap = []
        serial = 0  # Break ties without comparing ListNode objects.

        for node in lists:
            if node is not None:
                heapq.heappush(heap, (node.val, serial, node))
                serial += 1

        dummy = ListNode()
        tail = dummy

        while heap:
            _, _, node = heapq.heappop(heap)
            tail.next = node
            tail = node

            if node.next is not None:
                heapq.heappush(heap, (node.next.val, serial, node.next))
                serial += 1

        tail.next = None
        return dummy.next

Complexity:

  • Time: O(N log k), where each of the N nodes is pushed and popped once.
  • Space: O(k) for the heap, which holds at most one node per input list.

Common follow-ups

  • How can divide and conquer solve this? Merge lists in pairs over successive rounds, also taking O(N log k) time.
  • What if the lists are supplied as a stream? Keep one current node per active list in the heap and add lists as they arrive.
  • Can the inputs be modified? Yes; this solution relinks and reuses their nodes.
CodingHardIXLSoftware Engineer

17. Stickers to Spell Word (LeetCode)

Model answer

The task

Find the fewest stickers whose letters can collectively form the target word. A sticker may be used more than once; return -1 if the target cannot be formed.

Key idea

Represent the letters still needed as a 26-element count tuple and memoize the minimum stickers required for each tuple. At each step, choose a needed letter and only try stickers that contain it, ensuring every choice makes progress.

Approach

  1. Count the target letters and each sticker’s letters, ignoring letters not in the target.
  2. If any needed letter appears on no sticker, return -1.
  3. In the recursive search, choose a remaining letter covered by the fewest sticker types.
  4. Try each sticker containing that letter, subtract its counts (without going below zero), and take the best result.
  5. Memoize results so each remaining-count state is solved once.
from functools import lru_cache

class Solution:
    def minStickers(self, stickers: list[str], target: str) -> int:
        target_count = [0] * 26
        for char in target:
            target_count[ord(char) - ord("a")] += 1

        # Keep only relevant letters, capped at what the target needs.
        sticker_counts = []
        for sticker in stickers:
            counts = [0] * 26
            for char in sticker:
                index = ord(char) - ord("a")
                if target_count[index]:
                    counts[index] += 1
            sticker_counts.append(
                tuple(min(counts[i], target_count[i]) for i in range(26))
            )

        coverage = [
            sum(counts[i] > 0 for counts in sticker_counts)
            for i in range(26)
        ]
        if any(target_count[i] and coverage[i] == 0 for i in range(26)):
            return -1

        start = tuple(target_count)

        @lru_cache(None)
        def solve(remaining: tuple[int, ...]) -> int:
            if not any(remaining):
                return 0

            # Choose a needed letter with the fewest sticker options.
            letter = min(
                (i for i, count in enumerate(remaining) if count),
                key=lambda i: coverage[i],
            )

            best = float("inf")
            for sticker in sticker_counts:
                if sticker[letter] == 0:
                    continue

                next_remaining = tuple(
                    max(0, remaining[i] - sticker[i]) for i in range(26)
                )
                best = min(best, 1 + solve(next_remaining))

            return best

        answer = solve(start)
        return -1 if answer == float("inf") else answer

Complexity:

  • Time: O(Q × S × A), where Q is the number of memoized states, S is the number of stickers, and A = 26 letters.
  • Space: O(Q × A) for memoized count tuples.

Common follow-ups

  • How can dominated stickers be removed? Discard a sticker whose useful letter counts are no greater than another sticker’s counts.
  • What if stickers have different costs? Add the sticker’s cost in each transition instead of 1.
  • How can this be modeled with bitmasks? Track covered target positions, though count states handle repeated letters more naturally.

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