Quick Overview

This question evaluates understanding of graph data structures and shortest-path concepts, including correct modeling of undirected edges, unweighted versus weighted pathfinding, and algorithmic time and space complexity.

Find Shortest Paths in Road Network

Company: Palantir

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

You are reviewing code for a road-network graph. The domain objects are: ```java class Location { String name; Location(String name) { this.name = name; } } class Road { Location from; Location to; int distance; Road(Location from, Location to, int distance) { this.from = from; this.to = to; this.distance = distance; } } class RoadConnection { Location destination; int distance; RoadConnection(Location destination, int distance) { this.destination = destination; this.distance = distance; } } ``` A `Road` represents a bidirectional road between two cities. The existing implementation accidentally treats each road as one-way. Implement or review the graph logic for the following tasks: 1. Build an adjacency-list representation from a list of `Road` objects. Make sure roads are handled as bidirectional. 2. Given two `Location` objects, return the shortest distance when every road has weight `1`. Return `-1` if no path exists. 3. Given two `Location` objects, return the shortest total distance when road distances can be arbitrary non-negative integers. Return `-1` if no path exists. Discuss the expected time and space complexity for each shortest-path method.

Overview: This question evaluates understanding of graph data structures and shortest-path concepts, including correct modeling of undirected edges, unweighted versus weighted pathfinding, and algorithmic time and space complexity.

Read the full Palantir Software Engineer interview experience this question came from

Part 1: Build a Bidirectional Road Adjacency List

You are given a list of roads in a road network. Each road is represented as [from_city, to_city, distance]. A road is bidirectional, so if there is a road from A to B, then B must also connect to A with the same distance. Build and return an adjacency-list representation of the graph. To make the output deterministic, return a Python dict whose keys are inserted in lexicographic order, and for each city, sort its neighbor list by neighbor name and then by distance. If the input is empty, return an empty dict.

Constraints

  • 0 <= len(roads) <= 10^4
  • 0 <= distance <= 10^9
  • City names are non-empty strings
  • Each road connects two distinct cities
  • If duplicate roads appear in the input, preserve them in the adjacency list

Examples

Input: [['A', 'B', 5], ['B', 'C', 3]]

Expected Output: {'A': [['B', 5]], 'B': [['A', 5], ['C', 3]], 'C': [['B', 3]]}

Explanation: Road A-B adds both A->B and B->A. Road B-C adds both B->C and C->B.

Input: [['Delhi', 'Mumbai', 2], ['Ahmedabad', 'Delhi', 1], ['Chennai', 'Bengaluru', 4]]

Expected Output: {'Ahmedabad': [['Delhi', 1]], 'Bengaluru': [['Chennai', 4]], 'Chennai': [['Bengaluru', 4]], 'Delhi': [['Ahmedabad', 1], ['Mumbai', 2]], 'Mumbai': [['Delhi', 2]]}

Explanation: The graph has two disconnected components, and the output is sorted lexicographically.

Hints

  1. Each undirected road creates two adjacency entries: one for from_city and one for to_city.
  2. Use a dictionary of lists while building the graph, then sort once at the end for deterministic output.

Part 2: Shortest Number of Roads Between Two Cities

You are given an undirected road network where every road has the same cost: 1. Each road is represented as [city1, city2]. Return the minimum number of roads needed to travel from start to end. Because roads are bidirectional, [A, B] means you can travel both A -> B and B -> A. If no path exists, return -1. If start and end are the same city, return 0.

Constraints

  • 0 <= len(roads) <= 10^5
  • City names are non-empty strings
  • Each road connects two distinct cities
  • The graph may be disconnected
  • If start == end, the answer is 0 even if the city does not appear in roads

Examples

Input: ([['A', 'B'], ['B', 'C'], ['C', 'D']], 'A', 'D')

Expected Output: 3

Explanation: The only path is A -> B -> C -> D, which uses 3 roads.

Input: ([['A', 'B'], ['A', 'C'], ['C', 'D']], 'B', 'D')

Expected Output: 3

Explanation: The shortest path is B -> A -> C -> D.

Hints

  1. When every edge has equal weight, you want the path with the fewest edges. Think about exploring the graph level by level.
  2. Be sure to add every road in both directions before searching.

Part 3: Shortest Total Distance with Weighted Roads

You are given an undirected road network where each road has a non-negative distance. Each road is represented as [from_city, to_city, distance]. Return the minimum total distance needed to travel from start to end. Because roads are bidirectional, [A, B, 7] means you can travel both A -> B and B -> A with distance 7. If no path exists, return -1. If start and end are the same city, return 0.

Constraints

  • 0 <= len(roads) <= 10^5
  • 0 <= distance <= 10^9
  • City names are non-empty strings
  • Each road connects two distinct cities
  • All road distances are non-negative

Examples

Input: ([['A', 'B', 4], ['A', 'C', 2], ['C', 'B', 1], ['B', 'D', 5], ['C', 'D', 8]], 'A', 'D')

Expected Output: 8

Explanation: The best route is A -> C -> B -> D with total distance 2 + 1 + 5 = 8.

Input: ([['X', 'Y', 7]], 'Y', 'X')

Expected Output: 7

Explanation: This checks that a single road works in both directions.

Hints

  1. A greedy strategy works here because edge weights are non-negative: repeatedly expand the city with the smallest known tentative distance.
  2. A min-heap is useful for efficiently retrieving the next city to process.

Loading coding console...