mergeSort

Mergesort is an optimized sorting algorithm which is a common choice to implement `sort` methods in standard libraries as an alternative to quicksort or heapsort.

Mergesort uses a divide-and-conquer strategy. It begins by treating the input list of length N as a set of N “sublists” of length 1, which are considered to be sorted. Adjacent sublists are then “merged” into sorted sublists of length 2, which are merged into sorted sublists of length 4, and so on, until only a single sorted list remains. (Note, if N is odd, an extra sublist of length 1 will be left after the first merge, and so on.)

Time complexity: The entire input must be iterated through n, and you’re narrowing the workload by half every time you merge so n * logn = O(nlogn).

  1. Split array in halfScreen Shot 2018-01-09 at 9.10.16 AM
  2. Recursively sort each half
  3. Merge sorted arrays into larger sorted arrayScreen Shot 2018-01-09 at 9.11.20 AM.png

This can be implemented using either a recursive (“top-down”) or an iterative (“bottom-up”) approach.

Recursive Solution:

var mergeSort = function(array) {
  if (array.length < 2) {      
    return array;   
  }   

  var mid = Math.floor(array.length / 2);   
  var left = array.slice(0, mid);   
  var right = array.slice(mid);   
  return merge(mergeSort(left), mergeSort(right)); 
}; 

var merge = function (left, right) {   
  var output = [];   
  var i = 0;    
  var j = 0;   

while (left.length > i && right.length > j) {
    if (left[i] < right[j]) {
      output.push(left[i]);
      i++;
    } else{
      output.push(right[j]);
      j++;
    }
  }

  return output.concat(left.slice(i)).concat(right.slice(j));
}

 

mergeSort

How to deploy on Heroku

  1. heroku create
  2. create any config variables (PORT, TOKEN, ACCESS KEYS, etc.)
  3. set up web version of your database (e.g. mlab for mongodb)
  4. Edit package.json file
    • move any devDependencies to dependencies
    • add any necessary scripts

    Screen Shot 2018-01-08 at 11.12.22 PM

  5. Modify code to account for both production and development.Screen Shot 2018-01-08 at 11.10.55 PM
  6. git add/commit
  7. git push heroku master
  8. heroku logs to debug

 

How to deploy on Heroku

Authentication

Authentication is used by a server when the server needs to know exactly who is accessing their information or site.

The evolution of authentication:

Screen Shot 2018-01-01 at 10.15.44 PMScreen Shot 2018-01-01 at 10.15.52 PMScreen Shot 2018-01-01 at 10.15.59 PM

Screen Shot 2018-01-01 at 10.16.43 PM
Encryption: a reversible transformation of text into an alternative representation.
Screen Shot 2018-01-01 at 10.17.54 PM
Hashing: a version of encryption that is irreversible and destroys some of the information instead of just obfuscating it.

Screen Shot 2018-01-01 at 10.19.02 PM

Salt: a set of pseudorandom information which is added to a password before it is hashed.  Adding salt to a password significantly increases data set’s resistance to rainbow tables.

Rainbow table: a precomputed table generated from commonly-used password patterns using known hashing algorithms. It is used to reverse cryptographic hash functions, usually for cracking password hashes.  Hackers can compare hashed passwords to those known hashed values in the table to decode passwords.

Tokens: externally encrypted piece of information, and can be used in place of a username and a password to authenticate a user.

  • A token is delivered to a client via a cookie immediately after successful authentication and the server later uses the token to identify and authenticate the user.

Cookies:  Small pieces of text stored on a user’s computer by their client/browser. Common uses for cookies are authentication, storing of site preferences, shopping cart items, and server session identification.  All cookies for a given host are transmitted back to the server on every subsequent request.

Sessions: A server-side storage of information that is desired to persist throughout the user’s interaction with the web site or web application.  Sessions are tokens with an expiration date.

* You either want to use a token or a session, but not both.  

Authentication

HTTP Transaction

Host: Computers connected to a network are often called ‘hosts’, regardless if they’re hosting a service or not.

  • A single host can have many services running.
  • Client and server can be on the same computer/host (e.g. when you’re building a small application). However, most often, they are on different hosts.

Server: a computer or computer program that manages access to a centralized resource or service in a network.  The server can refer to the host computer itself or the service running on the host computer.  Servers are often classified by the services they provide (e.g. web server).

  • Servers provide services to many clients.
  • Servers communicate with other servers to handle aspects of those client requests they don’t provide.  This is referred to as inter-server or server-to-server communication.
  • A server has one IP address and multiple ports.

