ThuyNT13

/*
First calculate the hash of first *n* letter substring (abcd) in string. 
  
Iterate through string, starting at index of next (= pattern length): 
  subString = (first + subSubstring) + next
  
  1. drop a (first)
    (a*7^0 + b*7^1 + c*7^2 + d*7^3) - a*7^0
  2. divide everything by 7
    (b*7^1 + c*7^2 + d*7^3) / 7 => b*7^0 + c*7^1 + d*7^2

ThuyNT13

Thùy T. Ngô

(562) 308-8091  |  thuy@thuy.life  |  Website  |  GitHub  |  LinkedIn

---

SKILLS & TOOLS

Languages:   Ruby, JavaScript, Java, SQL, HTML, CSS, Bash

ThuyNT13

What are linked lists?

Linked lists are a way to store sequential data. A linked list is made up of one or more list nodes that contain the data and a link or pointer to the next node in the sequence. We call the start of the linked list the head and the end of the linked list the tail.

Image from: https://www.tutorialspoint.com/data_structures_algorithms/linked_lists_algorithm.htm

Why would we use a linked list?

• Constant time insertions/deletions
• Easily expandable

ThuyNT13

Big O notation is a way for us to describe how long it takes for an algorithm to run. We can use Big O notation to compare how efficient different approaches to solving a problem are. In big O notation we describe the runtime of an algorithm in terms of how quickly the runtime grows as the input to the algorithm gets very, very large. Let’s break down the definition a bit:

• How quickly the runtime grows:

  • We can’t give an exact amount of time that an algorithm will run for because it depends on too many things. Is it running on a supercomputer, a really old desktop, or a calculator? Which language is it written in? Is the computer running anything else at the same time? All of these can affect the runtime, so we remove these variables by focusing on how the runtime grows.

• Based on the input:

• Since we are removing runtime from the description we need another way to express the speed - we can’t use seconds anymore. Instead we’ll use the size of the input to describe it. We will use