Yahoo interview questions & answers

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

CodingEasyYahooSoftware Engineer

1. Roman to Integer (LeetCode)

Model answer

The task

Convert a string of Roman numeral symbols into its integer value. Roman numerals use a small set of symbols, with some smaller values placed before larger ones to indicate subtraction.

Key idea

Scan the string from left to right, comparing each symbol’s value with the next one. If the current value is smaller, subtract it; otherwise, add it. This handles subtractive pairs without needing to process them separately.

Approach

  1. Store the integer value for each Roman numeral symbol in a lookup table.
  2. Initialize a running total to zero.
  3. For each symbol, compare its value with the following symbol’s value, if one exists.
  4. Subtract the current value when it is smaller than the next value; otherwise, add it.
  5. Return the total. This assumes the input is a valid Roman numeral.
class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        total = 0

        for i, symbol in enumerate(s):
            current = values[symbol]

            # A smaller value before a larger value is subtracted.
            if i + 1 < len(s) and current < values[s[i + 1]]:
                total -= current
            else:
                total += current

        return total

Complexity: Time: O(n), where n is the string length, since each symbol is visited once.

Complexity: Space: O(1), because the lookup table has a fixed number of entries.

Common follow-ups

  • How would you handle invalid Roman numeral strings? Validate symbol order and repetition rules before or during conversion.
  • How would you convert an integer to a Roman numeral? Greedily subtract from a descending list of allowed values, including subtractive pairs.
  • Can the conversion be done scanning right to left? Yes; subtract a value if it is smaller than the largest value already seen to its right, otherwise add it.
CodingEasyYahooSoftware Engineer

2. 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.
CodingEasyYahooSoftware Engineer

3. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyYahooSoftware Engineer

4. Maximum Depth of Binary Tree (LeetCode)

Model answer

The task

Given the root of a binary tree, return the number of nodes on its longest path from the root to a leaf. An empty tree has depth zero.

Key idea

For any non-empty node, its deepest path goes through either its left or right child. Its depth is one plus the larger depth of those subtrees.

Approach

  1. If the current node is None, return zero.
  2. Recursively find the depth of the left subtree.
  3. Recursively find the depth of the right subtree.
  4. Return one plus the larger result.
# Definition for a binary tree node:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # An empty subtree contributes no nodes to the depth.
        if root is None:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        # Count this node, then take the deeper subtree.
        return 1 + max(left_depth, right_depth)

Complexity:

  • Time: O(n), where n is the number of nodes; each node is visited once.
  • Space: O(h), where h is the tree height due to the recursive call stack. In the worst case, h is n.

Common follow-ups

  • How can this be solved iteratively? Use a queue for breadth-first search and count the levels processed.
  • What if the tree is very skewed and recursion depth is a concern? Use iterative breadth-first search to avoid a deep call stack.
  • How does the solution change for an N-ary tree? Compute the maximum depth among all children, then add one for the current node.
CodingEasyYahooSoftware Engineer

5. Linked List Cycle (LeetCode)

Model answer

The task

Determine whether a singly linked list eventually revisits a node, forming a cycle.

Key idea

Move two pointers through the list at different speeds. If a cycle exists, the faster pointer eventually catches the slower one; if the fast pointer reaches the end, the list is acyclic.

Approach

  1. Initialize both pointers at the list head.
  2. Advance the slow pointer by one node and the fast pointer by two.
  3. If the fast pointer or its next node is None, return False.
  4. If the pointers meet, return True.
from typing import Optional

class Solution:
    def hasCycle(self, head: Optional["ListNode"]) -> bool:
        # The slow pointer moves one step at a time.
        slow = head
        # The fast pointer moves two steps at a time.
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True

        return False

Complexity:

  • Time: O(n), where n is the number of nodes visited before the pointers meet or the list ends.
  • Space: O(1), because only two pointers are used.

Common follow-ups

  • How could you solve it using a hash set? Record visited node identities; a repeated identity means there is a cycle, using O(n) extra space.
  • How can you find the cycle’s starting node? After the pointers meet, reset one to the head and move both one step at a time; their next meeting is the start.
  • How can you find the cycle’s length? Keep one pointer at the meeting node and advance another until it returns, counting steps.
CodingEasyYahooSoftware Engineer

6. Longest Common Prefix (LeetCode)

Model answer

The task

Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.

Key idea

Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.

Approach

  1. If the list is empty, return an empty string.
  2. Scan each character of the first string from left to right.
  3. For each position, compare that character with the character at the same position in every other string.
  4. If a string is too short or a character differs, return the matching prefix before that position.
  5. If all positions match, return the first string.
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Complexity:

  • Time: O(S), where S is the total number of characters inspected.
  • Space: O(1) auxiliary space, excluding the returned prefix.

