BNY Mellon interview questions & answers

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

CodingEasyBNY MellonSoftware Engineer

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

Model answer

The task

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

Key idea

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

Approach

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

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

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

        return best_profit

Complexity:

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

Common follow-ups

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

2. Kth Largest Element in an Array (LeetCode)

Model answer

The task

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

Key idea

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

Approach

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

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

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

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

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

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

Complexity:

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

Common follow-ups

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

3. Sum of Distances (LeetCode)

Model answer

The task

For each position in an integer array, compute the sum of its distances to all other positions holding the same value. Return those sums in an array aligned with the original positions.

Key idea

Group positions by value; within each group, positions are sorted because they are collected during a left-to-right scan. Prefix sums let us find the total distance to positions on either side of each index in constant time.

Approach

  1. Scan the array and collect each value’s positions.
  2. For each group, build prefix sums of its positions.
  3. At group position k, calculate the contribution from earlier positions as index * k - prefix[k].
  4. Calculate the contribution from later positions using the remaining prefix sum.
  5. Store the two contributions’ sum at the original index.
from collections import defaultdict
from typing import List

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        positions = defaultdict(list)

        for index, value in enumerate(nums):
            positions[value].append(index)

        result = [0] * len(nums)

        for indices in positions.values():
            prefix = [0]
            for index in indices:
                prefix.append(prefix[-1] + index)

            count = len(indices)
            for k, index in enumerate(indices):
                left_distance = index * k - prefix[k]
                right_count = count - k - 1
                right_distance = (
                    prefix[count] - prefix[k + 1] - index * right_count
                )
                result[index] = left_distance + right_distance

        return result

Complexity:

  • Time: O(n), since each position is grouped and processed a constant number of times.
  • Space: O(n), for the position groups, prefix sums, and result.

Common follow-ups

  • Can the prefix arrays be avoided? Yes; compute each group’s contributions with a left-to-right pass and a right-to-left pass.
  • What if updates to the array are allowed? A changed value affects the groups for both the old and new values; dynamic updates need suitable ordered index structures.
  • How does the method handle values appearing once? Their group has one position, so both distance contributions are zero.
CodingMediumBNY MellonSoftware Engineer

4. Palindromic Substrings (LeetCode)

Model answer

The task

Given a string, count how many of its substrings are palindromes. Count each substring by its position, so equal text at different positions contributes more than once.

Key idea

Every palindrome has a center: either one character or the gap between two characters. Expand outward from each possible center while the characters match, counting each palindrome found.

Approach

  1. Initialize a counter for the palindromic substrings.
  2. Visit each character position as an odd-length center.
  3. Visit each gap between adjacent characters as an even-length center.
  4. For each center, expand left and right while the characters match, adding one to the counter for each match.
  5. Return the counter.
class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)

        def expand(left: int, right: int) -> int:
            found = 0

            # Every matching expansion forms another palindrome.
            while left >= 0 and right < n and s[left] == s[right]:
                found += 1
                left -= 1
                right += 1

            return found

        for center in range(n):
            # Odd-length palindromes centered on one character.
            count += expand(center, center)

            # Even-length palindromes centered between characters.
            count += expand(center, center + 1)

        return count

Complexity:

  • Time: O(n²), since each of the O(n) centers can expand across O(n) characters.
  • Space: O(1), using only a counter and a few indices.

Common follow-ups

  • How would you find the longest palindromic substring? Track the longest span found during each expansion.
  • How would you count distinct palindrome values instead of occurrences? Store the distinct palindrome strings in a set; this can require O(n²) space.
  • Can this be solved with dynamic programming? Yes: record whether each interval is a palindrome based on its end characters and its inner interval, using O(n²) time and space.
CodingMediumBNY MellonSoftware Engineer

5. 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.
CodingMediumBNY MellonSoftware Engineer

6. Bitwise ORs of Subarrays (LeetCode)

Model answer

The task

Count how many different values can be produced by bitwise-ORing the elements of a contiguous, nonempty subarray.

Key idea

For each position, keep the distinct OR values of subarrays that end there. Extending every such subarray with the current value produces the next set, whose size is bounded by the number of bits in the values.

