Wells Fargo interview questions & answers

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

CodingEasyWells FargoSoftware Engineer

1. Backspace String Compare (LeetCode)

Model answer

The task

Compare two strings after applying backspaces: each # removes the most recent character when one exists. Return whether the resulting strings are equal.

Key idea

Scan both strings from right to left. Count how many characters each backspace should skip, so the strings can be compared without building their edited versions.

Approach

  1. Start a pointer at the end of each string.
  2. For each string, move left while tracking pending backspaces.
  3. Skip a character if a backspace is pending; otherwise it is the next visible character.
  4. Compare the next visible characters. If they differ, return False.
  5. Continue until both strings have no visible characters left, then return True.
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def next_visible(text: str, index: int) -> tuple[str | None, int]:
            """Return the next character not erased by a backspace, and its index."""
            skips = 0

            while index >= 0:
                if text[index] == "#":
                    skips += 1
                elif skips > 0:
                    skips -= 1
                else:
                    return text[index], index - 1

                index -= 1

            return None, -1

        i, j = len(s) - 1, len(t) - 1

        while i >= 0 or j >= 0:
            char_s, i = next_visible(s, i)
            char_t, j = next_visible(t, j)

            if char_s != char_t:
                return False

        return True

Complexity:

  • Time: O(m + n), where m and n are the string lengths; each character is visited at most once.
  • Space: O(1), excluding the helper’s constant-size state.

Common follow-ups

  • What if backspace is represented by a different character? Pass it into the helper or replace the "#" check.
  • How would you implement this with a stack? Build each edited string by appending ordinary characters and popping on backspace, then compare.
  • What happens when a backspace appears with nothing to erase? It is ignored, as handled by the skip count.
CodingEasyWells FargoSoftware Engineer

2. Rotate String (LeetCode)

Model answer

The task

Determine whether one string can be obtained by repeatedly moving the first character of another string to its end. The resulting string must match exactly.

Key idea

A rotation of s appears as a substring of s + s. Check for that match using KMP string matching, which runs in linear time.

Approach

  1. If the strings have different lengths, they cannot be rotations.
  2. Build the KMP prefix table for the target string.
  3. Scan s + s with KMP, returning True if the target is found.
  4. Return False if the scan finishes without a match.
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        if not goal:
            return True

        # Build the KMP prefix table: the longest proper prefix that
        # is also a suffix for each prefix of goal.
        prefix = [0] * len(goal)
        matched = 0

        for i in range(1, len(goal)):
            while matched and goal[i] != goal[matched]:
                matched = prefix[matched - 1]
            if goal[i] == goal[matched]:
                matched += 1
                prefix[i] = matched

        # Search for goal in the doubled string.
        matched = 0
        for char in s + s:
            while matched and char != goal[matched]:
                matched = prefix[matched - 1]
            if char == goal[matched]:
                matched += 1
                if matched == len(goal):
                    return True

        return False

Complexity:

  • Time: O(n), for building the prefix table and scanning the doubled string.
  • Space: O(n), for the prefix table.

Common follow-ups

  • Can you use a built-in string search instead? Yes: check whether goal occurs in s + s; KMP gives an explicit linear-time bound.
  • What if the strings have different lengths? They cannot be rotations, so return False immediately.
  • Does the empty string match itself? Yes; zero rotations leave it unchanged.
CodingEasyWells FargoSoftware Engineer

3. Count Vowel Substrings of a String (LeetCode)

Model answer

The task

Count substrings made entirely of vowels that contain each of the five vowels at least once.

Key idea

For each ending position, keep the most recent position of every vowel in the current uninterrupted vowel segment. If all five have appeared, the earliest valid start is one position after the smallest of those last positions.

Approach

  1. Scan the string from left to right.
  2. When a consonant appears, mark the start of the new vowel-only segment and clear the last-seen positions.
  3. For a vowel, update its last-seen position.
  4. Once all five vowels have been seen in this segment, add the number of valid starting positions for this ending position.
class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        vowels = set("aeiou")
        last_seen = {}
        segment_start = 0
        total = 0

        for right, char in enumerate(word):
            if char not in vowels:
                # Substrings cannot cross a consonant.
                segment_start = right + 1
                last_seen.clear()
                continue

            last_seen[char] = right

            if len(last_seen) == 5:
                # Any start from segment_start through the earliest
                # last-seen vowel produces a substring with all five.
                earliest_last_seen = min(last_seen.values())
                total += earliest_last_seen - segment_start + 1

        return total

