Shortest City Route with the Most Intermediate Stops
Updated
Problem statement
A list cities gives distinct points on a 2D plane; a city’s ID is its array index. For this exercise, assume travel is allowed directly between any two different cities and costs their Manhattan distance: |x1-x2| + |y1-y2|. A route starts at source, ends at destination, and visits each city at most once.
First minimize total travel distance. Among routes with that minimum distance, maximize the number of intermediate cities. If those quantities tie, return the lexicographically smallest sequence of city IDs, including both endpoints.
The goal is a short route through as many intermediate 2D cities as possible, using the travel graph, Manhattan costs, strict priority order and tie rule above. Physical distance is the primary objective; counting graph hops alone does not solve this contract.
Function
planCityRoute(cities: int[][], source: int, destination: int) → int[]Examples
Example 1
cities = [[0,0],[1,0],[1,1],[2,1],[2,2]]source = 0destination = 4return = [0,1,2,3,4]This route has Manhattan distance 4, equal to the direct distance, and visits all three intermediate cities.
Example 2
cities = [[0,0],[1,0],[0,1],[1,1]]source = 0destination = 3return = [0,1,3]The routes via city 1 and via city 2 both have distance 2 and one intermediate city. The lexicographically smaller ID sequence goes via 1; visiting both would make a longer route.
Constraints
- For this exercise, assume
2 <= cities.length <= 100andcities[i].length == 2. -1000 <= cities[i][j] <= 1000.0 <= source < cities.lengthand0 <= destination < cities.length.- Cities have pairwise distinct coordinates and
source != destination.
More JP Morgan Chase Onsite Interview questions
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU CacheONSITE INTERVIEW · Seen Nov 2026
- Employees Above Average SalaryONSITE INTERVIEW · Seen Sep 2026
- Highest-Earning Employees By DepartmentONSITE INTERVIEW · Seen Sep 2026
- K Largest Integers in Descending OrderONSITE INTERVIEW · Seen Aug 2026
- Tile a Three-Row Board with DominoesONSITE INTERVIEW · Seen Jan 2026
- Two SumONSITE INTERVIEW · Seen Nov 2025
- Intersection of Two ListsONSITE INTERVIEW · Seen Jan 2025
- Maximum Subarray SumONSITE INTERVIEW · Seen Jan 2025
- Fibonacci NumberONSITE INTERVIEW · Seen Nov 2024
Similar questions at other companies
- Parallel Courses IIISnowflake · ONSITE INTERVIEWSnowflake interview questions
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- Grid Robot Route with Charging PrioritiesUber · PHONE SCREEN · ONSITE INTERVIEWUber interview questions
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Minimum Semesters With Course CapacityAmazon · ONSITE INTERVIEW
- Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
- Shortest Path Visiting All NodesInMobi · ONSITE INTERVIEWInMobi interview questions
- Minimum Distance Matching in a ForestScale AI · PHONE SCREEN · ONSITE INTERVIEWScale AI interview questions
- Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
- Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions
Interview reports that mention this question
JP Morgan Chase interview experiences
- JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
- JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
- JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
- JP Morgan Chase Data and AI Intern Superday: 11 Experiences
- JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)