Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

let requirementss: [String: [String]] = [
    "calculus":["english", "math2"],
    "math2":["math1", "english", "arabic"],
    "math1":["english"],
    "english": [],
    "arabic": []
]

func minSemsToFinishAllCourses(courses: [String: [String]]) -> Int {
    let allCourses = Array(courses.map({ (key, value) -> [String] in
        return Array([[key],value].joined())
    }).joined())
    return Set(allCourses).count
}

print(minSemsToFinishAllCourses(courses: requirementss))

- eugene.kazaev November 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ProTechMulti November 24, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- Laxmi Narsimha Rao Oruganti November 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- ProTechMulti November 25, 2018 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Laxmi Narsimha Rao Oruganti November 25, 2018 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More