Compute Minimum Broadcast Latencies Between Cities

Question

The question asks the candidate to compute the minimum broadcast latencies between cities, essentially finding the fastest paths from one city to all others based on varying ping times.

Codemia · Accepted Answer

To solve the problem of finding the minimum broadcast latencies between cities, we can represent the cities and their ping times as a weighted graph. Each city is a node, and the ping time between two cities is the weight of the edge connecting them. We will use Dijkstra's algorithm to compute the shortest paths from the starting city to all other cities.

Dijkstra's algorithm is an efficient way to find the shortest path in a graph with non-negative weights. The algorithm works as follows:
1. Initialize the distance to the starting city as 0 and all other cities as infinity.
2. Use a priority queue to explore the city with the smallest known distance.
3. For each neighboring city, calculate the potential new distance and update it if it is smaller than the previously known distance.
4. Repeat until all cities have been processed.

Here is a Python implementation:
```python
import heapq
from collections import defaultdict

def dijkstra(graph, start):
    min_heap = [(0, start)]  # (distance, city)
    distances = {city: float('inf') for city in graph}
    distances[start] = 0
    while min_heap:
        current_distance, current_city = heapq.heappop(min_heap)
        if current_distance > distances[current_city]:
            continue
        for neighbor, weight in graph[current_city].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(min_heap, (distance, neighbor))
    return distances
```
This function takes a graph represented as an adjacency list and a starting city, returning the shortest distances to all other cities.

The time complexity of Dijkstra's algorithm using a priority queue is O((V + E) log V), where V is the number of vertices (cities) and E is the number of edges (connections between cities). The space complexity is O(V) due to the storage of distances and the graph representation.

If the ping times between cities change frequently, we can consider using a dynamic shortest path algorithm, such as the Ramalingam-Reps algorithm. This approach allows us to efficiently update the shortest paths without recomputing everything from scratch. We would need to maintain a data structure that can handle edge updates and re-evaluate affected paths accordingly.

It is important to consider edge cases such as:
- Cities that are not connected at all, which would result in infinite distances.
- Self-loops or negative weights, which Dijkstra's algorithm does not handle. We should validate the input graph before applying the algorithm.

Compute Minimum Broadcast Latencies Between Cities

Netflix

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Netflix Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string