Deutsche Bank interview questions & answers

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

CodingEasyDeutsche BankSoftware Engineer

1. Squares of a Sorted Array (LeetCode)

Model answer

The task

Given an array sorted in nondecreasing order, return a new array containing the square of each value, also sorted in nondecreasing order.

Key idea

Squaring can make negative values large, so the largest square must come from one of the two ends of the input. Compare the absolute values at both ends and fill the result from right to left.

Approach

  1. Set pointers at the first and last elements.
  2. Allocate a result array of the same length.
  3. Compare the absolute values at the pointers.
  4. Place the larger square at the current result position, then move the corresponding pointer inward.
  5. Continue until every position has been filled.
class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        left, right = 0, len(nums) - 1
        result = [0] * len(nums)
        write = len(nums) - 1

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                value = nums[left]
                left += 1
            else:
                value = nums[right]
                right -= 1

            result[write] = value * value
            write -= 1

        return result

Complexity:

  • Time: O(n), since each input element is processed once.
  • Space: O(n), for the returned array.

Common follow-ups

  • Can this be done without allocating a result array? Not while returning a separate sorted array in the general case; the output itself requires O(n) space.
  • What if the input is not sorted? Sort it first, which takes O(n log n), then use the two-pointer method.
  • How do duplicates affect the algorithm? They need no special handling; equal absolute values produce equal squares.
CodingEasyDeutsche BankSoftware Engineer

2. Minimum Operations to Make the Array Increasing (LeetCode)

Model answer

The task

Given an integer array, find the fewest single-element increments needed to make it strictly increasing. Each operation increases one element by 1.

Key idea

Process the array from left to right. For each element, keep it if it is already greater than the previous adjusted element; otherwise, raise it to exactly one more than that element.

Approach

  1. Start with zero operations and no previous adjusted value.
  2. Visit each array element from left to right.
  3. If it is not greater than the previous adjusted value, increment it conceptually to previous + 1.
  4. Add the required increase to the operation count and use the adjusted value as the new previous value.
  5. Return the total.
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        operations = 0
        previous = None

        for value in nums:
            if previous is not None and value <= previous:
                adjusted = previous + 1
                operations += adjusted - value
            else:
                adjusted = value

            previous = adjusted

        return operations

Complexity:

  • Time: O(n), where n is the number of array elements.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if the array must be non-decreasing instead? Allow each value to equal the previous one; adjust only when it is smaller.
  • What if increments have different costs? Choose the cheapest feasible adjustment at each position, if costs are independent and constraints permit it.
  • Can the adjusted array also be returned? Store each adjusted value during the same pass and return it alongside the operation count.
CodingEasyDeutsche BankSoftware Engineer

3. Pascal's Triangle (LeetCode)

Model answer

The task

Given a number of rows, build Pascal’s Triangle up to that many rows. Each row starts and ends with 1, and each interior value is the sum of the two values above it.

Key idea

Construct rows from top to bottom. For each new row, use the previous row to compute its interior values.

Approach

  1. Start with an empty list of rows.
  2. For each row index, create a row of the required length filled with 1s.
  3. For interior positions, add the two relevant values from the preceding row.
  4. Append the completed row and return all rows.
from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle: List[List[int]] = []

        for row_index in range(numRows):
            # The first and last entries are always 1.
            row = [1] * (row_index + 1)

            # Compute interior entries from the previous row.
            if row_index > 1:
                previous = triangle[-1]
                for column in range(1, row_index):
                    row[column] = previous[column - 1] + previous[column]

            triangle.append(row)

        return triangle

Complexity:

  • Time: O(n²), since the total number of entries generated is proportional to the square of the number of rows.
  • Space: O(n²), to store the returned triangle.

Common follow-ups

  • Return only the row at a given index: build rows iteratively while retaining only the current row.
  • Generate a row using binomial coefficients: compute each value from the preceding value in constant time.
  • Reduce auxiliary space: update one row in place, working from right to left so earlier values remain available.
CodingEasyDeutsche BankSoftware Engineer

4. 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.
CodingEasyDeutsche BankSoftware Engineer

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

Model answer

The task

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

Key idea

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

Approach

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

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

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

        return best_profit

