All Halfway Courses Across Course Tracks
Updated
Problem statement
Students can choose among several tracks of courses, and different tracks may share courses. You get the course links as pairs, where [source, destination] means destination can be taken right after source.
A starting course is a course that is never a destination, and an ending course is a course that is never a source. A track starts at a starting course, follows links one at a time, and stops at an ending course. Each student follows one whole track.
For a track of L courses numbered from 0, its halfway course is the course at position (L - 1) / 2, rounded down. With an even L, this is the first of the two middle courses.
Return every course that is the halfway course of at least one track. List each course once, sorted by character code, as in standard string sorting.
Function
allHalfwayCourses(pairs: String[][]) → String[]Examples
Example 1
pairs = [["Logic","COBOL"],["Data Structures","Algorithms"],["Creative Writing","Data Structures"],["Algorithms","COBOL"],["Intro to Computer Science","Data Structures"],["Logic","Compilers"],["Data Structures","Logic"],["Graphics","Networking"],["Networking","Algorithms"],["Creative Writing","System Administration"],["Databases","System Administration"],["Creative Writing","Databases"],["Intro to Computer Science","Graphics"]]return = ["Creative Writing","Data Structures","Databases","Networking"]- The starting courses are Intro to Computer Science and Creative Writing. Following the pairs from them gives 9 tracks.
- Intro to Computer Science → Graphics → Networking → Algorithms → COBOL has 5 courses, so its halfway course is Networking (position 2).
- Every 4-course track through Data Structures, such as Intro to Computer Science → Data Structures → Logic → COBOL, has Data Structures at position 1.
- Creative Writing → Databases → System Administration gives Databases, and the 2-course track Creative Writing → System Administration gives Creative Writing.
- The distinct halfway courses, sorted, are Creative Writing, Data Structures, Databases and Networking.
Example 2
pairs = [["Course_3","Course_7"],["Course_0","Course_1"],["Course_1","Course_2"],["Course_2","Course_3"],["Course_3","Course_4"],["Course_4","Course_5"],["Course_5","Course_6"]]return = ["Course_2","Course_3"]There are two tracks. Course_0 → … → Course_6 has 7 courses, so its halfway course is Course_3. Course_0 → Course_1 → Course_2 → Course_3 → Course_7 has 5 courses, so its halfway course is Course_2.
Constraints
1 <= pairs.length <= 300- Each pair is
[source, destination]with two different course names, and no pair appears twice. - A course name has 1 to 30 characters: letters, digits, spaces and underscores, with no space at the start or end and no two spaces in a row.
- At most
150different courses appear. - Following the pairs never leads back to an earlier course (there are no cycles), and there are at most
20000tracks in total.
More Crunchyroll Phone Screen questions
Similar questions at other companies
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Work Order Critical PathHadrian · PHONE SCREENHadrian interview questions
- Course ScheduleNykaa · PHONE SCREENNykaa interview questions
- Longest Name Chain in a Directed Acyclic GraphOscar Health · PHONE SCREEN
- Service Dependency Load FactorsRobinhood · PHONE SCREENRobinhood interview questions
- Employee Hierarchy Cycle and Depth AnalysisMicrosoft · PHONE SCREENMicrosoft interview questions
- Longest Chain BookingAirbnb · PHONE SCREENAirbnb interview questions
- Effective Role PrivilegesSnowflake · PHONE SCREENSnowflake interview questions