Approach

  1. Initialize an empty set of all OR values and an empty set for subarrays ending at the previous position.
  2. For each value, start a new ending set with that value alone.
  3. OR the current value into every value in the previous ending set and add the results to the new set.
  4. Add the new ending set to the overall set, then use it for the next iteration.
  5. Return the number of values in the overall set.
class Solution:
    def subarrayBitwiseORs(self, arr: list[int]) -> int:
        all_ors = set()
        ending_ors = set()

        for value in arr:
            # Start a subarray at this position, and extend each
            # subarray that ended at the previous position.
            next_ending_ors = {value}
            for previous_or in ending_ors:
                next_ending_ors.add(previous_or | value)

            all_ors.update(next_ending_ors)
            ending_ors = next_ending_ors

        return len(all_ors)

Complexity:

  • Time: O(nW), where W is the maximum bit length; each position has at most O(W) distinct ending OR values.
  • Space: O(nW) for the set of all distinct results.

Common follow-ups

  • What if the array is empty? The method returns 0, since there are no nonempty subarrays.
  • Can the ending set grow to O(n)? No; OR only adds set bits, so it has at most O(W) distinct values.
  • How would you return the distinct OR values instead of their count? Return all_ors rather than its length.
CodingMediumBNY MellonSoftware Engineer

7. Car Fleet (LeetCode)

Model answer

The task

Given a destination and each car’s starting position and speed, count how many fleets reach the destination. Cars that catch up before arrival travel together at the speed of the slowest car in their fleet.

Key idea

Process cars from nearest to the destination to farthest. A car joins the fleet ahead if it would arrive no later than that fleet; otherwise, it forms a new fleet.

Approach

  1. Pair each car’s position with its speed.
  2. Sort the pairs by position, from closest to farthest from the destination.
  3. Compute each car’s arrival time.
  4. Count a new fleet whenever its arrival time is greater than the arrival time of the fleet ahead. Update that fleet’s time.
class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Process cars from nearest to the destination to farthest.
        cars = sorted(zip(position, speed), reverse=True)

        fleets = 0
        front_fleet_time = 0.0

        for pos, vel in cars:
            arrival_time = (target - pos) / vel

            # This car cannot catch the fleet ahead before the destination.
            if arrival_time > front_fleet_time:
                fleets += 1
                front_fleet_time = arrival_time

        return fleets

Complexity:

  • Time: O(n log n), for sorting the cars.
  • Space: O(n), for storing the sorted car pairs.

Common follow-ups

  • What if cars can start at the same position? Define how those cars are handled, then process them as a group.
  • Can the fleet count be computed with a stack? Yes; push each arrival time and merge times when a following car catches the fleet ahead.
  • How would you handle a very large number of cars? Sort positions externally or process already-sorted input in a streaming pass.
CodingMediumBNY MellonSoftware Engineer

8. 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.
CodingMediumBNY MellonSoftware Engineer

9. Count Number of Maximum Bitwise-OR Subsets (LeetCode)

Model answer

The task

Given an integer array, find the bitwise OR obtainable by OR-ing all its elements, then count the non-empty subsets whose OR equals that maximum.

Key idea

The OR of the entire array is the largest OR any subset can achieve. Enumerate subsets by making an include-or-skip choice for each element, and count those that reach this target.

Approach

  1. OR all elements to compute the target.
  2. Use depth-first search to process the array from left to right.
  3. At each element, explore skipping it and including it.
  4. At the end, count the subset if its OR equals the target and it contains at least one element.
from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        target = 0
        for value in nums:
            target |= value

        count = 0

        def search(index: int, current_or: int, chosen: bool) -> None:
            nonlocal count

            if index == len(nums):
                if chosen and current_or == target:
                    count += 1
                return

            # Skip this element.
            search(index + 1, current_or, chosen)

            # Include this element.
            search(index + 1, current_or | nums[index], True)

        search(0, 0, False)
        return count

Complexity:

  • Time: O(2ⁿ), exploring every subset.
  • Space: O(n), for the recursion stack.

Common follow-ups

  • Can this be solved iteratively? Yes; maintain counts of ways to form each OR value as elements are processed.
  • What if only the maximum OR value is needed? OR all array elements in one pass.
  • How would you handle a very large array? Use the iterative OR-state approach when the number of distinct OR values stays small.
CodingMediumBNY MellonSoftware Engineer

10. Minimize Length of Array Using Operations (LeetCode)

Model answer