Complexity:

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

Common follow-ups

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

6. Minimum Operations to Collect Elements (LeetCode)

Model answer

The task

Count how many elements must be taken from the end of the array before every value from 1 through k has appeared.

Key idea

Scan the array from right to left, matching the order in which elements are taken. Track distinct values in the range 1..k; stop once all k have been seen.

Approach

  1. Create a set for the required values seen so far.
  2. Visit elements from the end of the array.
  3. Add an element to the set if it is between 1 and k.
  4. Return the number of visited elements as soon as the set contains k values.
  5. If the scan ends first, return the array length.
class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        seen = set()

        for operations, value in enumerate(reversed(nums), start=1):
            if 1 <= value <= k:
                seen.add(value)

            if len(seen) == k:
                return operations

        return len(nums)

Complexity:

  • Time: O(n), where n is the length of nums.
  • Space: O(k), for the set of collected values.

Common follow-ups

  • What if values can be very large? Ignore values outside 1..k; they cannot help collect a required element.
  • Can the set be replaced with a boolean array? Yes; use an array of length k + 1 to track which required values have appeared.
  • What if the elements are streamed from the end? Keep the same set and count, stopping when all k required values have appeared.
CodingMediumDeutsche BankSoftware Engineer

7. The Time When the Network Becomes Idle (LeetCode)

Model answer

The task

Given an undirected network with server 0 and a patience value for each server, find the earliest second after which no messages are in transit and no server will send another message.

Key idea

A server’s first message takes its shortest-path distance to reach server 0, and the reply takes the same time back. If the reply takes rtt seconds, only retransmissions sent strictly before rtt can occur. The network becomes idle one second after the latest reply arrives.

Approach

  1. Build an adjacency list from the network connections.
  2. Run BFS from server 0 to find each server’s shortest-path distance.
  3. For each nonzero server, compute its round-trip time as twice its distance.
  4. Find its final retransmission time using its patience value, then compute when that message’s reply arrives.
  5. Return one second after the latest such arrival.
from collections import deque
from typing import List

