Solve server updates and grid inconvenience minimization

Quick 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.

Solve server updates and grid inconvenience minimization

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

1) 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). 2) 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).

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.

|Home/Coding & Algorithms/Amazon
Amazon logo
Amazon
Sep 6, 2025
mediumSoftware EngineerOnline AssessmentCoding & Algorithms
9
0
  1. 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).
  2. 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).

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...