How should I practice Nearest Neighbouring City?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Akuna Capital online assessment problems in FastPrep.

Is Nearest Neighbouring City associated with Akuna Capital?

FastPrep tags this as a Akuna Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Nearest Neighbouring City

Learn this problem

● Medium

Akuna CapitalOA

Problem statement

A number of cities are placed at distinct integer coordinates on a Cartesian plane. The arrays cities, xCoordinates, and yCoordinates describe each city's name and position.

For every name in queries, find the nearest other city that shares either the same x-coordinate or the same y-coordinate with the queried city. Distance is measured using Manhattan distance: |x1 - x2| + |y1 - y2|.

If no other city shares an x-coordinate or y-coordinate with the queried city, return "NONE".
If multiple eligible cities have the same minimum distance, return the lexicographically smallest city name.

Return the answers in the same order as queries.

Function

findNearestCities(numOfCities: int, cities: String[], xCoordinates: int[], yCoordinates: int[], numOfQueries: int, queries: String[]) → String[]

Examples

Example 1

numOfCities = 3cities = ["c1", "c2", "c3"]xCoordinates = [3, 2, 1]yCoordinates = [3, 2, 3]numOfQueries = 3queries = ["c1", "c2", "c3"]return = ["c3", "NONE", "c1"]

y x 0123401234 c3 c2 c1

The plot places c1 = (3, 3), c2 = (2, 2), and c3 = (1, 3) at their source coordinates. Cities c1 and c3 share y-coordinate 3, while c2 shares neither coordinate with another city.

Example 2

numOfCities = 3cities = ["fastcity", "bigbanana", "xyz"]xCoordinates = [23, 23, 23]yCoordinates = [1, 10, 20]numOfQueries = 3queries = ["fastcity", "bigbanana", "xyz"]return = ["bigbanana", "fastcity", "bigbanana"]

y x 05101520250510152025 fastcity (23, 1) bigbanana (23, 10) xyz (23, 20)

All three cities lie on the vertical line x = 23. Their y-coordinates are 1, 10, and 20, matching the source diagram.

Example 3

numOfCities = 3cities = ["london", "warsaw", "hackerland"]xCoordinates = [1, 10, 20]yCoordinates = [1, 10, 10]numOfQueries = 3queries = ["london", "warsaw", "hackerland"]return = ["NONE", "hackerland", "warsaw"]

y x 0510152025051015 london (1, 1) warsaw (10, 10) hackerland (20, 10)

london = (1, 1) is isolated. warsaw = (10, 10) and hackerland = (20, 10) share y-coordinate 10, so they are nearest to each other.

Example 4

numOfCities = 5cities = ["green", "red", "blue", "yellow", "pink"]xCoordinates = [100, 200, 300, 400, 500]yCoordinates = [100, 200, 300, 400, 500]numOfQueries = 5queries = ["green", "red", "blue", "yellow", "pink"]return = ["NONE", "NONE", "NONE", "NONE", "NONE"]

y x 01002003004005006000100200300400500600 green red blue yellow pink

Every city lies on the diagonal x = y, but no two distinct cities share an x-coordinate or a y-coordinate. Therefore every query returns "NONE".

Constraints

1 ≤ n, m ≤ 10^5

1 ≤ x[i], y[i] ≤ 10^9

1 ≤ length of q[i] and c[i] ≤ 10

Each character of all c[i] and q[i] is in the range ascii[a-z, 0-9, -]

All city name values, c[i], are unique

All cities have unique coordinates