class Solution:
    def networkBecomesIdle(
        self, edges: List[List[int]], patience: List[int]
    ) -> int:
        n = len(patience)
        graph = [[] for _ in range(n)]

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        # Find shortest-path distances from the master server, 0.
        distance = [-1] * n
        distance[0] = 0
        queue = deque([0])

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if distance[neighbor] == -1:
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        latest_reply = 0

        for server in range(1, n):
            round_trip = 2 * distance[server]

            # The final retry must be sent strictly before the first reply.
            last_retry = ((round_trip - 1) // patience[server]) * patience[server]
            latest_reply = max(latest_reply, last_retry + round_trip)

        # The network is idle starting one second after the last reply.
        return latest_reply + 1

Complexity:

  • Time: O(n + m), for BFS and processing all servers, where m is the number of connections.
  • Space: O(n + m), for the adjacency list, distances, and BFS queue.

Common follow-ups

  • What if links have different travel times? Use a shortest-path algorithm for weighted edges, such as Dijkstra’s algorithm.
  • What if the network is directed? Build directed adjacency lists and compute the required outward and return travel times separately.
  • How would you handle a large, sparse network? Store connections as adjacency lists and use BFS, as above.
CodingMediumDeutsche BankSoftware Engineer

8. 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.
CodingMediumDeutsche BankSoftware Engineer

9. Reverse Words in a String (LeetCode)

Model answer

The task

Return the words of a string in reverse order, with exactly one space between words and no leading or trailing spaces. Treat any run of whitespace as a separator.

Key idea

Reverse the entire character array, then reverse each word to restore its letters. While scanning, compact words in place and write only one space between them.

Approach

  1. Convert the string to a mutable character array and reverse it.
  2. Scan past whitespace to find each word.
  3. Reverse the letters within that word.
  4. Copy the word to the next write position, inserting one space if needed.
  5. Join the compacted portion of the array.
class Solution:
    def reverseWords(self, s: str) -> str:
        chars = list(s)
        n = len(chars)

        def reverse(left: int, right: int) -> None:
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1

        # Reversing the whole string puts the words in reverse order.
        reverse(0, n - 1)

        read = 0
        write = 0

        while read < n:
            # Skip any whitespace between words.
            while read < n and chars[read].isspace():
                read += 1

            if read == n:
                break

            start = read

            # Find the end of the current word.
            while read < n and not chars[read].isspace():
                read += 1

            end = read - 1
            reverse(start, end)

            # Keep exactly one space between output words.
            if write > 0:
                chars[write] = " "
                write += 1

            # Compact this word into the output prefix.
            for i in range(start, end + 1):
                chars[write] = chars[i]
                write += 1

        return "".join(chars[:write])

Complexity:

  • Time: O(n), where n is the string length.
  • Space: O(n) for the mutable character array.

Common follow-ups

  • How would you handle only ordinary spaces as separators? Replace isspace() with comparisons to " ".
  • Can this be done in place? The character operations are in place, but Python strings are immutable, so the array requires O(n) space.
  • What if the input is a stream too large to fit in memory? Use an external or chunked representation, while preserving word boundaries between chunks.
CodingMediumDeutsche BankSoftware Engineer

10. Pour Water Between Buckets to Make Water Levels Equal (LeetCode)

Model answer

The task

Given bucket water amounts and the percentage lost during a pour, find the greatest amount that can be left in every bucket after equalizing them.

Key idea

For a proposed final level, buckets above it are donors and buckets below it need water. A donor’s excess contributes only the retained fraction toward filling deficits, so feasibility is monotonic: if a level is feasible, every lower level is feasible too.

Approach

  1. Search for the final level between the smallest and largest initial amounts.
  2. For each candidate, sum the excess in buckets above it, multiplied by the retained fraction.
  3. Sum the deficits in buckets below it.
  4. If usable surplus covers the deficits, raise the lower bound; otherwise lower the upper bound.
  5. Return the greatest feasible level found.
from typing import List

class Solution:
    def equalizeWater(self, buckets: List[int], loss: int) -> float:
        # Fraction of poured water that reaches the receiving bucket.
        retained = (100 - loss) / 100.0
        low = float(min(buckets))
        high = float(max(buckets))

        # Keep the feasible endpoint as the lower bound.
        for _ in range(80):
            target = (low + high) / 2.0
            usable_surplus = 0.0
            needed = 0.0

            for amount in buckets:
                if amount > target:
                    usable_surplus += (amount - target) * retained
                else:
                    needed += target - amount

            if usable_surplus >= needed:
                low = target
            else:
                high = target

        return low

Complexity:

  • Time: O(n · 80), for 80 binary-search iterations over all buckets.
  • Space: O(1), using only a few running totals.

Common follow-ups

  • What if there is no water loss? The method reduces to finding the average water level.
  • How should precision be chosen? Iterate until the search interval is sufficiently small, or stop when its width is below a tolerance.
  • What if the loss percentage is 100? Poured water never reaches another bucket, so the maximum equal level is the smallest initial amount.
CodingMediumDeutsche BankSoftware Engineer

11. Different Ways to Add Parentheses (LeetCode)

Model answer

The task

Given an arithmetic expression with integer operands and +, -, and *, return every result obtainable by inserting parentheses in all valid ways. Keep duplicate results when different parenthesizations produce the same value.

Key idea

Each operator can be the final operation in a parenthesized expression. Try each operator as a split, recursively find all results on its left and right, then combine every pair.

Memoization avoids recomputing results for the same operand range.

Approach

  1. Separate the expression into operands and operators.
  2. Define a cached function for the results from an inclusive range of operands.
  3. If the range contains one operand, return its integer value.
  4. For each operator in the range, recursively compute left and right results.
  5. Combine every left-right pair using that operator and return the collected results.
from functools import lru_cache
from typing import List

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        operands: List[int] = []
        operators: List[str] = []

        # Parse the expression into numbers and operators.
        number = 0
        reading_number = False

        for char in expression:
            if char.isdigit():
                number = number * 10 + int(char)
                reading_number = True
            else:
                operands.append(number)
                operators.append(char)
                number = 0
                reading_number = False

        if reading_number:
            operands.append(number)

        @lru_cache(maxsize=None)
        def compute(left: int, right: int) -> tuple[int, ...]:
            if left == right:
                return (operands[left],)

            results = []
            for split in range(left, right):
                operator = operators[split]
                left_values = compute(left, split)
                right_values = compute(split + 1, right)

                for a in left_values:
                    for b in right_values:
                        if operator == "+":
                            results.append(a + b)
                        elif operator == "-":
                            results.append(a - b)
                        else:  # operator == "*"
                            results.append(a * b)

            return tuple(results)

        return list(compute(0, len(operands) - 1))

Complexity:

  • Time: O(k² · Cₖ), a conservative bound for combining results across cached ranges, where k is the number of operators and Cₖ is the kth Catalan number.
  • Space: O(k² · Cₖ) in the worst case for cached result lists; the returned list itself can contain Cₖ values.

Common follow-ups

  • What if the expression contains division? Define the required division and rounding behavior, then add that operation when combining results.
  • Can duplicate results be removed? Use a set for each range, but this changes the output to distinct values only.
  • How would you reduce memory? Avoid caching every range, or compute ranges on demand with an explicit time-memory tradeoff.
CodingMediumDeutsche BankSoftware Engineer

12. Coin Change (LeetCode)

Model answer

The task

Given coin denominations that can be used any number of times, find the fewest coins needed to make the target amount. Return -1 if no combination can make it.

Key idea

Let dp[x] be the minimum number of coins needed to form amount x. For each coin, update larger amounts in ascending order so that the same coin can be reused.

Approach

  1. Initialize all states as unreachable, except dp[0] = 0.
  2. Process each coin denomination.
  3. For each amount from that coin through the target, use the coin if the preceding amount is reachable.
  4. Return the target state, or -1 if it remains unreachable.
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # amount + 1 is larger than any possible answer using positive coins.
        unreachable = amount + 1
        dp = [unreachable] * (amount + 1)
        dp[0] = 0

        # Ascending amounts allow each denomination to be used repeatedly.
        for coin in coins:
            for current in range(coin, amount + 1):
                if dp[current - coin] != unreachable:
                    dp[current] = min(
                        dp[current],
                        dp[current - coin] + 1,
                    )

        return dp[amount] if dp[amount] != unreachable else -1

Complexity:

  • Time: O(n × amount), where n is the number of denominations.
  • Space: O(amount) for the dynamic programming array.

Common follow-ups

  • How can the actual coins be returned? Store the last coin used whenever a state improves, then backtrack from the target.
  • Could breadth-first search solve it? Yes; treat each amount as a node and each coin as an edge, and find the shortest path from zero to the target.
  • What changes if each coin has a limited supply? Track the remaining inventory or use a bounded-knapsack method instead of the unlimited reuse update.
CodingMediumDeutsche BankSoftware Engineer

13. Maximum Coins Heroes Can Collect (LeetCode)

Model answer

The task

For each hero, find the total coins from all monsters whose power is no greater than that hero’s. Return the totals in the original hero order.

Key idea

Sort monsters by power and build prefix sums of their coin values. A binary search then finds how many monsters each hero can defeat, and the corresponding prefix sum gives the answer.

Approach

  1. Pair each monster’s power with its coin reward.
  2. Sort those pairs by power.
  3. Build prefix sums of rewards in sorted order.
  4. For each hero, use bisect_right to count monsters with power at most the hero’s power.
  5. Use that count to look up the total in the prefix sums.
from bisect import bisect_right
from itertools import accumulate
from typing import List

class Solution:
    def maximumCoins(
        self, heroes: List[int], monsters: List[int], coins: List[int]
    ) -> List[int]:
        # Sort monsters and their rewards together by monster power.
        pairs = sorted(zip(monsters, coins))
        powers = [power for power, _ in pairs]

        # prefix[i] is the total reward from the first i sorted monsters.
        prefix = [0, *accumulate(reward for _, reward in pairs)]

        # bisect_right includes monsters whose power equals the hero's power.
        return [prefix[bisect_right(powers, hero)] for hero in heroes]

Complexity:

  • Time: O(m log m + h log m), for sorting m monsters and searching for each of h heroes.
  • Space: O(m), for the sorted pairs and prefix sums.

Common follow-ups

  • What if a hero can defeat monsters with power strictly less than theirs? Use bisect_left instead.
  • What if monster rewards can be negative? Prefix sums still work; the same lookup returns the sum of all eligible rewards.
  • What if many queries arrive over time? Keep the sorted powers and prefix sums, then answer each query with binary search.
CodingHardDeutsche BankSoftware Engineer

14. Split Array With Same Average (LeetCode)

Model answer

The task

Determine whether the array can be divided into two nonempty parts with equal average. The parts do not need to be contiguous.

Key idea

A chosen subset of size k has the same average as the whole array exactly when its sum is k total / n. To avoid fractions, transform each value x into n x - total; a valid subset then has transformed sum zero.

Split the transformed values in half, store subset sums by subset size, and look for two complementary sums that add to zero. Exclude the empty subset and the entire array.

Approach

  1. Transform each value using the array length and total sum.
  2. Split the transformed values into two halves.
  3. For each half, collect subset sums grouped by subset size.
  4. Check whether a sum from one half has its negation in the other half, with a combined size between 1 and n - 1.
  5. Return whether such a pair exists.
class Solution:
    def splitArraySameAverage(self, nums: list[int]) -> bool:
        n = len(nums)
        total = sum(nums)

        # A zero-sum subset of these transformed values has the
        # same average as the original array.
        transformed = [n * value - total for value in nums]
        middle = n // 2

        def subset_sums_by_size(values: list[int]) -> list[set[int]]:
            groups = [set() for _ in range(len(values) + 1)]
            groups[0].add(0)

            processed = 0
            for value in values:
                # Descending order ensures each value is used once.
                for size in range(processed, -1, -1):
                    for current_sum in groups[size]:
                        groups[size + 1].add(current_sum + value)
                processed += 1

            return groups

        left = subset_sums_by_size(transformed[:middle])
        right = subset_sums_by_size(transformed[middle:])

        for left_size, sums in enumerate(left):
            for current_sum in sums:
                for right_size, right_sums in enumerate(right):
                    combined_size = left_size + right_size

                    # Exclude the empty subset and the full array.
                    if 0 < combined_size < n and -current_sum in right_sums:
                        return True

        return False

Complexity:

  • Time: O(n * 2^(n/2)) for generating and matching subset sums.
  • Space: O(2^(n/2)) for the stored sums.

Common follow-ups

  • How would you handle larger arrays? Use cardinality-based dynamic programming when the value range makes it practical.
  • Why transform values instead of using floating-point averages? The transformation makes the equality exact with integer arithmetic.
  • What if the split had to be contiguous? This approach would not apply; contiguous partitions need prefix-sum reasoning.
CodingHardDeutsche BankSoftware Engineer

15. Apply Operations to Maximize Frequency Score (LeetCode)

Model answer

The task

Given an integer array and a budget of unit changes, find the largest number of elements that can be made equal without exceeding the budget.

Key idea

Sort the array. For any chosen contiguous range in sorted order, changing every value to its median minimizes the total number of unit changes. Prefix sums let us calculate that cost in constant time, so a sliding window can find the largest affordable range.

Approach

  1. Sort the values and build prefix sums.
  2. Extend a window one value at a time.
  3. Use its middle value as the target and compute the cost to adjust both sides.
  4. While the cost exceeds the budget, move the left edge forward.
  5. Track the largest valid window.
from typing import List

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        # prefix[i] is the sum of nums[0:i].
        prefix = [0] * (n + 1)
        for i, value in enumerate(nums):
            prefix[i + 1] = prefix[i] + value

        left = 0
        best = 0

        for right in range(n):
            while left <= right:
                mid = (left + right) // 2
                target = nums[mid]

                # Cost to raise the left half to target.
                left_cost = target * (mid - left) - (
                    prefix[mid] - prefix[left]
                )

                # Cost to lower the right half to target.
                right_cost = (
                    prefix[right + 1] - prefix[mid + 1]
                    - target * (right - mid)
                )

                if left_cost + right_cost <= k:
                    break

                left += 1

            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n log n), due to sorting; the window scan and cost checks take O(n).
  • Space: O(n), for the prefix sums.

