Start and End of a Trip From Shuffled Tickets
Updated
Problem statement
You have a pile of plane tickets. Ticket tickets[i] = [from, to] is one flight from city from to city to.
All the tickets together make up one trip: they can be put in an order where each flight leaves from the city where the previous flight landed, and every ticket is used exactly once. The trip may visit a city more than once, including the city where it started, so it can contain loops. Two tickets may be identical. The tickets are given in a shuffled order.
Return a list [start, end]: the city where the trip starts and the city where it ends.
Function
findTripEnds(tickets: String[][]) → String[]Examples
Example 1
tickets = [["kyiv","oslo"],["oslo","lima"],["rome","oslo"],["oslo","kyiv"]]return = ["rome","lima"]The tickets put in order are rome → oslo, oslo → kyiv, kyiv → oslo, oslo → lima. The trip passes through oslo twice. It starts in rome and ends in lima.
Example 2
tickets = [["cork","bern"],["bern","doha"],["bern","cork"]]return = ["bern","doha"]In order: bern → cork, cork → bern, bern → doha. The trip comes back to bern, where it started, and then flies on to doha. So the answer is ["bern", "doha"], even though bern is also a destination of one ticket.
Example 3
tickets = [["paris","tokyo"]]return = ["paris","tokyo"]With one ticket, the trip starts at its first city and ends at its second city.
Constraints
1 <= tickets.length <= 10^4tickets[i].length == 21 <= tickets[i][j].length <= 10- Every city name consists only of lowercase English letters.
tickets[i][0] != tickets[i][1]- The tickets can be put in an order that forms one trip, as described above.
- The trip ends in a different city from the one where it starts.
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Halfway Course in a Single TrackCrunchyroll · PHONE SCREENCrunchyroll interview questions
- Network Endpoint or Cycle BoundaryOpenAI · OA · PHONE SCREENOpenAI interview questions
- Most Active Caller by Distinct ContactsGoogle · PHONE SCREENGoogle interview questions
- Initial and Final Accounts in a Transfer ChainAmazon · PHONE SCREEN
- Find Root IDs from Parent ReferencesZip · PHONE SCREENZip interview questions
- Rooms With Two Other Entrances and a Treasure SuccessorWalmart · PHONE SCREENWalmart interview questions
- Do Two Nodes Share a Proper Ancestor?Karat · PHONE SCREENKarat interview questions
- People with Zero or One ParentIndeed · PHONE SCREENIndeed interview questions
- Nodes With Zero or Three ParentsCompass International Holdings · PHONE SCREENCompass International Holdings interview questions
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN