TJ Eastmond tjeastmond

BFS & DFS Notes

Links

Fundamentally a graph is a data structure which is characterized by nonlinearity for representing connections of vertices (or nodes) and edges. By definition:

A graph is a data structure which consists of a finite set of nodes (or vertices) with a set of edges connecting a pair of nodes (or vertices).

System Design Cheatsheet

Picking the right architecture = Picking the right battles + Managing trade-offs

Basic Steps

Clarify and agree on the scope of the system

User cases (description of sequences of events that, taken together, lead to a system doing something useful)
- Who is going to use it?
- How are they going to use it?

	/**
	* 10
	* / \
	* 4 17
	* / \ / \
	* 1 9 12 18
	* /
	* 22
	*/

	// reverse character array

	const reverse = arr => {
	if (arr.length === 1) return arr;
	let left = 0;
	let right = arr.length - 1;
	while (left < right) {
	[arr[left], arr[right]] = [arr[right], arr[left]];
	left++;
	right--;

	// quicksort

	const quicksort = (arr, left = 0, right = arr.length - 1) => {
	if (left >= right) return;
	const pivot = arr[Math.floor((left + right) / 2)];
	const index = partition(arr, left, right, pivot);
	quicksort(arr, left, index - 1);
	quicksort(arr, index, right);
	return arr;
	};

	/**
	* Simple mergesort exercise
	*/

	const mergeSort = unsortedArray => {
	if (unsortedArray.length <= 1) return unsortedArray;
	const middle = Math.floor(unsortedArray.length / 2);
	const left = unsortedArray.slice(0, middle);
	const right = unsortedArray.slice(middle);
	return merge(mergeSort(left), mergeSort(right));

	function getNames(person) {
	const names = [];
	names.push(person.name);
	person.children.forEach(child => names.push(...getNames(child)));
	return names;
	}

	const people = {
	name: "Robin",
	children: [

	function head() {
	console.log("HEAD");
	/* Some more logic that goes down here then will return function */

	return function body(arg) {
	console.log(arg);
	function inner() {
	console.log("INNER METHOD");
	}
	// return "SOMETHING USEFUL";

	var memoizer = function(memo, func) {
	var recur = function(n) {
	var result = memo[n];
	if (typeof result !== 'number') {
	result = func(recur, n);
	memo[n] = result;
	}
	return result;
	};
	return recur;

	function log(msg) {
	console.log(msg);
	}