Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 307
Good morning! Here's your coding interview problem for today.

This problem was asked by Oracle.

Given a binary search tree, find the floor and ceiling of a given integer. The floor is the highest element in the tree less than or equal to an integer, while the ceiling is the lowest element in the tree greater than or equal to an integer.

If either value does not exist, return None.

Pull request:
Day307
Resolves #628.

Patch:
diff --git a/README.md b/README.md
index 9a237bc..1b45316 100644
--- a/README.md
+++ b/README.md
@@ -315,3 +315,4 @@ problems from
 * [Day 304](https://github.com/vaskoz/dailycodingproblem-go/issues/618)
 * [Day 305](https://github.com/vaskoz/dailycodingproblem-go/issues/622)
 * [Day 306](https://github.com/vaskoz/dailycodingproblem-go/issues/626)
+* [Day 307](https://github.com/vaskoz/dailycodingproblem-go/issues/628)
diff --git a/day307/problem.go b/day307/problem.go
new file mode 100644
index 0000000..a56ae61
--- /dev/null
+++ b/day307/problem.go
@@ -0,0 +1,113 @@
+package day307
+
+import "errors"
+
+var errNoAnswer = errors.New("no answer exists")
+
+// ErrNoAnswer returns the error returned for no answer.
+func ErrNoAnswer() error {
+	return errNoAnswer
+}
+
+// BinaryTree is a binary tree of integers.
+type BinaryTree struct {
+	Value       int
+	Left, Right *BinaryTree
+}
+
+// FloorRecursive returns the highest element in the tree less
+// than or equal to the target.
+// Returns an error if no answer exists.
+func FloorRecursive(root *BinaryTree, target int) (int, error) {
+	if root == nil {
+		return 0, errNoAnswer
+	}
+	if target == root.Value {
+		return target, nil
+	}
+	if target < root.Value {
+		return FloorRecursive(root.Left, target)
+	}
+	ans, err := FloorRecursive(root.Right, target)
+	if err != nil && root.Value <= target {
+		return root.Value, nil
+	}
+	return ans, err
+}
+
+// FloorFaster returns the highest element in the tree less
+// than or equal to the target.
+// Returns an error if no answer exists.
+func FloorFaster(root *BinaryTree, target int) (int, error) {
+	curr := root
+	var candidate *BinaryTree
+	for {
+		if curr.Value == target {
+			return curr.Value, nil
+		}
+		if target < curr.Value {
+			if curr.Left != nil {
+				curr = curr.Left
+			} else {
+				return 0, errNoAnswer
+			}
+		} else {
+			candidate = curr
+			if curr.Right != nil {
+				curr = curr.Right
+			} else if candidate != nil {
+				return candidate.Value, nil
+			}
+		}
+	}
+}
+
+// CeilingRecursive returns the lowest element in the tree greater
+// than or equal to the target.
+// Returns an error if no answer exists.
+func CeilingRecursive(root *BinaryTree, target int) (int, error) {
+	if root == nil {
+		return 0, errNoAnswer
+	}
+	if target == root.Value {
+		return target, nil
+	}
+	if target < root.Value {
+		ans, err := CeilingRecursive(root.Left, target)
+		if err != nil && root.Value >= target {
+			return root.Value, nil
+		}
+		return ans, err
+	}
+	return CeilingRecursive(root.Right, target)
+}
+
+// CeilingFaster returns the lowest element in the tree greater
+// than or equal to the target.
+// Returns an error if no answer exists.
+func CeilingFaster(root *BinaryTree, target int) (int, error) {
+	curr := root
+	var candidate *BinaryTree
+	for {
+		if curr.Value == target {
+			return curr.Value, nil
+		}
+		if target < curr.Value {
+			candidate = curr
+			if curr.Left != nil {
+				curr = curr.Left
+			} else if candidate != nil {
+				return candidate.Value, nil
+			}
+		} else {
+			switch {
+			case curr.Right != nil:
+				curr = curr.Right
+			case candidate != nil:
+				return candidate.Value, nil
+			default:
+				return 0, errNoAnswer
+			}
+		}
+	}
+}


Test patch:
diff --git a/day307/problem_test.go b/day307/problem_test.go
new file mode 100644
index 0000000..92ee150
--- /dev/null
+++ b/day307/problem_test.go
@@ -0,0 +1,146 @@
+package day307
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	root             *BinaryTree
+	target           int
+	expectedFloor    int
+	expectedFloorErr error
+	expectedCeil     int
+	expectedCeilErr  error
+}{
+	{
+		&BinaryTree{
+			11,
+			&BinaryTree{9, nil, nil},
+			&BinaryTree{12, nil, nil},
+		},
+		10,
+		9,
+		nil,
+		11,
+		nil,
+	},
+	{
+		&BinaryTree{
+			11,
+			&BinaryTree{9, nil, nil},
+			&BinaryTree{12, nil, nil},
+		},
+		12,
+		12,
+		nil,
+		12,
+		nil,
+	},
+	{
+		&BinaryTree{
+			11,
+			&BinaryTree{9, nil, nil},
+			&BinaryTree{12, nil, nil},
+		},
+		13,
+		12,
+		nil,
+		0,
+		ErrNoAnswer(),
+	},
+	{
+		&BinaryTree{
+			11,
+			&BinaryTree{9, nil, nil},
+			&BinaryTree{12, nil, nil},
+		},
+		8,
+		0,
+		ErrNoAnswer(),
+		9,
+		nil,
+	},
+	{
+		&BinaryTree{
+			12,
+			&BinaryTree{9, nil, nil},
+			&BinaryTree{14, nil, nil},
+		},
+		11,
+		9,
+		nil,
+		12,
+		nil,
+	},
+}
+
+func TestFloorRecursive(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result, err := FloorRecursive(tc.root, tc.target); result != tc.expectedFloor ||
+			err != tc.expectedFloorErr {
+			t.Errorf("TCID %d Expected (%v,%v), got (%v,%v)", tcid, tc.expectedFloor, tc.expectedFloorErr, result, err)
+		}
+	}
+}
+
+func BenchmarkFloorRecursive(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FloorRecursive(tc.root, tc.target) // nolint
+		}
+	}
+}
+
+func TestFloorFaster(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result, err := FloorFaster(tc.root, tc.target); result != tc.expectedFloor ||
+			err != tc.expectedFloorErr {
+			t.Errorf("TCID %d Expected (%v,%v), got (%v,%v)", tcid, tc.expectedFloor, tc.expectedFloorErr, result, err)
+		}
+	}
+}
+
+func BenchmarkFloorFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FloorRecursive(tc.root, tc.target) // nolint
+		}
+	}
+}
+
+func TestCeilingRecursive(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result, err := CeilingRecursive(tc.root, tc.target); result != tc.expectedCeil ||
+			err != tc.expectedCeilErr {
+			t.Errorf("TCID %d Expected (%v,%v), got (%v,%v)", tcid, tc.expectedCeil, tc.expectedCeilErr, result, err)
+		}
+	}
+}
+
+func BenchmarkCeiling(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CeilingRecursive(tc.root, tc.target) // nolint
+		}
+	}
+}
+
+func TestCeilingFaster(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result, err := CeilingFaster(tc.root, tc.target); result != tc.expectedCeil ||
+			err != tc.expectedCeilErr {
+			t.Errorf("TCID %d Expected (%v,%v), got (%v,%v)", tcid, tc.expectedCeil, tc.expectedCeilErr, result, err)
+		}
+	}
+}
+
+func BenchmarkCeilingFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CeilingFaster(tc.root, tc.target) // nolint
+		}
+	}
+}