Interview Question
Country: United States
The solution:
Create a reverse map that will store Map<String, Set<String>>.
The reverse map will be used for quick access of removing course dependencies.
The main idea is that we start with the courses that doesn't have dependencies, registering them for the 1st semester. Next we will remove the assigned courses from the dependencies and run again the loop and follow the same rules, register courses without dependencies. Until we will register all courses to semesters.
I tried to write more readable code:
package com.tech.yriaznov;
import java.util.*;
public class Main {
public static void main(String[] args) {
int semesters = MinSemsToFinishAllCourses(GetMockData());
System.out.print("Total semesters: " + semesters);
}
public static int MinSemsToFinishAllCourses(Map<String,List<String>> courses) {
Map<String,Set<String>> reverseMap = ReverseMap(courses);
int totalCourses = courses.size();
int registeredCourses = 0;
int currentSemester = 1;
Set<String> registredCoursesSet = new HashSet<>();
while(registeredCourses < totalCourses) {
Set<String> forClear = new HashSet<>();
for(String key : courses.keySet()) {
if(courses.get(key).size() > 0 || registredCoursesSet.contains(key)) continue;
registredCoursesSet.add(key);
registeredCourses++;
forClear.add(key);
System.out.println("Course: " + key + " on semester " + currentSemester);
}
for(String key : forClear) {
ClearDependencies(key,courses,reverseMap);
}
currentSemester++;
}
return currentSemester-1;
}
public static void ClearDependencies(String course,Map<String,List<String>> courses,
Map<String,Set<String>> reverseMap) {
Set<String> depCourses = reverseMap.get(course);
if(depCourses == null) return;
for(String key : depCourses) {
courses.get(key).remove(course);
}
}
public static Map<String,Set<String>> ReverseMap(Map<String,List<String>> courses) {
Map<String,Set<String>> reverseMap = new HashMap<>();
for(String key : courses.keySet()) {
List<String> list = courses.get(key);
for(int i=0; i<list.size();i++) {
String course = list.get(i);
Set<String> subList = reverseMap.getOrDefault(course,null);
if(subList == null) reverseMap.put(course,new HashSet<>());
reverseMap.get(course).add(key);
}
}
return reverseMap;
}
public static Map<String,List<String>> GetMockData() {
Map<String,List<String>> mockData = new HashMap<>();
List<String> Calculus = new ArrayList<>();
Calculus.add("English");
Calculus.add("Math2");
mockData.put("Calculus",Calculus);
List<String> Math2 = new ArrayList<>();
Math2.add("Math1");
Math2.add("Arabic");
Math2.add("English");
mockData.put("Math2",Math2);
List<String> Math1 = new ArrayList<>();
Math1.add("English");
mockData.put("Math1",Math1);
mockData.put("English",new ArrayList<>());
mockData.put("Arabic",new ArrayList<>());
return mockData;
}
}
Output:
Course: English on semester 1
Course: Arabic on semester 1
Course: Math1 on semester 2
Course: Math2 on semester 3
Course: Calculus on semester 4
Total semesters: 4
This seems like a good tree problem. Think like each node in a tree is a course, children are nothing but per-requisites. As a single course can be pre-requisites to multiple other courses, we can't really imagine this as a tree, but actually need to have a graph. To make the problem simple, after building the graph, keep the courses with multiple parents (or that have this course as pre-req) at the highest depth.
Algorithm:
- Treat this as a Graph where nodes are courses and edges are pre-requisites (i.e. directed edges)
- Create an initial node as 'ALL' to represent ALL coursees
- Create nodes for all other courses and create an edge between ALL node to each of these nodes
- For each pre-requisites relationship add edges in the graph
- Convert the graph into tree by pruning any edges to a node with shorter depth (with ALL node as root node)
- Assume each semester allows 'N' courses
- Do a level order traversal of the tree, get an output in an array
- Pick the 'N' courses at a time from the last to first and produce semester wise course schedule
For example:
Courses are: A, B, C, D, E, F, G, H
Legend: [X, {Y,Z}] Course X pre-requisites are courses Y, Z
Pre-requisites:
- [A, {B,C}], [E, {D, F, G}], [H, {None}]
- [B, {None}], [C, {D}], [F, {None}], [G, {None}]
- [D, {None}]
Initial Graph:
(without edges from ALL root node if the node already has an edge from another node)
ALL -------.
/ \ |
/ \ |
A .----E H
/ \ | / \
/ \ | / \
B C | F G
\|
D
- Course D has multiple parents C and E
- Depth of D via parent C is more than via parent E, so prune edge D-E
Initial Tree:
(after pruning of extraneous edges)
ALL -------.
/ \ |
/ \ |
A E H
/ \ / \
/ \ / \
B C F G
\
D
Level Order Output of Tree:
[A, E, H, B, C, F, G, D]
Say, no. of Courses per Semester = 4
Pick courses from right to left for each semester
Semester-1: [D, G, F, C]
Semester-2: [B, H, E, A]
Great solution... I thought about some thing similar but found some problem. How do you treat nodes that are floating without relation. Let's say I have a general course that isn't a pre-requisite to any other course. Would you connect it to the graph in some way? Or you store it in another data structure?
Hi @ProTechMulti - Not just nodes w/o relation, but I could have groups of courses that are exclusive to each other. Hence, I created a dummy root node 'ALL' to attach all of them.
I have updated my answer above with more details to clarify a bit more. I am hoping that I was able to answer your question. If not. please do let me know.
- eugene.kazaev November 23, 2018