Common follow-ups

  • What if only increments are allowed? Use the window’s largest value as the target and compute the cost of raising the others.
  • Can the prefix-sum array be avoided? Yes; maintain a suitable running cost as the window changes, though the bookkeeping is more involved.
  • What if the budget changes for multiple queries? Precompute candidate window costs or use a query-oriented strategy, depending on the number and structure of queries.
CodingHardDeutsche BankSoftware Engineer

16. Maximum Running Time of N Computers (LeetCode)

Model answer

The task

Given n computers and batteries with fixed charge durations, find the longest time all computers can run simultaneously. Batteries may be swapped between computers as needed.

Key idea

For a proposed duration t, each battery can contribute at most t minutes, so the available usable charge is sum(min(b, t)). The duration is feasible exactly when that total is at least n * t; feasibility is monotonic, so binary search finds the maximum.

Approach

  1. Set the search range from zero to sum(batteries) // n.
  2. For a candidate duration, cap each battery’s contribution at that duration.
  3. Check whether the capped total can supply all n computers for the candidate duration.
  4. Binary search for the greatest feasible duration.
from typing import List

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        # No schedule can use more charge than the total available.
        low = 0
        high = sum(batteries) // n

        def can_run_for(minutes: int) -> bool:
            usable = sum(min(charge, minutes) for charge in batteries)
            return usable >= n * minutes

        # Feasibility is monotonic: if a duration works, every shorter
        # duration works too.
        while low < high:
            mid = (low + high + 1) // 2  # Upper midpoint avoids a stalled search.
            if can_run_for(mid):
                low = mid
            else:
                high = mid - 1

        return low