Complexity:

  • Time: O(n), since each character is processed once and at most five positions are checked.
  • Space: O(1), as the map stores positions for at most five vowels.

Common follow-ups

  • What if vowels are case-insensitive? Normalize each character before testing it.
  • What if the required vowel set changes? Replace the fixed vowel set and require all its members to be present.
  • How would you count substrings with at least k distinct vowels? Track vowel frequencies and use a sliding-window count.
CodingEasyWells FargoSoftware Engineer

4. Count Binary Substrings (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

Complexity:

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

Common follow-ups

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

5. Intersection of Two Linked Lists (LeetCode)

Model answer

The task

Given the heads of two singly linked lists, return the node where they first join, or None if they never join. Nodes must be compared by identity, not by their stored values.

Key idea

Use two pointers that each traverse both lists. When a pointer reaches the end of its list, redirect it to the other list’s head. This equalizes the total distance traveled, so the pointers meet at the intersection or both reach None.

Approach

  1. Start one pointer at each list’s head.
  2. Advance both pointers one node at a time.
  3. When a pointer reaches None, redirect it to the other list’s head.
  4. Stop when the pointers are identical; return that node.
# LeetCode provides the ListNode definition.
class Solution:
    def getIntersectionNode(self, headA: "ListNode", headB: "ListNode") -> "ListNode":
        pointer_a = headA
        pointer_b = headB

        while pointer_a is not pointer_b:
            # Switching heads makes both pointers traverse the same total length.
            pointer_a = pointer_a.next if pointer_a else headB
            pointer_b = pointer_b.next if pointer_b else headA

        return pointer_a

Complexity:

  • Time: O(m + n), where m and n are the list lengths; each pointer traverses at most both lists.
  • Space: O(1), using only two pointers.

Common follow-ups

  • What if extra space is allowed? Store nodes from one list in a set, then scan the other and return the first node found.
  • Can this be solved by measuring lengths? Yes. Advance the pointer on the longer list by the length difference, then move both pointers together.
  • What if the lists may contain cycles? First determine whether each list has a cycle; intersection detection then needs to account for cyclic structure.
  • Why not compare node values? Different nodes can store the same value; an intersection means both lists reference the exact same node.
CodingEasyWells FargoSoftware Engineer

6. Merge Strings Alternately (LeetCode)

Model answer

The task

Combine two strings by taking one character from each in turn, starting with the first string. If one string runs out first, add the rest of the other string unchanged.

Key idea

Keep an index for each string and append characters while both indices are valid. Then append whichever suffix remains, if any.

Approach

  1. Initialize two indices at the start of the strings and an empty list of output characters.
  2. While both indices are within their strings, append one character from each and advance both indices.
  3. Append any unprocessed suffix from the first string.
  4. Append any unprocessed suffix from the second string.
  5. Join the output characters into the returned string.
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        i = 0
        j = 0
        merged = []

        # Interleave characters while both strings have characters left.
        while i < len(word1) and j < len(word2):
            merged.append(word1[i])
            merged.append(word2[j])
            i += 1
            j += 1

        # Preserve any remaining characters from either string.
        merged.extend(word1[i:])
        merged.extend(word2[j:])

        return "".join(merged)

Complexity:

  • Time: O(m + n), where m and n are the string lengths; every character is processed once.
  • Space: O(m + n) for the resulting character list and returned string.

Common follow-ups

  • What if the second string should be taken first? Swap which character is appended first in each loop iteration.
  • Can the result be built without slicing the leftover suffix? Append remaining characters in a loop, avoiding temporary slice strings.
  • What if there are many strings to interleave? Track an index per string and repeatedly append the next available character from each string in order.
CodingEasyWells FargoSoftware Engineer

7. 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.
CodingEasyWells FargoSoftware Engineer

8. Minimum String Length After Removing Substrings (LeetCode)

Model answer

The task

Repeatedly remove any occurrence of "AB" or "CD" from a string until neither remains. Return the length of the resulting string.

Key idea

A stack keeps the characters that have not been removed. When a new character completes one of the two removable pairs with the stack’s top, pop the top instead of adding the new character.

Approach

  1. Start with an empty stack.
  2. Scan the string from left to right.
  3. For each character, check whether it forms "AB" or "CD" with the stack’s top.
  4. If it does, pop the top; otherwise, push the character.
  5. Return the stack’s length.
class Solution:
    def minLength(self, s: str) -> int:
        stack = []

        for char in s:
            # Remove the pair if this character completes one.
            if stack and (
                (stack[-1] == "A" and char == "B")
                or (stack[-1] == "C" and char == "D")
            ):
                stack.pop()
            else:
                stack.append(char)

        return len(stack)

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, for the stack.

Common follow-ups

  • What if there are more removable pairs? Store the allowed pairs in a set and check whether the top character and current character form a pair.
  • Can this be done in place? Yes. Use the input string as a character array and maintain a write index as the stack top.
  • Why does one scan handle newly exposed pairs? After a removal, later characters are checked against the updated stack, so newly adjacent characters are handled as the scan continues.
CodingEasyWells FargoSoftware Engineer

9. Kth Largest Element in a Stream (LeetCode)

Model answer

The task

Build a data structure that receives an initial collection of numbers and then accepts new numbers one at a time. After each addition, report the kth largest number seen so far.

Key idea

Keep a min-heap containing only the largest k values seen. Its smallest element is the kth largest overall, because every value outside the heap is no larger than any value inside it.

Approach

  1. Create an empty min-heap.
  2. For each initial value, add it to the heap.
  3. If the heap grows beyond k, remove its smallest value.
  4. For each new value, repeat the same insertion and removal.
  5. Return the heap’s smallest value.
import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = []

        # Keep only the k largest values seen so far.
        for value in nums:
            self._add_to_heap(value)

    def _add_to_heap(self, value: int) -> None:
        heapq.heappush(self.heap, value)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)

    def add(self, value: int) -> int:
        self._add_to_heap(value)
        return self.heap[0]

