Coupang Interview Questions

Consider a trip from one city to another that may contain many layovers. Given the list of flights out of order, each with a starting city and end city, write a function plan_trip to reconstruct the path of the trip so the trip tickets are in order.

Example:

For a trip from Bombay to Beijing:

Input:

flights = [
    ['Chennai', 'Bangalore'], 
    ['Bombay', 'Delhi'], 
    ['Goa', 'Chennai'], 
    ['Delhi', 'Goa'], 
    ['Bangalore', 'Beijing']
]
output = [
    ['Bombay', 'Delhi'], 
    ['Delhi', 'Goa'], 
    ['Goa', 'Chennai'], 
    ['Chennai', 'Bangalore'], 
    ['Bangalore', 'Beijing'],
]