Complexity:

  • Time: O(m log S), where m is the number of batteries and S = sum(batteries) // n; each feasibility check scans the batteries.
  • Space: O(1) extra space.

Common follow-ups

  • What if some batteries cannot be swapped between computers? Model the allowed assignments; the capped-sum feasibility test may no longer be sufficient.
  • Can the actual battery schedule be returned? Yes, but constructing it requires tracking and distributing each battery’s usable intervals.
  • What if battery charge values change over time? This static binary-search check does not directly apply; the changing state must be incorporated into the feasibility model.
CodingHardDeutsche BankSoftware Engineer

17. N-Queens II (LeetCode)

Model answer

The task

Count the distinct ways to place n queens on an n × n chessboard so that no two queens attack each other. Return the count, not the board layouts.

Key idea

Place one queen per row and track which columns and diagonals are already occupied. Bit masks let us find all safe columns for a row and try each option efficiently.

Approach

  1. Represent occupied columns and diagonals as bit masks.
  2. For each row, compute the available columns by excluding attacked positions.
  3. Try each available column, updating the masks for the next row.
  4. When all rows are filled, add one to the solution count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        full = (1 << n) - 1

        def search(columns: int, diag_left: int, diag_right: int) -> int:
            # Every row has a queen once all n rows have been processed.
            if columns == full:
                return 1

            # Bits set in available represent safe columns for this row.
            available = full & ~(columns | diag_left | diag_right)
            count = 0

            while available:
                # Choose and remove the rightmost available column.
                queen = available & -available
                available ^= queen

                count += search(
                    columns | queen,
                    ((diag_left | queen) << 1) & full,
                    (diag_right | queen) >> 1,
                )

            return count

        return search(0, 0, 0)

