Problem A Get the Order of Courses (6 points) In the school curriculum, there is a sequential relationship between courses One can only take the subsequent courses if have finished the prerequisite courses In this problem, we constructed a list for the courses and their relationships Your task is to find out the fastest schedule to complete all given courses and return the corresponding course schedule (course order) Problem definition Implement the function called get order of courses(relationships List List str ) List str Function parameter relationships i prerequisite course, next course the prerequisite course has to be taken before the next course Return type List str return a list indicating the course order Each element in the list should be the name of the course If there is no way to take all the courses, return See section Hints for more explanation Example 1 Input relations CSE 11,CSE 22 , CSE 22,CSE 33 Output 'CSE 11', 'CSE 22', 'CSE 33' Explanation quarter 1 course CSE 11, quarter 2 course CSE 22 quarter 3 course CSE 33 Example 2 Input relations ART 212,ART 232 , ART 232,HIST194 , HIST194,ART 212 Output Explanation There is no way to finish those courses under given relations Example 3 Input relations HIST 199,LING 211 , HIST 199,ART 912 , HIST 199,ART 431 , HIST 199,ART 55 , LING 211,LING 777 Output 'HIST 199','LING 211','ART 912','ART 431','ART 55','LING 777' Explanation quarter 1 course HIST 199 quarter 2 course LING 211, ART 912, ART 431, ART 55 quarter 3 course LING 777 Hints Topological sorting will be the ideal way to solve this In the output schedule, the order that needs to be followed is that the prerequisite course needs to be saved before the next course That is, the prerequisite course should have a smaller index in the output list For courses that can be taken in the same quarter, the order does not matter For example, all of the following outputs are correct Input relations HIST 199,LING 211 , HIST 199,ART 912 , HIST 199,ART 431 , HIST 199,ART 55 , LING 211,LING 777 Output1 'HIST 199','LING 211','ART 912','ART 431','ART 55','LING 777' Output2 'HIST 199','ART 431','LING 211','ART 912','ART 55','LING 777' Output3 'HIST 199','ART 431','LING 211','ART 55','ART 912','LING 777' Explanation HIST 199 should be taken first ART 431, LING 211, ART 912, ART 55 can be taken at the same time, so the order of those 4 courses does not matter LING 777 should be taken last (after LING 211) Course schedules interpretation may not be unique, but the minimum required quarters are fixed for each input For example, in Example 3 there are two interpretations of the schedule, as shown below, but the output for this function is still following the order shown in the previous hint Output 'HIST 199','LING 211','ART 912','ART 431','ART 55','LING 777' Interpretation1 quarter 1 course HIST 199 quarter 2 course LING 211 quarter 3 course ART 912, ART 431, ART 55,LING 777 Interpretation2 quarter 1 course HIST 199 quarter 2 course LING 211, ART 912, ART 431, ART 55 quarter 3 course LING 777 You can assume that the course name will always be a valid string Problem B Find all Paths between Cities (6 points) We represent the connection between cities using a DAG (directed acyclic graph) The vertex on the graph denotes the city, and the edge denotes the path between cities Your task is to find out all the path combinations to travel from one given city to another Problem definition Implement the function called find paths(connection List List int , source int, destination int) List List int , to return a list including all paths from the city source to the city destination You may return them in any order If the path does not exist, return an empty list Note that we use the number ( int ) as the name of the city Function parameters connection a list with length N , where N is the number of paths involved in this connection map Each sublist in connection , connection i u,v , indicates that there is a path from the city u to city v source an integer that represents the name of the city destination an integer that represents the name of the city Return List List int a List stores all paths from city source to city destination Each path should be represented as a list of the city name Example 1 Input connection 0,1 , 0,4 , 1,2 , 2,3 , 3,4 source 2 destination 1 Output Explanation There is no path connection from city 2 to city 1 Example 2 Input connection 0,1 , 1,2 , 1,3 , 1,5 , 2,3 , 2,4 , 3,4 , 4,5 , 0,5 source 1 destination 5 Output 1,2,3,4,5 , 1,2,4,5 , 1,3,4,5 , 1,5 Explanation three paths 1 3 4 5 and 1 2 3 4 5 and 1 5 Constraints Input source and destination are different numbers, i e , source destination Input source and destination can always be found in the given connection map All cities (vertices) in the connection map are unique Hints The connection is a DAG, i e , directed and acyclic The input connection is not sorted Problem C Largest Score Pattern (3 extra points) (Optional) Given three arrays of the same length username , website , and timestamp , where each tuple i represents that the user username i visited the website website i at the time timestamp i A pattern is a list of three websites, not necessarily distinct The score of a pattern is the number of users that consecutive visited all the websites in the pattern in the same order they appeared in the pattern (see more explanation in section Hints) The task is to find the pattern with the largest score, and if there are multiple patterns with the same score, return the lexicographically smallest pattern Problem definition the task is to implement a function find largest pattern( username List str , timestamp List int , website List str ) List str that takes three arrays of strings username , website , and an array of integers timestamp , and returns a list of three strings, representing the pattern with the largest score Function parameters username a list of strings representing the usernames of the users who visited the websites timestamp a list of integers representing the timestamps at which the users visited the websites website a list of strings representing the names of the websites visited by the users Return List str a list of three strings representing the website pattern with the largest score Example 1 Input username bob , bob , bob , john , john , john , john , mike , mike , mike , timestamp 1,2,3,4,5,6,7,8,9,10 , website song , page , faq , song , cart , maps , song , song , page , faq Output song , page , faq Explanation The tuples in this example are bob , song ,1 , bob , page ,2 , bob , faq ,3 , john , song ,4 , john , cart ,5 , john , maps ,6 , john , song ,7 , mike , song ,8 , mike , page ,9 , and mike , faq ,10 The pattern song , page , faq has score 2 (bob and mike) The pattern song , cart , maps has score 1 (john) The pattern song , cart , song has score 1 (john) The pattern song , maps , song has score 1 (john) The pattern cart , maps , song has score 1 (john) The pattern song , song , song has score 0 (no user visited song 3 times) Constraints It is guaranteed that there is at least one valid pattern in the input You can assume that given lists are always sorted by the timestamp The websites in the pattern must be visited by a user continuously (user wise) for a score For example, John visited song , cart , maps , song then, we cannot say song , maps , song is a visited pattern of John, since John also visited cart in between song and maps Continuous visits are defined user wise For example, John visited song , cart , maps , song at timestamp 1,2,3,5 , and another user Bob visited cart at timestamp 4 This will not break the continuity of pattern cart , maps , song Hints This problem is not closely related to graph theory Think of it more in terms of OTHER data structures

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 25, 2024