Complexity:

  • Time: O(log k) per added value; initialization takes O(n log k) for n initial values.
  • Space: O(k) for the heap.

Common follow-ups

  • How would you support a different k? Keep all values in an order-statistics tree, or rebuild the size-k heap when k changes.
  • What if many kth-largest queries arrive between additions? The heap’s root answers each query in O(1).
  • What if the data stream is unbounded? The heap still uses O(k) memory, regardless of stream length.
CodingMediumWells FargoSoftware Engineer

10. 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.
CodingMediumWells FargoSoftware Engineer

11. 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.
CodingMediumWells FargoSoftware Engineer

12. 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.
CodingMediumWells FargoSoftware Engineer

13. Maximum Earnings From Taxi (LeetCode)

Model answer

The task

Given a destination distance and a list of rides, choose compatible rides to maximize total earnings. A ride earns its distance plus its tip, and another ride may begin as soon as the previous one ends.

Key idea

Sort rides by ending point and use dynamic programming. For each ride, binary-search how many earlier rides finish no later than its start; then compare taking it with skipping it.

Approach

  1. Sort rides by end point.
  2. Store the sorted end points for binary searches.
  3. For each ride, find the count of earlier rides that do not overlap it.
  4. Set the best earnings so far to the maximum of skipping the ride or adding its earnings to the compatible prefix’s best total.
  5. Return the best total.
from bisect import bisect_right
from typing import List

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda ride: ride[1])
        ends = [end for _, end, _ in rides]

        # dp[i] is the best earnings using the first i rides.
        dp = [0] * (len(rides) + 1)

        for i, (start, end, tip) in enumerate(rides):
            # Count earlier rides that finish by this ride's start.
            compatible_count = bisect_right(ends, start, 0, i)
            earnings = end - start + tip

            dp[i + 1] = max(
                dp[i],  # Skip this ride.
                dp[compatible_count] + earnings,  # Take this ride.
            )

        return dp[-1]

Complexity:

  • Time: O(m log m), for sorting and one binary search per ride.
  • Space: O(m), for the sorted end points and DP array, where m is the number of rides.

Common follow-ups

  • How would you handle rides that can overlap at endpoints? Adjust the binary-search comparison to match whether endpoint sharing is allowed.
  • Can the DP be computed by start point instead? Yes; sort by start and use a reverse DP with a search for the next compatible ride.
  • What if rides arrive online? The sorted offline DP relies on knowing ride order; online variants need an ordered structure and may require additional assumptions about incoming rides.
CodingMediumWells FargoSoftware Engineer

14. Shortest and Lexicographically Smallest Beautiful String (LeetCode)

Model answer

The task

Given a binary string and a positive integer k, return the shortest substring containing exactly k ones. If several shortest substrings exist, return the lexicographically smallest; return an empty string if none exists.

Key idea

Record the positions of all ones. Any shortest valid substring must begin and end at ones, and its ones must be a group of k consecutive ones in that position list.