Complexity:

  • Time: O(n!) search-tree upper bound, with diagonal checks pruning branches.
  • Space: O(n) recursion depth, excluding the masks.

Common follow-ups

  • How can symmetry reduce the search? Count first-row placements on half the board, double their totals, and handle the middle column separately when n is odd.
  • How would you return the actual board arrangements? Store each chosen column along the recursion path and build a board at each complete placement.
  • What if n becomes very large? The count grows rapidly; discuss symmetry, pruning, or specialized counting methods, noting that exact counting remains expensive.
CodingHardDeutsche BankSoftware Engineer

18. Find the Maximum Sum of Node Values (LeetCode)

Model answer

The task

Given node values, a fixed XOR value, and the edges of a tree, choose edge operations to maximize the sum of the resulting node values. An operation XORs both endpoints of one edge.

Key idea

Each edge operation toggles two nodes, so the set of nodes toggled an odd number of times must have even size. In a connected tree, any even-sized set can be produced. Compute each node’s gain from XORing it, then choose gains while keeping the number chosen even.

Approach

  1. Start with the sum of the original values.
  2. For each value, compute its gain: (value ^ k) - value.
  3. Add all positive gains.
  4. If that selected set has odd size, adjust by the smallest absolute gain to make the selection’s size even.
  5. Return the resulting maximum sum.