Client: can refer to a software or a device that accesses a service made available by a server.  If the server is on another host, the client accesses it via a network.

HTTP transaction:  When a client or browser makes a single request for HTTP content, the followings happen:

  1. DNS Lookup: Client sends DNS query to local ISP DNS server and DNS sever responds with the IP address for the requested website (eg. google.com).
  2. Client establishes TCP connection with google.com’s IP address.
  3. Client sends HTTP request to google’s web server.
    • HTTP requests are made via REST methods: GET, POST, PUT, DELETE, OPTIONS, HEAD.
  4. Server processes the request, finds the resource, and sends the response to client.
  5. Client formats the response and displays it on the browser.
  6. Client closes or reuses the connection for further request.

HTTP Header:  contains additional info about the client browser, the requested page, and the server, etc.

HTTP Body: contains either the resource sent (in a POST request) or the resource fetched (in a POST response).

Screen Shot 2018-01-01 at 9.52.41 PM.png
Example of an HTTP Request
Screen Shot 2018-01-01 at 9.55.57 PM.png
Example of an HTTP Response

 

Routing: parses the url received by a server to identify and trigger target behavior requested by user via that url.

Screen Shot 2018-01-01 at 9.36.40 PM

Workers: background jobs that run behind the scenes.

  • daemon: OS processes that handle background jobs.  They’re basically servers for OS requests.
  • Cron: a daemon that schedules OS jobs or workers.

 

HTTP Transaction

Data Storage & Databases

Serving static pages for users can be suitable for landing pages, or for personal blogs. However, if you want to deliver personalized content you have to store the data somewhere, and there are two ways to do that:

Volatile/Temporary Memory (RAM):

  • Extremely fast but expensive.
  • Memory resets each time you restart your application so data is not retained.
  • If you don’t clean up, you can end up with stack overflow.
  • Variables are stored in RAM.

Non-volatile/Permanent Memory (hard drive): 

  • Slow but inexpensive.
  • Data has to be serialized, or translated, into a format that can be stored or transmitted and reconstructed later.   An example of serialization is JSON.stringify() and JSON.parse().
  • Data persistence is achieved by saving a program state in non-volatile memory because data is retained when you restart your application.
  • There are two ways to store data in your hard drive:
    • Database:
      • A giant excel sheet that you can add, remove, or update data that you want to persist.
      • You would not want to store large data such as asset files  in the database.
    • File System (fs):
      • Assets like images and videos are usually stored in your file system (and referenced from your database).
      • Your file system is stored in your hard drive along with your database (if you have one).

DATABASES:

noSQL:

  • use ID index to achieve O(1)
  • records are stored in JSON and need to be parsed to find particular field.
  • You don’t have to define a schema and you can store any arbitrary JSON.
  • Example: PostgresSQL

SQL:

  • use array-like techniques (fixed width data format) to achieve O(1)
  • Have to define schemas.
  • faster at computing relationships because
    • it can skip ID indexing step (ID -> Disk Location).
    • records are stored in binary format (not JSON) and fields are always in the same location in every record.
  • Example: mongoDB

Screen Shot 2017-12-22 at 10.51.08 AM.png

ORM: softwares such as Sequelize that provide Javascript-like syntax for interaction with databases.

Schemas:  description of the way data is organized in a database.

  • PRIMARY KEY:  A column with primary key means the value of the column is unique.  Primary keys from one tables are often referred to in other tables.
  • FOREIGN KEY: When the value of a column is intended to refer to a column in another table, it is called a foreign key.

Screen Shot 2017-12-22 at 11.14.19 AM

By referring to data in columns of other tables rather than duplicating the data in two tables, it’s more memory efficient.

SCHEMA & QUERY DESIGN 

join table: breaks many-to-many relationship into one-to-many relationships.

 

Data Storage & Databases

Asynchronous Code & Promises

Node.js is a cross-platform runtime environment and a library for running Javascript applications outside of the browser.  It uses non-blocking I/O and asynchronous events to create a highly performance environment built on Google’s V8 engine.

The engine is consisted of the memory heap (where memory allocations happen) and the call stack (where the stack frames are as code executes).

Asynchronous callbacks–allow us to execute heavy code without blocking the UI and making the browser unresponsive.

