This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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). |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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()) { |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class MyNewQueue<T> { | |
mainStack: MyStack<T> | |
tempStack: MyStack<T> | |
constructor(value: T) { | |
this.mainStack = new MyStack() | |
this.tempStack = new MyStack() | |
this.mainStack.push(value) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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. | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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> |
NewerOlder