Common follow-ups

  • How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
  • Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
  • What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.
CodingEasyYahooSoftware Engineer

7. Matrix Cells in Distance Order (LeetCode)

Model answer

The task

Given a rectangular grid and a starting cell, return every cell ordered by its Manhattan distance from that cell. Cells at the same distance may appear in any order.

Key idea

Generate each cell once, then sort the cells using Manhattan distance as the key. The distance between two cells is the sum of the absolute differences in their row and column indices.

Approach

  1. Enumerate all row and column index pairs in the grid.
  2. Sort the pairs by their Manhattan distance from the given cell.
  3. Return the sorted list.
from typing import List

class Solution:
    def allCellsDistOrder(
        self,
        rows: int,
        cols: int,
        rCenter: int,
        cCenter: int
    ) -> List[List[int]]:
        cells = [
            [r, c]
            for r in range(rows)
            for c in range(cols)
        ]

        cells.sort(
            key=lambda cell: (
                abs(cell[0] - rCenter) + abs(cell[1] - cCenter)
            )
        )
        return cells

Complexity:

  • Time: O(RC log(RC)), where R and C are the grid dimensions and sorting orders all RC cells.
  • Space: O(RC) for storing the cells.

Common follow-ups

  • Can you avoid sorting? Yes; bucket cells by distance, whose maximum is bounded by the grid dimensions, then concatenate the buckets.
  • Can you return cells in distance order as they are discovered? Use breadth-first search from the starting cell, visiting its four neighbors.
  • Does tie order matter? No, as long as cells are ordered by nondecreasing distance.
CodingEasyYahooSoftware Engineer

8. Reverse Linked List (LeetCode)

Model answer

The task

Given the head of a singly linked list, reverse its links in place and return the new head.

Key idea

Recursively reverse the list starting at the second node. As the recursion unwinds, point each node’s successor back to it, then clear its old forward link.

Approach

  1. If the list has zero or one node, it is already reversed.
  2. Recursively reverse the list after the head and save its new head.
  3. Point the next node back to the current node.
  4. Set the current node’s next pointer to None to finish the reversed list.
  5. Return the saved new head.
class Solution:
    def reverseList(self, head):
        # An empty or single-node list is already reversed.
        if head is None or head.next is None:
            return head

        # Reverse the remainder of the list.
        new_head = self.reverseList(head.next)

        # Put the current node after its former successor.
        head.next.next = head
        head.next = None

        return new_head

Complexity:

  • Time: O(n), where n is the number of nodes.
  • Space: O(n), for the recursive call stack.

Common follow-ups

  • Can you do it iteratively with O(1) extra space? Use previous, current, and next_node pointers to reverse links while traversing.
  • What if the list is empty or has one node? The base case returns it unchanged.
  • Can you reverse only a portion of the list? Track the sublist boundaries and reconnect them after reversing that segment.
CodingEasyYahooSoftware Engineer

9. Binary Number with Alternating Bits (LeetCode)

Model answer

The task

Determine whether the binary representation of a positive integer alternates between 0 and 1 at every adjacent bit position.

Key idea

XOR the number with a one-bit right shift. Each pair of adjacent bits differs exactly when the corresponding bit in the XOR result is 1. So the number alternates precisely when that result consists entirely of 1 bits.

Approach

  1. Compute n ^ (n >> 1) to compare each bit with its neighbor.
  2. Check whether the result is a sequence of all 1 bits.
  3. For a positive integer x, that holds exactly when x & (x + 1) is zero.
  4. Return the result of that check.
class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        # Adjacent bits differ exactly where this XOR has a 1.
        adjacent_differences = n ^ (n >> 1)

        # A positive integer of all 1 bits satisfies x & (x + 1) == 0.
        return (adjacent_differences & (adjacent_differences + 1)) == 0

Complexity:

  • Time: O(log n), for operations on the bits of n.
  • Space: O(1), using a fixed number of values.

Common follow-ups

  • How would you solve it with a loop? Compare each bit to the next, stopping if a pair matches.
  • What if the input can be zero? Decide whether its empty or single-bit representation is considered alternating, then handle that convention explicitly.
  • Can you validate the all-ones condition another way? Check that x + 1 is a power of two.
CodingEasyYahooSoftware Engineer

10. Contains Duplicate (LeetCode)

Model answer

The task

Determine whether an integer array contains at least one value that appears more than once. Return True if it does and False otherwise.

