Panda Guru LogoPanda
Guru

D. E. Shaw India | OA | Nearest Neighbouring City

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:

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:

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.