Problem A - Get the Order of Courses (6 points) In the school curriculum, there is a sequential relationship between courses. One can only take

Problem A - Get the Order of Courses (6 points)

In the school curriculum, there is a sequential relationship between courses. One can only take the subsequent courses if have finished the prerequisite courses. In this problem, we constructed a list for the courses and their relationships. Your task is to find out the fastest schedule to complete all given courses and return the corresponding course schedule (course order).

Problem definition:

Implement the function called: get_order_of_courses(relationships: List[List[str]]) -> List[str]

Function parameter:

relationships[i] = [prerequisite_course, next_course]:the prerequisite_course has to be taken before the next_course.
Return type - List[str]: return a list indicating the course order. Each element in the list should be the name of the course. If there is no way to take all the courses, return []. See section-Hints for more explanation.

Example 1:

Input: relations = [[CSE-11,CSE-22],[CSE-22,CSE-33]] Output: ['CSE-11', 'CSE-22', 'CSE-33'] Explanation: quarter 1: course CSE-11, quarter 2: course CSE-22. quarter 3: course CSE-33.

Example 2:

Input: relations = [[ART-212,ART-232],[ART-232,HIST194],[HIST194,ART-212]] Output: [] Explanation: There is no way to finish those courses under given relations.

Example 3:

Input: relations = [[HIST-199,LING-211],[HIST-199,ART-912],[HIST-199,ART-431],[HIST-199,ART-55],[LING-211,LING-777]] Output: ['HIST-199','LING-211','ART-912','ART-431','ART-55','LING-777'] Explanation: quarter 1: course HIST-199. quarter 2: course LING-211, ART-912, ART-431, ART-55. quarter 3: course LING-777.

Hints:

Topological sorting will be the ideal way to solve this.
In the output schedule, the order that needs to be followed is that: the prerequisite_course needs to be saved before the next_course. That is, the prerequisite_course should have a smaller index in the output list.
For courses that can be taken in the same quarter, the order does not matter. For example, all of the following outputs are correct.

 Input: relations = [[HIST-199,LING-211],[HIST-199,ART-912],[HIST-199,ART-431],[HIST-199,ART-55],[LING-211,LING-777]] Output1: ['HIST-199','LING-211','ART-912','ART-431','ART-55','LING-777'] Output2: ['HIST-199','ART-431','LING-211','ART-912','ART-55','LING-777'] Output3: ['HIST-199','ART-431','LING-211','ART-55','ART-912','LING-777'] Explanation: HIST-199 should be taken first ART-431, LING-211, ART-912, ART-55 can be taken at the same time, so the order of those 4 courses does not matter LING-777 should be taken last (after LING-211)