Key idea

Track values seen so far in a hash set. If a value is already in the set, a duplicate has been found; otherwise, add it and continue.

Approach

  1. Create an empty set.
  2. Scan the array from left to right.
  3. For each value, check whether it is already in the set.
  4. Return True if it is; otherwise, add the value to the set.
  5. If the scan finishes, return False.
from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()

        for value in nums:
            if value in seen:
                return True
            seen.add(value)

        return False

Complexity:

  • Time: O(n) on average; each set lookup and insertion takes O(1) on average.
  • Space: O(n) in the worst case, when all values are distinct.

Common follow-ups

  • Can you reduce auxiliary space? Sort the array in place, then compare each pair of adjacent values; this takes O(1) extra space if in-place sorting is allowed.
  • What if the input is too large to fit in memory? Partition or hash values across storage, then check each partition for repeats.
  • How does the method handle an empty or single-element array? It returns False, since neither can contain a duplicate.
CodingMediumYahooSoftware Engineer

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

12. Restore IP Addresses (LeetCode)

Model answer

The task

Given a string of digits, insert three dots to form all valid IPv4 addresses. Each address has four numeric parts from 0 to 255, and a part may not have leading zeros unless it is exactly "0".

Key idea

Build the address one part at a time with backtracking. Each part can contain only one to three digits, so there are at most three choices per step; reject invalid parts immediately.

Approach

  1. Start at the beginning of the string with no parts selected.
  2. Before branching, check whether the remaining digits can fit into the remaining parts.
  3. Try taking one, two, or three digits for the next part.
  4. Skip parts with leading zeros or values above 255.
  5. When four parts are selected, add the address if all digits were used.
class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        result = []
        parts = []

        def backtrack(start: int) -> None:
            parts_left = 4 - len(parts)
            digits_left = len(s) - start

            # Each remaining part must use 1 to 3 digits.
            if not (parts_left <= digits_left <= 3 * parts_left):
                return

            if parts_left == 0:
                if start == len(s):
                    result.append(".".join(parts))
                return

            for length in range(1, 4):
                end = start + length
                if end > len(s):
                    break

                part = s[start:end]

                # Multi-digit parts cannot start with zero.
                if length > 1 and part[0] == "0":
                    continue
                if int(part) > 255:
                    continue

                parts.append(part)
                backtrack(end)
                parts.pop()

        backtrack(0)
        return result

Complexity:

  • Time: O(R), where R is the number of returned addresses; only four parts are chosen, each with at most three candidate lengths.
  • Space: O(R) for the results, plus O(1) auxiliary space because the recursion depth is at most four.

Common follow-ups

  • How would you count addresses without returning them? Increment a counter at each valid complete address instead of storing it.
  • Can the pruning be improved? The bounds check already rejects states where the remaining digits cannot fit into the remaining parts.
  • What if the address format changes? Parameterize the number of parts, maximum part length, and maximum numeric value.
  • How would you support IPv6? Use the same backtracking pattern, but validate hexadecimal groups and the IPv6-specific formatting rules.
CodingMediumYahooSoftware Engineer

13. 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.
CodingMediumYahooSoftware Engineer

14. Word Search (LeetCode)

Model answer

The task

Determine whether a word can be traced through adjacent cells in a character grid. Each cell may be used at most once in the same trace.

Key idea

Try each cell as a starting point and use depth-first search to match the word one character at a time. Track cells used in the current path, then undo that tracking when backtracking.

Approach

  1. Return False if the grid is empty or the word is longer than the number of cells.
  2. Start a DFS from every cell matching the word’s first character.
  3. In the DFS, reject out-of-bounds cells, used cells, or character mismatches.
  4. Return True once all characters are matched.
  5. Add each matched cell to the path before exploring neighbors, and remove it afterward.
from typing import List, Set, Tuple

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not word:
            return True
        if not board or not board[0]:
            return False

        rows, cols = len(board), len(board[0])
        if len(word) > rows * cols:
            return False

        used: Set[Tuple[int, int]] = set()

        def search(row: int, col: int, index: int) -> bool:
            if (
                row < 0 or row >= rows
                or col < 0 or col >= cols
                or (row, col) in used
                or board[row][col] != word[index]
            ):
                return False

            if index == len(word) - 1:
                return True

            used.add((row, col))
            found = (
                search(row + 1, col, index + 1)
                or search(row - 1, col, index + 1)
                or search(row, col + 1, index + 1)
                or search(row, col - 1, index + 1)
            )
            used.remove((row, col))
            return found

        for row in range(rows):
            for col in range(cols):
                if search(row, col, 0):
                    return True

        return False

