runtimequestion 347 Algorithms & Complexity · medium
Refactor the airline-name join
This function labels each flight with its airline's name. Its answers are right, and the dashboard depends on every detail of them, but with 7,000 flights and the full carrier table it compares every flight with every airline. Refactor it so the carrier table is read once, without changing a single result.
Function
label_flights(flights, airlines) (keep the name and parameters)Behaviourunchanged:
"<flight_id> <airline name>" for each flight in order; "Unknown" when no airline has the code; if a code appears more than once in the table, the last row's name is used (that is what the original does)Constraintread the airline table about once: at most 1,500 reads for 500 flights and 1,000 airlines
Examples
calllabel_flights([{'flight_id': '12207', 'airline_code': 'UA'}, {'flight_id': '12208', 'airline_code': 'MQ'}, {'flight_id': '12209', 'airline_code': 'AA'}], [{'airline_code': 'AA', 'airline_name': 'American Airlines'}, {'airline_code': 'B6', 'airline_name': 'JetBlue Airways'}, {'airline_code': 'UA', 'airline_name': 'United Air Lines'}])returns['12207 United Air Lines', '12208 Unknown', '12209 American Airlines']
calllabel_flights([{'flight_id': '12290', 'airline_code': 'B6'}], [{'airline_code': 'AA', 'airline_name': 'American Airlines'}, {'airline_code': 'B6', 'airline_name': 'JetBlue Airways'}, {'airline_code': 'UA', 'airline_name': 'United Air Lines'}])returns['12290 JetBlue Airways']
calllabel_flights([], [{'airline_code': 'AA', 'airline_name': 'American Airlines'}, {'airline_code': 'B6', 'airline_name': 'JetBlue Airways'}, {'airline_code': 'UA', 'airline_name': 'United Air Lines'}])returns[]