Merge Event Preferences
Updated
Problem statement
A group of friends is planning a trip. You are given preferences, where preferences[i] lists the events person i wants to attend, in the order that person wants them to happen.
Build one schedule: a list that contains every event named in preferences exactly once, such that each person's events appear in the schedule in the same order as in that person's list. Other events may sit between them.
If several schedules work, return the smallest one in dictionary order. To compare two schedules, find the first position where they differ; the schedule whose event name there comes first alphabetically is smaller. Names are compared letter by letter, and a name that is the start of a longer name comes first ("art" comes before "arts").
If the preferences conflict so that no schedule works, return an empty list.
Function
mergePreferences(preferences: List<List<String>>) → List<String>Examples
Example 1
preferences = [["brunch","hike","dinner"],["hike","museum"],["brunch","museum","dinner"]]return = ["brunch","hike","museum","dinner"]Person 0 needs brunch, then hike, then dinner. Person 1 needs hike before museum, and person 2 needs brunch, then museum, then dinner.
Only brunch has nothing that must come before it, so it goes first. Next, museum still waits for hike and dinner waits for both, so hike is second. Then museum, then dinner. This is the only schedule that works.
Example 2
preferences = [["surf","yoga"],["dinner","yoga"],["beach"]]return = ["beach","dinner","surf","yoga"]The only rules are that surf and dinner both come before yoga. Person 2 only names beach, so it can go anywhere. Many schedules work, for example ["surf","dinner","yoga","beach"].
The smallest one in dictionary order puts the smallest possible event first at every step. At the start, beach, dinner and surf are all free to go, and beach is the smallest. Then dinner, then surf, and finally yoga, which is free only after both of them.
Example 3
preferences = [["hike","surf"],["surf","tour"],["tour","hike"]]return = []The three people need hike before surf, surf before tour, and tour before hike. Following these rules from hike leads back to hike, so no event can go first. The preferences conflict, and the answer is an empty list.
Constraints
1 <= preferences.length <= 1001 <= preferences[i].length <= 501 <= preferences[i][j].length <= 8preferences[i][j]consists of lowercase English letters.- The events in one person's list are all different.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Topological Sort with Secondary OrderingRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Data Pipeline Steps with Search and Run OrderRippling · PHONE SCREENRippling interview questions
- Lexicographically Smallest Topological OrderCoinbase · PHONE SCREENCoinbase interview questions
- Mutual-Friend RecommendationsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- Task Scheduler with Prerequisites and Execution PathsBrex · PHONE SCREEN
- Lexicographically Smallest Topological OrderByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Merge Subsequences Into a Consistent Total OrderGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Lexicographic Dependency OrderIllumio · PHONE SCREENIllumio interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)