mtroiani

Trees

What are Trees?

Trees are a type of data structure consisting of nodes and links to other nodes. Each tree starts with a node called the root node. This node has zero or more child nodes which in turn may also have zero or more child nodes. From this we can see that trees can be thought of as recursive data structures - each node can be thought of as its own tree. Furthermore, trees cannot have cycles - that is, a child node cannot link back to its parent (or any other ancestor), and nodes can have exactly one parent node. In general nodes can have any number of child nodes, but for our discussion we'll focus on a binary tree or a tree where nodes can have at most 2 children.

Source: Wikipedia

We often work with trees by defining a tree node class, conta

mtroiani

Arrays (and Strings)

What are arrays?

Arrays are a data structure that hold an ordered collection of items. Each spot in the array has an index which (generally) starts at 0. In some languages, such as C or Java, you must declare how long the array will be when you create it. If you need to increase the size of the array you'd need to declare a new one and move over the old items. In other languages, such as Python, the data structure will automatically resize itself - these are called resizing ararys. Arrays are handy because they have constant time lookup and insertion on average. This is because the contents of the array are stored contiguously in memory, so during lookup the computer just need to do a bit of math to find the index you're looking for.

For example, if your array started at memory location 100 and you were looking up index 3, your computer would just have to add the index to the memory location to find the correct location in memory.

Memory | Index | Data --- | --- | __

mtroiani

Recursion and DP

What is Recursion?

Recursion is just something that is defined in terms of itself. Applied to computer science, it's a function that calls itself within the function. Then how do we prevent an infinite loop? Well, we used two different types of cases in a recursive function:

• A base case - this is a scenario that doesn't use recursion to arrive at an answer
• A rule that reduces all other cases towards the base case

Let's take a look at an example - the Fibonacci numbers: Here are the first few Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21... We can calculate a Fibonacci number n > 1, by adding the Fibonacci number n - 1 and n - 2. The Fibonacci number 0 is 0, and the Fibonacci number 1 is 1. Let's break this down into a recursive function.

mtroiani

Hashmaps and Hashsets

What are hashmaps?

Hashmaps are a way to store key/value pairs with a fast (O(1) on average) lookup time.

We commonly use arrays for constant time lookups, but hashmaps give us more flexability as to what we can store. For example, you may have used an array's index to 'map' to character values:

Let's count the number of times each character appears: "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vivamus sed posuere nunc, sit amet blandit felis. Ut non orci eget."

Index | Data |

mtroiani

// Bonfire: Seek and Destroy
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-seek-and-destroy
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function destroyer(arr) {
  var args = Array.prototype.slice.call(arguments);
  args.splice(0, 1);
  arr = arr.filter(function(n) {
        return args.indexOf(n) === -1;

mtroiani

// Bonfire: Where do I belong
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-where-do-i-belong
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function where(arr, num) {
  arr.push(num);
  arr = arr.sort(function(a, b) {
    return a - b; 
  });

mtroiani

// Bonfire: Falsy Bouncer
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-falsy-bouncer
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function bouncer(arr) {
  function bounce(id) {
    return Boolean(id);
  }
  var theList = arr.filter(bounce);

mtroiani

// Bonfire: Mutations
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-mutations
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function mutation(arr) {
  var target = arr[0];
  target = target.toLowerCase().split('');
  var test = arr[1];
  test = test.toLowerCase().split('');

mtroiani

// Bonfire: Slasher flick
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-slasher-flick
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function slasher(arr, howMany) {
  return arr.splice(howMany, arr.length);
}

slasher([1, 2, 3], 2);

mtroiani

// Bonfire: Chunky Monkey
// Author: @mtroiani
// Challenge: http://www.freecodecamp.com/challenges/bonfire-chunky-monkey
// Learn to Code at Free Code Camp (www.freecodecamp.com)

function chunk(arr, size) {
  var chunkedArr = [];
  var n = 0;
  for (var i = 0; i < arr.length; i += size) {
    chunkedArr.push(arr.slice(i, i + size));