You can execute any chunk of code asynchronously by using setTimeout(callback, milliseconds).  setTimeout doesn’t automatically put your callback on the event loop queue.  It sets up a timer, and when that timer expires, your callback will enter the event loop to be executed.

The event loop is a special queue for asynchronous callbacks.  Its job is to monitor the call stack and the callback queue.  If the call stack is empty, it will take the first event from the callback queue and push it to the call stack, which effectively runs it.

Below is an awesome gif showing this process of queueing up asynchronous callbacks and executing them.

asyncPromises are the solution to callback hell.

  • It is an object that may produce a single value some time in the future: either a resolved value, or a reason that it’s rejected.
  • A promise may be in one of the 3 possible states: fulfilled, rejected, or pending.
  • All promise instances get a then method which allows you to react to the promise.  then method callbacks  can also be chained.
  • The catch callback is executed when the promise is rejected.

Screen Shot 2018-01-01 at 8.09.19 PM

Sources:

Asynchronous Code & Promises

Backbone.js

Backbone is a lightweight MVC framework primarily used for developing single-page web applications.  It relies only on underscore.js and jQuery, making it smaller in size than most frameworks and libraries.

Model—contains the business logic, validations, and data storage for an application.  It manages an internal table of data attributes, and triggers "change" events when any of its data is modified.

Screen Shot 2017-12-18 at 8.41.31 AM

Collection—an ordered set of models which can bind to events whenever a model in the collection is modified. Like an individual model, a collection fires events whenever a change occurs. Whenever a model is added or removed from a collection a change event is fired.

Screen Shot 2017-12-18 at 8.40.48 AMView

View—Each view manages the rendering and user interaction within its own DOM element. If you’re strict about not allowing views to reach outside of themselves, it helps keep your interface flexible — allowing views to be rendered in isolation in any place where they might be needed.

Screen Shot 2017-12-18 at 8.43.26 AM

Event—a module that can be mixed into any object, giving it the ability to bind and trigger custom named events like user clicks or mouse overs.  Events do not have to be declared before they are bound, and may take passed arguments.

Screen Shot 2017-12-18 at 8.48.18 AM

 

Resources: 

Backbone.js

ReactJS

ReactJS is a Javascript library that is built on the premise of declarative and reusable components.  It’s the view layer in MVC and can be used with other frameworks or libraries to build applications.

  • one-way data binding: example – when you type in an input field, it doesn’t directly change the state of that component.  Instead, it updates the data model, which causes the UI to be updated.
  • virtual DOM: A virtual representation of the real DOM that React uses to intelligently re-render each component.  Each time the data changes in the app, a new Virtual DOM  is created, and the differences between the new Virtual DOM and the previous Virtual DOM will be updated in the real DOM.  Read more.
  • JSX:  XML/HTML-like syntax used by React that extends ECMAScript so that XML/HTML-like text can co-exist with JavaScript/React code.  (use Babel to transpile JSX and ES6 into Javascript).  JSX expressions are shorthand for ‘React.createElement’.

Components: 

  • A React app is a tree of nested components.
  • Props and state control each component.
  • Components must implement render.
  • Use class components for stateful components.

Screen Shot 2017-12-16 at 5.05.59 PM

  • Don’t use class for stateless components.

Screen Shot 2017-12-16 at 5.07.12 PM

Events: 

  • Events are created inside components and are added to their corresponding render function.  (e.g. onListItemHover event above).

Props:

  • Props contain information set by the parent component and can be passed to the child component(s). It’s the equivalent of $scope in Angular).
  • When a component is rendered, it can access its props using this.props.
  • Props are immutable.

State:

  • State is what makes your app interactive.
  • In general, you should initialize state in the constructor, and then call setState when you want to change it.
  • State is mutable.
  • State should be held at the top-most component that needs access to it.
  • Components manage their own state.
  • Initial values can be set for state.
  • State can be passed from parent components to child components as props.
    • Example:  Component A is parent of Component B.  When component B is clicked on, it updates state on component A.  In order for this to happen:
      1. Define a function that updates state on component A.
      2. Pass the function as a prop to component B.
      3. Invoke the function when B is clicked on.

Lifecycle Methods:

