Bloomberg·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Bloomberg coding round, one algorithmic problem the whole time. The question was more geometry-flavored than I expected from a finance company interview, and the optimal path required knowing a specific trick I'd never actually used before.

Questions Asked (1)

You have a 2D grid where some cells contain houses and others are empty. You need to pick one cell to place a turret that protects all houses within Manhattan distance k. Return the maximum number of houses you can protect with a single turret placement.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the brute force and talked through it fine: iterate every cell, count houses within distance k, track the max.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (grid size, number of houses, k) and discuss the brute-force approach of checking every cell and counting houses within Manhattan distance k. Then optimize using a rotated coordinate system (u = x+y, v = x-y) to transform the Manhattan distance condition into a square range query, enabling efficient counting with prefix sums or a sliding window.

Pro tip: Mention that the rotated coordinates convert the diamond-shaped Manhattan ball into an axis-aligned square, which allows using 2D prefix sums for O(1) range queries after O(RC) preprocessing. This demonstrates deep algorithmic insight and is a common trick in competitive programming.

1. Clarify constraints and edge cases

Ask about grid dimensions, number of houses, value of k, and whether the turret can be placed on a house. Discuss edge cases like k=0, no houses, or k larger than grid dimensions.

2. Brute-force baseline

For each cell, iterate over all houses and count those with Manhattan distance ≤ k. Complexity O((RC) * H). Explain this is simple but may be too slow for large inputs.

3. Optimize with rotated coordinates

Transform each house (x, y) to (u = x+y, v = x-y). The Manhattan distance condition becomes max(|u-u0|, |v-v0|) ≤ k, i.e., a square in (u,v) space. Then for each possible turret position (also transformed), count houses in that square.

4. Use prefix sums for fast counting

Build a 2D prefix sum array over the transformed grid (size up to (R+C) x (R+C)). For each cell, compute the number of houses in the square [u-k, u+k] x [v-k, v+k] in O(1) time. Track the maximum.

5. Analyze complexity and trade-offs

Time: O(RC + (R+C)^2) preprocessing and O(RC) queries. Space: O((R+C)^2). Compare with brute-force and discuss when each is preferable.

Key Points to Mention

Manhattan distance and its geometric interpretation as a diamond.
Coordinate transformation (u = x+y, v = x-y) to convert diamond to square.
2D prefix sums for O(1) range sum queries.
Time and space complexity analysis of both brute-force and optimized solutions.
Handling of edge cases: k=0, no houses, turret on house, grid boundaries.
Potential alternative: sliding window or line sweep if grid is sparse.

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