from typing import List

class Solution:
    def maximumValueSum(
        self,
        nums: List[int],
        k: int,
        edges: List[List[int]]
    ) -> int:
        # The tree's connectivity ensures any even-sized set of nodes
        # can be toggled by applying operations along paths.
        gains = [(value ^ k) - value for value in nums]

        total = sum(nums)
        positive_count = 0

        for gain in gains:
            if gain > 0:
                total += gain
                positive_count += 1

        # An odd number of selected toggles is not feasible.
        # Changing the choice for the least costly node fixes parity.
        if positive_count % 2 == 1:
            total -= min(abs(gain) for gain in gains)

        return total

Complexity:

  • Time: O(n), where n is the number of nodes.
  • Space: O(n) for the gains list.

Common follow-ups

  • Can this be done without storing gains? Yes; track the smallest absolute gain while scanning.
  • What if the graph is disconnected? The chosen toggled set must have even size within each connected component.
  • How can parity be handled with dynamic programming? Track the best sum for an even or odd number of chosen nodes, updating both states per value.
CodingHardDeutsche BankSoftware Engineer

19. Smallest K-Length Subsequence With Occurrences of a Letter (LeetCode)

Model answer

The task

Choose an order-preserving subsequence of length k that contains at least repetition copies of letter. Among all such subsequences, return the lexicographically smallest one.

Key idea

Build the answer greedily with a monotonic stack. A larger chosen character can be removed when the current character is smaller—but only if the remaining suffix can still fill the subsequence and meet the required letter count.

Approach

  1. Count the target letters that remain to be processed.
  2. Scan the string, updating that count before handling each character.
  3. While the stack ends in a larger character, test whether replacing it with the current character still allows a valid completion. Pop when it does.
  4. Add the current character if the stack has room and the suffix can still complete a valid answer.
  5. The feasibility check accounts for both remaining positions and remaining target letters.
from collections import Counter

class Solution:
    def smallestSubsequence(
        self, s: str, k: int, letter: str, repetition: int
    ) -> str:
        remaining_letters = Counter(s)
        stack = []
        chosen_letters = 0
        n = len(s)

        def feasible(length: int, letters: int, positions: int,
                     available_letters: int) -> bool:
            slots_needed = k - length
            letters_needed = max(0, repetition - letters)

            return (
                length <= k
                and length + positions >= k
                and letters_needed <= slots_needed
                and letters_needed <= available_letters
            )

        for i, ch in enumerate(s):
            remaining_letters[ch] -= 1
            positions_after = n - i - 1

            # Replace a larger stack character with ch when completion
            # remains possible.
            while stack and stack[-1] > ch:
                removed_is_letter = stack[-1] == letter
                new_letters = chosen_letters - removed_is_letter + (ch == letter)

                if not feasible(
                    len(stack), new_letters, positions_after,
                    remaining_letters[letter]
                ):
                    break

                stack.pop()
                chosen_letters -= removed_is_letter

            # Keep ch if it fits and leaves a feasible completion.
            if len(stack) < k:
                new_letters = chosen_letters + (ch == letter)
                if feasible(
                    len(stack) + 1, new_letters, positions_after,
                    remaining_letters[letter]
                ):
                    stack.append(ch)
                    chosen_letters = new_letters

        return "".join(stack)

Complexity:

  • Time: O(n), since each character is pushed and popped at most once.
  • Space: O(n), for the stack and the character-frequency counter.

Common follow-ups

  • What if the required character count is zero? The same feasibility check works without a special case.
  • How would you handle multiple required characters? Track counts for each required character and include each in the feasibility check.
  • Why is the stack greedy? It removes a larger prefix character only when a smaller replacement preserves the possibility of a valid completion.

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