Longest Anchored Song Chain
Updated
Problem statement
Build a playlist from songs. The playlist must start with the first song in the input array. After playing one song, the first word of the next title must exactly match the last word of the current title. No song may be played more than once.
Return the playlist containing the most songs, including its required first song. If several longest playlists exist, compare their complete song titles at the first position where they differ and return the lexicographically smallest playlist.
Titles consist of letters and spaces and have at least one word. Their first and last words are capitalized. For this exercise, assume all titles are distinct, words use single ASCII spaces without leading or trailing spaces, and title comparisons use exact ASCII order. Preserve every title exactly. Match boundary words with their original case.
Function
longestSongChain(songs: String[]) → String[]Examples
Example 1
songs = ["Every Breath You Take","Down By the River","River of Dreams","Take me to the River","Dreams","Blues Hand Me Down","Forever Young","American Dreams","All My Love","Cantaloop","Take it All","Love is Forever","Young American"]return = ["Every Breath You Take","Take it All","All My Love","Love is Forever","Forever Young","Young American","American Dreams","Dreams"]The chosen eight-song chain follows Take → All → Love → Forever → Young → American → Dreams. The alternative second song Take me to the River leads through River of Dreams to Dreams, producing only four songs. Dreams cannot be reused after it has played.
Example 2
songs = ["Bye Bye","Bye Bye Love","Bye Bye Baby"]return = ["Bye Bye","Bye Bye Baby"]Both possible second songs end the playlist after two songs. At the first differing title, Bye Bye Baby precedes Bye Bye Love, so the Baby playlist wins.
Constraints
- For this exercise, assume
1 <= songs.length <= 15. - Each title has 1 to 80 ASCII letters or spaces and matches the stated word grammar.
- Every word is nonempty and alphabetic; the first and last words begin with an uppercase letter. All complete titles are distinct.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Cheapest Visiting Order with PrerequisitesIndeed · OAIndeed interview questions
- Count Routes Through Four Shop TypesOpenAI · OAOpenAI interview questions
- Beautiful Number OrderingsDocuSign · OADocuSign interview questions
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Count and Score Distinct Hat AssignmentsRoblox · ONSITE INTERVIEWRoblox interview questions
- Shortest Round Trip Through All DeliveriesGoogle · ONSITE INTERVIEWGoogle interview questions
- Minimum Semesters With Course CapacityAmazon · ONSITE INTERVIEW
- Maximize Valid TrainsBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Shortest Path Visiting All NodesInMobi · ONSITE INTERVIEWInMobi interview questions