## Google Interview Question

Software Developers**Country:**United States

I think that's a good algorithm. Only a small correction: if I understood this correctly.. step 2, when they have the same semester, the weight should be set to 2 since in order to start the next one in the fall you need to have this one completed in this fall. So, you could start the next one not in the same semester or not even in the next semester, but in a semester after that.

topological sort to get the graph detailing prerequisite, then dfs from starting nodes, to get the number of semesters needed

Doesn't taking the topological sort hinder the parallelism? For example, in the 1st university say both mt42 and cs123 are offered in fall. Taking the top sort will give you mt42 and cs123 one after the other and we've lost the parallelism. Unless we get the top sort and then on top of that parse the top sort with the semester information and the hard limit.

Keep a score for each course, iterating frm the third line of the input

CourseScore = SemScore + SumOf(CourseScore(Dependent Course score))

where SemScore is 0,1 depending on whether the course is in Fall or Spring

the second term can be calculated using memoization or recursion

Alright, this took me a couple of hours to put together in a comfortable setup, I don't know how they expect this in an interview. The question is pretty easy if you remove the constraint of maximum courses per semester, but otherwise this has to be a recursive backtracking solution. It could probably done using dynamic programming as well but I'm afraid it will have a high memory complexity.

Below is a solution using a recursive method. The basic idea is topological sort, we have one map called the 'blueprint' which is essentially a dependency graph of the input unchanged, and another map 'curr_map' that is constantly being modified to reflect the courses we have chosen to take. Each time we choose to take courses in a given semester we remove them from the current map (and all of their dependencies) and when we backtrack we add them back. The method 'get_options' is a modified version of the 'get sources' procedure in topological sort that takes into account the current semester. The code is pretty long, but it works. Enjoy!

