Solve server updates and grid inconvenience minimization
Overview
This question evaluates a candidate's ability to design efficient dynamic data structures and algorithms for large-scale batch updates and for optimizing grid-based metrics, testing skills in update/query efficiency, metric-space reasoning (Chebyshev distance), and rigorous complexity and edge-case analysis.
Amazon
Sep 6, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
- You are given an integer array server of length n, where server[i] is the number of requests the i-th server can process. Over multiple days, you receive replacement operations: on day j, replace every element equal to replacedId[j] with newId[j]. After each day, output the sum of all elements in server. Design an algorithm and data structures to process all daily replacements and report the sums efficiently. Analyze time and space complexities and discuss edge cases (e.g., replacedId equals newId, values not present, very large value ranges).
- You are given a binary grid where 1 denotes an existing delivery center and 0 denotes an empty cell. The distance between two cells is the Chebyshev distance: max(|x1 − x2|, |y1 − y2|). Define the city's inconvenience as the maximum, over all 0-cells, of the distance to its nearest 1-cell. You may change at most one 0-cell to 1. Return the minimum possible inconvenience after adding at most one center, and outline an efficient algorithm with complexity analysis and handling of edge cases (e.g., no existing centers, all cells are centers, multiple optimal placements).