Approach

  1. Collect the indices of every '1'.
  2. If there are fewer than k, return an empty string.
  3. For each group of k consecutive ones, use its first and last positions as substring boundaries.
  4. Keep the shortest candidate; break equal-length ties by lexicographic order.
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # A shortest valid substring starts and ends at a one.
        ones = [i for i, ch in enumerate(s) if ch == "1"]

        if len(ones) < k:
            return ""

        best = ""

        # Each window of k consecutive ones defines a tight candidate.
        for i in range(len(ones) - k + 1):
            left = ones[i]
            right = ones[i + k - 1]
            candidate = s[left:right + 1]

            if (
                not best
                or len(candidate) < len(best)
                or (len(candidate) == len(best) and candidate < best)
            ):
                best = candidate

        return best

Complexity:

  • Time: O(n²) in the worst case, due to comparing candidate substrings.
  • Space: O(n) for the recorded one positions.

Common follow-ups

  • What if no substring contains k ones? Return the empty string.
  • Why only consider consecutive groups of ones? Any valid substring’s ones form such a group; extra boundary characters can only make it longer.
  • How would you handle many queries with different k values? Reuse the recorded one positions, then scan the relevant groups for each query.
CodingMediumWells FargoSoftware Engineer

15. 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.
CodingMediumWells FargoSoftware Engineer

16. Subarray Product Less Than K (LeetCode)

Model answer

The task

Count the contiguous subarrays whose product is strictly less than k.

Key idea

With positive numbers, extending a window never decreases its product. Maintain the longest window whose product is below k; every suffix of that window ending at the current position also qualifies.

Approach

  1. If k <= 1, return 0, since positive-number products are at least 1.
  2. Expand the right edge, multiplying its value into the window product.
  3. While the product is at least k, move the left edge forward and divide out the values it passes.
  4. Add the window length to the count: each possible starting point in the current window gives one qualifying subarray ending at the right edge.
from typing import List

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        left = 0
        product = 1
        count = 0

        for right, value in enumerate(nums):
            product *= value

            # Restore the condition that the window product is less than k.
            while product >= k:
                product //= nums[left]
                left += 1

            # Every nonempty suffix of this window is valid.
            count += right - left + 1

        return count

Complexity:

  • Time: O(n), since each element enters and leaves the window at most once.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if the array can contain zeros? Split at zeros, count positive-only ranges, and account for subarrays containing zero separately.
  • What if values can be negative? This sliding-window method no longer applies; products are not monotonic as the window grows.
  • Can the answer exceed a 32-bit integer? Yes; use an integer type large enough for the maximum subarray count.
CodingMediumWells FargoSoftware Engineer

17. Maximum Subarray (LeetCode)

Model answer

The task

Given an integer array, find the largest sum obtainable from a nonempty contiguous subarray. The array may contain only negative numbers.

Key idea

At each position, the best subarray ending there either starts at the current value or extends the best subarray ending just before it. Track that running best and the largest sum seen so far; this naturally handles all-negative arrays.

Approach

  1. Initialize both the running sum and overall maximum to the first value.
  2. Scan the remaining values from left to right.
  3. For each value, either start a new subarray there or extend the previous one.
  4. Update the overall maximum whenever the running sum improves.
  5. Return the overall maximum.
from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # The subarray must be nonempty, so start with the first element.
        current_sum = best_sum = nums[0]

        for value in nums[1:]:
            # Either begin at this value or extend the prior subarray.
            current_sum = max(value, current_sum + value)
            best_sum = max(best_sum, current_sum)

        return best_sum

Complexity:

  • Time: O(n), where n is the number of array elements; each is processed once.
  • Space: O(1), since only two running sums are stored.

Common follow-ups

  • How would you return the subarray’s start and end indices? Track the current start index and record both indices whenever the overall maximum improves.
  • What if the input can be empty? Define the desired empty-input result, then handle it before accessing the first element.
  • How does divide and conquer solve this? Recursively compute the best sum on each half, plus the best suffix on the left and prefix on the right; combine the three results.
CodingMediumWells FargoSoftware Engineer