```
#pragma once
#include <iostream>
#include <memory>
#include <list>
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
namespace course_optimizer
{
template <typename K, typename V>
using map = boost::unordered_map<K, V>;
template <typename T>
using set = boost::unordered_set<T>;
template <typename T>
using shared_ptr = std::shared_ptr<T>;
enum class semester_t { fall, spring, both };
semester_t convert(char c)
{
if ('F' == c) return semester_t::fall;
else if ('S' == c) return semester_t::spring;
else if ('B' == c) return semester_t::both;
else throw std::invalid_argument("invalid course time character argument.");
}
using course_id = std::string;
using istream = std::istream;
class node
{
public:
node(course_id _id) : id(_id) {};
std::string id;
semester_t time;
set<shared_ptr<node>> outgoing;
set<shared_ptr<node>> incoming;
};
class optimizer
{
public:
using course_map = map < course_id, shared_ptr<node> > ;
optimizer(istream& in, size_t num, size_t mcps) : mcps_(mcps)
{
course_id id;
for (auto i = 0; i < num; ++i)
{
in >> id;
courses_[id] = std::make_shared<node>(id);
}
for (auto i = 0; i < num; ++i)
{
in >> id;
char ct;
in >> ct;
if (courses_.find(id) == courses_.end()) throw std::invalid_argument("invalid id argument.");
courses_[id]->time = convert(ct);
auto num_pre = 0;
in >> num_pre;
if (num_pre < 0) throw std::invalid_argument("invalid prerequisite argument: cannot be negative.");
for (auto j = 0; j < num_pre; ++j)
{
course_id pre_id;
in >> pre_id;
courses_[id]->incoming.insert(courses_[pre_id]);
courses_[pre_id]->outgoing.insert(courses_[id]);
}
}
}
size_t compute_min_courses()
{
auto curr_map = copy_course_map(courses_);
return compute(courses_, curr_map, semester_t::fall);
}
private:
size_t compute(const course_map& blueprint, course_map& curr_map, const semester_t& semester, std::list<course_id> options = std::list<course_id>(), size_t options_processed = 0)
{
if (curr_map.empty()) return 0;
semester_t next_semester = (semester_t::fall == semester) ? semester_t::spring : semester_t::fall;
if (options.empty()) options = get_options(curr_map, semester);
if (options.size() <= mcps_)
{
// we can take all of the options. remove from current map and get the recursive call result
for (const auto& id : options)
{
for (auto& n : curr_map[id]->outgoing)
{
n->incoming.erase(curr_map[id]);
}
curr_map.erase(id);
}
auto rv = 1 + compute(blueprint, curr_map, next_semester);
// recover the current map
for (const auto& id : options)
{
curr_map[id] = std::make_shared<node>(id);
curr_map[id]->time = blueprint.at(id)->time;
for (const auto& n : blueprint.at(id)->outgoing)
{
curr_map[n->id]->incoming.insert(curr_map[id]);
}
}
return rv;
}
else
{
// we have to pick an option to ignore (not take this semester). options_processed is a counter to avoid duplicating recursive calls.
auto min = std::numeric_limits<size_t>::max();
for (auto i = std::next(std::begin(options), options_processed); i != std::end(options); ++i)
{
// dont take it
auto id = *i;
i = options.erase(i);
min = std::min(min, compute(blueprint, curr_map, semester, options, options_processed));
i = options.insert(i, id);
++options_processed;
}
return min;
}
}
// get all courses that can be taken in the input semester and have all of their requisites filled already (no incoming).
std::list<course_id> get_options(const course_map& courses, const semester_t& semester)
{
std::list<course_id> options;
for (const auto& p : courses)
{
if (p.second->incoming.empty() && (semester_t::both == p.second->time || semester == p.second->time))
{
options.push_back(p.first);
}
}
return options;
}
course_map copy_course_map(const course_map& source)
{
course_map dest;
for (const auto& p : source)
{
dest[p.first] = std::make_shared<node>(p.first);
dest[p.first]->time = p.second->time;
}
for (const auto& p : source)
{
for (const auto& n : p.second->incoming)
{
dest[p.first]->incoming.insert(dest[n->id]);
}
for (const auto& n : p.second->outgoing)
{
dest[p.first]->outgoing.insert(dest[n->id]);
}
}
return dest;
}
// m = max courses per semester
const size_t mcps_;
// dependency map
course_map courses_;
};
void solve(istream& in)
{
auto n = 0, m = 0;
in >> n >> m;
while (n > 0 && m > 0)
{
optimizer opt(in, n, m);
std::cout << "The minimum number of semesters required to graduate is " << opt.compute_min_courses() << "." << std::endl;
in >> n >> m;
}
}
}
```