React components have a lifecycle, and you’re able to access specific phases of that lifecycle to update certain parts of each component.

  • Component creation: 
    • componentWillMount: called before the render method is executed.
    • componentDidMount: called after render method is executed.
      • example: You’re creating an application that streams music from the SoundCloud API as soon as a client connects to your website.  You would use componentDidMount to make that Ajax request to SoundCloud to ensure you have the song data you need once the application renders.
  • State changes:
    • shouldComponentUpdate
    • componentWillUpdate
    • componentDidUpdate

Read more.

ReactJS

Angular

Angular is an MVW (model-view-whatever) framework for properly architected single-page applications.   It’s opinionated, declarative, has two-way binding, and allows separation of presentation and business logic.

Angular 1 and 2 are quite different.

Modules:

Module are top-level containers for different parts of the application.

Controllers:

  • Controllers build logic for a particular view
  • Controllers configure and manage the $scope object.
  • Controllers make your components stateful.  Without controllers, your component is stateless.

Screen Shot 2017-12-15 at 10.46.47 AM

In example above, controller is not part of a component so to access the attributes, you have to use $scope.  If the controller is within a component, you have to use ‘this’ (and $ctrl in template). 

Scope: 

  • In Angular 1, you access scope using $scope.
  • In Angular 2, you access scope using this (because $scope and controllers don’t exist) and $ctrl.  (It’s similar to props in React)

Factories/Services:

  • Factories and services are objects that you can register with Angular so their data and behavior can be shared among different parts of the app. (e.g. registering an API with Angular so it can be accessed everywhere in the app)
  • The main difference between factories and services is that services are instantiated with the ‘new’ keyword so you do not need to return the object.
  • Services allow the use of ES6 classes because they are constructor functions.

Components:

Angular 1.x uses components but Angular 2 is entirely component-based.

  • In a component, there is always a template, which is used to render your view.
  • If you’re passing data from or to a component, use data binding.
    • When using binding, specify what you want the attribute to be treated as:
      • ‘@’ : strings
      • ‘<‘ :  one-way binding. Used to pass variables down.
      • ‘=’:  two-way binding.  Not very common.
      • ‘&’: methods or functions
  • Use ‘this’ keyword to access scope within controller in component.

Screen Shot 2017-12-15 at 12.14.01 PM

Screen Shot 2017-12-15 at 12.27.25 PM

data binding is used above to pass the ‘item’ variable from ‘todoList’ component to ‘entry’ subcomponent.

Directives:

Directives supercharge your HTML by giving it angular power!

There are four categories of directives:

  1. attribute (most commonly used)
  2. class name
  3. comment
  4. element (components are basically element directives)

Filters: 

Angular offers filters that make your app dynamic.  Some filters include: JSON, uppercase, lowercase, etc.

Syntax: 

  • built-in directives are prefixed with ‘ng’ in Angular 1.  (e.g. ng-click).  No ‘ng’ in Angular 2.
  • To present something to a user, use double curly braces {{ }}
  • When you want something to be invoked by Angular, use double quotes.

AngularJS Resources:

 

 

Angular

Rock Paper Scissors

To solve this problem recursively, think of the game as a tree and you want to traverse all possible solutions depth-first.  That means going all the way down one branch first before moving back up to evaluate the previous level(s).

Screen Shot 2017-12-10 at 6.19.47 PM

Recursive Solution:

var rockPaperScissors = function(n) {
  var output = [];
  var choices = ['rock', 'paper', 'scissors'];
  n = n || 3;

  var makeCombo = function(movesPlayed, roundsLeft) {
    if (roundsLeft === 0){
      output.push(movesPlayed);
    } else {
       for (var i = 0; i < choices.length; i++) {
         makeCombo(movesPlayed.concat(choices[i]), roundsLeft - 1);
       }
    }
  }
  makeCombo([], n);
  return output;
};

 

Order of execution: 

1. makeCombo([], 3)
2. makeCombo([‘rock’], 2);
3. makeCombo([‘rock rock’], 1);
4. makeCombo([‘rock paper’], 1);
5. makeCombo([‘rock scissors’], 1);
6. makeCombo([‘rock rock rock’], 0);
7. push [‘rock rock rock’] to output
8. makeCombo([‘rock rock paper’], 0);
9. push [‘rock rock paper’] to output
10. makeCombo([‘rock rock scissors’], 0);
11. push [‘rock rock scissors’] to output

12. makeCombo([‘paper’], 2);

..

…. makeCombo([‘scissors’], 2);

 

 

 

Rock Paper Scissors