Minimize Maximum Chebyshev Distance by Adding One Delivery Center
Given an N×M city grid where delivery centers are marked as 1 and houses as 0, find the minimum possible maximum Chebyshev distance (8-directional movement) from any house to its nearest delivery center by strategically placing at most one additional delivery center.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late September, 2026
Given an N×M city grid, delivery centers are marked as 1 and houses as 0. Inconvenience is defined by the maximum Chebyshev distance (allowing 8-directional/diagonal movement) from any house to its nearest delivery center. Find the absolute minimum possible maximum inconvenience by strategically adding at most one new delivery center. 0 0 1 0 0 1 Current Distance 2 1 0 2 1 0 Output 1 0 1 0 0 1 Now the Distance is 0 1 0 0 1 0 This question was asked in Online Assessment
Hello Interview Premium
Your account is free and you can post anonymously if you choose.