The task

Given an integer array, apply the permitted pairwise operations to make the array as short as possible. Return the minimum achievable length.

Key idea

Let m be the array’s smallest value. If some value is not divisible by m, the arithmetic operations can produce a smaller positive value, allowing the array to be reduced to length 1. Otherwise, only the copies of m determine the minimum length: the answer is half their count, rounded up.

Approach

  1. Find the minimum value m.
  2. Count how many times m occurs.
  3. If any array value is not divisible by m, return 1.
  4. Otherwise, return (count + 1) // 2.
from typing import List

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        minimum = min(nums)
        minimum_count = 0

        for value in nums:
            if value % minimum != 0:
                return 1
            if value == minimum:
                minimum_count += 1

        return (minimum_count + 1) // 2

Complexity:

  • Time: O(n), one pass through the array.
  • Space: O(1), using only a few counters.

Common follow-ups

  • Why do nonmultiples allow a final length of 1? The pairwise arithmetic reductions can produce a positive remainder smaller than the current minimum, then continue reducing until only one value remains.
  • Why count only the minimum values? When every value is divisible by the minimum, the other values can be reduced using it; the minimum values are the limiting elements.
  • What if all values are equal? The answer is (n + 1) // 2, directly from the count of the minimum.
CodingMediumBNY MellonSoftware Engineer

11. Longest Substring Without Repeating Characters (LeetCode)

Model answer

The task

Find the length of the longest contiguous section of a string in which every character appears at most once.

Key idea

Maintain a sliding window with no repeated characters. When a character repeats within the window, move the left edge just past its previous occurrence.

Approach

  1. Track each character’s most recent index in a dictionary.
  2. Keep left as the window’s starting index and best as its longest length so far.
  3. For each character, move left forward if its previous occurrence is inside the current window.
  4. Record the character’s current index and update best using the window length.
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0

        for right, char in enumerate(s):
            # Skip past a repeated character if it is in the current window.
            if char in last_seen and last_seen[char] >= left:
                left = last_seen[char] + 1

            last_seen[char] = right
            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), because each character is processed once.
  • Space: O(k), where k is the number of distinct characters encountered.

Common follow-ups

  • Return the substring itself: store the best window’s start and end indices when updating best.
  • Handle a stream of characters: keep the same window state and process each arriving character incrementally.
  • Use a fixed-size character set: replace the dictionary with an array of last-seen indices.
CodingHardBNY MellonSoftware Engineer

12. Lexicographically Maximum MEX Array (LeetCode)

Model answer

The task

The title suggests constructing a lexicographically largest sequence of MEX values from an array. The exact allowed operation is unclear; the approach and code below apply if the task is to partition the array into contiguous segments and output each segment’s MEX.

Key idea

For each remaining suffix, its MEX is the largest value any prefix segment can have. Greedily take the shortest prefix containing every smaller value; this emits that MEX while leaving as much of the array as possible for later segments.

Approach

  1. Count the frequencies of values from 0 through n; other values cannot affect a MEX.
  2. Keep a min-heap of values currently absent from the remaining suffix. Its minimum is the suffix MEX.
  3. Scan forward until the segment contains every value smaller than that MEX.
  4. If the MEX is zero, take one element so the scan always makes progress.
  5. Decrease frequencies as elements are consumed, adding values to the heap when their last occurrence is removed.
from collections import Counter
import heapq

def build(nums):
    """Build the maximum-MEX partition for the contiguous-segment formulation."""
    n = len(nums)
    freq = Counter(x for x in nums if 0 <= x <= n)

    # Values absent from the whole array are already missing from the suffix.
    missing = [x for x in range(n + 1) if freq[x] == 0]
    heapq.heapify(missing)

    result = []
    i = 0

    while i < n:
        target = missing[0]
        seen = set()
        start = i

        # A zero MEX needs no values to be seen; consume one element.
        if target == 0:
            i += 1
        else:
            while i < n and len(seen) < target:
                value = nums[i]
                if 0 <= value < target:
                    seen.add(value)
                i += 1

        result.append(target)

        # Update which values are absent from the unconsumed suffix.
        for value in nums[start:i]:
            if 0 <= value <= n:
                freq[value] -= 1
                if freq[value] == 0:
                    heapq.heappush(missing, value)

    return result

