Halfway courses

Students may decide to take different "tracks" or sequences of courses in the Computer Science curriculum. There may be more than one track that includes the same course, but each student follows a single linear track from a "root" node to a "leaf" node. In the graph below, their path always moves left to right.

Write a function that takes a list of (source, destination) pairs, and returns the name of all of the courses that the students could be taking when they are halfway through their track of courses.

Sample input:
all_courses = [
    ["Logic", "COBOL"],
    ["Data Structures", "Algorithms"],
    ["Creative Writing", "Data Structures"],
    ["Algorithms", "COBOL"],
    ["Intro to Computer Science", "Data Structures"],
    ["Logic", "Compilers"],
    ["Data Structures", "Logic"],
    ["Creative Writing", "System Administration"],
    ["Databases", "System Administration"],
    ["Creative Writing", "Databases"],
    ["Intro to Computer Science", "Graphics"],
]

Sample output (in any order):
          ["Data Structures", "Creative Writing", "Databases", "Intro to Computer Science"]

All paths through the curriculum (midpoint *highlighted*):

*Intro to C.S.* -> Graphics
Intro to C.S. -> *Data Structures* -> Algorithms -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> Compiler
Creative Writing -> *Databases* -> System Administration
*Creative Writing* -> System Administration
Creative Writing -> *Data Structures* -> Algorithms -> COBOL
Creative Writing -> *Data Structures* -> Logic -> COBOL
Creative Writing -> *Data Structures* -> Logic -> Compilers

Visual representation:

                    ____________
                    |          |
                    | Graphics |
               ---->|__________|
               |                          ______________
____________   |                          |            |
|          |   |    ______________     -->| Algorithms |--\     _____________
| Intro to |   |    |            |    /   |____________|   \    |           |
| C.S.     |---+    | Data       |   /                      >-->| COBOL     |
|__________|    \   | Structures |--+     ______________   /    |___________|
                 >->|____________|   \    |            |  /
____________    /                     \-->| Logic      |-+      _____________
|          |   /    ______________        |____________|  \     |           |
| Creative |  /     |            |                         \--->| Compilers |
| Writing  |-+----->| Databases  |                              |___________|
|__________|  \     |____________|-\     _________________________
               \                    \    |                       |
                \--------------------+-->| System Administration |
                                         |_______________________|

Complexity analysis variables:

n: number of pairs in the input

/** You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program. Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

Write a function that takes a list of (prerequisite, course) pairs, and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses, you should return the first one.)

Sample input 1: (arbitrarily ordered)

prereqs_courses1 = [

["Foundations of Computer Science", "Operating Systems"],

["Data Structures", "Algorithms"],

["Computer Networks", "Computer Architecture"],

["Algorithms", "Foundations of Computer Science"],

["Computer Architecture", "Data Structures"],

["Software Design", "Computer Networks"] ]

In this case, the order of the courses in the program is:

Software Design

Computer Networks

Computer Architecture

Data Structures Algorithms

Foundations of Computer Science

Operating Systems

Sample output 1: "Data Structures"

Sample input 2:

prereqs_courses2 = [

["Algorithms", "Foundations of Computer Science"],

["Data Structures", "Algorithms"],

["Foundations of Computer Science", "Logic"],

["Logic", "Compilers"],

["Compilers", "Distributed Systems"],

]

Sample output 2: "Foundations of Computer Science"

Sample input 3:

prereqs_courses3 = [

["Data Structures", "Algorithms"],

]

Sample output 3: "Data Structures"

Complexity analysis variables: n: number of pairs in the input /

import java.io.; import java.util.*; public class Solution { public static void main(String[] argv) { String[][] prereqsCourses1 = { {"Foundations of Computer Science", "Operating Systems"}, {"Data Structures", "Algorithms"}, {"Computer Networks", "Computer Architecture"}, {"Algorithms", "Foundations of Computer Science"}, {"Computer Architecture", "Data Structures"}, {"Software Design", "Computer Networks"} }; String[][] prereqsCourses2 = { {"Algorithms", "Foundations of Computer Science"}, {"Data Structures", "Algorithms"}, {"Foundations of Computer Science", "Logic"}, {"Logic", "Compilers"}, {"Compilers", "Distributed Systems"}, }; String[][] prereqsCourses3 = { {"Data Structures", "Algorithms"} }; System.out.println(findHalfway(prereqsCourses3)); } public static String findHalfway (String[][] courses) { } }

Solution:

const prereqs_courses1 = [
  ['Data Structures', 'Algorithms'],
  ['Foundations of Computer Science', 'Operating Systems'],
  ['Computer Networks', 'Computer Architecture'],
  ['Algorithms', 'Foundations of Computer Science'],
  ['Computer Architecture', 'Data Structures'],
  ['Software Design', 'Computer Networks'],
];

const prereqs_courses2 = [
  ['Data Structures', 'Algorithms'],
  ['Algorithms', 'Foundations of Computer Science'],
  ['Foundations of Computer Science', 'Logic'],
];

const prereqs_courses3 = [['Data Structures', 'Algorithms']];

const allCourses = [
  ['Logic', 'COBOL'],
  ['Data Structures', 'Algorithms'],
  ['Creative Writing', 'Data Structures'],
  ['Algorithms', 'COBOL'],
  ['Intro to Computer Science', 'Data Structures'],
  ['Logic', 'Compilers'],
  ['Data Structures', 'Logic'],
  ['Creative Writing', 'System Administration'],
  ['Databases', 'System Administration'],
  ['Creative Writing', 'Databases'],
  ['Intro to Computer Science', 'Graphics'],
];

第二题在第一题的基础上有交叉课程，换句话说是图里有圈的存在了，我讲完思路就没时间写了。 攒人品，‍‍‌‌‌‍‌‌‌‍‌‍‍‌‍‌‍‍‌‍希望能进下一轮。

Optimal solution:

public static String findHalfway (String[][] courses) {
      LinkedList<String> lst = new LinkedList<>();
      int x = courses.length;
      // assume there is always records.
      //"Data Structures" -> "Algorithms" -> "Foundations of Computer Science" -> "Operating Systems"
      Map<String, String> ba = new HashMap<>();
      Map<String, String> ab = new HashMap<>();
      for(int i=0; i<x; i++) {
        String before = courses[i][0];
        String after = courses[i][1];
        ba.put(before, after);
        ab.put(after, before);
      }
      lst.add(courses[0][0]);
      lst.add(courses[0][1]);
      for(int j=1; j<x; j++){
        String head = lst.getFirst();
        String tail = lst.getLast();
        if(ab.get(head) != null) {
          lst.addFirst(ab.get(head));
        }
        if(ba.get(tail) != null) {
          lst.addLast(ba.get(tail));
        }
      }
      return lst.get(x/2);
  }