Complexity:

  • Time: O(RC · 4^L), where R and C are grid dimensions and L is the word length; each cell may start a search.
  • Space: O(L), for the visited path and recursive call stack.

Common follow-ups

  • What if diagonal moves are allowed? Add the four diagonal directions to the DFS.
  • How can the search be pruned? Check character frequencies before searching, or start from the rarer end of the word.
  • How would you search for many words at once? Build a trie and search the grid while matching trie prefixes.
CodingMediumYahooSoftware Engineer

15. Spiral Matrix (LeetCode)

Model answer

The task

Return the matrix values in clockwise spiral order, starting from the top-left corner and moving inward.

Key idea

Track the unvisited rectangle with four boundaries. Visit its top, right, bottom, and left edges in turn, then shrink the rectangle and repeat.

Approach

  1. Return an empty list if the matrix has no rows or columns.
  2. Initialize boundaries for the top, bottom, left, and right edges.
  3. Traverse the top edge, then move the top boundary inward.
  4. Traverse the right edge, then move the right boundary inward.
  5. If rows remain, traverse the bottom edge in reverse; if columns remain, traverse the left edge upward.
  6. Repeat until the boundaries cross.
from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse the top edge from left to right.
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            # Traverse the right edge from top to bottom.
            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            # Traverse the bottom edge only if it has not been visited.
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1

            # Traverse the left edge only if it has not been visited.
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1

        return result

Complexity: Time: O(m × n), where each cell is visited once.

Complexity: Space: O(1) auxiliary space, excluding the output list.

Common follow-ups

  • How would you return the values counterclockwise? Change the traversal order and edge directions while maintaining the same boundary updates.
  • How does this handle a single row or column? The boundary checks prevent an edge from being visited twice.
  • Can the traversal be done without boundary variables? Yes, by marking visited cells and turning when blocked, but that requires O(m × n) extra space.
CodingMediumYahooSoftware Engineer

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

17. Decode String (LeetCode)

Model answer

The task

Decode a string where a number before brackets indicates how many times to repeat the bracketed section. Sections may be nested.

Key idea

Parse the input into a compact tree of literal fragments and repeat nodes instead of expanding nested sections immediately. Then traverse that tree to produce the decoded string, avoiding repeated copying of large intermediate strings.

Approach

  1. Scan the input, accumulating each repetition count.
  2. On an opening bracket, save the current fragment list and count, then start a new list.
  3. On a closing bracket, wrap the current list in a repeat node and add it to its parent.
  4. Traverse the resulting structure with an explicit stack, yielding literal fragments as they are needed.
  5. Join the yielded fragments into the result.
class Solution:
    def decodeString(self, s: str) -> str:
        # Each repeat node is a (count, fragments) tuple.
        current = []
        stack = []
        count = 0

        for char in s:
            if "0" <= char <= "9":
                count = count * 10 + int(char)
            elif char == "[":
                stack.append((current, count))
                current = []
                count = 0
            elif char == "]":
                parent, repeat = stack.pop()
                # Omit zero repetitions so traversal skips empty sections.
                if repeat:
                    parent.append((repeat, current))
                current = parent
            else:
                current.append(char)

        def fragments():
            # Frames contain a fragment list, its next index, and
            # how many times to traverse that list.
            frames = [[current, 0, 1]]

            while frames:
                parts, index, remaining = frames[-1]

                if index == len(parts):
                    remaining -= 1
                    if remaining == 0:
                        frames.pop()
                    else:
                        frames[-1][1] = 0
                        frames[-1][2] = remaining
                    continue

                node = parts[index]
                frames[-1][1] += 1

                if isinstance(node, str):
                    yield node
                else:
                    repeat, nested = node
                    frames.append([nested, 0, repeat])

        return "".join(fragments())

Complexity:

  • Time: O(n + m), where n is the encoded length and m is the decoded length.
  • Space: O(n + m) for the parsed structure and returned string.

Common follow-ups

  • How would you handle malformed input? Validate bracket balance and ensure each opening bracket has a preceding count.
  • How could this support streaming output? Yield decoded fragments to a consumer instead of joining them into one string.
  • What if the grammar adds escaping or other operators? Extend the parser with explicit rules and represent each operation as a distinct node.
CodingMediumYahooSoftware Engineer

18. Non-decreasing Subsequences (LeetCode)

Model answer

The task

Return every distinct subsequence of the input array that has at least two elements and is non-decreasing. The order within each subsequence must match the input.

Key idea

