Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 187
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given given a list of rectangles represented by min and max x- and y-coordinates. Compute whether or not a pair of rectangles overlap each other. If one rectangle completely covers another, it is considered overlapping.

For example, given the following rectangles:
```
{
    "top_left": (1, 4),
    "dimensions": (3, 3) # width, height
},
{
    "top_left": (-1, 3),
    "dimensions": (2, 1)
},
{
    "top_left": (0, 5),
    "dimensions": (4, 3)
}
```
return `true` as the first and third rectangle overlap each other.

Pull request:
Day187
Resolves #387.

Patch:
diff --git a/README.md b/README.md
index 4c01982..007c4ff 100644
--- a/README.md
+++ b/README.md
@@ -197,4 +197,5 @@ problems from
 * [Day 184](https://github.com/vaskoz/dailycodingproblem-go/issues/378)
 * [Day 185](https://github.com/vaskoz/dailycodingproblem-go/issues/381)
 * [Day 186](https://github.com/vaskoz/dailycodingproblem-go/issues/382)
+* [Day 187](https://github.com/vaskoz/dailycodingproblem-go/issues/387)
 * [Day 188](https://github.com/vaskoz/dailycodingproblem-go/issues/388)
diff --git a/day187/problem.go b/day187/problem.go
new file mode 100644
index 0000000..f3f1755
--- /dev/null
+++ b/day187/problem.go
@@ -0,0 +1,32 @@
+package day187
+
+// Rectangle is a representation of a rectangle.
+type Rectangle struct {
+	TopLeftX, TopLeftY int
+	Width, Height      int
+}
+
+// DoesRectanglePairOverlap returns true if any rectangles
+// overlap.
+// Runs in O(N^2) time.
+func DoesRectanglePairOverlap(rects []Rectangle) bool {
+	for i, left := range rects {
+		for j, right := range rects {
+			if j > i {
+				if left.TopLeftX > right.TopLeftX {
+					left, right = right, left
+				}
+				if right.TopLeftX < left.TopLeftX+left.Width {
+					up, dn := left, right
+					if up.TopLeftY < dn.TopLeftY {
+						up, dn = dn, up
+					}
+					if dn.TopLeftY > up.TopLeftY-up.Height {
+						return true
+					}
+				}
+			}
+		}
+	}
+	return false
+}


Test patch:
diff --git a/day187/problem_test.go b/day187/problem_test.go
new file mode 100644
index 0000000..13d1efc
--- /dev/null
+++ b/day187/problem_test.go
@@ -0,0 +1,32 @@
+package day187
+
+import "testing"
+
+var testcases = []struct {
+	rects    []Rectangle
+	expected bool
+}{
+	{[]Rectangle{{1, 4, 3, 3}, {-1, 3, 2, 1}, {0, 5, 4, 3}}, true},
+	{[]Rectangle{{1, 4, 1, 1}, {-1, 3, 1, 1}, {0, 5, 4, 3}}, false},
+	{[]Rectangle{{1, 1, 1, 1}, {2, 2, 1, 1}, {3, 3, 1, 1}}, false},
+	{[]Rectangle{{1, 1, 2, 1}, {2, 2, 1, 2}, {3, 3, 1, 1}}, true},
+	{[]Rectangle{{0, 9, 1, 1}, {1, 1, 1, 1}, {2, 2, 1, 1}, {0, 10, 2, 2}}, true},
+	{[]Rectangle{{1, 1, 1, 1}, {2, 2, 1, 1}, {0, 10, 2, 2}}, false},
+}
+
+func TestDoesRectanglePairOverlap(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := DoesRectanglePairOverlap(tc.rects); result != tc.expected {
+			t.Errorf("Given %v, expected %v, got %v", tc.rects, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkDoesRectanglePairOverlap(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			DoesRectanglePairOverlap(tc.rects)
+		}
+	}
+}