Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 24
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.

Design a binary tree node class with the following methods:

* **is_locked**, which returns whether the node is locked
* **lock**, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true.
* **unlock**, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true.

You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree.

Pull request:
Day24
Resolves #57 .

Patch:
diff --git a/README.md b/README.md
index e73a706..ce0ca19 100644
--- a/README.md
+++ b/README.md
@@ -37,3 +37,4 @@ problems from
 * [Day 21](https://github.com/vaskoz/dailycodingproblem-go/issues/51)
 * [Day 22](https://github.com/vaskoz/dailycodingproblem-go/issues/53)
 * [Day 23](https://github.com/vaskoz/dailycodingproblem-go/issues/55)
+* [Day 24](https://github.com/vaskoz/dailycodingproblem-go/issues/57)
diff --git a/day24/problem.go b/day24/problem.go
new file mode 100644
index 0000000..9883f71
--- /dev/null
+++ b/day24/problem.go
@@ -0,0 +1,58 @@
+package day24
+
+// LockableBinaryTree implements a binary tree where nodes
+// can be locked.
+type LockableBinaryTree struct {
+	Locked              bool
+	LockedDescendants   int
+	Left, Right, Parent *LockableBinaryTree
+}
+
+// IsLocked returns true if locked, false otherwise.
+func (lbt *LockableBinaryTree) IsLocked() bool {
+	return lbt.Locked
+}
+
+// Lock acquires a lock on this node if possible.
+// Returns true if lock is acquired, false if it wasn't.
+func (lbt *LockableBinaryTree) Lock() bool {
+	if lbt.canModify() {
+		lbt.Locked = true
+		cur := lbt.Parent
+		for cur != nil {
+			cur.LockedDescendants++
+			cur = cur.Parent
+		}
+		return true
+	}
+	return false
+}
+
+// Unlock frees this node if possible.
+// Returns true if unlocked, false if it couldn't be.
+func (lbt *LockableBinaryTree) Unlock() bool {
+	if lbt.canModify() {
+		lbt.Locked = false
+		cur := lbt.Parent
+		for cur != nil {
+			cur.LockedDescendants--
+			cur = cur.Parent
+		}
+		return true
+	}
+	return false
+}
+
+func (lbt *LockableBinaryTree) canModify() bool {
+	if lbt.LockedDescendants > 0 {
+		return false
+	}
+	cur := lbt.Parent
+	for cur != nil {
+		if cur.IsLocked() {
+			return false
+		}
+		cur = cur.Parent
+	}
+	return true
+}


Test patch:
diff --git a/day24/problem_test.go b/day24/problem_test.go
new file mode 100644
index 0000000..913467a
--- /dev/null
+++ b/day24/problem_test.go
@@ -0,0 +1,60 @@
+package day24
+
+import "testing"
+
+func createSmallTree() []*LockableBinaryTree {
+	root := &LockableBinaryTree{}
+	left := &LockableBinaryTree{Parent: root}
+	right := &LockableBinaryTree{Parent: root}
+	root.Left = left
+	root.Right = right
+	return []*LockableBinaryTree{root, left, right}
+}
+
+func TestLockableBinaryTree(t *testing.T) {
+	t.Parallel()
+	nodes := createSmallTree()
+	if locked := nodes[2].Lock(); !locked {
+		t.Error("Should be able to lock this node")
+	}
+	if locked := nodes[0].Lock(); locked {
+		t.Error("Should be able not be lockable because a child is locked")
+	}
+	if locked := nodes[1].Lock(); !locked {
+		t.Error("Locking other side of subtree should work")
+	}
+	if unlocked := nodes[2].Unlock(); !unlocked {
+		t.Error("Should unlock")
+	}
+	if locked := nodes[0].Lock(); locked {
+		t.Error("Should be able not be lockable because a child is locked")
+	}
+	if unlocked := nodes[1].Unlock(); !unlocked {
+		t.Error("Should unlock")
+	}
+	if locked := nodes[0].Lock(); !locked {
+		t.Error("Now the root is locked")
+	}
+	if locked := nodes[1].Lock(); locked {
+		t.Error("If root is locked can't lock left child")
+	}
+	if locked := nodes[2].Lock(); locked {
+		t.Error("If root is locked can't lock right child")
+	}
+}
+
+func BenchmarkLockableBinaryTree(b *testing.B) {
+	nodes := createSmallTree()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		nodes[2].Lock()
+		nodes[0].Lock()
+		nodes[1].Lock()
+		nodes[2].Unlock()
+		nodes[0].Lock()
+		nodes[1].Unlock()
+		nodes[0].Lock()
+		nodes[1].Lock()
+		nodes[2].Lock()
+	}
+}