YozhEzhi

Stack implementation using TypeScript

A stack is an abstract data type that stores a collection of elements, with two principal operations:

• push: adds an element to the collection
• pop: removes the most recently added element that was not yet removed. The order in which elements are poped is Last In First Out aka. LIFO. In this lesson we discuss how to implement it using JavaScript / TypeScript.

A stack is a Last in First out (LIFO) with key operations having a time complexity of O(1).

The objective is to implement these push and pop operations such that they operate in O(1) time. Fortunately in JavaScript implementations, array function that do not require any changes to the index of current items, have an average runtime of O(1).

YozhEzhi

What we're going to do is to approximate how these work underneath the hood; in reality since JavaScript is a garbage-collected language that you don't have worry about allocation and de-allocation, it is simplified.

ArrayList is done by directly interacting with an allocated piece of memory. You then interact with that allocated piece of memory by addressing the specific indices in the array. In other words, you just treat it like a normal array. However things get a bit more complicated when deleting items from an ArrayList: you have to collapse the list down to the spot where you deleted.

[a,b,c,d,e,f,g]

YozhEzhi

Работает только для отсортированных массивов.

function binarySearch(
  array,
  element,
  start = 0,
  end = array.length - 1,
) {
 if (end < start) return -1;

YozhEzhi

function repeatedItem {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) return array[i];
    }
  }
}

YozhEzhi

Merge sort is actually very useful and one of the easier divide-and-conquer algorithms to understand. It's easier to conceptualize than some of the other ones. A key to merge sort is that it is recursive.

The basic gist of merge sort is that you're going to take your big list, and first divide down in two half size lists and recursively call merge sort on those smaller list, which in turn will do the same.

The base case is when you have a list of one, at which point you will return that sorted list of one. On the way up the recursive calls, you will merge those sorted lists together (preferably by another merge function you'll write) that walks through both lists simultaneously and inserts the smaller value first, effectively creating a bigger sorted list.

YozhEzhi

Insertion sort is a step more complex but a bit more useful than bubble sort and is occasionally useful. The worst case scenario for it is similar to bubble sort's but its best case makes it suited for times when you're pretty sure a list almost sorted or likely already sorted.

We're going to start at the beginning of the list and assume we have a sorted list of length 1 where the first element is only sorted element. We're then going to grab the second element, and insert it into the correct spot in our sorted list, either the 0 index or the 1 index, depending if it's smaller or larger than our first element. We now have a sorted list of length 2. We then continue on down the line, inserting elements in our sorted side of the list as the unsorted side dwindles.

YozhEzhi

Quicksort is one of the most useful and powerful sorting algorithms out there, and it's not terribly difficult to conceptualize (compared to some algorithms we're not talking about anyway.) Above I mentioned that occasionally JavaScript doesn't mergesort for Array.prototype.sort. In those other cases, it's usually some variant on quicksort.

It's another divide-and-conquer, recursive algorithm but it takes a slightly different approach. The basic gist is that you take the last element in the list and call that the pivot. Everything that's smaller than the pivot gets put into a "left" list and everything that's greater get's put in a "right" list. You then call quick sort on the left and right lists independently (hence the recursion). After those two sorts come back, you concatenate the sorted left list, the pivot, and then the right list (in that order). The base case is when you have a list of length 1 or 0, where you just return the list given to you.

YozhEzhi

In bubble sort, we're going to loop through the array and compare each index with the index next to it. If the those two numbers are out of order (the lesser index's value is greater than the greater index's value) we swap those two numbers' places in the array. We keep looping over that array until everything is in place and nothing was swapped during the last iteration.

What's the Big O on this? Well, there's an inner loop to check to see if indexes need to be swapped, and an outer loop that's just checking to see if anything was swapped. That would be make it O(n²). Not efficient, but a great learning tool. You'll never use bubble sort for anything serious.

YozhEzhi

/**
 * A palindrome is a string that reads the same forward and backward.
 */
function isPalindrome (str) {
  return str === str.split('').reverse().join('');
}

/**
 * A more complex algorithmic challenge commonly presented
 * after isPalindrome, is to write a function to check if any

YozhEzhi

/**
 * A word is an anagram of another if you can rearrange its characters to
 * produce the second word.
 * Given two strings determine if they are anagrams of each other.
 * - 'earth' and 'heart' are anagrams
 * - 'silent' and 'listen' are anagrams
 * - 'foo' and 'bar' are not anagrams
 */
// Complexity: O(n * Logn).
function areAnagrams(s1, s2) {