Complexity:

  • Time: O(n log n), from heap updates; each array element is consumed once.
  • Space: O(n), for frequencies, the heap, and per-segment tracking.

Common follow-ups

  • What if segments may be non-contiguous? The greedy scan no longer applies; the permitted grouping operation must be specified.
  • What if only the maximum MEX value is needed? Count frequencies and find the smallest absent nonnegative integer.
  • What if the input is streamed? Maintain counts and missing values as elements arrive, but partition decisions may require buffering a segment.
CodingHardBNY MellonSoftware Engineer

13. Minimize Malware Spread (LeetCode)

Model answer

The task

Given an undirected graph and a set of initially infected nodes, remove one initial infection to minimize how many nodes eventually become infected. If several choices are equally good, return the smallest node index.

Key idea

Infection spreads through each connected component. Removing an infection helps only when it is the sole initially infected node in its component; in that case, it saves the entire component.

Approach

  1. Use disjoint-set union (DSU) to find the graph’s connected components.
  2. Count the initial infections in each component.
  3. For each initial node, consider its component size only if that component has exactly one initial infection.
  4. Choose the node that saves the largest component; break ties by choosing the smallest index.
  5. If no node saves a component, return the smallest initially infected node.
from typing import List

class Solution:
    def minMalwareSpread(
        self, graph: List[List[int]], initial: List[int]
    ) -> int:
        n = len(graph)
        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # Path halving
                x = parent[x]
            return x

        def union(a: int, b: int) -> None:
            root_a, root_b = find(a), find(b)
            if root_a == root_b:
                return

            # Union by size keeps the trees shallow.
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            size[root_a] += size[root_b]

        # Build connected components from the adjacency matrix.
        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j] == 1:
                    union(i, j)

        infected_count = [0] * n
        for node in initial:
            infected_count[find(node)] += 1

        # Sorting ensures the smallest index wins ties.
        answer = min(initial)
        best_saved = 0

        for node in sorted(initial):
            root = find(node)
            if infected_count[root] == 1 and size[root] > best_saved:
                best_saved = size[root]
                answer = node

        return answer

Complexity:

  • Time: O(n² α(n) + m log m), where n is the number of nodes, m the number of initial infections, and α the inverse Ackermann function.
  • Space: O(n) for the DSU and component infection counts.

Common follow-ups

  • What if removing a node also removes its edges? That is a different variant; recompute spread after excluding the node, often using DFS/BFS per candidate.
  • What if multiple initial infections can be removed? The choice may involve selecting components and becomes an optimization problem over the removal budget.
  • Can the graph be processed from an edge list? Yes; union the endpoints of each edge instead of scanning the adjacency matrix.
CodingHardBNY MellonSoftware Engineer

14. Count Visited Nodes in a Directed Graph (LeetCode)

Model answer

The task

Given a directed graph where every node has exactly one outgoing edge, return for each node the number of distinct nodes visited by repeatedly following edges, counting the start node and stopping when a node repeats.

Key idea

Such a graph consists of directed cycles with trees feeding into them. Remove nodes that cannot be on a cycle, assign each cycle node the cycle’s length, then process removed nodes in reverse order to build their counts from their successors.

Approach

  1. Compute each node’s indegree and queue all nodes with indegree zero.
  2. Repeatedly remove queued nodes, recording their order and reducing the indegree of each successor.
  3. Nodes with positive indegree after removal belong to cycles. Traverse each cycle and assign its length to every node in it.
  4. Process removed nodes in reverse order; each count is one plus the count of its successor.
from typing import List

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        indegree = [0] * n

        for successor in edges:
            indegree[successor] += 1

        # Remove all nodes that cannot be part of a directed cycle.
        queue = [node for node in range(n) if indegree[node] == 0]
        removed = []
        head = 0

        while head < len(queue):
            node = queue[head]
            head += 1
            removed.append(node)

            successor = edges[node]
            indegree[successor] -= 1
            if indegree[successor] == 0:
                queue.append(successor)

        answer = [0] * n

        # Remaining nodes form cycles; assign each cycle's length.
        for node in range(n):
            if indegree[node] > 0:
                cycle = []
                current = node

                while True:
                    cycle.append(current)
                    indegree[current] = 0  # Mark this cycle node as processed.
                    current = edges[current]
                    if current == node:
                        break

                cycle_length = len(cycle)
                for cycle_node in cycle:
                    answer[cycle_node] = cycle_length

        # Successors are already resolved when processing in reverse order.
        for node in reversed(removed):
            answer[node] = answer[edges[node]] + 1

        return answer

