subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 219 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts b/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts
new file mode 100644
index 000000000000..4c5e57607d87
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts
@@ -0,0 +1,219 @@
+/*******************************************************************************
+ * Setup
+ ******************************************************************************/
+
+interface BinaryTreeNode {
+  value: number;
+  left: BinaryTreeNode;
+  right: BinaryTreeNode;
+}
+
+class BinaryTreeNode {
+  constructor(value: number) {
+    this.value = value;
+    this.left  = null;
+    this.right = null;
+  }
+
+  insertLeft(value: number): BinaryTreeNode {
+    this.left = new BinaryTreeNode(value);
+    return this.left;
+  }
+
+  insertRight(value: number): BinaryTreeNode {
+    this.right = new BinaryTreeNode(value);
+    return this.right;
+  }
+}
+
+/*******************************************************************************
+ * First solution
+ ******************************************************************************/
+
+/**
+ * I first solved this problem using O(n) space and O(n*log(n))
+ * time. InterviewCake informs me that we can improve both the time and the
+ * space performance.
+ */
+function findSecondLargest_first(node: BinaryTreeNode): number {
+  const stack: Array<BinaryTreeNode> = [];
+  const xs: Array<number> = [];
+  stack.push(node);
+
+  while (stack.length > 0) {
+    const node = stack.pop()
+
+    xs.push(node.value);
+
+    if (node.left) {
+      stack.push(node.left);
+    }
+    if (node.right) {
+      stack.push(node.right);
+    }
+  }
+
+  xs.sort();
+
+  if (xs.length < 2) {
+    throw new Error('Cannot find the second largest element in a BST with fewer than two elements.');
+  } else {
+    return xs[xs.length - 2];
+  }
+}
+
+/*******************************************************************************
+ * Second solution
+ ******************************************************************************/
+
+/**
+ * My second solution accumulates a list of the values in the tree using an
+ * in-order traversal. This reduces the runtime costs from O(n*log(n)) from the
+ * previous solution to O(n). The memory cost is still O(n), which InterviewCake
+ * informs me can be reduced to O(1).
+ */
+function findSecondLargest_second(node: BinaryTreeNode): number {
+  const xs: Array<number> = accumulateInorder(node);
+
+  if (xs.length < 2) {
+    throw new Error('Cannot find the second largest element in a BST with fewer than two elements.');
+  } else {
+    return xs[xs.length - 2];
+  }
+}
+
+/**
+ * Returns an array containing the values of the tree, `node`, sorted in-order
+ * (i.e. from smallest-to-largest).
+ */
+function accumulateInorder(node: BinaryTreeNode): Array<number> {
+  let result = [];
+
+  if (node.left) {
+    result = result.concat(accumulateInorder(node.left));
+  }
+  result.push(node.value)
+  if (node.right) {
+    result = result.concat(accumulateInorder(node.right));
+  }
+
+  return result;
+}
+
+/*******************************************************************************
+ * Third solution
+ ******************************************************************************/
+
+/**
+ * Returns the largest number in a BST.
+ */
+function findLargest(node: BinaryTreeNode): number {
+  let curr: BinaryTreeNode = node;
+
+  while (curr.right) {
+    curr = curr.right;
+  }
+
+  return curr.value;
+}
+
+/**
+ * Returns the second largest number in a BST
+ */
+function findSecondLargest(node: BinaryTreeNode): number {
+  let curr = node;
+  let parent = null;
+
+  while (curr.right) {
+    parent = curr;
+    curr = curr.right
+  }
+
+  if (curr.left) {
+    return findLargest(curr.left);
+  }
+  else {
+    return parent.value;
+  }
+}
+
+
+// Tests
+let desc = 'full tree';
+let treeRoot = new BinaryTreeNode(50);
+let leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+let rightNode = treeRoot.insertRight(70);
+rightNode.insertLeft(60);
+rightNode.insertRight(80);
+assertEquals(findSecondLargest(treeRoot), 70, desc);
+
+desc = 'largest has a left child';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+rightNode.insertLeft(60);
+assertEquals(findSecondLargest(treeRoot), 60, desc);
+
+desc = 'largest has a left subtree';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+leftNode = rightNode.insertLeft(60);
+leftNode.insertRight(65);
+leftNode = leftNode.insertLeft(55);
+leftNode.insertRight(58);
+assertEquals(findSecondLargest(treeRoot), 65, desc);
+
+desc = 'second largest is root node';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+assertEquals(findSecondLargest(treeRoot), 50, desc);
+
+desc = 'descending linked list';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(40);
+leftNode = leftNode.insertLeft(30);
+leftNode = leftNode.insertLeft(20);
+leftNode = leftNode.insertLeft(10);
+assertEquals(findSecondLargest(treeRoot), 40, desc);
+
+desc = 'ascending linked list';
+treeRoot = new BinaryTreeNode(50);
+rightNode = treeRoot.insertRight(60);
+rightNode = rightNode.insertRight(70);
+rightNode = rightNode.insertRight(80);
+assertEquals(findSecondLargest(treeRoot), 70, desc);
+
+desc = 'one node tree';
+treeRoot = new BinaryTreeNode(50);
+assertThrowsError(() => findSecondLargest(treeRoot), desc);
+
+desc = 'when tree is empty';
+treeRoot = null;
+assertThrowsError(() => findSecondLargest(treeRoot), desc);
+
+function assertEquals(a, b, desc) {
+  if (a === b) {
+    console.log(`${desc} ... PASS`);
+  } else {
+    console.log(`${desc} ... FAIL: ${a} != ${b}`)
+  }
+}
+
+function assertThrowsError(func, desc) {
+  try {
+    func();
+    console.log(`${desc} ... FAIL`);
+  } catch (e) {
+    console.log(`${desc} ... PASS`);
+  }
+}