ACME·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Got an OA-style coding problem from ACME about minimizing grid inconvenience by placing one new delivery center. Pretty niche problem, not your typical LeetCode fare.

Questions Asked (1)

You have a grid where delivery centers are marked 1 and empty cells are marked 0. Distance between two cells is defined as the max of their absolute x and y coordinate differences (Chebyshev distance). The 'inconvenience' of the grid is the maximum distance any 0-cell has to its nearest 1-cell. You can flip at most one 0 to a 1. Find the minimum possible inconvenience after doing so.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Took me a while to even parse the distance definition.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and constraints, then propose a binary search on the answer combined with a feasibility check using Chebyshev distance properties. Explain how to check if a given inconvenience D is achievable by flipping at most one 0 to 1, and analyze the time complexity.

Pro tip: Mention that Chebyshev distance can be transformed to Manhattan distance via rotation, which might simplify the feasibility check. Also, discuss edge cases like no 1s or all 1s.

1. Understand the problem and constraints

Restate the problem in your own words, confirm the definition of Chebyshev distance, and ask about input size limits to determine the expected time complexity.

2. Identify the core challenge

Recognize that the inconvenience is the maximum over all 0-cells of the minimum Chebyshev distance to a 1-cell, and that flipping one 0 can reduce this maximum.

3. Propose a binary search on the answer

Since the inconvenience is monotonic (if D is feasible, any larger D is also feasible), binary search over possible distances from 0 to max possible (e.g., max grid dimension).

4. Design a feasibility check for a given D

For a candidate D, determine if there exists a 0-cell to flip such that every 0-cell is within Chebyshev distance D of some 1-cell. This can be done by finding the set of 0-cells not covered by existing 1s within distance D, and checking if a single new 1 can cover all of them.

5. Analyze complexity and optimize

Discuss the time complexity of the feasibility check (e.g., O(N*M) per check) and overall O(log(maxDist) * N*M). Mention possible optimizations like using rotated coordinates or precomputing distances.

Key Points to Mention

Chebyshev distance is equivalent to Manhattan distance after rotating coordinates by 45 degrees and scaling, which can simplify coverage checks.
Binary search is applicable because the feasibility of achieving inconvenience ≤ D is monotonic.
The feasibility check involves finding the intersection of Chebyshev balls (squares) centered at uncovered 0-cells; if non-empty, flipping a cell in that intersection works.
Edge cases: grid with no 1s (impossible to cover all 0s with one flip, so inconvenience remains infinite or undefined), grid with all 1s (inconvenience 0), and grid where flipping doesn't help.
Time complexity: O(N*M*log(max(N,M))) with naive check, but can be optimized to O(N*M) per check using prefix sums or sweep line.
Space complexity: O(N*M) for storing the grid and auxiliary arrays.

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