Frontend School

Popular Consecutive Flight Segments

DSA
medium

Popular Consecutive Flight Segments

Medium
Arrays
Hashing
Data Processing
Frequency Counting

Overview

At Ixigo, analyzing flight booking patterns is crucial for understanding demand, optimizing pricing strategies, and identifying potential anomalies. This problem focuses on extracting insights from raw booking data to pinpoint frequently traveled flight segments and observe their booking consistency. Your task is to process a stream of flight booking records to identify segments with high demand and understand how often they are booked consecutively, which can signal sudden surges or consistent popularity.

What you need to do / Task

Your goal is to implement a function that processes a list of flight bookings and identifies popular segments, along with their maximum consecutive booking streaks.

  1. Given an array bookings, where each element is a [originAirportCode, destinationAirportCode] pair, and an integer k.
  2. First, determine the total booking count for each unique flight segment [origin, destination].
  3. Identify all unique flight segments that have been booked k times or more in total. These are considered "popular" segments.
  4. For each identified popular segment, iterate through the original order of the bookings list to find the maximum number of times that segment appeared consecutively.
  5. Return a list of objects. Each object should contain:
    • segment: The [origin, destination] pair as a string[].
    • maxConsecutiveBookings: The maximum consecutive count found for that segment.
  6. The final list of objects must be sorted lexicographically. First, sort by the originAirportCode of the segment. If origins are identical, then sort by the destinationAirportCode.

Input & output

Function Signature: function getPopularConsecutiveSegments(bookings: string[][], k: number): { segment: string[], maxConsecutiveBookings: number }[]

  • bookings: An array of arrays, where each inner array [origin, destination] represents a flight segment. origin and destination are 3-letter uppercase airport codes (e.g., "DEL", "BOM").
  • k: An integer representing the minimum total booking count for a segment to be considered "popular".
  • Return: An array of objects. Each object has two properties: segment (a string[] representing [origin, destination]) and maxConsecutiveBookings (a number).

Clarifications

  • An empty bookings array should result in an empty returned array.
  • If no segments meet the k threshold, an empty array should be returned.
  • The maxConsecutiveBookings for a segment is 1 if it appears only once or never consecutively.
  • Segments are case-sensitive (e.g., ["del", "bom"] is different from ["DEL", "BOM"], but per constraints, all will be uppercase).

Examples

1

Example 1

Input:

bookings = [["DEL", "BOM"], ["BOM", "BLR"], ["DEL", "BOM"], ["DEL", "BOM"], ["BOM", "BLR"], ["DEL", "BOM"]], k = 3

Output:

[ { "segment": ["DEL", "BOM"], "maxConsecutiveBookings": 2 } ]

Note:

  1. Total counts: DEL-BOM: 4, BOM-BLR: 2.
  2. Popular segments (count >= 3): DEL-BOM.
  3. Max consecutive for DEL-BOM: Bookings are ["DEL","BOM"], ["BOM","BLR"], ["DEL","BOM"], ["DEL","BOM"], ["BOM","BLR"], ["DEL","BOM"]. The longest streak for DEL-BOM is 2 (at indices 2 and 3).
2

Example 2

Input:

bookings = [["NYC", "LAX"], ["LAX", "SFO"], ["NYC", "LAX"], ["NYC", "LAX"], ["LAX", "SFO"], ["LAX", "SFO"], ["LAX", "SFO"], ["NYC", "LAX"]], k = 3

Output:

[ { "segment": ["LAX", "SFO"], "maxConsecutiveBookings": 3 }, { "segment": ["NYC", "LAX"], "maxConsecutiveBookings": 2 } ]

Note:

  1. Total counts: NYC-LAX: 4, LAX-SFO: 4.
  2. Popular segments (count >= 3): LAX-SFO, NYC-LAX.
  3. Max consecutive for NYC-LAX: The longest streak is 2 (at indices 2 and 3).
  4. Max consecutive for LAX-SFO: The longest streak is 3 (at indices 4, 5, and 6).
  5. Sorted output: LAX-SFO comes before NYC-LAX alphabetically.
3

Example 3

Input:

bookings = [["A", "B"], ["C", "D"], ["A", "B"]], k = 3

Output:

[]

Note:

  1. Total counts: A-B: 2, C-D: 1.
  2. No segments meet the k=3 threshold. The output is an empty array.

Constraints

Constraints & assumptions

  • 1 <= bookings.length <= 10^5
  • bookings[i].length === 2 for all i.
  • bookings[i][j] consists of exactly 3 uppercase English letters (e.g., "DEL", "BOM").
  • 1 <= k <= bookings.length
  • Time Complexity: Aim for O(N) or O(N log N) where N is bookings.length.
  • Space Complexity: Aim for O(U) where U is the number of unique segments.

Out of scope

  • Error handling for invalid input formats (e.g., non-3-letter airport codes, k out of range).
  • Database interactions or external API calls.
  • User interface or presentation layer logic.

What interviewers evaluate

  • Correctness in identifying all unique segments and their total booking counts.
  • Accuracy in filtering segments based on the k threshold.
  • Precision in calculating the maximum consecutive bookings for each popular segment.
  • Adherence to the specified sorting order for the final output list.
  • Efficiency of the algorithm in terms of time and space complexity.
  • Clarity, readability, and overall structure of the code.

Loading editor...