← Bloomberg Interview Insights

Bloomberg·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Bloomberg SWE coding round, one problem the whole time. The question was harder than it looked and I fumbled around longer than I should have before landing on a real approach.

Questions Asked (1)

Q1

Given a string containing parentheses and other characters, remove the minimum number of invalid parentheses to make it valid. Return all possible results with no duplicates.

Algorithms & Data Structures
Author's notes

Knew BFS was the safe play since it naturally finds the minimum removals level by level, but I kept second-guessing myself and started rambling about DFS first without a clear pruning strategy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use BFS level-by-level to find the minimum number of removals, checking each string for validity and stopping at the first level where valid strings are found. Collect all valid strings at that level, using a set to avoid duplicates. Alternatively, use DFS with pruning by tracking the number of invalid parentheses to remove.

Pro tip: Clarify whether the input can contain other bracket types or only parentheses; if only parentheses, simplify the validity check. Also, mention that BFS guarantees minimum removals but can be memory-intensive; DFS with pruning is more space-efficient but requires careful duplicate handling.

1. Clarify requirements and edge cases

Confirm that only parentheses '(' and ')' are considered, and other characters are ignored. Discuss edge cases: empty string, already valid string, string with no parentheses, and strings with multiple valid results.

2. Define validity check

Implement a function to check if a string is valid: iterate through characters, maintain a balance counter, increment for '(' and decrement for ')', ensuring balance never goes negative and ends at zero.

3. Choose BFS or DFS approach

For BFS: start with the original string, generate all strings by removing one parenthesis, check validity, and continue level by level until valid strings are found. For DFS: recursively explore removals, pruning when the number of removals exceeds the current minimum found.

4. Handle duplicates and collect results

Use a set to store visited strings to avoid redundant work and duplicate results. When valid strings are found at the minimum removal level, add them to the result set.

5. Analyze complexity and optimize

Discuss time and space complexity: BFS can be exponential in worst case, but pruning and set usage help. Mention that the maximum number of removals can be bounded by counting unmatched parentheses.

Key Points to Mention

  • BFS guarantees minimum removals because it explores level by level.
  • Validity check using balance counter (never negative, ends at zero).
  • Using a set to avoid duplicate strings and redundant computations.
  • DFS with pruning can be more space-efficient but requires careful duplicate handling.
  • Time complexity: O(2^n) in worst case, but often much less with pruning.
  • Edge cases: empty string, already valid string, no parentheses, multiple valid results.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.