Complexity:

  • Time: O(n), since each node is processed a constant number of times.
  • Space: O(n), for indegrees, the queue, removal order, and answers.

Common follow-ups

  • How would you handle nodes with no outgoing edge? Add a terminal case with a defined count instead of assuming every node has a successor.
  • Can this be solved with recursive DFS? Yes, with memoization and cycle-state tracking, though recursion depth may require care.
  • What if only one node’s count is needed? The same decomposition works, but a full linear pass may still be needed to identify its cycle and path.
CodingHardBNY MellonSoftware Engineer

15. Count Good Subarrays (LeetCode)

Model answer

The task

The title suggests counting contiguous subarrays that satisfy a “good” condition, but the title and tags do not define that condition. Without it, a problem-specific algorithm or interface cannot be determined reliably.

Key idea

The tags suggest the intended solution may combine monotonic-stack boundaries with bitwise state. Which boundaries and state to maintain depends on the missing definition of “good,” so the code below is a generic reference, not a solution to a specific predicate.

Approach

  1. Specify a predicate that determines whether a subarray is good.
  2. Enumerate all subarray boundaries.
  3. Apply the predicate to each subarray and count those that pass.
  4. Once the predicate is known, optimize: monotonic stacks can find relevant extremum boundaries, while bitwise grouping can avoid revisiting repeated bitwise states.
from collections.abc import Callable, Sequence

def count_good_subarrays(
    nums: Sequence[int],
    is_good: Callable[[Sequence[int], int, int], bool],
) -> int:
    """Count subarrays accepted by is_good(nums, left, right).

    This generic reference assumes right is inclusive. The predicate's
    meaning and cost depend on the problem definition.
    """
    count = 0

    for left in range(len(nums)):
        for right in range(left, len(nums)):
            if is_good(nums, left, right):
                count += 1

    return count

Complexity:

  • Time: O(n² · P), where P is the cost of one predicate call.
  • Space: O(1) auxiliary space, excluding the predicate’s own storage.

Common follow-ups

  • How can this be made faster? Use the exact “good” condition to identify reusable state or boundaries; the tags suggest monotonic stacks and bitwise-state grouping.
  • What if the condition depends only on a subarray’s maximum or minimum? A monotonic stack can find the spans in which each element is an extremum.
  • What if the condition uses bitwise AND or OR? Track distinct bitwise results for subarrays ending at each position; their number is typically bounded by the bit width.
CodingHardBNY MellonSoftware Engineer

16. Cherry Pickup (LeetCode)

Model answer

The task

Given a square grid with cherries and impassable cells, find the maximum cherries collectable on a trip from the top-left to the bottom-right and back. A cherry can be collected only once, and neither leg may pass through an impassable cell.

Key idea

Treat the two legs as two travelers moving from the top-left to the bottom-right at the same time. After the same number of moves, both travelers are on the same diagonal, so their positions can be tracked by their row indices. Dynamic programming finds the best total cherries while counting a shared cell only once.

Approach

  1. Let dp[r1][r2] be the best total after the current number of moves, with the travelers in rows r1 and r2.
  2. Derive each column from the move count and row.
  3. For each pair of valid, non-thorn cells, consider the four combinations of previous rows.
  4. Add the cherries at both positions, counting them once if the travelers coincide.
  5. Return the best value at the destination, or zero if no valid round trip exists.
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if n == 0 or grid[0][0] == -1:
            return 0

        neg = float("-inf")
        dp = [[neg] * n for _ in range(n)]
        dp[0][0] = grid[0][0]

        # Both travelers make one move per step.
        for steps in range(1, 2 * n - 1):
            curr = [[neg] * n for _ in range(n)]

            # A row is possible only if its corresponding column is in bounds.
            low = max(0, steps - (n - 1))
            high = min(n - 1, steps)

            for r1 in range(low, high + 1):
                c1 = steps - r1
                if grid[r1][c1] == -1:
                    continue

                for r2 in range(low, high + 1):
                    c2 = steps - r2
                    if grid[r2][c2] == -1:
                        continue

                    best_previous = neg
                    # Each traveler either moved right (same row) or down
                    # (previous row was one less).
                    for p1 in (r1, r1 - 1):
                        for p2 in (r2, r2 - 1):
                            if 0 <= p1 < n and 0 <= p2 < n:
                                best_previous = max(
                                    best_previous, dp[p1][p2]
                                )

                    if best_previous == neg:
                        continue

                    cherries = grid[r1][c1]
                    if r1 != r2:  # Different rows mean different cells.
                        cherries += grid[r2][c2]

                    curr[r1][r2] = best_previous + cherries

            dp = curr

        return max(0, dp[n - 1][n - 1])