Course schedules interpretation may not be unique, but the minimum required quarters are fixed for each input. For example, in Example 3: there are two interpretations of the schedule, as shown below, but the output for this function is still following the order shown in the previous hint.

 Output: ['HIST-199','LING-211','ART-912','ART-431','ART-55','LING-777'] Interpretation1: quarter 1: course HIST-199. quarter 2: course LING-211. quarter 3: course ART-912, ART-431, ART-55,LING-777 Interpretation2: quarter 1: course HIST-199. quarter 2: course LING-211, ART-912, ART-431, ART-55. quarter 3: course LING-777.

You can assume that the course name will always be a valid string.

Problem B - Find all Paths between Cities (6 points):

We represent the connection between cities using a DAG (directed acyclic graph). The vertex on the graph denotes the city, and the edge denotes the path between cities. Your task is to find out all the path combinations to travel from one given city to another.

Problem definition:

Implement the function called: find_paths(connection: List[List[int]], source: int, destination: int) -> List[List[int]], to return a list including all paths from the city source to the city destination. You may return them in any order. If the path does not exist, return an empty list. Note that we use the number (int) as the name of the city.

Function parameters:

connection: a list with length N, where N is the number of paths involved in this connection map. Each sublist in connection, connection[i]=[u,v], indicates that there is a path from the city u to city v.
source: an integer that represents the name of the city.
destination: an integer that represents the name of the city.

Return :

List[List[int]] : a List stores all paths from city source to city destination. Each path should be represented as a list of the city name.

Example 1:

Input: connection = [[0,1],[0,4],[1,2],[2,3],[3,4]] source = 2 destination = 1 Output: [] Explanation: There is no path connection from city 2 to city 1

Example 2:

Input: connection = [[0,1],[1,2],[1,3],[1,5],[2,3],[2,4],[3,4],[4,5],[0,5]] source = 1 destination = 5 Output: [[1,2,3,4,5], [1,2,4,5], [1,3,4,5], [1,5]] Explanation: three paths: 1 -> 3 -> 4 -> 5 and 1 -> 2 -> 3 -> 4 -> 5 and 1 -> 5

Constraints:

Input source and destinationare different numbers, i.e., source destination
Input source and destinationcan always be found in the given connection map
All cities (vertices) in the connection map are unique

Hints:

The connectionis a DAG, i.e., directed and acyclic.
The input connection is not sorted.

Problem C - Largest Score Pattern (3 extra points) (Optional):

Given three arrays of the same length: username, website, and timestamp, where each tuple irepresents that the user username[i] visited the website website[i] at the time timestamp[i]. A pattern is a list of three websites, not necessarily distinct. The score of a pattern is the number of users that consecutive visited all the websites in the pattern in the same order they appeared in the pattern (see more explanation in section:Hints). The task is to find the pattern with the largest score, and if there are multiple patterns with the same score, return the lexicographically smallest pattern.

Problem definition:

the task is to implement a function find_largest_pattern(username: List[str], timestamp: List[int], website: List[str]) -> List[str]: that takes three arrays of strings username, website, and an array of integers timestamp, and returns a list of three strings, representing the pattern with the largest score.

Function parameters:

username : a list of strings representing the usernames of the users who visited the websites.
timestamp : a list of integers representing the timestamps at which the users visited the websites.
website : a list of strings representing the names of the websites visited by the users.

Return :

List[str]: a list of three strings representing the website pattern with the largest score.

Example 1:

Input: username = ["bob","bob","bob","john","john","john","john","mike","mike","mike"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["song","page","faq","song","cart","maps","song","song","page","faq"] Output: ["song","page","faq"] Explanation: The tuples in this example are: ["bob","song",1],["bob","page",2],["bob","faq",3],["john","song",4], ["john","cart",5],["john","maps",6],["john","song",7],["mike","song",8],["mike","page",9], and ["mike","faq",10]. The pattern ["song", "page", "faq"] has score 2 (bob and mike). The pattern ["song", "cart", "maps"] has score 1 (john). The pattern ["song", "cart", "song"] has score 1 (john). The pattern ["song", "maps", "song"] has score 1 (john). The pattern ["cart", "maps", "song"] has score 1 (john). The pattern ["song", "song", "song"] has score 0 (no user visited song 3 times).

Constraints:

It is guaranteed that there is at least one valid pattern in the input
You can assume that given lists are always sorted by the timestamp
The websites in the pattern must be visited by a user continuously (user-wise) for a score. For example, John visited ["song","cart","maps","song"]; then, we cannot say ["song","maps","song"] is a visited pattern of John, since John also visited "cart" in-between "song" and "maps".
Continuous visits are defined user-wise. For example, John visited ["song","cart","maps","song"] at timestamp [1,2,3,5], and another user Bob visited ["cart"] at timestamp [4]. This will not break the continuity of pattern ["cart","maps","song"]