Round 1
Questions: Determine the name of the nearest city that shares either an x or a y coordinate with the queried city. If no other cities share an x or a y coordinate, return 'NONE'. If two cities have the same distance to the queried city, consider the one with an alphabetically shorter name as the closest choice. The distance is the Manhattan distance, the absolute difference in x plus the absolute difference in y.
Example:
n = 3 c = ['c1', 'c2', 'c3'] x = [3, 2, 1] y = [3, 2, 3] q = ['c1', 'c2', 'c3']
The return array after all queries are complete is ['c3', 'NONE', 'c1'].
Function Description: Complete the function closestStraightCity with the following parameters:
- string c[n]: an array of strings that represent the names of each city[i]
- int x[n]: the x coordinates of each city[i]
- int y[n]: the y coordinates of each city[i]
- string q[m]: the names of each city to query
Returns: string[m]: an array of m strings where the index of i element denotes the return value of the index of i query.
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
Sample Case 0: Sample Input:
3 fastcity bigbanana xyz 3 23 23 3 1 10 3 20 3 fastcity bigbanana xyz
Sample Output:
bigbanana fastcity bigbanana
Sample Case 1: Sample Input:
3 london warsaw hackerland 3 1 10 3 1 10 3 1 10 3 london warsaw hackerland
Sample Output:
NONE hackerland warsaw
Sample Case 2: Sample Input:
5 green red blue yellow pink 5 100 200 300 400 500 5 100 200 300 400 500 5 green red blue yellow pink
Sample Output:
NONE NONE NONE NONE NONE
Working Solution - 10/13 test cases passed:
public static List<String> closestStraightCity(ArrayList<String> cities, ArrayList<Integer> x, ArrayList<Integer> y, ArrayList<String> queries) { // Maps to store cities by their coordinates Map<Integer, List<String>> xMap = new HashMap<>(); Map<Integer, List<String>> yMap = new HashMap<>(); Map<String, int[]> coord = new HashMap<>(); // Fill the coordinate map and coordinate grouping maps for (int i = 0; i < cities.size(); i++) { coord.put(cities.get(i), new int[]{x.get(i), y.get(i)}); xMap.computeIfAbsent(x.get(i), k -> new ArrayList<>()).add(cities.get(i)); yMap.computeIfAbsent(y.get(i), k -> new ArrayList<>()).add(cities.get(i)); } List<String> result = new ArrayList<>(); for (String q : queries) { int minDist = Integer.MAX_VALUE; String closestCity = null; int[] qCoord = coord.get(q); int qX = qCoord[0]; int qY = qCoord[1]; // Check cities with the same x coordinate. for (String c : xMap.getOrDefault(qX, new ArrayList<>())) { if (!c.equals(q)) { int dist = Math.abs(coord.get(c)[1] - qY); if (dist < minDist || (dist == minDist && (closestCity == null || c.compareTo(closestCity) < 0))) { minDist = dist; closestCity = c; } } } // Check cities with the same y coordinate. for (String c : yMap.getOrDefault(qY, new ArrayList<>())) { if (!c.equals(q)) { int dist = Math.abs(coord.get(c)[0] - qX); if (dist < minDist || (dist == minDist && (closestCity == null || c.compareTo(closestCity) < 0))) { minDist = dist; closestCity = c; } } } result.add(closestCity == null ? "NONE" : closestCity); } return result; }
Candidate's Approach
The approach involves creating maps to store cities based on their x and y coordinates. For each query, the algorithm checks the cities that share the same x or y coordinate and calculates the Manhattan distance to find the closest city. If multiple cities have the same distance, the one with the alphabetically shorter name is chosen.
Interviewer's Feedback
The solution passed 10 out of 13 test cases, indicating that there are some edge cases that need to be addressed. The candidate should consider optimizing the distance calculation and ensuring that all constraints are handled properly.