Complexity:

  • Time: O(n³), for O(n²) row pairs across O(n) move steps.
  • Space: O(n²), for the two rolling DP tables.

Common follow-ups

  • How would you handle larger, sparse grids? Store only reachable states or use sparse maps when few cells are open.
  • What if cells have arbitrary rewards? Add both cell values, still counting a shared cell once.
  • What if there are more than two travelers? Track each traveler’s position, though the state size grows quickly.
CodingHardBNY MellonSoftware Engineer

17. 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.
CodingHardBNY MellonSoftware Engineer

18. Find the Maximum Length of a Good Subsequence II (LeetCode)

Model answer

The task

Find the longest subsequence with at most k adjacent pairs of unequal values.

Key idea

Track the best subsequence ending in each value for every exact number of value changes. For a new value, extend a subsequence ending in that same value without adding a change, or extend one ending in a different value while adding a change.

For each change count, keep the best and second-best lengths across ending values. This lets us find the best prior subsequence that does not end in the current value in constant time.

Approach

  1. Store dp[value][j]: the longest subsequence ending in value with exactly j changes.
  2. For each number, compute its new lengths using the old DP states and the best prior ending values.
  3. For a transition adding a change, use the best ending value unless it matches the current number; otherwise use the second-best.
  4. Update the DP and the best-two summaries only after computing all states for that number.
  5. Return the maximum length over all states.
from typing import Dict, List, Optional, Tuple

class Solution:
    def maxSubsequenceLength(self, nums: List[int], k: int) -> int:
        # For each change count, retain the two best lengths from
        # different ending values.
        best_len = [[0, 0] for _ in range(k + 1)]
        best_val: List[List[Optional[int]]] = [
            [None, None] for _ in range(k + 1)
        ]

        dp: Dict[int, List[int]] = {}
        answer = 0

        def update_best(j: int, value: int, length: int) -> None:
            first_len, second_len = best_len[j]
            first_val, second_val = best_val[j]

            if first_val == value:
                best_len[j][0] = max(first_len, length)
            elif length > first_len:
                best_len[j] = [length, first_len]
                best_val[j] = [value, first_val]
            elif second_val == value:
                best_len[j][1] = max(second_len, length)
            elif length > second_len:
                best_len[j][1] = length
                best_val[j][1] = value

        for value in nums:
            ending = dp.setdefault(value, [0] * (k + 1))
            new_lengths = ending[:]

            for j in range(k + 1):
                # Extend a subsequence with the same ending value.
                if ending[j] > 0:
                    new_lengths[j] = max(new_lengths[j], ending[j] + 1)

                if j == 0:
                    new_lengths[j] = max(new_lengths[j], 1)
                else:
                    # Extend one ending in a different value.
                    slot = 0 if best_val[j - 1][0] != value else 1
                    previous_value = best_val[j - 1][slot]
                    if previous_value is not None:
                        new_lengths[j] = max(
                            new_lengths[j],
                            best_len[j - 1][slot] + 1,
                        )

            for j, length in enumerate(new_lengths):
                if length > ending[j]:
                    ending[j] = length
                    update_best(j, value, length)
                answer = max(answer, ending[j])

        return answer

Complexity:

  • Time: O(nk), processing each number across all change counts.
  • Space: O(uk), where u is the number of distinct values stored in the DP.

Common follow-ups

  • What if the number of changes must be exactly k? Return the state for exactly k, if it exists.
  • Can the best-two summaries be replaced with a scan? Yes, but scanning all ending values can make the runtime quadratic in the number of distinct values.
  • What if k is larger than the sequence can use? The DP naturally handles it; no subsequence can have more than n - 1 changes.

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