Build subsequences with backtracking, choosing only values at least as large as the last chosen value. At each recursion depth, skip values already tried there so duplicate values do not produce duplicate subsequences.

Approach

  1. Start a depth-first search with an empty path.
  2. Whenever the path has at least two elements, add a copy to the results.
  3. At each position, create a fresh set to track values tried at this depth.
  4. Skip a value if it is smaller than the path’s last value or has already been tried at this depth.
  5. Otherwise, add it to the path, recurse from the next index, then remove it.
from typing import List

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            if len(path) >= 2:
                result.append(path.copy())

            # This set applies only to choices at the current depth.
            used = set()

            for i in range(start, len(nums)):
                value = nums[i]

                if used and value in used:
                    continue
                if path and value < path[-1]:
                    continue

                used.add(value)
                path.append(value)
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

Complexity:

  • Time: O(n · 2ⁿ), accounting for exploring subsequences and copying results.
  • Space: O(n) auxiliary space for the recursion and current path, excluding the output.

Common follow-ups

  • How would you handle strictly increasing subsequences? Change the comparison to reject values less than or equal to the last value.
  • Why is the used set recreated at each depth? Identical values at different positions can lead to different choices deeper in the search.
  • What dominates memory use for large outputs? The returned subsequences; there can be exponentially many of them.
CodingMediumYahooSoftware Engineer

19. Validate Binary Search Tree (LeetCode)

Model answer

The task

Determine whether a binary tree satisfies binary search tree ordering: every node must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

Key idea

Checking only a node against its immediate children is not enough; values must also obey the limits imposed by every ancestor. Carry an exclusive lower and upper bound down the tree, tightening them as each node is visited.

Approach

  1. Start at the root with no lower or upper bound.
  2. For each node, reject it if it is not strictly inside the current bounds.
  3. Recursively check the left child with the node’s value as its new upper bound.
  4. Recursively check the right child with the node’s value as its new lower bound.
  5. An empty subtree is valid; return whether both child checks pass.
from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check(
            node: Optional[TreeNode],
            lower: Optional[int],
            upper: Optional[int],
        ) -> bool:
            if node is None:
                return True

            # Bounds are exclusive, so duplicate values are rejected.
            if lower is not None and node.val <= lower:
                return False
            if upper is not None and node.val >= upper:
                return False

            return (
                check(node.left, lower, node.val)
                and check(node.right, node.val, upper)
            )

        return check(root, None, None)

Complexity:

  • Time: O(n), where n is the number of nodes visited.
  • Space: O(h), for the recursive call stack, where h is the tree height.

Common follow-ups

  • How would you handle duplicate values? Define a consistent rule for which side may contain equals, then adjust the bound checks accordingly.
  • Can this be done iteratively? Use a stack of nodes with their lower and upper bounds.
  • What happens on a skewed tree? The time remains O(n), while recursion stack space grows to O(n); an iterative version avoids recursion depth limits.
CodingMediumYahooSoftware Engineer

20. Subarray Sum Equals K (LeetCode)

Model answer

The task

Count the contiguous subarrays whose elements sum to a given target k. The array may contain negative numbers, so subarray sums do not necessarily grow as the subarray gets longer.

Key idea

For each position, let prefix be the sum of all elements seen so far. A subarray ending here sums to k exactly when an earlier prefix sum equals prefix - k. Keep counts of earlier prefix sums in a hash table.

Approach

  1. Start with prefix sum 0 occurring once, representing the empty prefix.
  2. Scan the array and add each value to the running prefix sum.
  3. Add the number of times prefix - k has appeared to the answer.
  4. Record the current prefix sum for future positions.
from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Counts of prefix sums seen so far.
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1

        prefix_sum = 0
        subarray_count = 0

        for value in nums:
            prefix_sum += value

            # Each matching earlier prefix identifies one subarray
            # ending at the current position.
            subarray_count += prefix_counts[prefix_sum - k]

            # Record this prefix only after counting, so the match
            # refers to an earlier position.
            prefix_counts[prefix_sum] += 1

        return subarray_count

Complexity: Time: O(n), where n is the number of elements; each element is processed once.

Complexity: Space: O(n) in the worst case, for the distinct prefix sums stored.

Common follow-ups

  • Why not use a sliding window? Negative values break the monotonic behavior of window sums that sliding-window techniques rely on.
  • What if all values are nonnegative? A sliding window can be used, though prefix sums still provide a straightforward solution.
  • Can this count subarrays for many target values? The prefix-frequency scan is target-specific; repeated queries may need a different strategy depending on the input size and query count.

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