Compute nearest courier for each customer

Q: Compute nearest courier for each customer

This question evaluates nearest-neighbor search, computational geometry, spatial indexing and dynamic data structure skills, covering Euclidean and great-circle distance reasoning, tie-breaking by id, and algorithmic time/space complexity analysis.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two arrays: customers and dashers. Each customer i has coordinates (xi, yi). Each dasher j has coordinates (aj, bj) and an integer id. For every customer, return the id of the nearest dasher by Euclidean distance; on ties, return the smallest id. a) Implement a correct solution. b) Analyze time and space complexity. c) Propose and implement (or outline) a more scalable approach when C and D are up to 1e5 (e.g., spatial partitioning, k-d tree, or grid indexing). d) How would your approach change if dasher locations update frequently (insert, delete, move) or if distances are computed on latitude/longitude using great-circle distance?

Compute nearest courier for each customer

Overview

Comments (0)