Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 171
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

You are given a list of data entries that represent entries and exits of groups of people into a building. An entry looks like this:
`
{"timestamp": 1526579928, count: 3, "type": "enter"}
`
This means 3 people entered the building. An exit looks like this:
`
{"timestamp": 1526580382, count: 2, "type": "exit"}
`
This means that 2 people exited the building. timestamp is in Unix time.

Find the busiest period in the building, that is, the time with the most people in the building. Return it as a pair of (start, end) timestamps. You can assume the building always starts off and ends up empty, i.e. with 0 people inside.

Pull request:
Day171
Resolves #356.

Patch:
diff --git a/README.md b/README.md
index 84efb38..e8f3088 100644
--- a/README.md
+++ b/README.md
@@ -182,3 +182,4 @@ problems from
 * [Day 168](https://github.com/vaskoz/dailycodingproblem-go/issues/348)
 * [Day 169](https://github.com/vaskoz/dailycodingproblem-go/issues/352)
 * [Day 170](https://github.com/vaskoz/dailycodingproblem-go/issues/353)
+* [Day 171](https://github.com/vaskoz/dailycodingproblem-go/issues/356)
diff --git a/day171/problem.go b/day171/problem.go
new file mode 100644
index 0000000..31ad74b
--- /dev/null
+++ b/day171/problem.go
@@ -0,0 +1,47 @@
+package day171
+
+import "sort"
+
+// EnterOrExit represents either entering the building or exiting.
+type EnterOrExit string
+
+const (
+	// Enter means people are entering the building.
+	Enter EnterOrExit = "enter"
+	// Exit means people are leaving the building.
+	Exit EnterOrExit = "exit"
+)
+
+// Movement is an entry in the building's movement slice.
+type Movement struct {
+	Timestamp uint64
+	Count     int
+	Type      EnterOrExit
+}
+
+// BusiestBuildingTimes returns the timestamp start and end
+// when the building has the most people.
+// Runs in O(N log N) time because it sorts the input by timestamp.
+// Assumes building starts with 0 people and ends with 0 people.
+func BusiestBuildingTimes(moves []Movement) (uint64, uint64) {
+	sort.Slice(moves, func(i, j int) bool {
+		return moves[i].Timestamp < moves[j].Timestamp
+	})
+	if len(moves) == 0 {
+		return 0, 0
+	}
+	var start, end uint64
+	var count, maxCount int
+	for i, move := range moves {
+		if move.Type == Enter {
+			count += move.Count
+			if count > maxCount {
+				start = move.Timestamp
+				end = moves[i+1].Timestamp
+			}
+		} else if move.Type == Exit {
+			count -= move.Count
+		}
+	}
+	return start, end
+}


Test patch:
diff --git a/day171/problem_test.go b/day171/problem_test.go
new file mode 100644
index 0000000..9ee1827
--- /dev/null
+++ b/day171/problem_test.go
@@ -0,0 +1,30 @@
+package day171
+
+import "testing"
+
+var testcases = []struct {
+	moves      []Movement
+	start, end uint64
+}{
+	{[]Movement{{0, 3, Enter}, {1, 3, Exit}}, 0, 1},
+	{[]Movement{}, 0, 0},
+	{nil, 0, 0},
+	{[]Movement{{30, 20, Exit}, {10, 10, Enter}, {20, 10, Enter}}, 20, 30},
+}
+
+func TestBusiestBuildingTimes(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if start, end := BusiestBuildingTimes(tc.moves); start != tc.start || end != tc.end {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.start, tc.end, start, end)
+		}
+	}
+}
+
+func BenchmarkBusiestBuildingTimes(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BusiestBuildingTimes(tc.moves)
+		}
+	}
+}