Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 92
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

We're given a hashmap with a key courseId and value a list of courseIds, which represents that the prerequsite of courseId is courseIds. Return a sorted ordering of courses such that we can finish all courses.

Return null if there is no such ordering.

For example, given `{'CSC300': ['CSC100', 'CSC200'], 'CSC200': ['CSC100'], 'CSC100': []}, should return ['CSC100', 'CSC200', 'CSC300']`.

Pull request description:
Day92
Resolves #194.

Patch:
diff --git a/README.md b/README.md
index dbbf95a..70585dd 100644
--- a/README.md
+++ b/README.md
@@ -101,3 +101,4 @@ problems from
 * [Day 89](https://github.com/vaskoz/dailycodingproblem-go/issues/187)
 * [Day 90](https://github.com/vaskoz/dailycodingproblem-go/issues/189)
 * [Day 91](https://github.com/vaskoz/dailycodingproblem-go/issues/192)
+* [Day 92](https://github.com/vaskoz/dailycodingproblem-go/issues/194)
diff --git a/day92/problem.go b/day92/problem.go
new file mode 100644
index 0000000..16d957a
--- /dev/null
+++ b/day92/problem.go
@@ -0,0 +1,45 @@
+package day92
+
+// CourseOrder returns how to take all the courses.
+// If it's not possible to take all the courses, returns nil.
+// Runs in O(N) time.
+func CourseOrder(prereq map[string][]string) []string {
+	var result []string
+	marked := make(map[string]int)
+	for n := range prereq {
+		if _, found := marked[n]; !found {
+			newest := visit(n, prereq, marked, result)
+			if len(newest) > len(result) {
+				result = newest
+			}
+		}
+	}
+	if len(marked) != len(prereq) {
+		return nil
+	}
+	reverse(result)
+	return result
+}
+
+func reverse(n []string) {
+	for i := 0; i < len(n)/2; i++ {
+		n[i], n[len(n)-1-i] = n[len(n)-1-i], n[i]
+	}
+}
+
+func visit(node string, graph map[string][]string,
+	marked map[string]int, result []string) []string {
+	if mark := marked[node]; mark != 0 {
+		return nil
+	}
+	marked[node] = 1
+	for _, m := range graph[node] {
+		newest := visit(m, graph, marked, result)
+		if len(newest) > len(result) {
+			result = newest
+		}
+	}
+	marked[node] = 2
+	result = append([]string{node}, result...)
+	return result
+}


Test patch:
diff --git a/day92/problem_test.go b/day92/problem_test.go
new file mode 100644
index 0000000..1560f4a
--- /dev/null
+++ b/day92/problem_test.go
@@ -0,0 +1,40 @@
+package day92
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	prereqs  map[string][]string
+	expected []string
+}{
+	{map[string][]string{
+		"CSC300": {"CSC100", "CSC200"},
+		"CSC200": {"CSC100"},
+		"CSC100": {},
+	},
+		[]string{"CSC100", "CSC200", "CSC300"}},
+	{map[string][]string{
+		"CSC300": {"CSC100"},
+		"CSC400": {"CSC200"},
+	},
+		nil},
+}
+
+func TestCourseOrder(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CourseOrder(tc.prereqs); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkCourseOrder(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CourseOrder(tc.prereqs)
+		}
+	}
+}