AlexeiDarmin

/*
Developer notes:
Written in Typescript.

I chose to use an iterative approach because it's able to handle more data than a recursive approach
before hitting a stackoverfow error.

This algorithm runs in O(N) time and O(N) space, while avoiding cycles without actively searching for them. 
Actively checking for cycles would make the time compexity O(NlogN).

AlexeiDarmin

// Valiate binary tree: Implement a function to validate that a binary tree is a binary search tree.

function validateBST<T>(node: BinaryNode<T>) {
  if (!node) return true
  if (node.leftChild && node.leftChild.data > node.data) return false
  if (node.rightChild && node.rightChild.data < node.data) return false
  return validateBST(node.leftChild) && validateBST(node.rightChild)
}

AlexeiDarmin

/*
Check balanced: Implement a function to check if a binary tree is balanced. For the purposes of 
this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any
node never differ by more than one.
*/

// const myTree = buildTree([1,2,3,4,5,6,7,8, 9, 10, 11, 12, 13, 14])
const myTree = new BinaryNode(1)
myTree.rightChild = new BinaryNode(2)
myTree.rightChild.rightChild = new BinaryNode(3)

AlexeiDarmin

/*
  List of depths: Given a binary tree, design an algorithm which creates a linked list of all the nodes
  at each depth (eg if you have a tree with depth D, you'll have D linked lists.)

*/

interface DepthQueue<T> {
  depth: number,
  node: T
}

AlexeiDarmin

// given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minial height.
class BinaryNode<T> {
  data: T
  leftChild: BinaryNode<T>
  rightChild: BinaryNode<T>

  constructor(data: T) {
    this.data = data
  }

AlexeiDarmin

function hasPath<T>(n1: GraphNode<T>, n2: GraphNode<T>): boolean {
  const visitedByN1 = new Map()
  const visitedByN2 = new Map()

  let children1: GraphNode<T>[] = n1.children
  let children2: GraphNode<T>[] = n2.children

  while (children1.length > 0 || children2.length > 0) {
    let output = searchChildren(children1, visitedByN1, n2)

AlexeiDarmin

/*
Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack 
but you may not copy the elements into any other data structure such as an array. The stack supports the following
operations: push, pop, peek, and isEmpty.
*/

function sortStack<T>(mainStack: MyStack<T>): MyStack<T> {
  const tempStack = new MyStack<T>()
  while (!mainStack.isEmpty()) {

AlexeiDarmin

class MyNewQueue<T> {
  mainStack: MyStack<T>
  tempStack: MyStack<T>

  constructor(value: T) {
    this.mainStack = new MyStack()
    this.tempStack = new MyStack()

    this.mainStack.push(value)

AlexeiDarmin

/*
  Stack of plates: Imagine a literal stack of plates. If the stack gets too high, it might topple.
  Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.
  Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and 
  should create a new stack once the previous one exceeds capacity.
  
  SetOfStacks.push() and SetfStacks.pop() should behave identically to a single stack
  That is pop should return the same valeues as it would if there were just a single stack.
*/

AlexeiDarmin

/*
How would you design a stack which in addition to push and pop has a function min which returns
the minimum element. Push pop and min should all operate in O(1) time.
*/


class Node<T> {
  data: T
  next: Node<T>