Martin's Venezuelan Adventure Map
In this coding challenge named after Martin's adventure in Venezuela, you are given the input as a singly linked list where each node represents a city Martin visited in Venezuela, and the value in each node represents the number of days spent in that city. Your task is to generate a graph where each node represents a city indexed from 0 to n-1 (where n is the number of cities), and there should be an directed edge from city i to city j if the number of days spent in city j is exactly twice the days spent in city i.
The output should be a string representation of the adjacency list of the graph. Each city's connections should be printed on a new line in the format 'City i: [city1, city2,...]', where 'city i' is the index of the city, and [city1, city2,...] are indices of cities directly reachable from 'city i' based on the criteria specified above.
[ 5, 10, 15 ]
Explanation. City 0 with 5 days connects to City 1 with 10 days (5*2=10). City 1 with 10 days connects to City 2 with 15 days. No city matches twice the days of City 2, so it connects to no other city.
[ 2, 4, 7 ]
Explanation. City 0 with 2 days connects to City 1 with 4 days, because 2*2=4. No city has days that are exactly twice of either City 1 or City 2.
[ 30, 15, 60, 120 ]
Explanation. City 0 with 30 days connects directly to City 2 with 60 days. City 2 with 60 days connects directly to City 3 with 120 days. City 1 with 15 days does not find a match for 2x days.
Follow-up: Can you enhance your solution to handle cases where cities could also be connected if days spent in city `j` are twice or half, rounded down, the days of city `i`? How would you handle possible cyclic paths in this enhanced communication structure?
The linked list will have at least 1 and at most 100 nodes. Each node's value (days) will be a positive integer between 1 and 300. The linked list does not necessarily have unique values. The graph should not have any self-loops (i.e., no city with connections to itself). Graph indices start from 0.
- Views
- 12