```
/*
A C++ solution using map.
We store the courses in a map and schedule using greedy strategy.
We also put the courses in separate vectors for easy access.
In case there are more courses in a semester than allowed, we give
higher precedence to 'Fall' and 'Spring' than 'Both', since 'Both' can be
taken in any iteration.
*/
#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <string>
using namespace std;
#define BIG_INT 999999
enum semester{
Fall,
Spring,
Both
};
struct course;
typedef struct course Course;
struct course{
string name;
semester s;
int doneAt;
std::vector<string> dep;
};
typedef std::map<string, Course*> CourseMap;
int CalculateSemester(CourseMap& cmap,vector<string>* courses, int m){
int count = 0;
while(!courses[Fall].empty() || !courses[Spring].empty() || !courses[Both].empty()){
int size = 0;
int s = count%2;
// Schedule courses for Fall or Spring
while(!courses[s].empty() && size < m){
bool added = false;
for(int i=0; i<courses[s].size() && size < m; i++){
if(cmap[courses[s][i]]->doneAt == BIG_INT){
bool include = true;
int j=0;
for(j=0; j<cmap[courses[s][i]]->dep.size(); j++){
if(cmap[cmap[courses[s][i]]->dep[j]]->doneAt >= count){
include=false;
break;
}
}
if(include && size < m){
cmap[courses[s][i]]->doneAt = count;
size++;
courses[s].erase(courses[s].begin()+i);
added = true;
}
}
}
if(!added) break;
}
// Schedule coursed from Both
while(!courses[2].empty() && size < m){
bool added = false;
for(int i=0; i<courses[2].size() && size < m; i++){
if(cmap[courses[2][i]]->doneAt == BIG_INT){
bool include = true;
int j=0;
for(j=0; j<cmap[courses[2][i]]->dep.size(); j++){
if(cmap[cmap[courses[2][i]]->dep[j]]->doneAt >= count){
include=false;
break;
}
}
if(include && size < m){
cmap[courses[2][i]]->doneAt = count;
size++;
courses[2].erase(courses[2].begin()+i);
added = true;
}
}
}
if(!added) break;
}
count++;
}
return count;
}
int main() {
freopen("input.txt", "r", stdin);
while(true){
int n;
scanf("%d", &n);
if(n == -1) break;
int m;
scanf("%d", &m);
if(m == -1) break;
CourseMap cmap;
vector<string> courses[3];
char buf[100];
for(int i=0; i<n; i++) scanf("%s", buf);
for(int i=0; i<n; i++){
scanf("%s", buf);
Course* c = new Course();
c->doneAt = BIG_INT; // some big number
c->name = string(buf);
scanf("%s", buf);
c->s = (buf[0] == 'F' ? Fall : (buf[0] == 'S' ? Spring : Both));
courses[c->s].push_back(c->name);
int dp;
scanf("%d", &dp);
for(int j=0; j<dp; j++){
scanf("%s", buf);
c->dep.push_back(string(buf));
}
cmap[c->name] = c;
}
cout << "The minimum number of semesters required to graduate is " << CalculateSemester(cmap,&courses[0],m) << endl;
}
return 0;
}
```

1. construct graph of dependencies.

- dyzmax June 19, 20152. for every edge, if one of the nodes is “both” set weight to 0, if both nodes have the same semester assign 0, if they have different semesters assign 1

3. for every starting node (no dependency node) that starts in spring, add a non dependency artificial node that that has an edge to the starting node, with weight 1 (this is to ensure that we always start counting in fall)

4. you may have now multiple “starting” (without dependencies nodes). if this is the case add a single artificial node (let’s call it a “graph source”) that has 0 weight edges to all no dependency nodes. this will make your graph having only one no dependency node

5. do dijkstra algorithm starting from source (after the action from 4 you have only a single source node). after you are done you will get the lengths of the paths between the source node and all the nodes. max of those path lengths would be your answer if there are no semester limits.

6. let’s make your solution obey the limits. first let’s notice that after dijkstra run you have your courses sliced (grouped) in layers - all the nodes that have the same distance from the source are in the same layer, they are happening in a single semester. you iterate through layers starting from semester 0, and do the following:

a) if the number of nodes is <= the limit, you are fine. you go to the next layer (semester). in the limit check you do not consider artificial nodes you added in points 3 and 4

b) if the number of nodes is > the limit, then you need to push some nodes forward to obey the limit. if your limit is “l”, and number of nodes in the semester is “k” (k > l), then you need to choose all possible layer subsets that have l - k elements (the number of nodes that you have over limit). For every such subset you do the following:

i) you push them forward by modifying the graph. If the season assigned to your layer (spring or fall) is different than the season of the over the limit node or the over the limit node is “both”, you add 1 to the weight of all the edges incoming to this node. Otherwise (If the seasons are the same and over the limit node’s season is not both), you add 2.

ii) now you have a new graph, that fixed the limit in the layer you were in. you are doing dijsktra starting from this layer ( before you remove all the min path information for the nodes in the layers later than the one you removed over the limit nodes from). after dijkstra either you have a new result within limits, or one of the layers is again over the limits. You do the recursive call of the same limits fixing procedure - you push over the limit nodes forwrad etc etc. By doing that at some point you will fix all the layers.

7. when pushing forward all over the limit subsets and repeating that for all the over the limit layers, you will get a recursion tree which at leafs has one possible arrangement of courses that is within the limits and dependencies. Such tree has a max path. the min of max paths over all such trees is your solution.