18. Meeting Rooms II (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

            heapq.heappush(room_end_times, end)

        return len(room_end_times)

Complexity:

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

Common follow-ups

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

19. LFU Cache (LeetCode)

Model answer

The task

Design a cache with a fixed capacity that supports get and put. When it is full, evict the least frequently used key; if several keys have the same frequency, evict the least recently used among them.

Key idea

Track each key’s value and frequency, and maintain a doubly linked list of keys for each frequency. Within a list, keep the most recently used key at the front, so the least recently used key is at the back.

Approach

  1. Map each key to its cache node, and each frequency to a recency-ordered list.
  2. Keep min_freq to identify the frequency of the next eviction candidate.
  3. On get or an existing-key put, move the key to the next frequency’s list.
  4. On a new put, evict from the back of the min_freq list if needed, then insert at frequency 1.
class _Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None

class _DoublyLinkedList:
    def __init__(self):
        self.head = _Node(None, None)
        self.tail = _Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def pop_lru(self):
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}
        self.freq_lists = {}
        self.min_freq = 0

    def _touch(self, node):
        old_freq = node.freq
        old_list = self.freq_lists[old_freq]
        old_list.remove(node)

        if old_list.size == 0 and self.min_freq == old_freq:
            self.min_freq += 1

        node.freq += 1
        self.freq_lists.setdefault(node.freq, _DoublyLinkedList()).add_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._touch(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._touch(node)
            return

        if len(self.nodes) == self.capacity:
            lru_node = self.freq_lists[self.min_freq].pop_lru()
            del self.nodes[lru_node.key]

        node = _Node(key, value)
        self.nodes[key] = node
        self.freq_lists.setdefault(1, _DoublyLinkedList()).add_front(node)
        self.min_freq = 1

Complexity:

  • Time: O(1) expected per operation, using hash maps and constant-time list updates.
  • Space: O(capacity) for nodes and frequency lists.

Common follow-ups

  • What if eviction should use LRU only? Use one recency list instead of frequency lists.
  • How would you support aging so old accesses matter less? Periodically reduce or decay frequencies.
  • What if the cache is distributed? Discuss sharding and how to coordinate eviction state across shards.
CodingHardWells FargoSoftware Engineer

20. Verbal Arithmetic Puzzle (LeetCode)

Model answer

The task

Determine whether each letter in the addends and result can be replaced by a distinct digit so their arithmetic sum is valid. A multi-letter number cannot start with zero.

Key idea

Work from right to left, one decimal column at a time. Once the addend digits in a column are known, the result digit is forced by the column sum and carry.

Approach

  1. Collect the distinct letters; return False if there are more than ten.
  2. Record letters that cannot be zero because they begin multi-letter numbers.
  3. For each column, assign digits to any unassigned addend letters, respecting uniqueness and leading-zero rules.
  4. Check or assign the result letter using the column sum, then recurse to the next column with the carry.
  5. After all columns, accept only if no carry remains.
from typing import List

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        letters = set(result)
        for word in words:
            letters.update(word)

        if len(letters) > 10:
            return False

        leading = {
            word[0] for word in words + [result] if len(word) > 1
        }
        assignment = {}
        used_digits = set()

        columns = max(max(map(len, words)), len(result))

        def search_column(column: int, carry: int) -> bool:
            if column == columns:
                return carry == 0

            def add_words(word_index: int, total: int) -> bool:
                if word_index == len(words):
                    digit = total % 10
                    next_carry = total // 10

                    if column >= len(result):
                        # There is no result digit in this column.
                        return digit == 0 and search_column(
                            column + 1, next_carry
                        )

                    letter = result[-1 - column]
                    if letter in assignment:
                        if assignment[letter] != digit:
                            return False
                        return search_column(column + 1, next_carry)

                    if digit in used_digits:
                        return False
                    if digit == 0 and letter in leading:
                        return False

                    assignment[letter] = digit
                    used_digits.add(digit)
                    valid = search_column(column + 1, next_carry)
                    del assignment[letter]
                    used_digits.remove(digit)
                    return valid

                word = words[word_index]
                if column >= len(word):
                    return add_words(word_index + 1, total)

                letter = word[-1 - column]
                if letter in assignment:
                    return add_words(
                        word_index + 1, total + assignment[letter]
                    )

                for digit in range(10):
                    if digit in used_digits:
                        continue
                    if digit == 0 and letter in leading:
                        continue

                    assignment[letter] = digit
                    used_digits.add(digit)
                    if add_words(word_index + 1, total + digit):
                        return True
                    del assignment[letter]
                    used_digits.remove(digit)

                return False

            return add_words(0, carry)

        return search_column(0, 0)

Complexity:

  • Time: O(10! · W · C) in the worst case, where W is the number of addends and C is the number of columns.
  • Space: O(W + C), for the recursion stack and digit assignments.

Common follow-ups

  • What if more than ten distinct letters appear? Return False, since there are only ten digits.
  • How can search be pruned further? Check whether remaining columns can possibly accommodate the current carry and number lengths.
  • Can this handle bases other than ten? Yes; use digits from 0 to base - 1 and perform column arithmetic in that base.

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