How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Palantir.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Palantir during technical interviews.

Find Shortest Paths in Road Network | Palantir Coding Question

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.

Quick Answer: 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.

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.

Input: []

Expected Output: {}

Explanation: An empty road list produces an empty adjacency list.

Input: [['A', 'B', 1], ['A', 'B', 1]]

Expected Output: {'A': [['B', 1], ['B', 1]], 'B': [['A', 1], ['A', 1]]}

Explanation: Duplicate roads are preserved, so each duplicate contributes another pair of adjacency entries.

Hints

Each undirected road creates two adjacency entries: one for from_city and one for to_city.
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.

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

Expected Output: -1

Explanation: A and D are in different connected components.

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

Expected Output: 0

Explanation: No travel is needed when start and end are the same.

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

Expected Output: 1

Explanation: This confirms that roads must be treated as bidirectional.

Hints

When every edge has equal weight, you want the path with the fewest edges. Think about exploring the graph level by level.
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.

Input: ([['A', 'B', 0], ['B', 'C', 2], ['A', 'C', 5]], 'A', 'C')

Expected Output: 2

Explanation: The zero-weight edge makes A -> B -> C cheaper than the direct road.

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

Expected Output: -1

Explanation: There is no path between the two disconnected components.

Input: ([], 'Z', 'Z')

Expected Output: 0

Explanation: If start and end are the same city, the shortest distance is 0.

Hints

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

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.