DEV Community: Bryan C Guner

Disorganized List Of Everything A New Web Developer Needs To Know

Bryan C Guner — Tue, 05 Apr 2022 16:05:19 +0000

Tree Data Structure 🌲🌴🌳🎋

Bryan C Guner — Wed, 16 Feb 2022 18:21:32 +0000

The Tree data structure (In Javascript)

The #data-structures series is a collection of posts about reimplemented data structures in JavaScript.

Definition

A Tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root node. From Wikipedia

Complexity

Average
Access	Search	Insertion	Deletion
O(n)	O(n)	O(n)	O(n)

To get a full overview of the time and space complexity of the Tree data structure, have a look to this excellent Big O cheat sheet.

The code

function Node(data) {
  this.data = data;
  this.children = [];
}

function Tree() {
  this.root = null;
}

Tree.prototype.add = function(data, toNodeData) {
  var node = new Node(data);
  var parent = toNodeData ? this.findBFS(toNodeData) : null;
  if(parent) {
    parent.children.push(node);
  } else {
    if(!this.root) {
      this.root = node;
    } else {
      return 'Root node is already assigned';
    }
  }
};
Tree.prototype.remove = function(data) {
  if(this.root.data === data) {
    this.root = null;
  }

  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    for(var i = 0; i < node.children.length; i++) {
      if(node.children[i].data === data) {
        node.children.splice(i, 1);
      } else {
        queue.push(node.children[i]);
      }
    }
  }
};
Tree.prototype.contains = function(data) {
  return this.findBFS(data) ? true : false;
};
Tree.prototype.findBFS = function(data) {
  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    if(node.data === data) {
      return node;
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  return null;
};
Tree.prototype._preOrder = function(node, fn) {
  if(node) {
    if(fn) {
      fn(node);
    }
    for(var i = 0; i < node.children.length; i++) {
      this._preOrder(node.children[i], fn);
    }
  }
};
Tree.prototype._postOrder = function(node, fn) {
  if(node) {
    for(var i = 0; i < node.children.length; i++) {
      this._postOrder(node.children[i], fn);
    }
    if(fn) {
      fn(node);
    }
  }
};
Tree.prototype.traverseDFS = function(fn, method) {
  var current = this.root;
  if(method) {
    this['_' + method](current, fn);
  } else {
    this._preOrder(current, fn);
  }
};
Tree.prototype.traverseBFS = function(fn) {
  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    if(fn) {
      fn(node);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
};
Tree.prototype.print = function() {
  if(!this.root) {
    return console.log('No root node found');
  }
  var newline = new Node('|');
  var queue = [this.root, newline];
  var string = '';
  while(queue.length) {
    var node = queue.shift();
    string += node.data.toString() + ' ';
    if(node === newline && queue.length) {
      queue.push(newline);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  console.log(string.slice(0, -2).trim());
};
Tree.prototype.printByLevel = function() {
  if(!this.root) {
    return console.log('No root node found');
  }
  var newline = new Node('\n');
  var queue = [this.root, newline];
  var string = '';
  while(queue.length) {
    var node = queue.shift();
    string += node.data.toString() + (node.data !== '\n' ? ' ' : '');
    if(node === newline && queue.length) {
      queue.push(newline);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  console.log(string.trim());
};

var tree = new Tree();
tree.add('ceo');
tree.add('cto', 'ceo');
tree.add('dev1', 'cto');
tree.add('dev2', 'cto');
tree.add('dev3', 'cto');
tree.add('cfo', 'ceo');
tree.add('accountant', 'cfo');
tree.add('cmo', 'ceo');
tree.print(); // => ceo | cto cfo cmo | dev1 dev2 dev3 accountant
tree.printByLevel();  // => ceo \n cto cfo cmo \n dev1 dev2 dev3 accountant
console.log('tree contains dev1 is true:', tree.contains('dev1')); // => true
console.log('tree contains dev4 is false:', tree.contains('dev4')); // => false
console.log('--- BFS');
tree.traverseBFS(function(node) { console.log(node.data); }); // => ceo cto cfo cmo dev1 dev2 dev3 accountant
console.log('--- DFS preOrder');
tree.traverseDFS(function(node) { console.log(node.data); }, 'preOrder'); // => ceo cto dev1 dev2 dev3 cfo accountant cmo
console.log('--- DFS postOrder');
tree.traverseDFS(function(node) { console.log(node.data); }, 'postOrder'); // => dev1 dev2 dev3 cto accountant cfo cmo ceo
tree.remove('cmo');
tree.print(); // => ceo | cto cfo | dev1 dev2 dev3 accountant
tree.remove('cfo');
tree.print(); // => ceo | cto | dev1 dev2 dev3

What is a relational database?

Bryan C Guner — Sat, 11 Dec 2021 08:03:11 +0000

What is a relational database?

Data stored as row records in tables. Imagine a spreadsheet with column
headers describing the contents of each column, and each row is a
record.

A database can contain many tables. A table can contain many rows. A row
can contain many columns.

Records are related to those in different tables through common columns
that are present in both tables.

For example, an Employee table might have the following columns in
each record:

Employee
    EmployeeID  FirstName  LastName  DepartmentID

And a Department table might have the following columns in each
record:

Department
    DepartmentID  DepartmentName

Notice that both Employee and Department have a DepartmentID
column. This common column relates the two tables and can be used to
join them together with a query.

The structure described by the table definitions is known as the
schema.

Compare to NoSQL databases that work with key/value pairs or are
document stores.

Relational vs NoSQL

NoSQL is a term that refers to non-relational databases, most usually
document store databases. (Though it can apply to almost any kind of
non-relational database.)

MongoDB is a great example of a NoSQL database.

When Do You Use NoSQL Versus a Relational Database?

Unfortunately, there are no definitive rules on when to choose one or
the other.

Do you need ACID-compliance? Consider a relational database.

Does your schema (structure of data) change frequently? Consider NoSQL.

Does absolute consistency in your data matter, e.g. a bank, inventory
management system, employee management, academic records, etc.? Consider
a relational database.

Do you need easy-to-deploy high-availability? Consider NoSQL.

Do you need transactions to happen atomically? (The ability to update
multiple records simultaneously?) Consider a relational database.

Do you need read-only access to piles of data? Consider NoSQL.

PostgreSQL

PostgreSQL is a venerable relational database that is freely available
and world-class.

https://www.postgresql.org/

SQL, Structured Query Language

SQL ("sequel") is the language that people use for interfacing with
relational databases.

Create a table with CREATE TABLE

A database is made up of a number of tables. Let's create a table using
SQL in the shell. Be sure to end the command with a semicolon ;.

(Note: SQL commands are often capitalized by convention, but can be
lowercase.)

$ psql
psql (10.1)
Type "help" for help.

dbname=> CREATE TABLE Employee (ID INT, LastName VARCHAR(20));

Use the \dt command to show which tables exist:

dbname=> CREATE TABLE Employee (ID INT, LastName VARCHAR(20));
CREATE TABLE
dbname=> \dt
        List of relations
Schema |   Name   | Type  | Owner 
--------+----------+-------+-------
public | employee | table | beej
(1 row)

Use the \d command to see what columns a table has:

dbname=> \d Employee
                        Table "public.employee"
    Column    |         Type          | Collation | Nullable | Default 
--------------+-----------------------+-----------+----------+---------
 id           | integer               |           |          | 
 lastname     | character varying(20) |           |          |

Create a row with INSERT

dbname=> INSERT INTO Employee (ID, LastName) VALUES (10, 'Tanngnjostr');
INSERT 0 1

You can omit the column names if you're putting data in every column:

dbname=> INSERT INTO Employee VALUES (10, 'Tanngnjostr');
INSERT 0 1

Run some more inserts into the table:

INSERT INTO Employee VALUES (11, 'Alice');
INSERT INTO Employee VALUES (12, 'Bob');
INSERT INTO Employee VALUES (13, 'Charlie');
INSERT INTO Employee VALUES (14, 'Dave');
INSERT INTO Employee VALUES (15, 'Eve');

Read rows with SELECT

You can query the table with SELECT.

Query all the rows and columnts:

dbname=> SELECT * FROM Employee;
 id |  lastname   
----+-------------
 10 | Tanngnjostr
 11 | Alice
 12 | Bob
 13 | Charlie
 14 | Dave
 15 | Eve
(6 rows)

With SELECT, * means "all columns".

You can choose specific columns:

dbname=> SELECT LastName FROM Employee;
  lastname   
-------------
 Tanngnjostr
 Alice
 Bob
 Charlie
 Dave
 Eve
(6 rows)

And you can search for specific rows with the WHERE clause:

dbname=> SELECT * FROM Employee WHERE ID=12;
 id | lastname 
----+----------
 12 | Bob
(1 row)

dbname=> SELECT * FROM Employee WHERE ID=14 OR LastName='Bob';
 id | lastname 
----+----------
 12 | Bob
 14 | Dave
(2 rows)

Finally, you can rename the output columns, if you wish:

SELECT id AS Employee ID, LastName AS Name
    FROM Employee
    WHERE ID=14 OR LastName='Bob';

 Employee ID | Name 
-------------+----------
     12      | Bob
     14      | Dave

Update rows with UPDATE

The UPDATE command can update one or many rows. Restrict which rows
are updated with a WHERE clause.`

dbname=> UPDATE Employee SET LastName='Harvey' WHERE ID=10;
UPDATE 1

dbname=> SELECT * FROM Employee WHERE ID=10;
 id | lastname 
----+----------
 10 | Harvey
(1 row)

You can update multiple columns at once:

dbname=> UPDATE Employee SET LastName='Octothorpe', ID=99 WHERE ID=14;
UPDATE 1

Delete rows with DELETE

Delete from a table with the DELETE command. Use a WHERE clause to
restrict the delete.

CAUTION! If you don't use a WHERE clause, all rows will be deleted
from the table!

Delete some rows:

dbname=> DELETE FROM Employee WHERE ID >= 15;
DELETE 2

Delete ALL rows (Danger, Will Robinson!):

dbname=> DELETE FROM Employee;
DELETE 4

Deleting entire tables with DROP

If you want to get rid of an entire table, use DROP.

WARNING! There is no going back. Table will be completely blown
away. Destroyed ...by the Empire.

dbname=> DROP TABLE Employee;
DROP TABLE

The `WHERE` Clause

You've already seen some examples of how WHERE affects SELECT,
UPDATE, and DELETE.

Normal operators like <, >, =, <=, >= are available.

For example:

sql SELECT * from animals WHERE age >= 10;

`AND`, `OR`, and Parentheses

You can add more boolean logic with AND, OR, and affect precedence
with parentheses:

sql SELECT * from animals WHERE age >= 10 AND type = 'goat';

sql SELECT * from animals WHERE age >= 10 AND (type = 'goat' OR type = 'antelope');

`LIKE`

The LIKE operator can be used to do pattern matching.

sql _ -- Match any single character % -- Match any sequence of characters

To select all animals that start with ab:

sql SELECT * from animal WHERE name LIKE 'ab%';

Column Data Types

You probably noticed a few data types we specified with CREATE TABLE,
above. PostgreSQL has a lot of data
types.

This is an incomplete list of some of the more common types:

sql VARCHAR(n) -- Variable character string of max length n BOOLEAN -- TRUE or FALSE INTEGER -- Integer value INT -- Same as INTEGER DECIMAL(p,s) -- Decimal number with p digits of precision -- and s digits right of the decimal point REAL -- Floating point number DATE -- Holds a date TIME -- Holds a time TIMESTAMP -- Holds an instant of time (date and time) BLOB -- Binary object

ACID and CRUD

These are two common database terms.

ACID

Short for Atomicity, Consistency, Isolation, Durability. When
people mention "ACID-compliance", they're generally talking about the
ability of the database to accurately record transactions in the case of
crash or power failure.

Atomicity: all transactions will be "all or nothing".

Consistency: all transactions will leave the database in a consistent
state with all its defined rules and constraints.

Isonlation: the results of concurrent transactions is the same as if
those transactions had been executed sequentially.

Durability: Once a transaction is committed, it will remain committed,
despite crashes, power outages, snow, and sleet.

CRUD

Short for Create, Read, Update, Delete. Describes the four basic
functions of a data store.

In a relational database, these functions are handled by INSERT,
SELECT, UPDATE, and DELETE.

NULL and NOT NULL

Columns in records can sometimes have no data, referred to by the
special keyword as NULL. Sometimes it makes sense to have NULL
columns, and sometimes it doesn't.

If you explicitly want to disallow NULL columns in your table, you can
create the columns with the NOT NULL constraint:

CREATE TABLE Employee (
    ID INT NOT NULL,
    LastName VARCHAR(20));

COUNT

You can select a count of items in question with the COUNT operator.

For example, count the rows filtered by the WHERE clause:

`sql
SELECT COUNT(*) FROM Animals WHERE legcount >= 4;

count

Useful with GROUP BY, below.

ORDER BY

ORDER BY which sorts SELECT results for you. Use DESC to sort in
reverse order.

`sql
SELECT * FROM Pets
ORDER BY age DESC;

name	age
Rover	9
Zaphod	4
Mittens	3

GROUP BY

When used with an aggregating function like COUNT, can be
used to produce groups of results.

Count all the customers in certain countries:

`sql
SELECT COUNT(CustomerID), Country
FROM Customers
GROUP BY Country;

COUNT(CustomerID)	Country
1123	USA
734	Germany

                 etc.

Keys: Primary, Foreign, and Composite

Primary Key

Rows in a table often have one column that is called the primary key.
The value in this column applies to all the rest of the data in the
record. For example, an EmployeeID would be a great primary key,
assuming the rest of the record held employee information.

Employee
    ID (Primary Key)  LastName  FirstName  DepartmentID

To create a table and specify the primary key, use the NOT NULL and
PRIMARY KEY constraints:

sql CREATE TABLE Employee ( ID INT NOT NULL PRIMARY KEY, LastName VARCHAR(20), FirstName VARCHAR(20), DepartmentID INT);

You can always search quickly by primary key.

Foreign Keys

If a key refers to a primary key in another table, it is called a
foreign key (abbreviated "FK"). You are not allowed to make changes to
the database that would cause the foreign key to refer to a non-existent
record.

The database uses this to maintain referential integrity.

Create a foreign key using the REFERENCES constraint. It specifies the
remote table and column the key refers to.

`sql
CREATE TABLE Department (
ID INT NOT NULL PRIMARY KEY,
Name VARCHAR(20));

CREATE TABLE Employee (
ID INT NOT NULL PRIMARY KEY,
LastName VARCHAR(20),
FirstName VARCHAR(20),
DepartmentID INT REFERENCES Department(ID));
`

In the above example, you cannot add a row to Employee until that
DepartmentID already exists in Department's ID.

Also, you cannot delete a row from Department if that row's ID was a
DepartmentID in Employee.

Composite Keys

Keys can also consist of more than one column. Composite keys can be
created as follows:

sql CREATE TABLE example ( a INT, b INT, c INT, PRIMARY KEY (a, c));

Auto-increment Columns

These are columns that the database manages, usually in an
ever-increasing sequence. It's perfect for generation unique, numeric
IDs for primary Keys.

In some databases (e.g MySQL) this is done with an AUTO_INCREMENT
keyword. PostgreSQL is different.

In PostgreSQL, use the SERIAL keyword to auto-generate sequential
numeric IDs for records.

sql CREATE TABLE Company ( ID SERIAL PRIMARY KEY, Name VARCHAR(20));

When you insert, do not specify the ID column. You must however,
give a column name list that includes the remaining column names you are
inserting data for. The ID column will be automatically generated by the
database.

sql INSERT INTO Company (Name) VALUES ('My Awesome Company');

Joins

This concept is extremely important to understanding how to use
relational databases!

When you have two (or more) tables with data you wish to retrieve from
both, you do so by using a join. These come in a number of varieties,
some of which are covered here.

When you're using SELECT to make the join between two tables, you can
specify the tables specific columns are from by using the . operator.
This is especially useful when columns have the same name in the
different tables:

sql SELECT Animal.name, Farm.name FROM Animal, Farm WHERE Animal.FarmID = Farm.ID;

Tables to use in these examples:

`sql
CREATE TABLE Department (
ID INT NOT NULL PRIMARY KEY,
Name VARCHAR(20));

CREATE TABLE Employee (
ID INT NOT NULL PRIMARY KEY,
Name VARCHAR(20),
DepartmentID INT);

INSERT INTO Department VALUES (10, 'Marketing');
INSERT INTO Department VALUES (11, 'Sales');
INSERT INTO Department VALUES (12, 'Entertainment');

INSERT INTO Employee VALUES (1, 'Alice', 10);
INSERT INTO Employee VALUES (2, 'Bob', 12);
INSERT INTO Employee VALUES (3, 'Charlie', 99);
`

NOTE: Importantly, department ID 11 is not referred to from
Employee, and department ID 99 (Charlie) does not exist in
Department. This is instrumental in the following examples.

Inner Join, The Most Common Join

This is the most commonly-used join, by far, and is what people mean
when they just say "join" with no further qualifiers.

This will return only the rows that match the requirements from both
tables.

For example, we don't see "Sales" or "Charlie" in the join because
neither of them match up to the other table:

dbname=> SELECT Employee.ID, Employee.Name, Department.Name
             FROM Employee, Department
             WHERE Employee.DepartmentID = Department.ID;

 id | name  |     name      
----+-------+---------------
  1 | Alice | Marketing
  2 | Bob   | Entertainment
(2 rows)

Above, we used a WHERE clause to perform the inner join. This is
absolutely the most common way to do it.

There is an alternative syntax, below, that is barely ever used.

dbname=> SELECT Employee.ID, Employee.Name, Department.Name
             FROM Employee INNER JOIN Department
             ON Employee.DepartmentID = Department.ID;

 id | name  |     name      
----+-------+---------------
  1 | Alice | Marketing
  2 | Bob   | Entertainment
(2 rows)

Left Outer Join

This join works like an inner join, but also returns all the rows from
the "left" table (the one after the FROM clause). It puts NULL
in for the missing values in the "right" table (the one after the
LEFT JOIN clause.)

Example:

dbname=> SELECT Employee.ID, Employee.Name, Department.Name
             FROM Employee LEFT JOIN Department
             ON Employee.DepartmentID = Department.ID;

 id |  name   |     name      
----+---------+---------------
  1 | Alice   | Marketing
  2 | Bob     | Entertainment
  3 | Charlie | 
(3 rows)

Notice that even though Charlie's department isn't found in Department, his record is still listed with a NULL department name.

Right Outer Join

This join works like an inner join, but also returns all the rows from
the "right" table (the one after the RIGHT JOIN clause). It puts
NULL in for the missing values in the "right" table (the one after the
FROM clause.)

dbname=> SELECT Employee.ID, Employee.Name, Department.Name
             FROM Employee RIGHT JOIN Department
             ON Employee.DepartmentID = Department.ID;

 id | name  |     name      
----+-------+---------------
  1 | Alice | Marketing
  2 | Bob   | Entertainment
    |       | Sales
(3 rows)

Notice that even though there are no employees in the Sales department,
the Sales name is listed with a NULL employee name.

Full Outer Join

This is a blend of a Left and Right Outer Join. All information from
both tables is selected, with NULL filling the gaps where necessary.

 dbname=> SELECT Employee.ID, Employee.Name, Department.Name
              FROM Employee
              FULL JOIN Department
              ON Employee.DepartmentID = Department.ID;

 id |  name   |     name      
----+---------+---------------
  1 | Alice   | Marketing
  2 | Bob     | Entertainment
  3 | Charlie | 
    |         | Sales
(4 rows)

Indexes

When searching through tables, you use a WHERE clause to narrow things
down. For speed, the columns mentioned in the WHERE clause should
either be a primary key, or a column for which an index has been
built.

Indexes help speed searches. In a large table, searching over an
unindexed column will be slow.

Example of creating an index on the Employee table from the
Keys section:

dbname=> CREATE INDEX ON Employee (LastName);
CREATE INDEX

dbname=> \d Employee
                        Table "public.employee"
    Column    |         Type          | Collation | Nullable | Default 
--------------+-----------------------+-----------+----------+---------
 id           | integer               |           | not null | 
 lastname     | character varying(20) |           |          | 
 firstname    | character varying(20) |           |          | 
 departmentid | integer               |           |          | 
Indexes:
    "employee_pkey" PRIMARY KEY, btree (id)
    "employee_lastname_idx" btree (lastname)
Foreign-key constraints:
    "employee_departmentid_fkey" FOREIGN KEY (departmentid) REFERENCES department(id)

PostgreSQL CREATE INDEX documentation

Transactions

In PostgreSQL, you can bundle a series of statements into a
transaction. The transaction is executed atomically, which means
either the entire transaction occurs, or none of the transaction occurs.
There will never be a case where a transaction partially occurs.

Create a transaction by starting with a BEGIN statement, followed by
all the statements that are to be within the transaction.

START TRANSACTION is generally synonymous with BEGIN in SQL.

To execute the transaction ("Let's do it!"), end with a COMMIT
statement.

To abort the transaction and do nothing ("On second thought,
nevermind!") end with a ROLLBACK statement. This makes it like
nothing within the transaction ever happened.

Usually transactions happen within a program that checks for sanity and
either commits or rolls back.

Pseudocode making DB calls that check if a rollback is necessary:

`javascript
db("BEGIN"); // Begin transaction

db(UPDATE accounts SET balance = balance - 100.00 WHERE name = 'Alice');

let balance = db("SELECT balance WHERE name = 'Alice'");

// Don't let the balance go below zero:
if (balance < 0) {
db("ROLLBACK"); // Never mind!! Roll it all back.
} else {
db("COMMIT"); // Plenty of cash
}
`

In the above example, the UPDATE and SELECT must happen at the same
time (atomically) or else another process could sneak in between and
withdraw too much money. Because it needs to be atomic, it's wrapped in
a transaction.

If you just enter a single SQL statement that is not inside a BEGIN
transaction block, it gets automatically wrapped in a BEGIN/COMMIT
block. It is a mini transaction that is COMMITted immediately.

Not all SQL databases support transactions, but most do.

The EXPLAIN Command

The EXPLAIN command will tell you how much time the database is
spending doing a query, and what it's doing in that time.

It's a powerful command that can help tell you where you need to add
indexes, change structure, or rewrite queries.

dbname=> EXPLAIN SELECT * FROM foo;

                       QUERY PLAN
---------------------------------------------------------
 Seq Scan on foo  (cost=0.00..155.00 rows=10000 width=4)
(1 row)

For more information, see the PostgreSQL EXPLAIN documentation

Quick and Dirty DB Design

Designing a non-trivial database is a difficult, learned skill best left to
professionals. Feel free to do small databases with minimal training, but if you
get in a professional situation with a large database that needs to be designed,
you should consult with people with strong domain knowledge.

That said, here are a couple pointers.

In general, all your tables should have a unique PRIMARY KEY for each row.
It's common to use SERIAL or AUTO_INCREMENT to make this happen.
Keep an eye out for commonly duplicated data. If you are duplicating text data
across several records, consider that maybe it should be in its own table and
referred to with a foreign key.
Watch out for unrelated data in the same record. If it's a record in the
Employee table but it has Department_Address as a column, that probably
belongs in a Department table, referred to by a public key.

But if you really want to design database, read on to the Normalization and
Normal Forms section.

Normalization and Normal Forms

[This topic is very deep and this section cannot do it full justice.]

Normalization is the process of designing or refactoring your tables
for maximum consistency and minimum redundancy.

With NoSQL databases, we're used to denormalized data that is stored
with speed in mind, and not so much consistency (sometimes NoSQL
databases talk about eventual consistency).

Non-normalized tables are considered an anti-pattern in relational databases.

There are many normal forms. We'll talk about First, Second, and Third
normal forms.

Anomalies

One of the reasons for normalizing tables is to avoid anomalies.

Insert anomaly: When we cannot insert a row into the table because
some of the dependent information is not yet known. For example, we
cannot create a new class record in the school database, because the
record requires at least one student, and none have enrolled yet.

Update anomaly: When information is duplicated in the database and
some rows are updated but not others. For example, say a record contains
a city and a zipcode, but then the post office changes the zipcode. If
some of the records are updated but not others, some cities will have
the old zipcodes.

Delete anomaly: The opposite of an insert anomaly. When we delete some
information and other related information must also be deleted against
our will. For example, deleting the last student from a course causes
the other course information to be also deleted.

By normalizing your tables, you can avoid these anomalies.

First Normal Form (1NF)

When a database is in first normal form, there is a primary key for each
row, and there are no repeating sets of columns that should be in their
own table.

Unnormalized (column titles on separate lines for clarity):

Farm
    ID
    AnimalName1  AnimalBreed1  AnimalProducesEggs1
    AnimalName2  AnimalBreed2  AnimalProducesEggs2

1NF:

Farm
    ID

Animal
    ID  FarmID[FK Farm(ID)]  Name  Breed  ProducesEggs

Use a join to select all the animals in the farm:

sql SELECT Name, Farm.ID FROM Animal, Farm WHERE Farm.ID = Animal.FarmID;

Second Normal Form (2NF)

To be in 2NF, a table must already be in 1NF.

Additionally, all non-key data must fully relate to the key data in the table.

In the farm example, above, Animal has a Name and a key FarmID, but
these two pieces of information are not related.

We can fix this by adding a table to link the other two tables together:

2NF:

Farm
    ID

FarmAnimal
    FarmID[FK Farm(ID)]  AnimalID[FK Animal(ID)]

Animal
    ID  Name  Breed  ProducesEggs

Use a join to select all the animals in the farms:

sql SELECT Name, Farm.ID FROM Animal, FarmAnimal, Farm WHERE Farm.ID = FarmAnimal.FarmID AND Animal.ID = FarmAnimal.AnimalID;

Third Normal Form (3NF)

A table in 3NF must already be in 2NF.

Additionally, columns that relate to each other AND to the key need to
be moved into their own tables. This is known as removing transitive
dependencies.

In the Farm example, the columns Breed and ProducesEggs are related.
If you know the breed, you automatically know if it produces eggs or
not.

3NF:

Farm
    ID

FarmAnimal
    FarmID[FK Farm(ID)]  AnimalID[FK Animal(ID)]

BreedEggs
    Breed  ProducesEggs

Animal
    ID  Name  Breed[FK BreedEggs(Breed)]

Use a join to select all the animals names that produce eggs
in the farm:

sql SELECT Name, Farm.ID FROM Animal, FarmAnimal, BreedEggs, Farm WHERE Farm.ID = FarmAnimal.FarmID AND Animal.ID = FarmAnimal.AnimalID AND Animal.Breed = BreedEggs.Breed AND BreedEggs.ProducesEggs = TRUE;

Node-Postgres

This is a library that allows you to interface with PostgreSQL through
NodeJS.

Its documentation is exceptionally good.

Node-Postgres on GitHub

Security

PostgreSQL Password

You might have noticed that you don't need a password to access your
database that you created. This is because PostgreSQL by default uses
something called peer authentication
mode.

In a nutshell, it makes sure that you are logged in as yourself before
you access your database. If a different user tries to access your
database, they will be denied.

If you need to set up password access, see client authentication in the
PostgreSQL
manual

Writing Client Software

When writing code that accesses databases, there are a few rules you
should follow to keep things safe.

Don't store database passwords or other sensitive information in your
code repository. Store dummy credentials instead.
When building SQL queries in code, use parameterized
queries.
You build your query with parameter placeholders for where the query
arguments will go.

This is your number-one line of defense against SQL injection
attacks.

It's a seriously noob move to not use parameterized queries.

Other Relational Databases

There are tons of them by Microsoft, Oracle, etc. etc.

Other popular open source databases in widespread use are:

MySQL Multi-user, industrial class.
SQLite Single-user, very fast, good for config files.

Assignment: Install PostgreSQL

IMPORTANT! These instructions assume you haven't already installed
PostgreSQL. If you have already installed it, skip this section or
Google for how to upgrade your installation.

Mac with Homebrew

Open a terminal
Install PostgreSQL: brew install postgresql

If you get install errors at this point relating to the link phase
failing or missing permissions, look back in the output and see
what file it failed to write.

For example, if it's failing to write something in
/usr/local/share/man-something, try setting the ownership on
those directories to yourself.

Example (from the command line):

$ sudo chown -R $(whoami) /usr/local/share/man

Then try to install again.
Start the database process
- If you want to start it every time you log in, run:
  
  brew services start postgresql

* If you want to just start it one time right now, run:

      pg_ctl -D /usr/local/var/postgres start

Create a database named the same as your username: createdb $(whoami)
- Optionally you can call it anything you want, but the shell defaults to looking for a database named the same as your user.

This database will contain tables.

Then start a shell by running psql and see if it works. You should see
this prompt:

$ psql
psql (10.1)
Type "help" for help.

dbname=>

(Use psql databasename if you created the database under something
other than your username.)

Use \l to get a list of databases.

You can enter \q to exit the shell.

Windows

Reports are that one of the easiest installs is with
chocolatey. Might want to try that
first.

You can also download a Windows
installer from the
official site.

Another option is to use the Windows Subsystem for
Linux
and follow the Ubuntu instructions for installing
PostgreSQL.

Arch Linux

Arch requires a bit more hands-on, but not much more. Check this out if
you want to see a different Unix-y install procedure (or if you run
Arch).

Installing PostgreSQL on Arch Linux

Assignment: Create a Table and Use It

Launch the shell on your database, and create a table.

sql CREATE TABLE Employee (ID INT, FirstName VARCHAR(20), LastName VARCHAR(20));

Insert some records:

sql INSERT INTO Employee VALUES (1, 'Alpha', 'Alphason'); INSERT INTO Employee VALUES (2, 'Bravo', 'Bravoson'); INSERT INTO Employee VALUES (3, 'Charlie', 'Charleson'); INSERT INTO Employee VALUES (4, 'Delta', 'Deltason'); INSERT INTO Employee VALUES (5, 'Echo', 'Ecoson');

Select all records:

sql SELECT * FROM Employee;

Select Employee #3's record:

sql SELECT * FROM Employee WHERE ID=3;

Delete Employee #3's record:

sql DELETE FROM Employee WHERE ID=3;

Use SELECT to verify the record is deleted.

Update Employee #2's name to be "Foxtrot Foxtrotson":

sql UPDATE Employee SET FirstName='Foxtrot', LastName='Foxtrotson' WHERE ID=2;

Use SELECT to verify the update.

Assignment: NodeJS Program to Create and Populate a Table

Using Node-Postgres, write a program that
creates a table.

Run the following query from your JS code:

sql CREATE TABLE IF NOT EXISTS Earthquake (Name VARCHAR(20), Magnitude REAL)

Populate the table with the following data:

javascript let data = [ ["Earthquake 1", 2.2], ["Earthquake 2", 7.0], ["Earthquake 3", 1.8], ["Earthquake 4", 5.2], ["Earthquake 5", 2.9], ["Earthquake 6", 0.6], ["Earthquake 7", 6.6] ];

You'll have to run an INSERT statement for each one.

Open a PostgreSQL shell (psql) and verify the table exists:

user-> \dt
          List of relations
 Schema |    Name    | Type  | Owner 
--------+------------+-------+-------
 public | earthquake | table | user
(1 row)

Also verify it is populated:

user-> SELECT * from Earthquake;

     name     | magnitude 
--------------+-----------
 Earthquake 1 |       2.2
 Earthquake 2 |         7
 Earthquake 3 |       1.8
 Earthquake 4 |       5.2
 Earthquake 5 |       2.9
 Earthquake 6 |       0.6
 Earthquake 7 |       6.6
(7 rows)

Hints:

Extra Credit:

Add an ID column to help normalize the database. Make this column SERIAL to auto-increment.
Add Date, Lat, and Lon columns to record more information about the event.

Assignment: Command-line Earthquake Query Tool

Write a tool that queries the database for earthquakes that are at least
a given magnitude.

$ node earthquake 2.9
Earthquakes with magnitudes greater than or equal to 2.9:

Earthquake 2: 7
Earthquake 7: 6.6
Earthquake 4: 5.2
Earthquake 5: 2.9

Use ORDER BY Magnitude DESC to order the results in descending order
by magnitude.

Assignment: RESTful Earthquake Data Server

Use ExpressJS and write a webserver that
implements a RESTful API to access the earthquake data.

Endpoints:

/ (GET) Output usage information in HTML.

Example results:

html <html> <body>Usage: [endpoint info]</body> </html>

/minmag (GET) Output JSON list of earthquakes that are larger than the
value specified in the mag parameter. Use form encoding to pass the
data.

Example results:

json { "results": [ { "name": "Earthquake 2", "magnitude": 7 }, { "name": "Earthquake 4", "magnitude": 5.2 } ] }

Extra Credit:

/new (POST) Add a new earthquake to the database. Use form encoding to
pass name and mag. Return a JSON status message:

json { "status": "ok" }

json { "status": "error", "message": "[error message]" }

/delete (DELETE) Delete an earthquake from the database. Use form
encoding to pass name. Return status similar to /new, above.

UPDATE Employee SET FirstName='Foxtrot', LastName='Foxtrotson' WHERE ID=2;
Use SELECT to verify the update.

Fundamental Data Structures in JavaScript

Bryan C Guner — Sat, 11 Dec 2021 03:19:45 +0000

Fundamental Data Structures in JavaScript

(and a bit of python pseudo code)

Fundamental Data Structures in JavaScript
- (and a bit of python pseudo code)
Table Of Contents:
Resuorces:
- Data Structures & Algorithms Resource List Part 1
- Guess the author of the following quotes:
- Update:
- Algorithms
- Data Structures:
- A simple to follow guide to Lists Stacks and Queues, with animated gifs, diagrams, and code examples
- Linked Lists
- What is a Linked List?
  - "So…this sounds a lot like an Array…"
- Types of Linked Lists
- Linked List Methods
- Time and Space Complexity Analysis
- Time Complexity — Access and Search
  - Scenarios
  - Discussion
- Time Complexity — Insertion and Deletion
  - Scenarios
  - Discussion
- Space Complexity
  - Scenarios
  - Discussion
- Stacks and Queues
- What is a Stack?
- What is a Queue?
- Stack and Queue Properties
- Time and Space Complexity Analysis
  - Time Complexity — Access and Search
  - Time Complexity — Insertion and Deletion
  - Space Complexity
- When should we use Stacks and Queues?
Graphs:
- Graph Data Structure Interview Questions At A Glance
- Graphs
- Questions
  - What is a Graph?
  - Why is it important to learn Graphs?
  - How many types of graphs are there?
  - What is the time complexity (big-O) to add/remove/get a vertex/edge for a graph?
- Graph Representations
- Adjacency List
- Adjacency Matrix
- Tradeoffs
  - Space Complexity
  - Add Vertex
  - Remove Vertex
  - Add Edge
  - Remove Edge
  - Find Edge
  - Get All Edges from Vertex
- Breadth-First Search
  - BFS
- Applications of BFS
- Coloring BFS
- BFS Pseudocode
- BFS Steps
- Depth-First Search
  - DFS
- Applications of DFS
- DFS Pseudocode
- DFS Steps
- Connected Components
- Uses
- How to find connected componnents
- Bonus Python Question
This Bellman-Ford Code is for determination whether we can get
shortest path from given graph or not for single-source shortest-paths problem.
In other words, if given graph has any negative-weight cycle that is reachable
from the source, then it will give answer False for "no solution exits".
For argument graph, it should be a dictionary type
such as
- Review of Concepts
- Undirected Graph
- Types
- Dense Graph
- Sparse Graph
- Weighted Graph
- Directed Graph
- Undirected Graph
- Node Class
- Adjacency Matrix
- Adjacency List
  - Stacks
  - Queues
- Data Structures… Under The Hood
- Data Structures Reference
- Array
- Linked List
- Queue
- Stack
- Tree
- Binary Search Tree
- Binary Search Tree
- Graph
- Heap
- Adjacency list
- Adjacency matrix
- Arrays
- Pointers
- Linked lists
- Doubly Linked Lists
- Not cache-friendly
- Hash tables
- Breadth-First Search (BFS) and Breadth-First Traversal
- Binary Search Tree
- Graph Data Structure: Directed, Acyclic, etc
- Binary numbers
Implementations
- Resources (article content below):
  - Videos
  - Books
  - Coding practice
  - Courses
  - Guides
- space
- time
- Several operations
- Dependent on data
- Big O notation
- The Array data structure
- Definition
- 2. Objects
- The Hash Table
- Definition
- The Set
- Sets
- Definition
- The Singly Linked List
- Definition
- The Doubly Linked List
- Definition
- The Stack
- Definition
- The Queue
- Definition
- The Tree
- Definition
- The Graph
- Definition
- Cycle Visual
- Ways to Reference Graph Nodes
- Node Class
- Adjacency Matrix
- Adjacency List
- Code Examples
- Basic Graph Class
- Node Class Examples
- Traversal Examples
  - With Graph Node Class
- With Adjacency List
Memoization & Tabulation (Dynamic Programming)
- What is Memoization?
  - And why this programming paradigm shouldn't make you cringe
- Memoizing factorial
- Memoizing the Fibonacci generator
- The memoization formula
Practice:

Resuorces:

_**

🏐⇒⇒⇒Click Here To Expand⇐⇐⇐🏐**_

Data Structures & Algorithms Resource List Part 1

Guess the author of the following quotes:

> Talk is cheap. Show me the code.

> Software is like sex: it's better when it's free.

> Microsoft isn't evil, they just make really crappy operating systems.

Update:

Algorithms

100 days of algorithms
Algorithms — Solved algorithms and data structures problems in many languages.
Algorithms by Jeff Erickson (Code) (HN)
Top algos/DS to learn
Some neat algorithms
Mathematical Proof of Algorithm Correctness and Efficiency (2019)
Algorithm Visualizer — Interactive online platform that visualizes algorithms from code.
Algorithms for Optimization book
Collaborative book on algorithms (Code)
Algorithms in C by Robert Sedgewick
Algorithm Design Manual
MIT Introduction to Algorithms course (2011)
How to implement an algorithm from a scientific paper (2012)
Quadsort — Stable non-recursive merge sort named quadsort.
System design algorithms — Algorithms you should know before system design.
Algorithms Design book
Think Complexity
All Algorithms implemented in Rust
Solutions to Introduction to Algorithms book (Code)
Maze Algorithms (2011) (HN)
Algorithmic Design Paradigms book (Code)
Words and buttons Online Blog (Code)
Algorithms animated
Cache Oblivious Algorithms (2020) (HN)
You could have invented fractional cascading (2012)
Guide to learning algorithms through LeetCode (Code) (HN)
How hard is unshuffling a string?
Optimization Algorithms on Matrix Manifolds
Problem Solving with Algorithms and Data Structures (HN) (PDF)
Algorithms implemented in Python
Algorithms implemented in JavaScript
Algorithms & Data Structures in Java
Wolfsort — Stable adaptive hybrid radix / merge sort.
Evolutionary Computation Bestiary — Bestiary of evolutionary, swarm and other metaphor-based algorithms.
Elements of Programming book — Decomposing programs into a system of algorithmic components. (Review) (HN) (Lobsters)
Competitive Programming Algorithms
CPP/C — C/C++ algorithms/DS problems.
How to design an algorithm (2018)
CSE 373 — Introduction to Algorithms, by Steven Skiena (2020)
Computer Algorithms II course (2020)
Improving Binary Search by Guessing (2019)
The case for a learned sorting algorithm (2020) (HN)
Elementary Algorithms — Introduces elementary algorithms and data structures. Includes side-by-side comparisons of purely functional realization and their imperative counterpart.
Combinatorics Algorithms for Coding Interviews (2018)
Algorithms written in different programming languages (Web)
Solving the Sequence Alignment problem in Python (2020)
The Sound of Sorting — Visualization and "Audibilization" of Sorting Algorithms. (Web)
Miniselect: Practical and Generic Selection Algorithms (2020)
The Slowest Quicksort (2019)
Functional Algorithm Design (2020)
Algorithms To Live By — Book Notes
Numerical Algorithms (2015)
Using approximate nearest neighbor search in real world applications (2020)
In search of the fastest concurrent Union-Find algorithm (2019)
Computer Science 521 Advanced Algorithm Design

Data Structures:

## A simple to follow guide to Lists Stacks and Queues, with animated gifs, diagrams, and code examples

Linked Lists

In the university setting, it's common for Linked Lists to appear early on in an undergraduate's Computer Science coursework. While they don't always have the most practical real-world applications in industry, Linked Lists make for an important and effective educational tool in helping develop a student's mental model on what data structures actually are to begin with. Linked lists are simple. They have many compelling, reoccurring edge cases to consider that emphasize to the student the need for care and intent while implementing data structures. They can be applied as the underlying data structure while implementing a variety of other prevalent abstract data types, such as Lists, Stacks, and Queues, and they have a level of versatility high enough to clearly illustrate the value of the Object Oriented Programming paradigm. They also come up in software engineering interviews quite often.

What is a Linked List?

A Linked List data structure represents a linear sequence of "vertices" (or "nodes"), and tracks three important properties.

Linked List Properties:

The data being tracked by a particular Linked List does not live inside the Linked List instance itself. Instead, each vertex is actually an instance of an even simpler, smaller data structure, often referred to as a "Node". Depending on the type of Linked List (there are many), Node instances track some very important properties as well. **Linked List Node Properties:** Property Description `value`: The actual value this node represents.`next`The next node in the list (relative to this node).`previous`The previous node in the list (relative to this node). **NOTE:** The `previous` property is for Doubly Linked Lists only! Linked Lists contain _ordered_ data, just like arrays. The first node in the list is, indeed, first. From the perspective of the very first node in the list, the _next_ node is the second node. From the perspective of the second node in the list, the _previous_ node is the first node, and the _next_ node is the third node. And so it goes. #### "So…this sounds a lot like an Array…" Admittedly, this does _sound_ a lot like an Array so far, and that's because Arrays and Linked Lists are both implementations of the List ADT. However, there is an incredibly important distinction to be made between Arrays and Linked Lists, and that is how they _physically store_ their data. (As opposed to how they _represent_ the order of their data.) Recall that Arrays contain _contiguous_ data. Each element of an array is actually stored _next to_ it's neighboring element _in the actual hardware of your machine_, in a single continuous block in memory. _An Array's contiguous data being stored in a continuous block of addresses in memory._ Unlike Arrays, Linked Lists contain _non-contiguous_ data. Though Linked Lists _represent_ data that is ordered linearly, that mental model is just that — an interpretation of the _representation_ of information, not reality. In reality, in the actual hardware of your machine, whether it be in disk or in memory, a Linked List's Nodes are not stored in a single continuous block of addresses. Rather, Linked List Nodes live at randomly distributed addresses throughout your machine! The only reason we know which node comes next in the list is because we've assigned its reference to the current node's `next` pointer. _A Singly Linked List's non-contiguous data (Nodes) being stored at randomly distributed addresses in memory._ For this reason, Linked List Nodes have _no indices_, and no _random access_. Without random access, we do not have the ability to look up an individual Linked List Node in constant time. Instead, to find a particular Node, we have to start at the very first Node and iterate through the Linked List one node at a time, checking each Node's _next_ Node until we find the one we're interested in. So when implementing a Linked List, we actually must implement both the Linked List class _and_ the Node class. Since the actual data lives in the Nodes, it's simpler to implement the Node class first. ### Types of Linked Lists There are four flavors of Linked List you should be familiar with when walking into your job interviews. **Linked List Types:** ***Note:****These Linked List types are not always mutually exclusive.* For instance: - Any type of Linked List can be implemented Circularly (e.g. A Circular Doubly Linked List). - A Doubly Linked List is actually just a special case of a Multiply Linked List. You are most likely to encounter Singly and Doubly Linked Lists in your upcoming job search, so we are going to focus exclusively on those two moving forward. However, in more senior level interviews, it is very valuable to have some familiarity with the other types of Linked Lists. Though you may not actually code them out, _you will win extra points by illustrating your ability to weigh the tradeoffs of your technical decisions_ by discussing how your choice of Linked List type may affect the efficiency of the solutions you propose. ### Linked List Methods

Linked Lists are great foundation builders when learning about data structures because they share a number of similar methods (and edge cases) with many other common data structures. You will find that many of the concepts discussed here will repeat themselves as we dive into some of the more complex non-linear data structures later on, like Trees and Graphs.

Time and Space Complexity Analysis

Before we begin our analysis, here is a quick summary of the Time and Space constraints of each Linked List Operation. The complexities below apply to both Singly and Doubly Linked Lists:

Before moving forward, see if you can reason to yourself why each operation has the time and space complexity listed above!

Time Complexity — Access and Search

Scenarios

We have a Linked List, and we'd like to find the 8th item in the list.
We have a Linked List of sorted alphabet letters, and we'd like to see if the letter "Q" is inside that list.

Discussion

Unlike Arrays, Linked Lists Nodes are not stored contiguously in memory, and thereby do not have an indexed set of memory addresses at which we can quickly lookup individual nodes in constant time. Instead, we must begin at the head of the list (or possibly at the tail, if we have a Doubly Linked List), and iterate through the list until we arrive at the node of interest.

In Scenario 1, we'll know we're there because we've iterated 8 times. In Scenario 2, we'll know we're there because, while iterating, we've checked each node's value and found one that matches our target value, "Q".

In the worst case scenario, we may have to traverse the entire Linked List until we arrive at the final node. This makes both Access & Search Linear Time operations.

Time Complexity — Insertion and Deletion

Scenarios

We have an empty Linked List, and we'd like to insert our first node.
We have a Linked List, and we'd like to insert or delete a node at the Head or Tail.
We have a Linked List, and we'd like to insert or delete a node from somewhere in the middle of the list.

Discussion

Since we have our Linked List Nodes stored in a non-contiguous manner that relies on pointers to keep track of where the next and previous nodes live, Linked Lists liberate us from the linear time nature of Array insertions and deletions. We no longer have to adjust the position at which each node/element is stored after making an insertion at a particular position in the list. Instead, if we want to insert a new node at position i, we can simply:

Create a new node.
Set the new node's next and previous pointers to the nodes that live at positions i and i - 1, respectively.
Adjust the next pointer of the node that lives at position i - 1 to point to the new node.
Adjust the previous pointer of the node that lives at position i to point to the new node.

And we're done, in Constant Time. No iterating across the entire list necessary.

"But hold on one second," you may be thinking. "In order to insert a new node in the middle of the list, don't we have to lookup its position? Doesn't that take linear time?!"

Yes, it is tempting to call insertion or deletion in the middle of a Linked List a linear time operation since there is lookup involved. However, it's usually the case that you'll already have a reference to the node where your desired insertion or deletion will occur.

For this reason, we separate the Access time complexity from the Insertion/Deletion time complexity, and formally state that Insertion and Deletion in a Linked List are Constant Time across the board.

Note: Without a reference to the node at which an insertion or deletion will occur, due to linear time lookup, an insertion or deletion in the middle of a Linked List will still take Linear Time, sum total.

Space Complexity

Scenarios

We're given a Linked List, and need to operate on it.
We've decided to create a new Linked List as part of strategy to solve some problem.

Discussion

It's obvious that Linked Lists have one node for every one item in the list, and for that reason we know that Linked Lists take up Linear Space in memory. However, when asked in an interview setting what the Space Complexity of your solution to a problem is, it's important to recognize the difference between the two scenarios above.

In Scenario 1, we are not creating a new Linked List. We simply need to operate on the one given. Since we are not storing a new node for every node represented in the Linked List we are provided, our solution is not necessarily linear in space.

In Scenario 2, we are creating a new Linked List. If the number of nodes we create is linearly correlated to the size of our input data, we are now operating in Linear Space.

*Note**: Linked Lists can be traversed both iteratively and recursively. If you choose to traverse a Linked List recursively, there will be a recursive function call added to the call stack for every node in the Linked List. Even if you're provided the Linked List, as in Scenario 1, you will still use Linear Space in the call stack, and that counts.*

Stacks and Queues

Stacks and Queues aren't really "data structures" by the strict definition of the term. The more appropriate terminology would be to call them abstract data types (ADTs), meaning that their definitions are more conceptual and related to the rules governing their user-facing behaviors rather than their core implementations.

For the sake of simplicity, we'll refer to them as data structures and ADTs interchangeably throughout the course, but the distinction is an important one to be familiar with as you level up as an engineer.

Now that that's out of the way, Stacks and Queues represent a linear collection of nodes or values. In this way, they are quite similar to the Linked List data structure we discussed in the previous section. In fact, you can even use a modified version of a Linked List to implement each of them. (Hint, hint.)

These two ADTs are similar to each other as well, but each obey their own special rule regarding the order with which Nodes can be added and removed from the structure.

Since we've covered Linked Lists in great length, these two data structures will be quick and easy. Let's break them down individually in the next couple of sections.

What is a Stack?

Stacks are a Last In First Out (LIFO) data structure. The last Node added to a stack is always the first Node to be removed, and as a result, the first Node added is always the last Node removed.

The name Stack actually comes from this characteristic, as it is helpful to visualize the data structure as a vertical stack of items. Personally, I like to think of a Stack as a stack of plates, or a stack of sheets of paper. This seems to make them more approachable, because the analogy relates to something in our everyday lives.

If you can imagine adding items to, or removing items from, a Stack of…literally anything…you'll realize that every (sane) person naturally obeys the LIFO rule.

We add things to the top of a stack. We remove things from the top of a stack. We never add things to, or remove things from, the bottom of the stack. That's just crazy.

Note: We can use JavaScript Arrays to implement a basic stack. Array#push adds to the top of the stack and Array#pop will remove from the top of the stack. In the exercise that follows, we'll build our own Stack class from scratch (without using any arrays). In an interview setting, your evaluator may be okay with you using an array as a stack.

What is a Queue?

Queues are a First In First Out (FIFO) data structure. The first Node added to the queue is always the first Node to be removed.

The name Queue comes from this characteristic, as it is helpful to visualize this data structure as a horizontal line of items with a beginning and an end. Personally, I like to think of a Queue as the line one waits on for an amusement park, at a grocery store checkout, or to see the teller at a bank.

If you can imagine a queue of humans waiting…again, for literally anything…you'll realize that most people (the civil ones) naturally obey the FIFO rule.

People add themselves to the back of a queue, wait their turn in line, and make their way toward the front. People exit from the front of a queue, but only when they have made their way to being first in line.

We never add ourselves to the front of a queue (unless there is no one else in line), otherwise we would be "cutting" the line, and other humans don't seem to appreciate that.

Note: We can use JavaScript Arrays to implement a basic queue. Array#push adds to the back (enqueue) and Array#shift will remove from the front (dequeue). In the exercise that follows, we'll build our own Queue class from scratch (without using any arrays). In an interview setting, your evaluator may be okay with you using an array as a queue.

Stack and Queue Properties

Stacks and Queues are so similar in composition that we can discuss their properties together. They track the following three properties:

Stack Properties | Queue Properties:

Notice that rather than having a `head` and a `tail` like Linked Lists, Stacks have a `top`, and Queues have a `front` and a `back` instead. Stacks don't have the equivalent of a `tail` because you only ever push or pop things off the top of Stacks. These properties are essentially the same; pointers to the end points of the respective List ADT where important actions way take place. The differences in naming conventions are strictly for human comprehension. -------- Similarly to Linked Lists, the values stored inside a Stack or a Queue are actually contained within Stack Node and Queue Node instances. Stack, Queue, and Singly Linked List Nodes are all identical, but just as a reminder and for the sake of completion, these List Nodes track the following two properties: ### Time and Space Complexity Analysis Before we begin our analysis, here is a quick summary of the Time and Space constraints of each Stack Operation. Data Structure Operation Time Complexity (Avg)Time Complexity (Worst)Space Complexity (Worst)Access`Θ(n)O(n)O(n)`Search`Θ(n)O(n)O(n)`Insertion`Θ(1)O(1)O(n)`Deletion`Θ(1)O(1)O(n)` Before moving forward, see if you can reason to yourself why each operation has the time and space complexity listed above! #### Time Complexity — Access and Search When the Stack ADT was first conceived, its inventor definitely did not prioritize searching and accessing individual Nodes or values in the list. The same idea applies for the Queue ADT. There are certainly better data structures for speedy search and lookup, and if these operations are a priority for your use case, it would be best to choose something else! Search and Access are both linear time operations for Stacks and Queues, and that shouldn't be too unclear. Both ADTs are nearly identical to Linked Lists in this way. The only way to find a Node somewhere in the middle of a Stack or a Queue, is to start at the `top` (or the `back`) and traverse downward (or forward) toward the `bottom` (or `front`) one node at a time via each Node's `next` property. This is a linear time operation, O(n). #### Time Complexity — Insertion and Deletion For Stacks and Queues, insertion and deletion is what it's all about. If there is one feature a Stack absolutely must have, it's constant time insertion and removal to and from the `top` of the Stack (FIFO). The same applies for Queues, but with insertion occurring at the `back` and removal occurring at the `front` (LIFO). Think about it. When you add a plate to the top of a stack of plates, do you have to iterate through all of the other plates first to do so? Of course not. You simply add your plate to the top of the stack, and that's that. The concept is the same for removal. Therefore, Stacks and Queues have constant time Insertion and Deletion via their `push` and `pop` or `enqueue` and `dequeue` methods, O(1). #### Space Complexity The space complexity of Stacks and Queues is very simple. Whether we are instantiating a new instance of a Stack or Queue to store a set of data, or we are using a Stack or Queue as part of a strategy to solve some problem, Stacks and Queues always store one Node for each value they receive as input. For this reason, we always consider Stacks and Queues to have a linear space complexity, O(n). ### When should we use Stacks and Queues? At this point, we've done a lot of work understanding the ins and outs of Stacks and Queues, but we still haven't really discussed what we can use them for. The answer is actually…a lot! For one, Stacks and Queues can be used as intermediate data structures while implementing some of the more complicated data structures and methods we'll see in some of our upcoming sections. For example, the implementation of the breadth-first Tree traversal algorithm takes advantage of a Queue instance, and the depth-first Graph traversal algorithm exploits the benefits of a Stack instance. Additionally, Stacks and Queues serve as the essential underlying data structures to a wide variety of applications you use all the time. Just to name a few: # Graphs: ### Graph Data Structure Interview Questions At A Glance > Because they're just about the most important data structure there is.

Graphs

graph: collections of data represented by nodes and connections between nodes

graphs: way to formally represent network; ordered pairs

graphs: modeling relations between many items; Facebook friends (you = node; friendship = edge; bidirectional); twitter = unidirectional

graph theory: study of graphs

big O of graphs: G = V(E)

trees are a type of graph

Components required to make a graph:

nodes or vertices: represent objects in a dataset (cities, animals, web pages)
edges: connections between vertices; can be bidirectional
weight: cost to travel across an edge; optional (aka cost)

Useful for:

maps
networks of activity
anything you can represent as a network
multi-way relational data

Types of Graphs:

directed: can only move in one direction along edges; which direction indicated by arrows
undirected: allows movement in both directions along edges; bidirectional
cyclic: weighted; edges allow you to revisit at least 1 vertex; example weather
acyclical: vertices can only be visited once; example recipe

Two common ways to represent graphs in code:

adjacency lists: graph stores list of vertices; for each vertex, it stores list of connected vertices
adjacency matrices: two-dimensional array of lists with built-in edge weights; denotes no relationship

Both have strengths and weaknesses.

Questions

What is a Graph?

A Graph is a data structure that models objects and pairwise relationships between them with nodes and edges. For example: Users and friendships, locations and paths between them, parents and children, etc.

Why is it important to learn Graphs?

Graphs represent relationships between data. Anytime you can identify a relationship pattern, you can build a graph and often gain insights through a traversal. These insights can be very powerful, allowing you to find new relationships, like users who have a similar taste in music or purchasing.

How many types of graphs are there?

Graphs can be directed or undirected, cyclic or acyclic, weighted or unweighted. They can also be represented with different underlying structures including, but not limited to, adjacency lists, adjacency matrices, object and pointers, or a custom solution.

What is the time complexity (big-O) to add/remove/get a vertex/edge for a graph?

It depends on the implementation. (Graph Representations). Before choosing an implementation, it is wise to consider the tradeoffs and complexities of the most commonly used operations.

Graph Representations

The two most common ways to represent graphs in code are adjacency lists and adjacency matrices, each with its own strengths and weaknesses. When deciding on a graph implementation, it's important to understand the type of data and operations you will be using.

Adjacency List

In an adjacency list, the graph stores a list of vertices and for each vertex, a list of each vertex to which it's connected. So, for the following graph…

…an adjacency list in Python could look something like this:

    class Graph:
        def __init__(self):
            self.vertices = {
                              "A": {"B"},
                              "B": {"C", "D"},
                              "C": {"E"},
                              "D": {"F", "G"},
                              "E": {"C"},
                              "F": {"C"},
                              "G": {"A", "F"}
                            }

Note that this adjacency list doesn't actually use any lists. The vertices collection is a dictionary which lets us access each collection of edges in O(1) constant time while the edges are contained in a set which lets us check for the existence of edges in O(1) constant time.

Adjacency Matrix

Now, let's see what this graph might look like as an adjacency matrix:

    class Graph:
        def __init__(self):
            self.edges = [[0,1,0,0,0,0,0],
                          [0,0,1,1,0,0,0],
                          [0,0,0,0,1,0,0],
                          [0,0,0,0,0,1,1],
                          [0,0,1,0,0,0,0],
                          [0,0,1,0,0,0,0],
                          [1,0,0,0,0,1,0]]

We represent this matrix as a two-dimensional array, or a list of lists. With this implementation, we get the benefit of built-in edge weights but do not have an association between the values of our vertices and their index.

In practice, both of these would probably contain more information by including Vertex or Edge classes.

Tradeoffs

Both adjacency matrices and adjacency lists have their own strengths and weaknesses. Let's explore their tradeoffs.

For the following:

V: Total number of vertices in the graph
E: Total number of edges in the graph
e: Average number of edges per vertex

Space Complexity

Adjacency Matrix: O(V ^ 2)
Adjacency List: O(V + E)

Consider a sparse graph with 100 vertices and only one edge. An adjacency list would have to store all 100 vertices but only needs to keep track of that single edge. The adjacency matrix would need to store 100x100=10,000 possible connections, even though all but one would be 0.

Now consider a dense graph where each vertex points to each other vertex. In this case, the total number of edges will approach V² so the space complexities of each are comparable. However, dictionaries and sets are less space efficient than lists so for dense graphs, the adjacency matrix is more efficient.

Takeaway: Adjacency lists are more space efficient for sparse graphs while adjacency matrices become efficient for dense graphs.

Add Vertex

Adjacency Matrix: O(V)
Adjacency List: O(1)

Adding a vertex is extremely simple in an adjacency list:

self.vertices["H"] = set()

Adding a new key to a dictionary is a constant-time operation.

For an adjacency matrix, we would need to add a new value to the end of each existing row, then add a new row at the end.

for v in self.edges:
  self.edges[v].append(0)
v.append([0] * len(self.edges + 1))

Remember that with Python lists, appending to the end of a list is usually O(1) due to over-allocation of memory but can be O(n) when the over-allocated memory fills up. When this occurs, adding the vertex can be O(V²).

Takeaway: Adding vertices is very efficient in adjacency lists but very inefficient for adjacency matrices.

Remove Vertex

Adjacency Matrix: O(V ^ 2)
Adjacency List: O(V)

Removing vertices is pretty inefficient in both representations. In an adjacency matrix, we need to remove the removed vertex's row, then remove that column from each other row. Removing an element from a list requires moving everything after that element over by one slot which takes an average of V/2 operations. Since we need to do that for every single row in our matrix, that results in a V² time complexity. On top of that, we need to reduce the index of each vertex after our removed index by 1 as well which doesn't add to our quadratic time complexity, but does add extra operations.

For an adjacency list, we need to visit each vertex and remove all edges pointing to our removed vertex. Removing elements from sets and dictionaries is a O(1) operation, so this results in an overall O(V) time complexity.

Takeaway: Removing vertices is inefficient in both adjacency matrices and lists but more inefficient in matrices.

Add Edge

Adjacency Matrix: O(1)
Adjacency List: O(1)

Adding an edge in an adjacency matrix is quite simple:

self.edges[v1][v2] = 1

Adding an edge in an adjacency list is similarly simple:

self.vertices[v1].add(v2)

Both are constant-time operations.

Takeaway: Adding edges to both adjacency lists and matrices is very efficient.

Remove Edge

Adjacency Matrix: O(1)
Adjacency List: O(1)

Removing an edge from an adjacency matrix is quite simple:

self.edges[v1][v2] = 0

Removing an edge from an adjacency list is similarly simple:

self.vertices[v1].remove(v2)

Both are constant-time operations.

Takeaway: Removing edges from both adjacency lists and matrices is very efficient.

Find Edge

Adjacency Matrix: O(1)
Adjacency List: O(1)

Finding an edge in an adjacency matrix is quite simple:

return self.edges[v1][v2] > 0

Finding an edge in an adjacency list is similarly simple:

return v2 in self.vertices[v1]

Both are constant-time operations.

Takeaway: Finding edges from both adjacency lists and matrices is very efficient.

Get All Edges from Vertex

Adjacency Matrix: O(V)
Adjacency List: O(1)

Say you want to know all the edges originating from a particular vertex. With an adjacency list, this is as simple as returning the value from the vertex dictionary:

return self.vertex[v]

In an adjacency matrix, however, it's a bit more complicated. You would need to iterate through the entire row and populate a list based on the results:

v_edges = []
for v2 in self.edges[v]:
    if self.edges[v][v2] > 0:
        v_edges.append(v2)
return v_edges

Takeaway: Fetching all edges is more efficient in an adjacency list than an adjacency matrix.

Breadth-First Search

Can use breadth-first search when searching a graph; explores graph outward in rings of increasing distance from starting vertex; never attempts to explore vertex it is or has already explored

BFS

Applications of BFS

pathfinding, routing
web crawlers
find neighbor nodes in P2P network
finding people/connections away on social network
find neighboring locations on graph
broadcasting on a network
cycle detection in a graph
finding connected components
solving several theoretical graph problems

Coloring BFS

It's useful to color vertexes as you arrive at them and as you leave them behind as already searched.

unlisted: white

vertices whose neighbors are being explored: gray

vertices with no unexplored neighbors: black

BFS Pseudocode

    def BFS(graph, start_vert):
        for v of graph.vertices:
            v.color = white
        start_vert.color = gray
        queue.enqueue(start_vert)
        while !queue isEmpty():
        # peek at head but don't dequeue
        u = queue[0]
        for v of u.neighbors:
            if v.color == white:
                v.color == gray
                queue.enqueue(v)
        queue.dequeue()
        u.color = black

BFS Steps

Mark graph vertices white.
Mark starting vertex gray.
Enqueue starting vertex.
Check if queue is not empty.
If not empty, peek at first item in queue.
Loop through that vertex's neighbors.
Check if unvisited.
If unvisited, mark as gray and enqueue vertex.
Dequeue current vertex and mark as black.
Repeat until all vertices are explored.

Depth-First Search

dives down the graph as far as it can before backtracking and exploring another branch; never attempts to explore a vertex it has already explored or is in the process of exploring; exact order will vary depending on which branches get taken first and which is starting vertex

DFS

Applications of DFS

preferred method for exploring a graph if we want to ensure we visit every node in graph
finding minimum spanning trees of weighted graphs
pathfinding
detecting cycles in graphs
solving and generating mazes
topological sorting, useful for scheduling sequences of dependent jobs

DFS Pseudocode

    # recursion
    def explore(graph):
        visit(this_vert)
        explore(remaining_graph)

    # iterative
    def DFS(graph):
        for v of graph.verts:
            v.color = white
            v.parent = null
        for v of graph.verts:
            if v.color == white:
                DFS_visit(v)

    def DFS_visit(v):
        v.color = gray
        for neighbor of v.adjacent_nodes:
            if neighbor.color == white:
                neighbor.parent = v
                DFS_visit(neighbor)
        v.color = black

DFS Steps

Take graph as parameter.
Marks all vertices as unvisited.
Sets vertex parent as null.
Passes each unvisited vertex into DFS_visit().
Mark current vertex as gray.
Loops through its unvisited neighbors.
Sets parent and makes recursive call to DFS_visit().
Marks vertex as black.
Repeat until done.

Connected Components

connected components: in a disjoint graph, groups of nodes on a graph that are connected with each other

Uses

typically very large graphs, networks
social networks
networks (which devices can reach one another)
epidemics (how spread, who started, where next)

key to finding connected components: searching algorithms, breadth-first search

How to find connected componnents

for each node in graph:
has it been explored
if no, do BFS
all nodes reached are connected
if yes, already in connected component
go to next node

strongly connected components: any node in this group can get to any other node

Bonus Python Question

'''py

This Bellman-Ford Code is for determination whether we can get

shortest path from given graph or not for single-source shortest-paths problem.

In other words, if given graph has any negative-weight cycle that is reachable

from the source, then it will give answer False for "no solution exits".

For argument graph, it should be a dictionary type

such as

graph = {

'a': {'b': 6, 'e': 7},

'b': {'c': 5, 'd': -4, 'e': 8},

'c': {'b': -2},

'd': {'a': 2, 'c': 7},

'e': {'b': -3}

}

Review of Concepts

A graph is any collection of nodes and edges.
A graph is a less restrictive class of collections of nodes than structures like a tree.
It doesn't need to have a root node (not every node needs to be accessible from a single node)
It can have cycles (a group of nodes whose paths begin and end at the same node)

Cycles in a graph - Cycles are not always "isolated", they can be one part of a larger graph. You can detect them by starting your search on a specific node and finding a path that takes you back to that same node. - Any number of edges may leave a given node - A Path is a sequence of nodes on a graph ### Undirected Graph **Undirected Graph:** An undirected graph is one where the edges do not specify a particular direction. The edges are bi-directional. ### Types

Dense Graph

Dense Graph — A graph with lots of edges.
"Dense graphs have many edges. But, wait! 🚧 I know what you must be thinking, how can you determine what qualifies as "many edges"? This is a little bit too subjective, right? ? I agree with you, so let's quantify it a little bit:
Let's find the maximum number of edges in a directed graph. If there are |V| nodes in a directed graph (in the example below, six nodes), that means that each node can have up to |v| connections (in the example below, six connections).
Why? Because each node could potentially connect with all other nodes and with itself (see "loop" below). Therefore, the maximum number of edges that the graph can have is |V|\*|V| , which is the total number of nodes multiplied by the maximum number of connections that each node can have."
When the number of edges in the graph is close to the maximum number of edges, the graph is dense.

Sparse Graph

Sparse Graph — Few edges
When the number of edges in the graph is significantly fewer than the maximum number of edges, the graph is sparse.

Weighted Graph

Weighted Graph — Edges have a cost or a weight to traversal

Directed Graph

Directed Graph — Edges only go one direction

Undirected Graph

Undirected Graph — Edges don't have a direction. All graphs are assumed to be undirected unless otherwise stated

Node Class

Uses a class to define the neighbors as properties of each node.

Adjacency Matrix

The row index will correspond to the source of an edge and the column index will correspond to the edges destination.

When the edges have a direction, matrix[i][j] may not be the same as matrix[j][i]
It is common to say that a node is adjacent to itself so matrix[x][x] is true for any node
Will be O(n²) space complexity

Adjacency List

Seeks to solve the shortcomings of the matrix implementation. It uses an object where keys represent node labels and values associated with that key are the adjacent node keys held in an array.

Stacks

The Call Stack is a Stack data structure, and is used to manage the order of function invocations in your code.
Browser History is often implemented using a Stack, with one great example being the browser history object in the very popular React Router module.
Undo/Redo functionality in just about any application. For example:
When you're coding in your text editor, each of the actions you take on your keyboard are recorded by pushing that event to a Stack.
When you hit [cmd + z] to undo your most recent action, that event is poped off the Stack, because the last event that occured should be the first one to be undone (LIFO).
When you hit [cmd + y] to redo your most recent action, that event is pushed back onto the Stack.

Queues

Printers use a Queue to manage incoming jobs to ensure that documents are printed in the order they are received.
Chat rooms, online video games, and customer service phone lines use a Queue to ensure that patrons are served in the order they arrive.
In the case of a Chat Room, to be admitted to a size-limited room.
In the case of an Online Multi-Player Game, players wait in a lobby until there is enough space and it is their turn to be admitted to a game.
In the case of a Customer Service Phone Line…you get the point.
As a more advanced use case, Queues are often used as components or services in the system design of a service-oriented architecture. A very popular and easy to use example of this is Amazon's Simple Queue Service (SQS), which is a part of their Amazon Web Services (AWS) offering.
You would add this service to your system between two other services, one that is sending information for processing, and one that is receiving information to be processed, when the volume of incoming requests is high and the integrity of the order with which those requests are processed must be maintained.

Further resources:

bgoonz's gists

Instantly share code, notes, and snippets. Web Developer, Electrical Engineer JavaScript | CSS | Bootstrap | Python |…gist.github.com

Data Structures Reference

Data Structures… Under The Hood

Data Structures Reference

Array

Stores things in order. Has quick lookups by index.

Linked List

Also stores things in order. Faster insertions and deletions than

arrays, but slower lookups (you have to "walk down" the whole list).

Queue

Like the line outside a busy restaurant. "First come, first served."

Stack

Like a stack of dirty plates in the sink. The first one you take off the

top is the last one you put down.

Tree

Good for storing hierarchies. Each node can have "child" nodes.

Binary Search Tree

Everything in the left subtree is smaller than the current node,

everything in the right subtree is larger. lookups, but only if the tree

is balanced!

Binary Search Tree

Graph

Good for storing networks, geography, social relationships, etc.

Heap

A binary tree where the smallest value is always at the top. Use it to implement a priority queue.

![A binary heap is a binary tree where the nodes are organized to so that the smallest value is always at the top.]

Adjacency list

A list where the index represents the node and the value at that index is a list of the node's neighbors:

graph = [ [1], [0, 2, 3], [1, 3], [1, 2], ]

Since node 3 has edges to nodes 1 and 2, graph[3] has the adjacency list [1, 2].

We could also use a dictionary where the keys represent the node and the values are the lists of neighbors.

graph = { 0: [1], 1: [0, 2, 3], 2: [1, 3], 3: [1, 2], }

This would be useful if the nodes were represented by strings, objects, or otherwise didn't map cleanly to list indices.

Adjacency matrix

A matrix of 0s and 1s indicating whether node x connects to node y (0 means no, 1 means yes).

graph = [ [0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0], ]

Since node 3 has edges to nodes 1 and 2, graph[3][1] and graph[3][2] have value 1.

a = LinkedListNode(5) b = LinkedListNode(1) c = LinkedListNode(9) a.next = b b.next = c

Arrays

Ok, so we know how to store individual numbers. Let's talk about storing several numbers.

That's right, things are starting to heat up.

Suppose we wanted to keep a count of how many bottles of kombucha we drink every day.

Let's store each day's kombucha count in an 8-bit, fixed-width, unsigned integer. That should be plenty — we're not likely to get through more than 256 (2⁸) bottles in a single day, right?

And let's store the kombucha counts right next to each other in RAM, starting at memory address 0:

Bam. That's an **array**. RAM is*basically* an array already. Just like with RAM, the elements of an array are numbered. We call that number the **index** of the array element (plural: indices). In _this_ example, each array element's index is the same as its address in RAM. But that's not usually true. Suppose another program like Spotify had already stored some information at memory address 2: We'd have to start our array below it, for example at memory address 3. So index 0 in our array would be at memory address 3, and index 1 would be at memory address 4, etc.: Suppose we wanted to get the kombucha count at index 4 in our array. How do we figure out what*address in memory* to go to? Simple math: Take the array's starting address (3), add the index we're looking for (4), and that's the address of the item we're looking for. 3 + 4 = 7. In general, for getting the nth item in our array: \\text{address of nth item in array} = \\text{address of array start} + n This works out nicely because the size of the addressed memory slots and the size of each kombucha count are _both_ 1 byte. So a slot in our array corresponds to a slot in RAM. But that's not always the case. In fact, it's _usually not_ the case. We _usually_ use _64-bit_ integers. So how do we build an array of _64-bit_ (8 byte) integers on top of our _8-bit_ (1 byte) memory slots? We simply give each array index _8_ address slots instead of 1: So we can still use simple math to grab the start of the nth item in our array — just gotta throw in some multiplication: \\text{address of nth item in array} = \\text{address of array start} + (n \* \\text{size of each item in bytes}) Don't worry — adding this multiplication doesn't really slow us down. Remember: addition, subtraction, multiplication, and division of fixed-width integers takes time. So _all_ the math we're using here to get the address of the nth item in the array takes time. And remember how we said the memory controller has a _direct connection_ to each slot in RAM? That means we can read the stuff at any given memory address in time. **Together, this means looking up the contents of a given array index is time.** This fast lookup capability is the most important property of arrays. But the formula we used to get the address of the nth item in our array only works _if_: 1. **Each item in the array is the _same size_** (takes up the same number of bytes). 1. **The array is _uninterrupted_ (contiguous) in memory**. There can't be any gaps in the array…like to "skip over" a memory slot Spotify was already using. These things make our formula for finding the nth item _work_ because they make our array _predictable_. We can _predict_ exactly where in memory the nth element of our array will be. But they also constrain what kinds of things we can put in an array. Every item has to be the same size. And if our array is going to store a _lot_ of stuff, we'll need a _bunch_ of uninterrupted free space in RAM. Which gets hard when most of our RAM is already occupied by other programs (like Spotify). That's the tradeoff. Arrays have fast lookups ( time), but each item in the array needs to be the same size, and you need a big block of uninterrupted free memory to store the array. -------- ## Pointers Remember how we said every item in an array had to be the same size? Let's dig into that a little more. Suppose we wanted to store a bunch of ideas for baby names. Because we've got some _really_ cute ones. Each name is a string. Which is really an array. And now we want to store _those arrays_ in an array. _Whoa_. Now, what if our baby names have different lengths? That'd violate our rule that all the items in an array need to be the same size! We could put our baby names in arbitrarily large arrays (say, 13 characters each), and just use a special character to mark the end of the string within each array… "Wigglesworth" is a cute baby name, right? But look at all that wasted space after "Bill". And what if we wanted to store a string that was _more_ than 13 characters? We'd be out of luck. There's a better way. Instead of storing the strings right inside our array, let's just put the strings wherever we can fit them in memory. Then we'll have each element in our array hold the _address in memory_ of its corresponding string. Each address is an integer, so really our outer array is just an array of integers. We can call each of these integers a **pointer**, since it points to another spot in memory. The pointers are marked with a \* at the beginning. Pretty clever, right? This fixes _both_ the disadvantages of arrays: 1. The items don't have to be the same length — each string can be as long or as short as we want. 1. We don't need enough uninterrupted free memory to store all our strings next to each other — we can place each of them separately, wherever there's space in RAM. We fixed it! No more tradeoffs. Right? Nope. Now we have a _new_ tradeoff: Remember how the memory controller sends the contents of _nearby_ memory addresses to the processor with each read? And the processor caches them? So reading sequential addresses in RAM is _faster_ because we can get most of those reads right from the cache? Our original array was very **cache-friendly**, because everything was sequential. So reading from the 0th index, then the 1st index, then the 2nd, etc. got an extra speedup from the processor cache. **But the pointers in this array make it _not_ cache-friendly**, because the baby names are scattered randomly around RAM. So reading from the 0th index, then the 1st index, etc. doesn't get that extra speedup from the cache. That's the tradeoff. This pointer-based array requires less uninterrupted memory and can accommodate elements that aren't all the same size, _but_ it's _slower_ because it's not cache-friendly. This slowdown isn't reflected in the big O time cost. Lookups in this pointer-based array are _still_ time. -------- ### Linked lists Our word processor is definitely going to need fast appends — appending to the document is like the _main thing_ you do with a word processor. Can we build a data structure that can store a string, has fast appends, _and_ doesn't require you to say how long the string will be ahead of time? Let's focus first on not having to know the length of our string ahead of time. Remember how we used _pointers_ to get around length issues with our array of baby names? What if we pushed that idea even further? What if each _character_ in our string were a _two-index array_ with: 1. the character itself 2. a pointer to the next character We would call each of these two-item arrays a **node** and we'd call this series of nodes a **linked list**. Here's how we'd actually implement it in memory: Notice how we're free to store our nodes wherever we can find two open slots in memory. They don't have to be next to each other. They don't even have to be*in order*: "But that's not cache-friendly, " you may be thinking. Good point! We'll get to that. The first node of a linked list is called the **head**, and the last node is usually called the **tail**. Confusingly, some people prefer to use "tail" to refer to _everything after the head_ of a linked list. In an interview it's fine to use either definition. Briefly say which definition you're using, just to be clear. It's important to have a pointer variable referencing the head of the list — otherwise we'd be unable to find our way back to the start of the list! We'll also sometimes keep a pointer to the tail. That comes in handy when we want to add something new to the end of the linked list. In fact, let's try that out: Suppose we had the string "LOG" stored in a linked list: Suppose we wanted to add an "S" to the end, to make it "LOGS". How would we do that? Easy. We just put it in a new node: And tweak some pointers: 1. Grab the last letter, which is "G". Our tail pointer lets us do this in time. 2. Point the last letter's next to the letter we're appending ("S"). 3. Update the tail pointer to point to our*new* last letter, "S". That's time. Why is it time? Because the runtime doesn't get bigger if the string gets bigger. No matter how many characters are in our string, we still just have to tweak a couple pointers for any append. Now, what if instead of a linked list, our string had been a _dynamic array_? We might not have any room at the end, forcing us to do one of those doubling operations to make space: So with a dynamic array, our append would have a*worst-case* time cost of . **Linked lists have worst-case -time appends, which is better than the worst-case time of dynamic arrays.** That _worst-case_ part is important. The _average case_ runtime for appends to linked lists and dynamic arrays is the same: . Now, what if we wanted to \*pre\*pend something to our string? Let's say we wanted to put a "B" at the beginning. For our linked list, it's just as easy as appending. Create the node: And tweak some pointers: 1. Point "B"'s next to "L". 2. Point the head to "B". Bam. time again. But if our string were a _dynamic array_… And we wanted to add in that "B": Eep. We have to*make room* for the "B"! We have to move _each character_ one space down: *Now* we can drop the "B" in there: What's our time cost here? It's all in the step where we made room for the first letter. We had to move _all n_ characters in our string. One at a time. That's time. **So linked lists have faster \*pre\*pends ( time) than dynamic arrays ( time).** No "worst case" caveat this time — prepends for dynamic arrays are _always_ time. And prepends for linked lists are _always_ time. These quick appends and prepends for linked lists come from the fact that linked list nodes can go anywhere in memory. They don't have to sit right next to each other the way items in an array do. So if linked lists are so great, why do we usually store strings in an array? **Because** arrays have -time lookups **.** And those constant-time lookups _come from_ the fact that all the array elements are lined up next to each other in memory. Lookups with a linked list are more of a process, because we have no way of knowing where the ith node is in memory. So we have to walk through the linked list node by node, counting as we go, until we hit the ith item. def get_ith_item_in_linked_list(head, i): if i < 0: raise ValueError("i can't be negative: %d" % i) current_node = head current_position = 0 while current_node: if current_position == i: \# Found it! return current_node \# Move on to the next node current_node = current_node.next current_position += 1 raise ValueError('List has fewer than i + 1 (%d) nodes' % (i + 1)) That's i + 1 steps down our linked list to get to the ith node (we made our function zero-based to match indices in arrays). **So linked lists have -time lookups.** Much slower than the -time lookups for arrays and dynamic arrays. Not only that — **walking down a linked list is _not_ cache-friendly.** Because the next node could be _anywhere_ in memory, we don't get any benefit from the processor cache. This means lookups in a linked list are even slower. So the tradeoff with linked lists is they have faster prepends and faster appends than dynamic arrays, _but_ they have slower lookups. -------- ## Doubly Linked Lists In a basic linked list, each item stores a single pointer to the next element. In a **doubly linked list**, items have pointers to the next _and the previous_ nodes. Doubly linked lists allow us to traverse our list*backwards*. In a*singly*linked list, if you just had a pointer to a node in the*middle*of a list, there would be*no way* to know what nodes came before it. Not a problem in a doubly linked list. ### Not cache-friendly Most computers have caching systems that make reading from sequential addresses in memory faster than reading from scattered addresses. Array items are always located right next to each other in computer memory, but linked list nodes can be scattered all over. So iterating through a linked list is usually quite a bit slower than iterating through the items in an array, even though they're both theoretically time. -------- ### Hash tables Quick lookups are often really important. For that reason, we tend to use arrays (-time lookups) much more often than linked lists (-time lookups). For example, suppose we wanted to count how many times each ASCII character appears in Romeo and Juliet. How would we store those counts? We can use arrays in a clever way here. Remember — characters are just numbers. In ASCII (a common character encoding) 'A' is 65, 'B' is 66, etc. So we can use the character('s number value) as the _index_ in our array, and store the _count_ for that character _at that index_ in the array: With this array, we can look up (and edit) the count for any character in constant time. Because we can access any index in our array in constant time. Something interesting is happening here — this array isn't just a list of values. This array is storing _two_ things: characters and counts. The characters are _implied_ by the indices. **So we can think of an array as a _table_ with _two columns_…except you don't really get to pick the values in one column (the indices) — they're always 0, 1, 2, 3, etc.** But what if we wanted to put _any_ value in that column and still get quick lookups? Suppose we wanted to count the number of times each _word_ appears in Romeo and Juliet. Can we adapt our array? Translating a _character_ into an array index was easy. But we'll have to do something more clever to translate a _word_ (a string) into an array index… Here's one way we could do it: Grab the number value for each character and add those up. The result is 429. But what if we only have*30* slots in our array? We'll use a common trick for forcing a number into a specific range: the modulus operator (%). Modding our sum by 30 ensures we get a whole number that's less than 30 (and at least 0): 429 \\: \\% \\: 30 = 9 Bam. That'll get us from a word (or any string) to an array index. This data structure is called a **hash table** or **hash map**. In our hash table, the _counts_ are the **values** and the _words_ ("lies, " etc.) are the **keys** (analogous to the _indices_ in an array). The process we used to translate a key into an array index is called a **hashing function**. !\[A blank array except for a 20, labeled as the value, stored at index 1. To the left the array is the word "lies," labeled as the key, with an arrow pointing to the right at diamond with a question mark in the middle, labeled as the hashing function. The diamond points to the 9th index of the array.\](https://www.interviewcake.com/images/svgs/cs_for_hackers\_\_hash_tables_lies_key_labeled.svg?bust=209) The hashing functions used in modern systems get pretty complicated — the one we used here is a simplified example. Note that our quick lookups are only in one direction — we can quickly get the value for a given key, but the only way to get the key for a given value is to walk through all the values and keys. Same thing with arrays — we can quickly look up the value at a given index, but the only way to figure out the index for a given value is to walk through the whole array. One problem — what if two keys hash to the same index in our array? Look at "lies" and "foes": They both sum up to 429! So of course they'll have the same answer when we mod by 30: 429 \\: \\% \\: 30 = 9 So our hashing function gives us the same answer for "lies" and "foes." This is called a **hash collision**. There are a few different strategies for dealing with them. Here's a common one: instead of storing the actual values in our array, let's have each array slot hold a _pointer_ to a _linked list_ holding the counts for all the words that hash to that index: One problem — how do we know which count is for "lies" and which is for "foes"? To fix this, we'll store the*word* as well as the count in each linked list node: "But wait!" you may be thinking, "Now lookups in our hash table take time in the worst case, since we have to walk down a linked list." That's true! You could even say that in the worst case*every*key creates a hash collision, so our whole hash table*degrades to a linked list*. In industry though, we usually wave our hands and say **collisions are rare enough that on _average_ lookups in a hash table are time**. And there are fancy algorithms that keep the number of collisions low and keep the lengths of our linked lists nice and short. But that's sort of the tradeoff with hash tables. You get fast lookups by key…except _some_ lookups could be slow. And of course, you only get those fast lookups in one direction — looking up the _key_ for a given _value_ still takes time ### Breadth-First Search (BFS) and Breadth-First Traversal **Breadth-first search** (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc. Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore "ripple out" from the starting point. Here's a how a BFS would traverse this tree, starting with the root: We'd visit all the immediate children (all the nodes that're one step away from our starting node): Then we'd move on to all*those*nodes' children (all the nodes that're*two steps* away from our starting node): And so on: Until we reach the end. Breadth-first search is often compared with **depth-first search**. Advantages: - A BFS will find the **shortest path** between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path. Disadvantages - A BFS on a binary tree _generally_ requires more memory than a DFS.

Binary Search Tree

A binary tree is a tree where <==(every node has two or fewer children)==>.

The children are usually called left and right.

class BinaryTreeNode(object):

This lets us build a structure like this:

That particular example is special because every level of the tree is completely full. There are no "gaps." We call this kind of tree "perfect."

Binary trees have a few interesting properties when they're perfect:

Property 1: the number of total nodes on each "level" doubles as we move down the tree.

Property 2: the number of nodes on the last level is equal to the sum of the number of nodes on all other levels (plus 1). In other words, about*half* of our nodes are on the last level.

<==(**Let's call the number of nodes n, **)==>

<==(_and the height of the tree h. _)==>

h can also be thought of as the "number of levels."

If we had h, how could we calculate n?

Let's just add up the number of nodes on each level!

If we zero-index the levels, the number of nodes on the xth level is exactly 2^x.

Level 0: 2⁰ nodes,
2. Level 1: 2¹ nodes,
3. Level 2: 2² nodes,
4. Level 3: 2³ nodes,
5. etc

So our total number of nodes is:

n = 2⁰ + 2¹ + 2² + 2³ + … + 2^{h-1}

Why only up to 2^{h-1}?

Notice that we started counting our levels at 0.

So if we have h levels in total,
the last level is actually the "h-1"-th level.
That means the number of nodes on the last level is 2^{h-1}.

But we can simplify.

Property 2 tells us that the number of nodes on the last level is (1 more than) half of the total number of nodes,

so we can just take the number of nodes on the last level, multiply it by 2, and subtract 1 to get the number of nodes overall.

We know the number of nodes on the last level is 2^{h-1},
So:

n = 2^{h-1} * 2–1

n = 2^{h-1} * 2¹ — 1

n = 2^{h-1+1}- 1

n = 2^{h} — 1

So that's how we can go from h to n. What about the other direction?

We need to bring the h down from the exponent.

That's what logs are for!

First, some quick review.

<==(log_{10} (100) )==>

simply means,

"What power must you raise 10 to in order to get 100?".

Which is 2,

because .

<==(10² = 100 )==>

Graph Data Structure: Directed, Acyclic, etc

Graph =====

Binary numbers

Let's put those bits to use. Let's store some stuff. Starting with numbers.

The number system we usually use (the one you probably learned in elementary school) is called base 10, because each digit has ten possible values (1, 2, 3, 4, 5, 6, 7, 8, 9, and 0).

But computers don't have digits with ten possible values. They have bits with two possible values. So they use base 2 numbers.

Base 10 is also called decimal. Base 2 is also called binary.

To understand binary, let's take a closer look at how decimal numbers work. Take the number "101" in decimal:

Notice we have two "1"s here, but they don't*mean*the same thing. The leftmost "1"means*100, and the rightmost "1"*means 1. That's because the leftmost "1" is in the hundreds place, while the rightmost "1" is in the ones place. And the "0" between them is in the tens place.

So this "101" in base 10 is telling us we have "1 hundred, 0 tens, and 1 one."

Notice how the*places*in base 10 (ones place, tens place, hundreds place, etc.) are*sequential powers of 10*:

10⁰=1 * 10¹=10 * 10²=100 * 10³=1000 * etc.

The places in binary (base 2) are sequential powers of 2:

2⁰=1 * 2¹=2 * 2²=4 * 2³=8 * etc.

So let's take that same "101" but this time let's read it as a binary number:

Reading this from right to left: we have a 1 in the ones place, a 0 in the twos place, and a 1 in the fours place. So our total is 4 + 0 + 1 which is 5.

Implementations

Resources (article content below):

Videos

Abdul Bari: YouTubeChannel for Algorithms
Data Structures and algorithms
Data Structures and algorithms Course
Khan Academy
Data structures by mycodeschoolPre-requisite for this lesson is good understanding of pointers in C.
MIT 6.006: Intro to Algorithms(2011)
Data Structures and Algorithms by Codewithharry

Books

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Competitive Programming 3 by Steven Halim and Felix Halim
Competitive Programmers Hand Book Beginner friendly hand book for competitive programmers.
Data Structures and Algorithms Made Easy by Narasimha Karumanchi
Learning Algorithms Through Programming and Puzzle Solving by Alexander Kulikov and Pavel Pevzner

Coding practice

Courses

Master the Coding Interview: Big Tech (FAANG) Interviews Course by Andrei and his team.
Common Python Data Structures Data structures are the fundamental constructs around which you build your programs. Each data structure provides a particular way of organizing data so it can be accessed efficiently, depending on your use case. Python ships with an extensive set of data structures in its standard library.
Fork CPP A good course for beginners.
EDU Advanced course.
C++ For Programmers Learn features and constructs for C++.

Guides

GeeksForGeeks --- A CS portal for geeks
Learneroo --- Algorithms
Top Coder tutorials
Infoarena training path (RO)
Steven & Felix Halim --- Increasing the Lower Bound of Programming Contests (UVA Online Judge)

space

The space complexity represents the memory consumption of a data structure. As for most of the things in life, you can't have it all, so it is with the data structures. You will generally need to trade some time for space or the other way around.

time

The time complexity for a data structure is in general more diverse than its space complexity.

Several operations

In contrary to algorithms, when you look at the time complexity for data structures you need to express it for several operations that you can do with data structures. It can be adding elements, deleting elements, accessing an element or even searching for an element.

Dependent on data

Something that data structure and algorithms have in common when talking about time complexity is that they are both dealing with data. When you deal with data you become dependent on them and as a result the time complexity is also dependent of the data that you received. To solve this problem we talk about 3 different time complexity.

The best-case complexity: when the data looks the best
The worst-case complexity: when the data looks the worst
The average-case complexity: when the data looks average

Big O notation

The complexity is usually expressed with the Big O notation. The wikipedia page about this subject is pretty complex but you can find here a good summary of the different complexity for the most famous data structures and sorting algorithms.

The Array data structure

Definition

An Array data structure, or simply an Array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. The simplest type of data structure is a linear array, also called one-dimensional array. From Wikipedia

Arrays are among the oldest and most important data structures and are used by every program. They are also used to implement many other data structures.

Complexity\
Average\
Access Search Insertion Deletion

O(1) O(n) O(1) O(n)

view raw ArrayADT.js hosted with ❤ by GitHub

indexvalue0 ... this is the first value, stored at zero position

The index of an array runs in sequence

2. This could be useful for storing data that are required to be ordered, such as rankings or queues

3. In JavaScript, array's value could be mixed; meaning value of each index could be of different data, be it String, Number or even Objects

view raw arrays.js hosted with ❤ by GitHub

2. Objects

Think of objects as a logical grouping of a bunch of properties.

Properties could be some variable that it's storing or some methods that it's using.

I also visualize an object as a table.

The main difference is that object's "index" need not be numbers and is not necessarily sequenced.

https://gist.github.com/bgoonz/ed42c5c0f3a1a7757b33b437a9ad7129#file-object-js %}

view raw object.js hosted with ❤ by GitHub

The Hash Table

Definition

A Hash Table (Hash Map) is a data structure used to implement an associative array, a structure that can map keys to values. A Hash Table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. From Wikipedia

Hash Tables are considered the more efficient data structure for lookup and for this reason, they are widely used.

Complexity\
Average\
Access Search Insertion Deletion

O(1) O(1) O(1)

The code

Note, here I am storing another object for every hash in my Hash Table.

view raw hashtable.js hosted with ❤ by GitHub

The Set

Sets

Sets are pretty much what it sounds like. It's the same intuition as Set in Mathematics. I visualize Sets as Venn Diagrams.

view raw native-set.js hosted with ❤ by GitHub

Definition

A Set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite Set. From Wikipedia

The Set data structure is usually used to test whether elements belong to set of values. Rather then only containing elements, Sets are more used to perform operations on multiple values at once with methods such as union, intersect, etc...

Complexity\
Average\
Access Search Insertion Deletion

O(n) O(n) O(n)

The code >

view raw setADS.js hosted with ❤ by GitHub

The Singly Linked List

Definition

A Singly Linked List is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence.

Linked Lists are among the simplest and most common data structures because it allows for efficient insertion or removal of elements from any position in the sequence.

Complexity\
Average\
Access Search Insertion Deletion\
O(n) O(n) O(1) O(1)

The code

view raw singly-linked-list.js hosted with ❤ by GitHub

The Doubly Linked List

Definition

A Doubly Linked List is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. From Wikipedia

Having two node links allow traversal in either direction but adding or removing a node in a doubly linked list requires changing more links than the same operations on a Singly Linked List.

Complexity\
Average\
Access Search Insertion Deletion\
O(n) O(n) O(1) O(1)

The code >

view raw doubly-linked-list.js hosted with ❤ by GitHub

The Stack

Definition

A Stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a Stack gives rise to its alternative name, LIFO (for last in, first out). From Wikipedia

A Stack often has a third method peek which allows to check the last pushed element without popping it.

Complexity\
Average\
Access Search Insertion Deletion\
O(n) O(n) O(1) O(1)

The code >

view raw stack.js hosted with ❤ by GitHub

The Queue

Definition

A Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal operations are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the Queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the Queue will be the first one to be removed.

As for the Stack data structure, a peek operation is often added to the Queue data structure. It returns the value of the front element without dequeuing it.

Complexity\
Average\
Access Search Insertion Deletion\
O(n) O(n) O(1) O(n)

The code >

view raw queue.js hosted with ❤ by GitHub

The Tree

Definition

A Tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root node. From Wikipedia

Complexity\
Average\
Access Search Insertion Deletion\
O(n) O(n) O(n) O(n)\
To get a full overview of the time and space complexity of the Tree data structure, have a look to this excellent Big O cheat sheet.

The code >

view raw bst.js hosted with ❤ by GitHub

The Graph

Definition

A Graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected Graph or a set of ordered pairs for a directed Graph. These pairs are known as edges, arcs, or lines for an undirected Graph and as arrows, directed edges, directed arcs, or directed lines for a directed Graph. The vertices may be part of the Graph structure, or may be external entities represented by integer indices or references.

A graph is any collection of nodes and edges.
Much more relaxed in structure than a tree.
It doesn't need to have a root node (not every node needs to be accessible from a single node)
It can have cycles (a group of nodes whose paths begin and end at the same node)
Cycles are not always "isolated", they can be one part of a larger graph. You can detect them by starting your search on a specific node and finding a path that takes you back to that same node.
Any number of edges may leave a given node
A Path is a sequence of nodes on a graph

Cycle Visual

A Graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Representation\
There are different ways of representing a graph, each of them with its own advantages and disadvantages. Here are the main 2:

Adjacency list: For every vertex a list of adjacent vertices is stored. This can be viewed as storing the list of edges. This data structure allows the storage of additional data on the vertices and edges.\
Adjacency matrix: Data are stored in a two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. The data on the edges and vertices must be stored externally.

Ways to Reference Graph Nodes

Node Class

Uses a class to define the neighbors as properties of each node.

class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

let a = new GraphNode("a");
let b = new GraphNode("b");
let c = new GraphNode("c");
let d = new GraphNode("d");
let e = new GraphNode("e");
let f = new GraphNode("f");
a.neighbors = [e, c, b];
c.neighbors = [b, d];
e.neighbors = [a];
f.neighbors = [e];

Adjacency Matrix

The row index will corespond to the source of an edge and the column index will correspond to the edges destination.

When the edges have a direction, matrix[i][j] may not be the same as matrix[j][i]
It is common to say that a node is adjacent to itself so matrix[x][x] is true for any node
Will be O(n^2) space complexity

let matrix = [

|       | **A**   | **B**  | **C**  | **D**  | **E**  | **F**  |
| ----- | ------- | ------ | ------ | ------ | ------ | ------ |
| **A** | [True,  | True,  | True,  | False, | True,  | False] |
| **B** | [False, | True,  | False, | False, | False, | False] |
| **C** | [False, | True,  | True,  | True,  | False, | False] |
| **D** | [False, | False, | False, | True,  | False, | False] |
| **E** | [True,  | False, | False, | False, | True,  | False] |
| **F** | [False, | False, | False, | False, | True,  | True]  |

];

Adjacency List

Seeks to solve the shortcomings of the matrix implementation. It uses an object where keys represent node labels and values associated with that key are the adjacent node keys held in an array.

let graph = {
  a: ["b", "c", "e"],
  b: [],
  c: ["b", "d"],
  d: [],
  e: ["a"],
  f: ["e"],
};

Code Examples

Basic Graph Class

class Graph {
  constructor() {
    this.adjList = {};
  }

  addVertex(vertex) {
    if (!this.adjList[vertex]) this.adjList[vertex] = [];
  }

  addEdges(srcValue, destValue) {
    this.addVertex(srcValue);
    this.addVertex(destValue);
    this.adjList[srcValue].push(destValue);
    this.adjList[destValue].push(srcValue);
  }

  buildGraph(edges) {
    edges.forEach((ele) => {
      this.addEdges(ele[0], ele[1]);
    });
    return this.adjList;
  }

  breadthFirstTraversal(startingVertex) {
    const queue = [startingVertex];
    const visited = new Set();
    const result = new Array();

    while (queue.length) {
      const value = queue.shift();
      if (visited.has(value)) continue;
      result.push(value);
      visited.add(value);
      queue.push(...this.adjList[value]);
    }
    return result;
  }

  depthFirstTraversalIterative(startingVertex) {
    const stack = [startingVertex];
    const visited = new Set();
    const result = new Array();

    while (stack.length) {
      const value = stack.pop();
      if (visited.has(value)) continue;
      result.push(value);
      visited.add(value);
      stack.push(...this.adjList[value]);
    }
    return result;
  }

  depthFirstTraversalRecursive(
    startingVertex,
    visited = new Set(),
    vertices = []
  ) {
    if (visited.has(startingVertex)) return [];

    vertices.push(startingVertex);
    visited.add(startingVertex);

    this.adjList[startingVertex].forEach((vertex) => {
      this.depthFirstTraversalRecursive(vertex, visited, vertices);
    });
    return [...vertices];
  }

Node Class Examples

class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

function breadthFirstSearch(startingNode, targetVal) {
  const queue = [startingNode];
  const visited = new Set();

  while (queue.length) {
    const node = queue.shift();
    if (visited.has(node.val)) continue;
    visited.add(node.val);
    if (node.val === targetVal) return node;
    node.neighbors.forEach((ele) => queue.push(ele));
  }
  return null;
}

function numRegions(graph) {
  let maxLength = 0;
  for (node in graph) {
    if (graph[node].length > maxLength) maxLength = graph[node].length;
  }
  if (maxLength === 0) {
    return (length = Object.keys(graph).length);
  } else {
    return maxLength;
  }
}

function maxValue(node, visited = new Set()) {
  let queue = [node];
  let maxValue = 0;
  while (queue.length) {
    let currentNode = queue.shift();
    if (visited.has(currentNode.val)) continue;
    visited.add(currentNode.val);
    if (currentNode.val > maxValue) maxValue = currentNode.val;
    currentNode.neighbors.forEach((ele) => queue.push(ele));
  }
  return maxValue;
}

Traversal Examples

With Graph Node Class

function depthFirstRecur(node, visited = new Set()) {
  if (visited.has(node.val)) return;

  console.log(node.val);
  visited.add(node.val);

  node.neighbors.forEach((neighbor) => {
    depthFirstRecur(neighbor, visited);
  });
}

function depthFirstIter(node) {
  let visited = new Set();
  let stack = [node];

  while (stack.length) {
    let node = stack.pop();

    if (visited.has(node.val)) continue;

    console.log(node.val);
    visited.add(node.val);

    stack.push(...node.neighbors);
  }
}

With Adjacency List

function depthFirst(graph) {
  let visited = new Set();

  for (let node in graph) {
    _depthFirstRecur(node, graph, visited);
  }
}

function _depthFirstRecur(node, graph, visited) {
  if (visited.has(node)) return;

  console.log(node);
  visited.add(node);

  graph[node].forEach((neighbor) => {
    _depthFirstRecur(neighbor, graph, visited);
  });
}

view raw graph-representation.md hosted with ❤ by GitHub

Graph

The code

view raw graph.js hosted with ❤ by GitHub

Memoization & Tabulation (Dynamic Programming)

What is Memoization?

And why this programming paradigm shouldn't make you cringe

Memoization is a design paradigm used to reduce the overall number of

calculations that can occur in algorithms that use recursive algorithms.

Recall that recursion solves a large problem by dividing it into smaller

sub-problems that are more manageable.

Memoization will store the results of the sub-problems in some other data structure, meaning that you avoid duplicate calculations and only "solve" each subproblem once.

This approach is near synonymous with another computer science term you may have heard before — caching. However, caching as a practice is not achieved exclusively by memoizing. Think of a cache as a little bucket where we will keep important information we don't want to forget in the near future but that isn't vitally important or part of the long-term makeup of our application. It's less important than the things we need to store in memory but more important than a variable we can discard as soon as we use it once.

There are two features that comprise memoization:

The function is recursive.
The additional data structure used is typically an object (we refer to this as
the memo).

This is a trade-off between the time it takes to run an algorithm (without

memoization) and the memory used to run the algorithm (with memoization).

Usually, memoization is a good trade-off when dealing with large data or

calculations.

You cannot always apply this technique to recursive problems. The problem must have an "overlapping subproblem structure" for memoization to be effective.

Generally speaking, computer memory is cheap and human time is incalculably valuable so we may opt for this approach even when the largest gains on paper can be made from converting RAM at the expense of execution speed.

Here's an example of a problem that has such a structure:

Using pennies, nickels, dimes, and quarters, how many combinations

of coins are there that total 27 cents?

Along the way to calculating the possible coin combination of 27

cents, you should also calculate the smallest coin combination of 25 cents as well as 21 cents and any smaller total that comprises a fraction of the total combination of 27 (so long as there is a one-cent piece; if there are only nickels and up, the problem deviates from this approach on a technicality but in essence, it is still calculated in the same manner, that is to say as a component of that bigger problem).

Remember, a computer is stupid and must check every possibility exhaustively to ensure that no possible combination is missed (in reality, I may be oversimplifying the truth of the matter but for now, please bear with me).

This is the essence of a redundant subcomponent of the overall problem.

Memoizing factorial

From this plain factorial above, it is clear that every time you call

factorial(6) you should get the same result of 720 each time. The code is

somewhat inefficient because you must go down the full recursive stack for each top-level call to factorial(6).

If we can store the result of factorial(6) the first time you calculate it, then on subsequent calls to factorial(6) you simply fetch the stored result in constant time.

The memo object above will map an argument of factorial to its return

value. That is, the keys will be arguments and their values will be the

corresponding results returned. By using the memo, you are able to avoid

duplicate recursive calls!

By the time your first call to factorial(6)returns, you will not have just the argument 6 stored in the memo. Rather, y*ou will have all arguments 2 to 6 stored in the memo.*

Perhaps you're not convinced because:

You didn't improve the speed of the algorithm by an order of Big-O (it is
still O(n)).
The code uses some global variable, so it's kind of ugly.

Memoizing the Fibonacci generator

Here's a naive implementation of a function that calculates the Fibonacci

number for a given input.

function fib(n) {
  if (n === 1 || n === 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

fib(6);     // => 8

The time complexity of this function is not super intuitive to describe because

the code branches twice recursively. Fret not! You'll find it useful to

visualize the calls needed to do this with a tree. When reasoning about the time complexity for recursive functions, draw a tree that helps you see the calls. Every node of the tree represents a call of the recursion:

- *n *, the height of this tree will be n. You derive this by following

the path going straight down the left side of the tree.

each internal node leads to two more nodes. Overall, this means that the tree will have roughly 2n nodes.
which is the same as saying that the fibfunction has an exponential time complexity of 2n.
That is very slow!

See for yourself, try running fib(50) - you'll be waiting for quite a lot longer than you've gotten used to waiting for a program to run in the last decade.

The green regions highlighted above are repetitive.

As the n grows bigger, the number of duplicate sub-trees grows exponentially.

Luckily you can fix this using memoization by using a similar object strategy.

You can use some JavaScript default arguments memo={} to clean things up:

You can see the marked nodes (function calls) that access the memo in green.

It's easy to see that this version of the Fibonacci generator will do far fewer

computations as n grows larger! In fact, this memoization has brought the time complexity down to linear O(n) time because the tree only branches on the left side. This is an enormous gain if you recall the complexity of class hierarchy.

The memoization formula

Now that you understand memoization, when should you apply it? Memoization is useful when attacking recursive problems that have many overlapping sub-problems.

You'll find it most useful to draw out the visual tree first. If you notice duplicate sub-trees, time to memoize. Here are the hard and fast

rules you can use to memoize a slow algorithm:

Write the unoptimized, brute force recursion and make sure it works.
Add the memo object as an additional argument to the function. The keys will
represent unique arguments to the function, and their values will represent the results for those arguments.
Add a base case condition to the function that returns the stored value if
the function's argument is in the memo.
Before you return the result of the recursive case, store it in the memo as a
value and make the function's argument its key.

Practice:


//! In tabulation we create a table(array) and fill it with elements.
// We will complete the table by filling entries from first to last, or "left to right".
// -->This means that the first entry of the table(first element of the array) will correspond to the smallest subproblem.
// ---->The final entry of the table(last element of the array) will correspond to the largest problem !!(which is also the final answer.)!!
// There are two main features that comprise the Tabulation strategy:
// //1. the function is iterative and not recursive
//// 2. the additional data structure used is typically an array, commonly referred to as the table
// Example:
// Once again, we will use the fibonacci example for demonstration
function tabulatedFib(n) {
  // !create a blank array with n reserved spots
  let table = new Array(n);
  //console.log(table);
  //! initialize the first two values
  table[0] = 0;
  table[1] = 1;
  // complete the table by moving from left to right,

  for (let i = 2; i <= n; i += 1) {
    table[i] = table[i - 1] + table[i - 2];
    //console.log(table);
  }
  ////console.log(table);
  return table[n];
}
//console.log("tabulatedFib(6): ", tabulatedFib(6));
//console.log("tabulatedFib(7): ", tabulatedFib(7));
/*
bryan@LAPTOP-F699FFV1:/mnt/c/Users/15512/Google Drive/a-A-September/weeks/week-7/days/tuesday/Past-Cohort/Useful$ node algos.js
[ <6 empty items> ]
[ 0, 1, 1, <3 empty items> ]
[ 0, 1, 1, 2, <2 empty items> ]
[ 0, 1, 1, 2, 3, <1 empty item> ]
[ 0, 1, 1, 2, 3, 5 ]
[0, 1, 1, 2, 3, 5, 8]
[ 0, 1, 1, 2, 3, 5, 8]
-tabulatedFib(6):  8
[ <7 empty items> ]
[ 0, 1, 1, <4 empty items> ]
[ 0, 1, 1, 2, <3 empty items> ]
[ 0, 1, 1, 2, 3, <2 empty items> ]
[ 0, 1, 1, 2, 3, 5, <1 empty item> ]
[0, 1, 1, 2,3, 5, 8]
[ 0, 1, 1,  2, 3, 5, 8, 13]
[ 0, 1, 1,  2, 3, 5, 8, 13]
-tabulatedFib(7):  13
*/
// console.log(tabulatedFib(7));      // => 13
// When we initialize the table and seed the first two values, it will look like this:
//   i        | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
// ------------------------------------------
// table[i] | 0 | 1 |   |   |   |   |   |   |
// After the loop finishes, the final table will be:
//   i       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
// -----------------------------------------
// table[i]| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13|

//// Bonus:
//? ------------------HOW DOES THIS WORK--------------------------------
//! MOORE's LAWWWWWWWWWWWWWWWWW!!!!!!!!!!!
//! This is NOT tabulation, but an improvement on the code we just wrote.
//1, 2, 3, 5, (8), 13, 21
//fib(5)=8
//[0,1]

function SpaceSavingFib(n) {
  let mostRecentFibs = [0, 1];
  if (n === 0) return mostRecentFibs[0]; //0
  for (let i = 2; i <= n; i++) {
    // because values are alredy in table
    const [secondLast, last] = mostRecentFibs; //destructure
    mostRecentFibs = [last, secondLast + last]; //? how does this work?
  }
  return mostRecentFibs[1];
}
//console.log("SpaceSavingFib(6): ", SpaceSavingFib(6)); //-SpaceSavingFib(6):  8
//?  ------------------------------------END OF CONFUSION LOL --------------

//// Word break-------------------------------------------------------------
/*
The fill() method changes all elements in an array to a static value, from a start index (default 0) to an end index (default array.length). 
It returns the modified array.
Syntax
arr.fill(value[, start[, end]])
Parameters
!value
-Value to fill the array with. (Note all elements in the array will be this exact value.)
?start Optional
-Start index, default 0.
?end Optional
-End index, default arr.length.

!Return value
-The modified array, filled with value.

Description
If start is negative, it is treated as array.length + start.
If end is negative, it is treated as array.length + end.
fill is intentionally generic: it does not require that its this value be an Array object.
fill is a mutator method: it will change the array itself and return it, not a copy of it.
If the first parameter is an object, each slot in the array will reference that object.
*/
function wordBreak(string, dictionary) {
  //! "gooddog", ["good", "dog"]

  ////The fill() method changes all elements in an array to a static value ⬆️, from a start index (default 0) to an end index (default array.length).
  ////It returns the modified array.

  let table = new Array(string.length + 1).fill(false); //-[false, false, false, false, false, false, false, false];
  table[0] = true; //-[true, false, false, false, false, false, false, false];
  for (let i = 0; i < table.length; i++) {
    if (table[i] === false) continue; //-table[0] = true, table[4] = true
    //console.log(table); // [ true,  false, false, false, true,  false, false, true]
    for (let j = i + 1; j < table.length; j++) {
      //*Unique Pairs
      let word = string.slice(i, j); //testing every combination of subsets of the string
      if (dictionary.includes(word)) table[j] = true; //table[4], table[8] = true
      //console.log(table);
    }
  }
  return table[table.length - 1];
}
const dictionary = ["good", "dog"];
const string = "gooddog";
// wordBreak( string, dictionary );
// console.log( wordBreak( string, dictionary ) ); //!true

//------------------------Annagram----------------------------------------------------------------------------------------------------------------------------
/*
!Anagrams
Our goal today is to write a method that determines if two given words are anagrams(the letters in one word can be rearranged to form the other word).
For example:
-->anagram("gizmo", "sally")    # => false
-->anagram("elvis", "lives")    # => true
Assume that there is no whitespace or punctuation in the given strings.
Phase 4;
Write one more method fourth_anagram.This time, use two objects to store the
number of times each letter appears in both words.
Compare the resulting objects.
What is the time complexity ?
    Bonus : Do it with only one object.
Discuss the time complexity of your solutions together, then call over your TA to look at them.
*/
function anagrams(str1, str2) {
  if (str1.length !== str2.length) return false; // if the lengths of the strings differ they cannot possibly be anagrams

  let count = {};

  for (let i = 0; i < str1.length; i++) {
    //---------------------String1-----------------------------------------------------------
    if (count[str1[i]] === undefined) {
      // if the string does not exist in the object
      count[str1[i]] = 0; //initialize the string as a key (and value 0)
    }
    count[str1[i]] += 1; // increase the value for that key by 1
    //--------------------string2------------------------------------------------------------
    if (count[str2[i]] === undefined) {
      // if the second string does not exist in the object
      count[str2[i]] = 0; //initialize the string as a key (and value 0)
    }
    count[str2[i]] -= 1;
    console.log(count);
    //--------------End of Loop--------------------------------------------------------------
  }
  // console.log(count);
  return Object.values(count).every((num) => {
    return num === 0;
  });
}
const str1 = "asdfgh";
const str2 = "hgfdsa";
//console.log(anagrams(str1, str2));
/*
{ a: 1, h: -1 }
{ a: 1, h: -1, s: 1, g: -1 }
{ a: 1, h: -1, s: 1, g: -1, d: 1, f: -1 }
{ a: 1, h: -1, s: 1, g: -1, d: 0, f: 0 }
{ a: 1, h: -1, s: 0, g: 0, d: 0, f: 0 }
{ a: 0, h: 0, s: 0, g: 0, d: 0, f: 0 }
true
*/
const str3 = "asdfghh";
const str4 = "hgfdsaa";
//console.log(anagrams(str3, str4));
/*
{ a: 1, h: -1 }
{ a: 1, h: -1, s: 1, g: -1 }
{ a: 1, h: -1, s: 1, g: -1, d: 1, f: -1 }
{ a: 1, h: -1, s: 1, g: -1, d: 0, f: 0 }
{ a: 1, h: -1, s: 0, g: 0, d: 0, f: 0 }
{ a: 0, h: 0, s: 0, g: 0, d: 0, f: 0 }
{ a: -1, h: 1, s: 0, g: 0, d: 0, f: 0 }
false
*/

// //-----------Anagram Walkthrough----------Uncomment-----------------------------
// function anagrams(str1, str2) {
//   if (str1.length !== str2.length) return false; // if the lengths of the strings differ they cannot possibly be anagrams
//
//   let count = {};
//   /*
// const str1 = "asdfgh";
// const str2 = "hgfdsa";
// */
//   //! when i = 0
//   //*when i = 1
//   //// when i = 2
//   //?when i = 3
//
//   for (let i = 0; i < str1.length; i++) {
//     //---------------------String1-----------------------------------------------------------
//     if (count[str1[i]] === undefined) {
//       //! true
//       //*true
//       ////true
//       //? FALSE
//       // if the string does not exist in the object
//       count[str1[i]] = 0; //! count = {"a":0}
//       //*{ a: 1, h: -1, s: 0,}
//       ////{ a: 1, h: -1, s: 1, g: -1, d: 0}
//       //? DOES NOT HAPPEN
//     }
//     count[str1[i]] += 1; //! count = {"a":1}
//     //*{ a: 1, h: -1, s: 1,}
//     ////{ a: 1, h: -1, s: 1, g: -1, d: 1}
//     //?
//     //--------------------string2------------------------------------------------------------
//     if (count[str2[i]] === undefined) {
//       //! true
//       //*true
//       ////true
//       //? FALSE
//       // if the second string does not exist in the object
//       count[str2[i]] = 0; //! count = {"a":0, "h":0}
//       //*{ a: 1, h: -1, s: 1, g: 0 }
//       ////{ a: 1, h: -1, s: 1, g: -1, d: 1, f: 0 }
//       //? { a: 1, h: -1, s: 1, g: -1, d: 1, f: 0 }  <----- f= 0 ... (!!!the f in each word cancels out!!!)
//     }
//     count[str2[i]] -= 1; //! count = {"a":0, "h":-1}
//     //*{ a: 1, h: -1, s: 1, g: -1 }
//     ////{ a: 1, h: -1, s: 1, g: -1, d: 1, f: -1 }
//     //?
//     console.log(count); //# Same as count object directly above this log statment
//
//     //--------------End of Loop--------------------------------------------------------------
//   }
//   // console.log(count);
//   return Object.values(count).every((num) => {
//     return num === 0;
//   });
// }
// const str1 = "asdfgh";
// const str2 = "hgfdsa";
// console.log(anagrams(str1, str2));//!true
//
// const str3 = "asdfghh";
// const str4 = "hgfdsaa";
// console.log(anagrams(str3, str4));//!false

//****************************END OF ANAGRAM***************************************************** */

//!  ***************************************MEMOIZATION*******************************************/*
/*
Memoization is a design pattern used to reduce the overall number of calculations in algorithms that use recursive strategies.
//Memoization will store the results of the sub-problems in some other data structure.
There are two features that comprise memoization:
-1. the function is recursive
-2. the additional data structure used is typically an object(we refer to this as the memo!) (or cache!)
Example:
Our fibonacci fucntions have two recursive calls.
- time complexity of O(2^n)
*/
function slowFib(n) {
  if (n === 1 || n === 2) return 1;
  return slowFib(n - 1) + slowFib(n - 2);
}
//slowFib(6);
//console.log("slowFib(6): ", slowFib(6)); //- slowFib(6):  8
//---------------------------------------------------------------------------------------------------
//                                         f(6)
//                     f(5)                  |                  f(4)
//           f(4)        |         f(3)      |        f(3)       |     f(2)      |
//    f(3)     |  f(2)   |   f(2)   |  f(1)  |   f(2)  |   f(1)  |
// f(2) | f(1) |
// Many of the recursive function calls are being made multiple times
//---------------------------------------------------------------------------------------------------
//! If we store these results in an object,we can reduce the number of recursive calls the function will make.

function fastFib(n, memo = { 1: 1, 2: 1 }) {
  if (n in memo) return memo[n];
  // if (n === 1 || n === 2) return 1;
  memo[n] = fastFib(n - 1, memo) + fastFib(n - 2, memo);
  return memo[n];
}
console.table([
  { "fastFib(4): ": fastFib(4) },
  { "fastFib(6): ": fastFib(6) },
  { "fastFib(50): ": fastFib(50) },
]);
/*
┌─────────┬──────────────┬──────────────┬───────────────┐
│ (index) │ fastFib(4):  │ fastFib(6):  │ fastFib(50):  │
├─────────┼──────────────┼──────────────┼───────────────┤
│    0    │      3       │              │               │
│    1    │              │      8       │               │
│    2    │              │              │  12586269025  │
└─────────┴──────────────┴──────────────┴───────────────┘
*/

/*
//fastFib(6); // => 8
//fastFib(50); // => 12586269025
Before memoization
                                        f(6)
                    f(5)                  |                  f(4)
          f(4)        |         f(3)      |        f(3)       |     f(2)      |
   f(3)     |  f(2)   |   f(2)   |  f(1)  |   f(2)  |   f(1)  |
f(2) | f(1) |
--------------------------------------------------------------------------------------
Now, our function calls will look like this:
                                        f(6)
                    f(5)                  |           f(4) <= retrieve stored answer
          f(4)        |         f(3)   <= retrieve stored answer
   f(3)     |  f(2)   |
f(2) | f(1) |
-In slowFib, the number of procedures is about 2^n, giving a time complexity of O(2^n)
-In fastFib, the number of procedures is 1+2(n-2) = 2n-3, giving a time complexity of O(n)
*/

10 Essential React Interview Questions For Aspiring Frontend Developers

Bryan C Guner — Fri, 10 Dec 2021 21:27:29 +0000

10 Essential React Interview Questions For Aspiring Frontend Developers

Comprehensive React Cheatsheet included at the bottom of this article!

10 Essential React Interview Questions For Aspiring Frontend Developers

Comprehensive React Cheatsheet included at the bottom of this article

Resources

Introduction to React for Complete Beginners

All of the code examples below will be included a second time at the bottom of this article as an embedded gist.javascript.plainenglish.io

Beginner’s Guide To React Part 2

As I learn to build web applications in React I will blog about it in this series in an attempt to capture the…bryanguner.medium.com

bgoonz/React_Notes_V3

A JavaScript library for building user interfaces Declarative React makes it painless to create interactive UIs. Design…github.com

Getting Started - React

A JavaScript library for building user interfacesreactjs.org

Also … here is my brand new blog site… built with react and a static site generator called GatsbyJS

It’s a work in progress

https://bgoonz-blog.netlify.app/

Photo by Ferenc Almasi on Unsplash### Beginning of the Article:

Pros

Easy to learn
HTML-like syntax allows templating and highly detailed documentation
Supports server-side rendering
Easy migrating between different versions of React
Uses JavaScript rather than framework-specific code

Cons

Poor documentation
Limited to only view part of MVC
New developers might see JSC as a barrier

Where to Use React

For apps that have multiple events
When your app development team excels in CSS, JavaScript and HTML
You want to create sharable components on your app
When you need a personalized app solution

Misconceptions about React

React is a framework

Many developers and aspiring students misinterpret React to be a fully functional framework. It is because we often compare React with major frameworks such as Angular and Ember. This comparison is not to compare the best frameworks but to focus on the differences and similarities of React and Angular’s approach that makes their offerings worth studying. Angular works on the MVC model to support the Model, View, and Controller layers of an app. React focuses only on the ‘V,’ which is the view layer of an application and how to make handling it easier to integrate smoothly into a project.

React’s Virtual DOM is faster than DOM

React uses a Virtual DOM, which is essentially a tree of JavaScript objects representing the actual browser DOM. The advantage of using this for the developers is that they don’t manipulate the DOM directly as developers do with jQuery when they write React apps. Instead, they would tell React how they want the DOM to make changes to the state object and allow React to make the necessary updates to the browser DOM. This helps create a comprehensive development model for developers as they don’t need to track all DOM changes. They can modify the state object, and React would use its algorithms to understand what part of UI changed compared to the previous DOM. Using this information updates the actual browser DOM. Virtual DOM provides an excellent API for creating UI and minimizes the update count to be made on the browser DOM.

However, it is not faster than the actual DOM. You just read that it needs to pull extra strings to figure out what part of UI needs to be updated before actually performing those updates. Hence, Virtual DOM is beneficial for many things, but it isn’t faster than DOM.

1. Explain how React uses a tree data structure called the virtual DOM to model the DOM

The virtual DOM is a copy of the actual DOM tree. Updates in React are made to the virtual DOM. React uses a diffing algorithm to reconcile the changes and send the to the DOM to commit and paint.

2. Create virtual DOM nodes using JSX To create a React virtual DOM node using JSX, define HTML syntax in a JavaScript file

Here, the JavaScript hello variable is set to a React virtual DOM h1 element with the text “Hello World!”.

You can also nest virtual DOM nodes in each other just like how you do it in HTML with the real DOM.

3. Use debugging tools to determine when a component is rendering

#### We use the React DevTools extension as an extension in our Browser DevTools to debug and view when a component is rendering

4. Describe how JSX transforms into actual DOM nodes

To transfer JSX into DOM nodes, we use the ReactDOM.render method. It takes a React virtual DOM node’s changes allows Babel to transpile it and sends the JS changes to commit to the DOM.

5. Use the `ReactDOM.render` method to have React render your virtual DOM nodes under an actual DOM node

6. Attach an event listener to an actual DOM node using a virtual node

The virtual DOM (VDOM) is a programming concept where an ideal, or “virtual”, representation of a UI is kept in memory and synced with the “real” DOM by a library such as ReactDOM. This process is called reconciliation.

This approach enables the declarative API of React: You tell React what state you want the UI to be in, and it makes sure the DOM matches that state. This abstracts out the attribute manipulation, event handling, and manual DOM updating that you would otherwise have to use to build your app.

Since “virtual DOM” is more of a pattern than a specific technology, people sometimes say it to mean different things. In React world, the term “virtual DOM” is usually associated with React elements since they are the objects representing the user interface. React, however, also uses internal objects called “fibers” to hold additional information about the component tree. They may also be considered a part of “virtual DOM” implementation in React.

Is the Shadow DOM the same as the Virtual DOM?

No, they are different. The Shadow DOM is a browser technology designed primarily for scoping variables and CSS in web components. The virtual DOM is a concept implemented by libraries in JavaScript on top of browser APIs.

To add an event listener to an element, define a method to handle the event and associate that method with the element event you want to listen for:

7. Use `create-react-app` to initialize a new React app and import required dependencies

Create the default create-react-application by typing in our terminal

Explanation of npm vs npx from Free Code Camp:

npm (node package manager) is the dependency/package manager you get out of the box when you install Node.js. It provides a way for developers to install packages both globally and locally.

Sometimes you might want to take a look at a specific package and try out some commands. But you cannot do that without installing the dependencies in your local node_modules folder.

npm the package manager

npm is a couple of things. First and foremost, it is an online repository for the publishing of open-source Node.js projects.

Second, it is a CLI tool that aids you to install those packages and manage their versions and dependencies. There are hundreds of thousands of Node.js libraries and applications on npm and many more are added every day.

npm by itself doesn’t run any packages. If you want to run a package using npm, you must specify that package in your package.json file.

When executables are installed via npm packages, npm creates links to them:

local installs have links created at the ./node_modules/.bin/ directory
global installs have links created from the global bin/ directory (for example: /usr/local/bin on Linux or at %AppData%/npm on Windows)

To execute a package with npm you either have to type the local path, like this:

./node_modules/.bin/your-package

or you can run a locally installed package by adding it into your package.json file in the scripts section, like this:

{
  "name": "your-application",
  "version": "1.0.0",
  "scripts": {
    "your-package": "your-package"
  }
}

Then you can run the script using npm run:

npm run your-package

You can see that running a package with plain npm requires quite a bit of ceremony.

Fortunately, this is where npx comes in handy.

npx the package runner

Since npm version 5.2.0 npx is pre-bundled with npm. So it’s pretty much a standard nowadays.

npx is also a CLI tool whose purpose is to make it easy to install and manage dependencies hosted in the npm registry.

It’s now very easy to run any sort of Node.js-based executable that you would normally install via npm.

You can run the following command to see if it is already installed for your current npm version:

which npx

If it’s not, you can install it like this:

npm install -g npx

Once you make sure you have it installed, let’s see a few of the use cases that make npx extremely helpful.

Run a locally installed package easily

If you wish to execute a locally installed package, all you need to do is type:

npx your-package

npx will check whether <command> or <package> exists in $PATH, or in the local project binaries, and if so it will execute it.

Execute packages that are not previously installed

Another major advantage is the ability to execute a package that wasn’t previously installed.

Sometimes you just want to use some CLI tools but you don’t want to install them globally just to test them out. This means you can save some disk space and simply run them only when you need them. This also means your global variables will be less polluted.

Now, where were we?

npx create-react-app <name of app> --use-npm

npx gives us the latest version. --use-npm just means to use npm instead of yarn or some other package manager

8. Pass props into a React component

props is an object that gets passed down from the parent component to the child component. The values can be of any data structure including a function (which is an object)

You can also interpolate values into JSX.
Set a variable to the string, “world”, and replace the string of “world” in the NavLinks JSX element with the variable wrapped in curly braces:

Accessing props:

To access our props object in another component we pass it the props argument and React will invoke the functional component with the props object.

Reminder

Conceptually, components are like JavaScript functions. They accept arbitrary inputs (called “props”) and return React elements describing what should appear on the screen.

Function and Class Components

The simplest way to define a component is to write a JavaScript function:

function Welcome(props) {
  return <h1>Hello, {props.name}</h1>;
}

This function is a valid React component because it accepts a single “props” (which stands for properties) object argument with data and returns a React element. We call such components “function components” because they are literally JavaScript functions.

You can also use an ES6 class to define a component:

class Welcome extends React.Component {
  render() {
    return <h1>Hello, {this.props.name}</h1>;
  }
}

The above two components are equivalent from React’s point of view.

You can pass down as many props keys as you want.

9. Destructure props

You can destructure the props object in the function component’s parameter.

10. Create routes using components from the react-router-dom package

a. Import the react-router-dom package:

npm i react-router-dom

In your index.js:

Above you import your BrowserRouter with which you can wrap your entire route hierarchy. This makes routing information from React Router available to all its descendent components.
Then in the component of your choosing, usually top tier such as App.js, you can create your routes using the Route and Switch Components

Discover More

Web-Dev-Hub

Memoization, Tabulation, and Sorting Algorithms by Example Why is looking at runtime not a reliable method of…bgoonz-blog.netlify.app

REACT CHEAT SHEET

More content at plainenglish.io

By Bryan Guner on June 11, 2021.

Canonical link

Exported from Medium on August 31, 2021.

Deploy React App To Heroku Using Postgres & Express

Bryan C Guner — Fri, 10 Dec 2021 21:26:02 +0000

Deploy React App To Heroku Using Postgres & Express

Heroku is an web application that makes deploying applications easy for a beginner.

Deploy React App To Heroku Using Postgres & Express

Heroku is an web application that makes deploying applications easy for a beginner.

Before you begin deploying, make sure to remove any console.log's or debugger's in any production code. You can search your entire project folder if you are using them anywhere.

You will set up Heroku to run on a production, not development, version of your application. When a Node.js application like yours is pushed up to Heroku, it is identified as a Node.js application because of the package.json file. It runs npm install automatically. Then, if there is a heroku-postbuild script in the package.json file, it will run that script. Afterwards, it will automatically run npm start.

In the following phases, you will configure your application to work in production, not just in development, and configure the package.json scripts for install, heroku-postbuild and start scripts to install, build your React application, and start the Express production server.

Phase 1: Heroku Connection

If you haven’t created a Heroku account yet, create one here.

Add a new application in your Heroku dashboard named whatever you want. Under the “Resources” tab in your new application, click “Find more add-ons” and add the “Heroku Postgres” add-on with the free Hobby Dev setting.

In your terminal, install the Heroku CLI. Afterwards, login to Heroku in your terminal by running the following:

heroku login

Add Heroku as a remote to your project’s git repository in the following command and replace <name-of-Heroku-app> with the name of the application you created in the Heroku dashboard.

heroku git:remote -a <name-of-Heroku-app>

Next, you will set up your Express + React application to be deployable to Heroku.

Phase 2: Setting up your Express + React application

Right now, your React application is on a different localhost port than your Express application. However, since your React application only consists of static files that don’t need to bundled continuously with changes in production, your Express application can serve the React assets in production too. These static files live in the frontend/build folder after running npm run build in the frontend folder.

Add the following changes into your backend/routes.index.js file.

At the root route, serve the React application’s static index.html file along with XSRF-TOKEN cookie. Then serve up all the React application's static files using the express.static middleware. Serve the index.html and set the XSRF-TOKEN cookie again on all routes that don't start in /api. You should already have this set up in backend/routes/index.js which should now look like this:

// backend/routes/index.js
const express = require('express');
const router = express.Router();
const apiRouter = require('./api');

router.use('/api', apiRouter);

// Static routes
// Serve React build files in production
if (process.env.NODE_ENV === 'production') {
  const path = require('path');
  // Serve the frontend's index.html file at the root route
  router.get('/', (req, res) => {
    res.cookie('XSRF-TOKEN', req.csrfToken());
    res.sendFile(
      path.resolve(__dirname, '../../frontend', 'build', 'index.html')
    );
  });

  // Serve the static assets in the frontend's build folder
  router.use(express.static(path.resolve("../frontend/build")));

  // Serve the frontend's index.html file at all other routes NOT starting with /api
  router.get(/^(?!\/?api).*/, (req, res) => {
    res.cookie('XSRF-TOKEN', req.csrfToken());
    res.sendFile(
      path.resolve(__dirname, '../../frontend', 'build', 'index.html')
    );
  });
}

// Add a XSRF-TOKEN cookie in development
if (process.env.NODE_ENV !== 'production') {
  router.get('/api/csrf/restore', (req, res) => {
    res.cookie('XSRF-TOKEN', req.csrfToken());
    res.status(201).json({});
  });
}

module.exports = router;

Your Express backend’s package.json should include scripts to run the sequelize CLI commands.

The backend/package.json's scripts should now look like this:

"scripts": {
    "sequelize": "sequelize",
    "sequelize-cli": "sequelize-cli",
    "start": "per-env",
    "start:development": "nodemon -r dotenv/config ./bin/www",
    "start:production": "node ./bin/www"
  },

Initialize a package.json file at the very root of your project directory (outside of both the backend and frontend folders). The scripts defined in this package.json file will be run by Heroku, not the scripts defined in the backend/package.json or the frontend/package.json.

When Heroku runs npm install, it should install packages for both the backend and the frontend. Overwrite the install script in the root package.json with:

npm --prefix backend install backend && npm --prefix frontend install frontend

This will run npm install in the backend folder then run npm install in the frontend folder.

Next, define a heroku-postbuild script that will run the npm run build command in the frontend folder. Remember, Heroku will automatically run this script after running npm install.

Define a sequelize script that will run npm run sequelize in the backend folder.

Finally, define a start that will run npm start in the `backend folder.

The root package.json's scripts should look like this:

"scripts": {
    "heroku-postbuild": "npm run build --prefix frontend",
    "install": "npm --prefix backend install backend && npm --prefix frontend install frontend",
    "dev:backend": "npm install --prefix backend start",
    "dev:frontend": "npm install --prefix frontend start",
    "sequelize": "npm run --prefix backend sequelize",
    "sequelize-cli": "npm run --prefix backend sequelize-cli",
    "start": "npm start --prefix backend"
  },

The dev:backend and dev:frontend scripts are optional and will not be used for Heroku.

Finally, commit your changes.

Phase 3: Deploy to Heroku

Once you’re finished setting this up, navigate to your application’s Heroku dashboard. Under “Settings” there is a section for “Config Vars”. Click the Reveal Config Vars button to see all your production environment variables. You should have a DATABASE_URL environment variable already from the Heroku Postgres add-on.

Add environment variables for JWT_EXPIRES_IN and JWT_SECRET and any other environment variables you need for production.

You can also set environment variables through the Heroku CLI you installed earlier in your terminal. See the docs for Setting Heroku Config Variables.

Push your project to Heroku. Heroku only allows the master branch to be pushed. But, you can alias your branch to be named master when pushing to Heroku. For example, to push a branch called login-branch to master run:

git push heroku login-branch:master

If you do want to push the master branch, just run:

git push heroku master

You may want to make two applications on Heroku, the master branch site that should have working code only. And your staging site that you can use to test your work in progress code.

Now you need to migrate and seed your production database.

Using the Heroku CLI, you can run commands inside of your production application just like in development using the heroku run command.

For example to migrate the production database, run:

heroku run npm run sequelize db:migrate

To seed the production database, run:

heroku run npm run sequelize db:seed:all

Note: You can interact with your database this way as you’d like, but beware that db:drop cannot be run in the Heroku environment. If you want to drop and create the database, you need to remove and add back the "Heroku Postgres" add-on.

Another way to interact with the production application is by opening a bash shell through your terminal by running:

heroku bash

In the opened shell, you can run things like npm run sequelize db:migrate.

Open your deployed site and check to see if you successfully deployed your Express + React application to Heroku!

If you see an Application Error or are experiencing different behavior than what you see in your local environment, check the logs by running:

heroku logs

If you want to open a connection to the logs to continuously output to your terminal, then run:

heroku logs --tail

The logs may clue you into why you are experiencing errors or different behavior.

If you found this guide helpful feel free to checkout my github/gists where I host similar content

bgoonz’s gists · GitHub

Alternate Instructions

Deploy MERN App To Heroku

Source: Article

Adding CSS To Your HTML

Bryan C Guner — Fri, 10 Dec 2021 21:24:47 +0000

Adding CSS To Your HTML

For beginners … very picture heavy since CSS is such a visual discipline!

Adding CSS To Your HTML

For beginners … very picture heavy since CSS is such a visual discipline

### Getting CSS Into Your HTML

To connect your CSS sheet to your HTML page, use the link tag like so.
Many developers use External pre-written CSS stylesheets for consistent design.
You can connect multiple stylesheets.

CSS Selectors

CSS Selector : Applies styles to a specific DOM element(s), there are various types:
Type Selectors : Matches by node name.

- Class Selectors : Matches by class name.

- ID Selectors : Matches by ID name.

- Universal Selectors : Selects all HTML elements on a page.

- Attribute Selectors : Matches elements based on the prescence or value of a given attribute. (i.e. a[title] will match all a elements with a title attribute)

/* Type selector */
div {
  background-color: #000000;
}

/* Class selector */
.active {
  color: #ffffff;
}

/* ID selector */
#list-1 {
  border: 1px solid gray;
}

/* Universal selector */
* {
  padding: 10px;
}

/* Attribute selector */
a[title] {
  font-size: 2em;
}

Class Selectors

Used to select all elements of a certain class denoted with a .[class name]
You can assign multiple classes to a DOM element by separating them with a space.

Compound Class Selectors

- To get around accidentally selecting elements with multiple classes beyond what we want to grab we can chain dots.

TO use a compound class selector just append the classes together when referencing them in the CSS.
i.e. .box.yellow will select only the first element.
KEEP IN MIND that if you do include a space it will make the selector into a descendant selector.

h1#heading,
h2.subheading {
font-style: italic;
}
When we want to target all h1 tags with the id of heading.

CSS Combinators

CSS Combinators are used to combine other selectors into more complex or targeted selectors — they are very powerful!
Be careful not to use too many of them as they will make your CSS far too complex.

`Descendant Selectors`

- Separated by a space.

Selects all descendants of a parent container.

`Direct Child Selectors`

- Indicated with a >.

Different from descendants because it only affects the direct children of an element.

CSS

.menu &gt; .is-active { background-color: #ffe0b2; }

HTML

  Belka  Strelka     Laika

Basic Python Notes

Bryan C Guner — Fri, 10 Dec 2021 21:22:45 +0000

Basics of Python


import sys
print('Hello, World')
print("It's raining!")
print('''
Welcome to Python
Have a great day!!!
''')

a = None
print(a)

Arithmetic in Python

- numeric types: integer and float

- add, subtract, multiply => notice numeric types of results

- powers, division

- integer division & modulo teaming up

- warning: watch for rounding errors

x = 25    # integer
y = 17.0  # float

 print(x)
 print(y)

 print(x + y)
 print(x - y)

 print(x * y)
 print(x / y)

 print(x // y) # integer division
 print(x % y) # modulo

 print(f'The result is {int(x // y)} remainder {int(x % y)}')

 print(x ** 2)
 print(y ** 2)

 x = 25
 y = 17.6

rounding errors due to floats

we can cast to int, round(num, digits), etc.


 print(x * y)
 print(int(x * y))
 print(round(x * y, 2))

Casting will truncate (floor) our float

print(int(17.2))
print(int(17.9))

Simple Input and Formatted Printing

- Prompt for input()

- Formatted printing 4 ways

name = input('What is your name?\n')

print('Hi, ' + name + '.')
print('Hi, %s.' % name)
print('Hi, {fname} {lname}.'.format(lname="Doe", fname="John"))
print(f'Hi, {name}.')

Duck Typing

- len()

- try ... except

a = False
try:
    print(len(a))
except:
    print(f'{a} has no length')

# More complex try blocks

a = 'False'
b = 6
c = 2
try:
    print(len(a))
    print(b/c)
    print(a[47])
except TypeError:
    print(f'{a} has no length')
except ZeroDivisionError as err:
    print(f'Cannot divide by zero! Error: {err}')
except:
    print(f'Uh oh, unknown error: {sys.exc_info()}')
else:
    print('No errors! Nice!')
finally:
    print('Thanks for using the program!')
# Arithmetic with Strings

a = "a"
b = "b"
an = "an"

print(b + an)
print(b + a*7)
print(b + an*2 + a)

print("$1" + ",000"*3)

# Length of a string
print(len("Spaghetti"))    # => 9

# Indexing into strings
print("Spaghetti"[0])    # => S
print("Spaghetti"[4])    # => h
print("Spaghetti"[-1])    # => i
print("Spaghetti"[-4])    # => e

# Indexing with ranges
print("Spaghetti"[1:4])  # => pag
print("Spaghetti"[4:-1])    # => hett
print("Spaghetti"[4:4])  # => (empty string)
print("Spaghetti"[:4])  # => Spag
print("Spaghetti"[:-1])    # => Spaghett
print("Spaghetti"[1:])  # => paghetti
print("Spaghetti"[-4:])    # => etti

# Using invalid indices
# print("Spaghetti"[15])    # => IndexError: string index out of range
# print("Spaghetti"[-15])    # => IndexError: string index out of range
print("Spaghetti"[:15])    # => Spaghetti
print("Spaghetti"[15:])    # => (empty string)
print("Spaghetti"[-15:])    # => Spaghetti
print("Spaghetti"[:-15])    # => (empty string)
print("Spaghetti"[15:20])    # => (empty string)

# .index() function
# Returns the first index where the character is found
print("Spaghetti".index("t"))    # => 6
# print("Spaghetti".index("s"))    # => ValueError: substring not found

# .count() function
# Returns the number of times the substring is found
print("Spaghetti".count("h"))    # => 1
print("Spaghetti".count("t"))    # => 2
print("Spaghetti".count("s"))    # => 0

# .split() function
# Returns a list (array) of substrings, split on the character passed
# If no character is passed, a space is used to split on
print("Hello World".split())    # => ["Hello", "World"]
print("i-am-a-dog".split("-"))    # => ["i", "am", "a", "dog"]

# .join() function
# Works in reverse from what you may be used to with JavaScript
# Called on a string that should be used to join each substring from the passed list
print(" ".join(["Hello", "World"]))    # => "Hello World"
# ["Hello", "World"].join(" ") JavaScript
print("-".join(["i", "am", "a", "dog"]))    # => "i-am-a-dog"

# .upper() and .lower() transformation functions
# These functions do not mutate
a = 'Hello'
print(a)
print(a.upper())
print(a)

# Some testing methods
# islower()
# isupper()
# startswith("substring")
# endswith("substring")
# isalpha() - only letters
# isalnum() - letters and numbers
# isdecimal() - only numbers
# isspace() - only whitespace
# istitle() - only title-cased letters (does not account for special words like 'a')
print('Once Upon A Time'.istitle())  # => True
print('Once Upon a Time'.istitle())  # => False
# Assignment Operators in Python
# - Increment (no postfix/prefix)
# - Powers and Integer division
# - Big Numbers
# - Stopping a runaway process (control+c)

i = 1
# i++ does not exist in Python, we have to use i += 1
i += 1
print(i)  # > 2

i += 4
print(i)  # > 6

i **= 2
print(i)  # > 36

i //= 10
print(i)  # > 3

i *= 10**200
print(i)  # > 3 followed by 200 0s (all written out)

print(float(i))  # > 3e+200 (floats are written in scientific notation)

i = 3
i **= 10**200
print(i)  # runaway process! control+c triggers a KeyboardInterrupt to stop it

# Meaning of Truth in Python
# - numeric types equivalent, but not strings
# - conditionals (if, elif, else)
# - truth equivalence

a = 1
b = 1.0
c = "1"

# print(a == b)
# print(a == c)
# print(b == c)

# if (a == c):
#     print("match")
# elif (a == b):
#     print("a matches b")
# else:
#     print("not a match")

a = []
# Falsy Values:
# 0, 0.0, 0j (complex number)
# ''
# False
# None
# []
# ()
# {}
# set()
# range(0)

if (a):
    print(f'{a} is true')
else:
    print(f'{a} is false')

# Logical Operators
# We use the keywords 'and', 'or', and 'not' in Python instead of &&, ||, and !
print(True and False)  # > False
print(True or False)  # > True
print(True and not False)  # > True

# Grouping Conditions
# Parentheses can group our conditions, just like JavaScript
print(False and (True or True))  # > False
print((False and True) or True)  # > True

# Short Circuiting
# If we can already determine the overall outcome of a compound conditional
# Python will not bother evaluating the rest of the statement
# False and (anything else) is always False, so the print is not evaluated
False and print("not printed")
# Cannot determine overall value so we have to evaluate the right side
False or print("printed #1")
# Cannot determine overall value so we have to evaluate the right side
True and print("printed #2")
# True or (anything else) is always True, so the print is not evaluated
True or print("not printed")

# JavaScript use case of short circuiting
# const composeEnhancers = window.__REDUX_DEVTOOLS_EXTENSION_COMPOSE__ || compose;
# While loops follow a very similar structure to JavaScript
i = 0
while i < 5:
    print(f'{i+1}. Hello, world.')
    i += 1

# The 'continue' keyword goes to the next loop
# The 'break' keyword exits out of the loop completely
i = 0
while True:
    print(f'{i+1}. Hello, world.')
    if i < 4:
        i += 1
        continue
    print("You've printed 5 times. Goodbye.")
    break

# Identity vs. Equality
# - is vs. ==
# - working with literals
# - isinstance()

a = 1
b = 1.0
c = "1"

print(a == b)
print(a is b)

print(c == "1")
print(c is "1")

print(b == 1)
print(b is 1)

print(b == 1 and isinstance(b, int))
print(a == 1 and isinstance(a, int))

# d = 100000000000000000000000000000000
d = float(10)
e = float(10)

print(id(d))
print(id(e))
print(d == e)
print(d is e)

b = int(b)
print(b)
print(b == 1 and isinstance(b, int))

print(a)
print(float(a))
print(str(a))

print(str(a) is c)
print(str(a) == c)

# Make an xor function
# Truth table
# | left  | right | Result |
# |-------|-------|--------|
# | True  | True  | False  |
# | True  | False | True   |
# | False | True  | True   |
# | False | False | False  |
# def xor(left, right):
#   return left != right


def xor(left, right): return left != right


print(xor(True, True))  # > False
print(xor(True, False))  # > True
print(xor(False, True))  # > True
print(xor(False, False))  # > False


def print_powers_of(base, exp=1):
    i = 1
    while i <= exp:
        print(base ** i)
        i += 1


# We are not hoisting the function declaration, we need to invoke after declared
print_powers_of(15)
print_powers_of(exp=6, base=7)
print_powers_of(2, 5)
print_powers_of(3, 5)
print_powers_of(10, 5)

if True:
    x = 10

print(x)
print(i)


def greeting_maker(salutation):
    print(salutation)

    def greeting(name):
        return f"{salutation} {name}"
    return greeting
# print(salutation) # Error, salutation is not defined at this scope


hello = greeting_maker("Hello")
hiya = greeting_maker("Hiya")

print(hello("Monica"))
print(hello("Raja"))

print(hiya("Raul"))
print(hiya("Tariq"))




![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oxgd7r73mtx2q835j85g.jpg)

Intro To The Concepts Behind React

Bryan C Guner — Sat, 30 Oct 2021 10:40:30 +0000

A Basic Component

The key abstraction that React provides is that of a component. To reiterate, a component is some thing that is being rendered in the browser. It could be a button, a form with a bunch of fields in it, a navigation bar at the top of the page, a single input field, etc. Any of these could be its own component. React doesn't place any restrictions on how large or small a component can be. You could have an entire static site encapsulated in a single React component, but that at that point you may as well not be using React. So the first thing to remember about a component is that a component must render something. If nothing is being rendered from a component, then React will throw an error.

Let's write the most basic of components we can possibly write. Inside of BasicComponent.js, first import React at the top of the file. Our most basic of
components looks like this:

import React from 'react';

const BasicComponent = () => <div>Hello World!</div>;

export default BasicComponent;

This is a component that simply returns a div tag with the words Hello World! inside. The last line simply exports our component so that it can be imported
by another file.

Notice that this component looks exactly like an anonymous arrow function that we've named BasicComponent. In fact, that is literally what this is. Nothing
more, nothing less. The arrow function then is simply returning the div tag. When a component is written as a function like this one is, it is called a
functional component.

While a component can of course get a lot more complicated than this, fundamentally, all a component does is render some HTML.

A Basic Class Component

The basic component you wrote in the previous exercise is an example of a functional component, which is appropriate since that component is literally
nothing more than a function that returns some HTML. Functional components are great when all you want a component to do is to render some stuff; they
are really good at doing just that.

Components can also be written as classes. For this exercise, we're going to write a class component that does exactly the same thing as the functional component we just wrote. We'll again need to import React at the top of the file, but we'll also need to add a little something. Our import statement will look like this:

import React, { Component } from 'react';

So, in addition to importing React, we're also importing the base Component class that is included in the React library. The export statement at the bottom of the file also stays, completely unchanged. Our class component will thus look like this:

import React, { Component } from 'react';

class BasicClassComponent extends Component {
    render() {
        return (
            <div>Hello World!</div>
        );
    }
}

export default BasicClassComponent;

Notice that our BasicClassComponent inherits from the base Component class that we imported from the React library, by virtue of the 'extends' keyword. That being said, there's nothing in this minimal component that takes advantage of any of those inherited methods. All we have is a method on our component class called render that returns the same div tag.

In this case, if we really were deciding between whether to use a functional component versus a class component to render a simple div tag, then the functional style is more appropriate to use. This is because class components are much better suited for handling component state and triggering events based on the component's lifecycle. Don't worry if you don't know what all these terms meant, we will get to them shortly.

The important takeaways at this point are that there are two types of components, functional and class components, and that functional components are well-suited if you're just looking to render some HTML. Class components, on the other hand, are much better suited for handling components that require more complex functionality, need to exhibit more varied behavior, and/or need to keep track of some state that may change throughout said component's lifecycle.

A Class Component with Some State

When we talked about class components, it was mentioned that class components can handle state. So what does that mean? Component state is any dynamic data that we want the component to keep track of. For example, let's say we have a form component. This form has some input fields that we'd like users to fill out. When a user types characters into an input field, how is that input persisted from the point of view of our form component?

The answer is by using component state! There are a few important concepts regarding component state, such as how to update it, pass it to another component, render it, etc. We'll talk about all of these in a bit, but for now, let's just focus on how to add state to a class component.

Only class components have the ability to persist state, so if at any time you realize that a component needs to keep track of some state, you know that you'll automatically need a class component instead of a functional component.

Our class component with state will look a lot like the basic class component we just wrote, but with some extra stuff:

import React, { Component } from 'react';

class ClassComponentWithState extends Component {
    constructor() {
        super();
        this.state = {};
    }

    render() {
        return (
            <div>Hello World!</div>
        );
    }
}

export default ClassComponentWithState;

So far, the only new thing going on here is the constructor block. If you recall how classes in JavaScript work, classes need constructors. Additionally, if a class is extending off of another class and wants access to its parent class's methods and properties, then the super function needs to be called inside the class's constructor function. Point being, the constructor function and the call to the super function are not associated with React, they are associated with all JavaScript classes.

Then there is the this.state property inside the constructor function that is set as an empty object. We're adding a property called state to our class and setting it to an empty object. State objects in React are always just plain old objects.

The observant student may be wondering why the basic class component we wrote in the previous exercise had no constructor function within its body. That is because we had no need for them since all our class component was doing was rendering some HTML. The constructor is needed here because that is where we need to initialize our state object. The call to super is needed because we can't reference this inside of our constructor without a call to super first.

Ok, now let's actually use this state object. One very common application of state objects in React components is to render the data being stored inside them within our component's render function. Let's change our current class component to do that.

class ClassComponentWithState extends Component {
    constructor() {
        super();
        this.state = {
            someData: 8
        };
    }

    render() {
        return (
            <div>{`Here's some data to render: ${this.state.someData}`}</div>
        );
    }
}

export default ClassComponentWithState;

So what's changed here? Well, we added a key-value pair to our state object inside our constructor. Then we changed the contents of the render function. Now, it's actually rendering the data that we have inside the state object. Notice that inside the div tags we're using a template string literal so that we can access the value of this.state.someData straight inside of our rendered content. This is a very handy piece of functionality that React provides for us when writing components.

With React's newest version, we can actually now add state to a component without explicitly defining a constructor on the class. We can refactor our class component to look like this:

class ClassComponentWithState extends Component {
    state = {
        someData: 8
    };

    render() {
        return (
            <div>{`Here's some data to render: ${this.state.someData}`}</div>
        );
    }
}

export default ClassComponentWithState;

Our code is slightly cleaner, and doesn't require as many keystrokes as the older version. Fewer keystrokes are always a plus in my book! This new syntax is what is often referred to as 'syntactic sugar': under the hood, the React library translates this back into the old constructor code that we first started with, so that the JavaScript remains valid to the JavaScript interpreter. The clue to this is the fact that when we want to access some data from the state object, we still need to call it with this.state.someData; changing it to just state.someData does not work.

While being able to write our code in this way is nice and convenient, going forward, I'm going to stick with the 'older' style of writing my React components by explicitly defining constructors so that you'll all have a better idea of what's going on under the hood. In other words, it's more "pedagogically sound". If you prefer the newer style (and I would in my own code), feel free to write your React components that way.

Class Component Updating State

Great, so we can render some state that our component persists for us. However, we said an important use case of component state is to handle dynamic data. A single static number isn't very dynamic at all. So now let's walk through how to update component state.

import React, { Component } from 'react';

class ClassComponentUpdatingState extends Component {
  constructor() {
    super();
    this.state = {
      aNumber: 8
    };
  }

  increment = () => {
    this.setState({ aNumber: ++this.state.aNumber });
  };

  decrement = () => {
    this.setState({ aNumber: --this.state.aNumber });
  };

  render() {
    return (
      <div>
        <div>{`Our number: ${this.state.aNumber}`}</div>
        <button onClick={this.increment}>+</button>
        <button onClick={this.decrement}>-</button>
      </div>
    );
  }
}

export default ClassComponentUpdatingState;

Notice that we've added two methods to our class: increment and decrement. increment and decrement are methods that we are adding to our class component. Unlike the render method,increment and decrement were not already a part of our class component. This is why increment and decrement are written as arrow functions, so that they are automatically bound to our class component. This needs to happen so that we can call them later on. Again, there's no crazy React black magic going on here, we simply added two methods to our class.

The more interesting thing is what is going on within the bodies of these methods. Each calls this funky setStatefunction. setState in fact is provided to us by React. It is the canonical way to update a component's state. Actually, it's the only way you should ever update a component's state. It may seem more verbose than necessary, but there are good reasons for why you should be doing it this way. I'm not going to get into those reasons now. I'll leave a link to the official documentation on the setState function, although I'm pretty sure at this point it will probably just blow your mind and/or overwhelm you with jargon. So for now, take this as a case of "because I'm telling you so".

So the way to use setState to update a component's state is to pass it an object with each of the state keys you wish to update, along with the updated value. In our increment method we said "I would like to update the aNumber property on my component state by adding one to it and then setting the new value as my new aNumber". The same thing happens in our decrement method, only we're subtracting instead of adding.

Then the other new concept we're running into here is how to actually call these methods we've added to our class. We added two HTML button tags within our render function, then in their respective onClick handlers, we specify the method that should be called whenever this button gets clicked. So whenever we click either of the buttons, our state gets updated appropriately and our component will re-render to show the correct value we're expecting.

Class Component Iterating State

Another common state pattern you'll see being used in React components is iterating over an array in our state object and rendering each array element in its own tag. This is often used in order to render lists.

Additionally, we want to be able to easily update lists and have React re-render our updated list. We'll see how both of these are done and how they work together within a single component in order to create the behavior of a dynamic list.

import React, { Component } from 'react';

class ClassComponentIteratingState extends Component {
    constructor() {
        super();

        this.state = {
            ingredients: ['flour', 'eggs', 'milk', 'sugar', 'vanilla extract'],
            newIngredient: ''
        };
    }

    handleIngredientInput = (event) => {
        this.setState({ newIngredient: event.target.value });
    };

    addIngredient = (event) => {
        event.preventDefault();
        const ingredientsList = this.state.ingredients;
        ingredientsList.push(this.state.newIngredient);
        this.setState({
            newIngredient: '',
            ingredients: ingredientsList
        });
    };

    render() {
        return (
            <div>
                {this.state.ingredients.map(ingredient => <div>{ingredient}</div>)}
                <form onSubmit={this.addIngredient}>
                    <input type="text" onChange={this.handleIngredientInput} placeholder="Add a new ingredient" value={this.state.newIngredient} />
                </form>
            </div>
        );
    }
}

export default ClassComponentIteratingState;

The first change to note is that our state object now has an 'ingredients' array, and a 'newIngredient' field that has been initialized to an empty string. The ingredients array contains the elements that we'll want to render in our list. We'll see shortly why the newIngredient field is needed.

The addIngredient and handleIngredientInput methods we've added to our class receives a parameter called 'event'. This event object is part of the browser's API. When we interact with some DOM element, such as clicking on an HTML button, the function that is invoked upon that button being clicked actually receives the event object. So when we type some input into an input tag, we're able grab each character that was typed into the input field through the event object paramter.

The handleIngredientInput method is what gets invoked every time the user presses a key to enter text in the input box for adding a new ingredient. Every character the user types gets persisted in the newIngredient field on the state object. We're able to grab the text in the input box using event.target.value, which holds the value of the string text that is currently in the input box. We use that to update our newIngredient string field.

Breaking down the addIngredient method, we see this event.preventDefault() invocation. This is because this method will be used upon submitting a form, and it turns out that submitting a form triggers some default form behavior that we don't want to trigger when we submit the form (namely refreshing the entire page). event.preventDefault() will prevent this default form behavior, meaning our form will only do what we want it to do when it is submitted.

Next, we store a reference to this.state.ingredients in a variable called ingredientsList. So we now have a copy of the array that is stored in our state object. We want to update the copy of the ingredients array first instead of directly updating the actual array itself in state. This is a React best practice.

Now we push whatever value is being stored at our newIngredient field onto the ingredientsList array so that our ingredientsList array is now more up-to-date than our this.state.ingredients array. So all we have to do now is call setState appropriately in order to update the value in our state object. Additionally, we also set the newIngredient field back to an empty string in order to clear out the input field once we submit a new ingredient. Now it's ready to accept more user input!

Looking at our render function, first note the this.state.ingredients.map call. This is looping through each ingredient in our ingredients array and returning each one within its own div tag. This is a very common syntax for rendering everything inside an array.

Then we have an HTML form which contains an input field. The purpose of this form is to allow a user to add new ingredients to the list. Note that we're passing our addIngredient method to the form's onSubmit handler. This means that our addIngredient method gets invoked whenever our form is submitted.

Lastly, the input field has an onChange handler that invokes our handleIngredientInput method whenever there is some sort of change in the input field, namely when a user types into it. Notice that the value field in our input tag reads off of this.state.newIngredient in order to know what value to display. So when a user enters text into the input field, the onChange handler is invoked every time, which updates our this.state.newIngredient field, which the input field
then renders.

Parent and Child Components

Now let's get into talking about how to have components interact with each other. A single isolated component isn't going to do us much good. That being said, it's possible to simply throw all of the HTML for a page into a single React component, though at that point that one component would be so bloated and monolithic that you might as well not have used React at all.

The beauty of React lies in the fact that it allows us to compose modular components together. Let's start off with the component we just saw, but let's change its name to ParentComponent.

import React, { Component } from 'react';
import ChildComponent from './ChildComponent';

class ParentComponent extends Component {
    constructor() {
        super();

        this.state = {
            ingredients: ['flour', 'eggs', 'milk', 'sugar', 'vanilla'],
            newIngredient: ''
        };
    }

    handleIngredientInput = (event) => {
        this.setState({ newIngredient: event.target.value });
    };

    addIngredient = (event) => {
        event.preventDefault();
        const ingredientsList = this.state.ingredients;
        ingredientsList.push(this.state.newIngredient);
        this.setState({
            newIngredient: '',
            ingredients: ingredientsList
        });
    };

    render() {
        return (
            <div>
                {this.state.ingredients.map(ingredient => <ChildComponent thing={ingredient} />)}
                <form onSubmit={this.addIngredient}>
                    <input type="text" onChange={this.handleIngredientInput} placeholder="Add a new ingredient" value={this.state.newIngredient} />
                </form>
            </div>
        );
    }
}

export default ParentComponent;

The only two other differences in this component are that we're importing a ChildComponent and then using it inside our this.state.ingredients.map call. ChildComponent is another React component. Notice that we're using it just as if it were any other HTML tag. This is how we lay out our component hierarchy: the ChildComponent is rendered within the ParentComponent. We can see this to be the case if we open up the developer console and inspect these elements.

Note also that we're passing each ingredient as a 'thing' to the ChildComponent component. This is how a parent component passes data to a child component. It doesn't need to be called 'thing'; you can call it whatever you want. Conceptually though, every piece of data that a parent component passes down to a child component is called a 'prop' in React lingo.

Let's take a look now at the Child Component. It serves two purposes: 1) to render the props data that it gets from a parent component, and 2) to add the ability for a user to click on it and have it toggle a strikethrough, indicating that the item is 'complete'.

import React, { Component } from 'react';

class ChildComponent extends Component {
  constructor() {
    super();
    this.state = {
      clicked: false
    };
  }

  handleClick = () => {
    this.setState({ clicked: !this.state.clicked });
  };

  render() {
    const styles = this.state.clicked ? { textDecoration: 'line-through'} : { textDecoration: 'none' };
    return (
      <div style={styles} onClick={this.handleClick}>{this.props.thing}</div>
    );
  }
}

export default ChildComponent;

The overall structure of the child component is nothing we haven't seen. It's just another class component with its own state object and a method called handleClick.

A component accesses its props via the this.props object. Any prop a parent component passes down to a child component is accessible inside the child component's this.prop object.

So our child component keeps its own state that tracks whether the component has been clicked or not. Then at the top of the render function, it uses a ternary condition to determine whether the div tag that is being rendered should have a strikethrough or not. The handleClick method is then invoked via an onClick handler on the div tag; it does the work of toggling the this.state.clicked boolean.

The overall structure of React applications can be represented as a hierarchical tree structure, just like how the DOM itself is structure. There is an overarching root component at the top of the hierarchy that every other component sits underneath. Specifying that a component should be a child of some parent component is as simple as throwing it in the parent component's render function, just like how we did it in this example.

Ultimate Markdown Cheatsheet

Bryan C Guner — Fri, 15 Oct 2021 14:56:55 +0000

Ultimate Markdown Cheat Sheet

Standard features
- Headings
- Paragraphs
- Breaks
- Horizontal Rule
- Emphasis
- Bold
- Italics
- Blockquotes
- Lists
- Unordered
- Ordered
- Time-saving Tip
- Code
- Inline code
- "Fenced" code block
- Indented code
- Syntax highlighting
- Links
- Autolinks
- Inline links
- Link titles
- Named Anchors
- Images
- Raw HTML
- Escaping with backslashes
Non-standard features
- Strikethrough
- Todo List
- Tables
- Aligning cells
- Footnotes
- Inline footnotes
- Additional Information
- What is markdown?
- Other Resources
- Contributing

Standard features

The following markdown features are defined by the [CommonMark][] standard, and are generally supported by all markdown parsers and editors.

Headings

Headings from h1 through h6 are constructed with a # for each level:

# h1 Heading
## h2 Heading
### h3 Heading
#### h4 Heading
##### h5 Heading
###### h6 Heading

Renders to this HTML:

<h1>h1 Heading</h1>
<h2>h2 Heading</h2>
<h3>h3 Heading</h3>
<h4>h4 Heading</h4>
<h5>h5 Heading</h5>
<h6>h6 Heading</h6>

Which looks like this in the browser:

h1 Heading

h2 Heading

h3 Heading

h4 Heading

h5 Heading

h6 Heading

A note about "Setext" Headings

Note that this document only describes ATX headings, as it is the preferred syntax for writing headings. However, the CommonMark specification also describes Setext headings, a heading format that is denoted by a line of dashes or equal signes following the heading. It's recommended by the author of this guide that you use only ATX headings, as they are easier to write and read in text editors, and are less likeley to conflict with other syntaxes and demarcations from language extensions.

Paragraphs

Body copy written as normal plain-text will be wrapped with <p></p> tags in the rendered HTML.

So this:

Lorem ipsum dolor sit amet, graecis denique ei vel, at duo primis mandamus. Et legere ocurreret pri, animal tacimates complectitur ad cum. Cu eum inermis inimicus efficiendi. Labore officiis his ex, soluta officiis concludaturque ei qui, vide sensibus vim ad.

Renders to this HTML:

<p>Lorem ipsum dolor sit amet, graecis denique ei vel, at duo primis mandamus. Et legere ocurreret pri, animal tacimates complectitur ad cum. Cu eum inermis inimicus efficiendi. Labore officiis his ex, soluta officiis concludaturque ei qui, vide sensibus vim ad.</p>

Breaks

You can use multiple consecutive newline characters (\n) to create extra spacing between sections in a markdown document. However, if you need to ensure that extra newlines are not collapsed, you can use as many HTML <br> elements as you want.

Horizontal Rule

The HTML <hr> element is for creating a "thematic break" between paragraph-level elements. In markdown, you can use of the following for this purpose:

___: three consecutive underscores
---: three consecutive dashes
***: three consecutive asterisks

Renders to:

Emphasis

Bold

For emphasizing a snippet of text with a heavier font-weight.

The following snippet of text is rendered as bold text.

**rendered as bold text**

renders to:

rendered as bold text

and this HTML

<strong>rendered as bold text</strong>

Italics

For emphasizing a snippet of text with italics.

The following snippet of text is rendered as italicized text.

_rendered as italicized text_

renders to:

rendered as italicized text

and this HTML:

<em>rendered as italicized text</em>

Blockquotes

Used for defining a section of quoting text from another source, within your document.

To create a blockquote, use > before any text you want to quote.

> Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer posuere erat a ante

Renders to:

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer posuere erat a ante.

And the generated HTML from a markdown parser might look something like this:

<blockquote>
  <p>Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer posuere erat a ante.</p>
</blockquote>

Blockquotes can also be nested:

> Donec massa lacus, ultricies a ullamcorper in, fermentum sed augue.
Nunc augue augue, aliquam non hendrerit ac, commodo vel nisi.
>> Sed adipiscing elit vitae augue consectetur a gravida nunc vehicula. Donec auctor
odio non est accumsan facilisis. Aliquam id turpis in dolor tincidunt mollis ac eu diam.
>>> Donec massa lacus, ultricies a ullamcorper in, fermentum sed augue.
Nunc augue augue, aliquam non hendrerit ac, commodo vel nisi.

Renders to:

Donec massa lacus, ultricies a ullamcorper in, fermentum sed augue.
Nunc augue augue, aliquam non hendrerit ac, commodo vel nisi.

Sed adipiscing elit vitae augue consectetur a gravida nunc vehicula. Donec auctor
odio non est accumsan facilisis. Aliquam id turpis in dolor tincidunt mollis ac eu diam.

Donec massa lacus, ultricies a ullamcorper in, fermentum sed augue.
Nunc augue augue, aliquam non hendrerit ac, commodo vel nisi.

Lists

Unordered Lists

A list of items in which the order of the items does not explicitly matter.

You may use any of the following symbols to denote bullets for each list item:

* valid bullet
- valid bullet
+ valid bullet

For example

+ Lorem ipsum dolor sit amet
+ Consectetur adipiscing elit
+ Integer molestie lorem at massa
+ Facilisis in pretium nisl aliquet
+ Nulla volutpat aliquam velit
  - Phasellus iaculis neque
  - Purus sodales ultricies
  - Vestibulum laoreet porttitor sem
  - Ac tristique libero volutpat at
+ Faucibus porta lacus fringilla vel
+ Aenean sit amet erat nunc
+ Eget porttitor lorem

Renders to:

Lorem ipsum dolor sit amet
Consectetur adipiscing elit
Integer molestie lorem at massa
Facilisis in pretium nisl aliquet
Nulla volutpat aliquam velit
- Phasellus iaculis neque
- Purus sodales ultricies
- Vestibulum laoreet porttitor sem
- Ac tristique libero volutpat at
Faucibus porta lacus fringilla vel
Aenean sit amet erat nunc
Eget porttitor lorem

And this HTML

<ul>
  <li>Lorem ipsum dolor sit amet</li>
  <li>Consectetur adipiscing elit</li>
  <li>Integer molestie lorem at massa</li>
  <li>Facilisis in pretium nisl aliquet</li>
  <li>Nulla volutpat aliquam velit
    <ul>
      <li>Phasellus iaculis neque</li>
      <li>Purus sodales ultricies</li>
      <li>Vestibulum laoreet porttitor sem</li>
      <li>Ac tristique libero volutpat at</li>
    </ul>
  </li>
  <li>Faucibus porta lacus fringilla vel</li>
  <li>Aenean sit amet erat nunc</li>
  <li>Eget porttitor lorem</li>
</ul>

Ordered Lists

A list of items in which the order of items does explicitly matter.

1. Lorem ipsum dolor sit amet
2. Consectetur adipiscing elit
3. Integer molestie lorem at massa
4. Facilisis in pretium nisl aliquet
5. Nulla volutpat aliquam velit
6. Faucibus porta lacus fringilla vel
7. Aenean sit amet erat nunc
8. Eget porttitor lorem

Renders to:

Lorem ipsum dolor sit amet
Consectetur adipiscing elit
Integer molestie lorem at massa
Facilisis in pretium nisl aliquet
Nulla volutpat aliquam velit
Faucibus porta lacus fringilla vel
Aenean sit amet erat nunc
Eget porttitor lorem

And this HTML:

<ol>
  <li>Lorem ipsum dolor sit amet</li>
  <li>Consectetur adipiscing elit</li>
  <li>Integer molestie lorem at massa</li>
  <li>Facilisis in pretium nisl aliquet</li>
  <li>Nulla volutpat aliquam velit</li>
  <li>Faucibus porta lacus fringilla vel</li>
  <li>Aenean sit amet erat nunc</li>
  <li>Eget porttitor lorem</li>
</ol>

Time-saving Tip!

Sometimes lists change, and when they do it's a pain to re-order all of the numbers. Markdown solves this problem by allowing you to simply use 1. before each item in the list.

For example:

1. Lorem ipsum dolor sit amet
1. Consectetur adipiscing elit
1. Integer molestie lorem at massa
1. Facilisis in pretium nisl aliquet
1. Nulla volutpat aliquam velit
1. Faucibus porta lacus fringilla vel
1. Aenean sit amet erat nunc
1. Eget porttitor lorem

Automatically re-numbers the items and renders to:

Lorem ipsum dolor sit amet
Consectetur adipiscing elit
Integer molestie lorem at massa
Facilisis in pretium nisl aliquet
Nulla volutpat aliquam velit
Faucibus porta lacus fringilla vel
Aenean sit amet erat nunc
Eget porttitor lorem

Code

Inline code

Wrap inline snippets of code with a single backtick: `.

For example, to show <div></div> inline with other text, just wrap it in backticks.

html For example, to show

inline with other text, just wrap it in backticks.

"Fenced" code block

Three consecutive backticks, referred to as "code fences", are used to denote multiple lines of code: `.

For example, this:

```html
Example text here...
```

Renders to something like this in HTML:

`html

Example text here...

And appears like this when viewed in a browser:

` Example text here... `

Indented code

You may also indent several lines of code by at least four spaces, but this is not recommended as it is harder to read, harder to maintain, and doesn't support syntax highlighting.

Example:

` // Some comments line 1 of code line 2 of code line 3 of code `

// Some comments
line 1 of code
line 2 of code
line 3 of code

Syntax highlighting

Various markdown parsers, such as remarkable, support syntax highlighting with fenced code blocks. To activate the correct styling for the language inside the code block, simply add the file extension of the language you want to use directly after the first code "fence": `js, and syntax highlighting will automatically be applied in the rendered HTML (if supported by the parser). For example, to apply syntax highlighting to JavaScript code:

```js
grunt.initConfig({
  assemble: {
    options: {
      assets: 'docs/assets',
      data: 'src/data/*.{json,yml}',
      helpers: 'src/custom-helpers.js',
      partials: ['src/partials/**/*.{hbs,md}']
    },
    pages: {
      options: {
        layout: 'default.hbs'
      },
      files: {
        './': ['src/templates/pages/index.hbs']
      }
    }
  }
});
```

Which renders to:

js grunt.initConfig({ assemble: { options: { assets: 'docs/assets', data: 'src/data/*.{json,yml}', helpers: 'src/custom-helpers.js', partials: ['src/partials/**/*.{hbs,md}'] }, pages: { options: { layout: 'default.hbs' }, files: { './': ['src/templates/pages/index.hbs'] } } } });

And this complicated HTML is an example of what might be generated by the markdown parser, when syntax highlighting is applied by a library like highlight.js:

`xml

grunt.initConfig({
  assemble: {
    options: {
      assets: 'docs/assets',
      data: 'src/data/*.{json,yml}',
      helpers: 'src/custom-helpers.js',
      partials: ['src/partials/**/*.{hbs,md}']
    },
    pages: {
      options: {
        layout: 'default.hbs'
      },
      files: {
        './': ['src/templates/pages/index.hbs']
      }
    }
  }
});

Chapter 1

Content for chapter one.

Chapter 2

Content for chapter one.

Chapter 3

Content for chapter one.
`

Anchor placement

Note that placement of achors is arbitrary, you can put them anywhere you want, not just in headings. This makes adding cross-references easy when writing markdown.

Images

Images have a similar syntax to links but include a preceding exclamation point.

![Minion](http://octodex.github.com/images/minion.png)

![Alt text](http://octodex.github.com/images/stormtroopocat.jpg "The Stormtroopocat")

Like links, Images also have a footnote style syntax

![Alt text][id]

With a reference later in the document defining the URL location:

Raw HTML

Any text between < and > that looks like an HTML tag will be parsed as a raw HTML tag and rendered to HTML without escaping.

(Note that markdown parsers do not attempt to validate your HTML).

Example:

**Visit <a href="https://github.com">Jon Schlinkert's GitHub Profile</a>.**

Renders to:

Visit Jon Schlinkert's GitHub Profile.

Escaping with backslashes

Any ASCII punctuation character may be escaped using a single backslash.

Example:

\*this is not italic*

Renders to:

*this is not italic*

Non-standard features

The following markdown features are not defined by the [CommonMark][] specification, but they are commonly supported by markdown parsers and editors, as well as sites like GitHub and GitLab.

Strikethrough

In GitHub Flavored Markdown (GFM) you can do strickthroughs.

~~Strike through this text.~~

Which renders to:

~~Strike through this text.~~

Todo List

[ ] Lorem ipsum dolor sit amet
[ ] Consectetur adipiscing elit
[ ] Integer molestie lorem at massa `

Renders to:

[ ] Lorem ipsum dolor sit amet
[ ] Consectetur adipiscing elit
[ ] Integer molestie lorem at massa

Links in todo lists

[ ] foo
[ ] baz
[ ] fez `

Renders to:

[ ] foo
[ ] baz
[ ] fez

Tables

Tables are created by adding pipes as dividers between each cell, and by adding a line of dashes (also separated by bars) beneath the header (this line of dashes is required).

pipes do not need to be vertically aligned.
pipes on the left and right sides of the table are sometimes optional
three or more dashes must be used for each cell in the separator row (between the table header and body)
the left and right pipes are optional with some markdown parsers

Example:

| Option | Description | | --- | --- | | data | path to data files to supply the data that will be passed into templates. | | engine | engine to be used for processing templates. Handlebars is the default. | | ext | extension to be used for dest files. |

Renders to:

Option	Description
data	path to data files to supply the data that will be passed into templates.
engine	engine to be used for processing templates. Handlebars is the default.
ext	extension to be used for dest files.

And this HTML:

`html

Option	Description
data	path to data files to supply the data that will be passed into templates.
engine	engine to be used for processing templates. Handlebars is the default.
ext	extension to be used for dest files.

Aligning cells

Center text in a column

To center the text in a column, add a colon to the middle of the dashes in the row beneath the header.

| Option | Description | | -:- | -:- | | data | path to data files to supply the data that will be passed into templates. | | engine | engine to be used for processing templates. Handlebars is the default. | | ext | extension to be used for dest files. |

Right-align the text in a column

To right-align the text in a column, add a colon to the middle of the dashes in the row beneath the header.

| Option | Description | | --: | --:| | data | path to data files to supply the data that will be passed into templates. | | engine | engine to be used for processing templates. Handlebars is the default. | | ext | extension to be used for dest files. |

Renders to:

Option	Description
data	path to data files to supply the data that will be passed into templates.
engine	engine to be used for processing templates. Handlebars is the default.
ext	extension to be used for dest files.

Footnotes

Markdown footnotes are not officially suppored by the [CommonMark][] specification. However, the feature is supported by [remarkable][] and other markdown parsers, and it's very useful when available.

Markdown footnotes are denoted by an opening square bracket, followed by a caret, followed by a number and a closing square bracket: [^1].

This is some text[^1] with a footnote reference link.

The accompanying text for the footnote can be added elsewhere in the document using the following syntax:

When rendered to HTML, footnotes are "stacked" by the markdown parser at the bottom of the file, in the order in which the footnotes were defined.

Inline footnotes

Some markdown parsers like [Remarkable][remarkable] also support inline footnotes. Inline footnotes are written using the following syntax: [^2 "This is an inline footnote"].

Additional Information

What is markdown?

Markdown is "a plain text format for writing structured documents, based on formatting conventions from email and usenet" -- [CommonMark][]

Sites like GitHub and Stackoverflow have popularized the use markdown as a plain-text alternative to traditional text editors, for writing things like documentation and comments.

Other Resources

We've been trained to make paper - A great blog post about why markdown frees us from the shackles of proprietary formats imposed by bloated word processors, such as Microsoft Word.
CommonMark - "A strongly defined, highly compatible specification of Markdown"

Python Tutorial

Bryan C Guner — Wed, 15 Sep 2021 20:30:22 +0000

Liquid syntax error: Variable '{{% raw %}' was not properly terminated with regexp: /\}\}/

Awesome List Of Github Repositories

Bryan C Guner — Tue, 31 Aug 2021 15:49:22 +0000

Awesome List Of Github Repositories

GitHub - bgoonz/awesome-4-new-developers: Top repos for new developers all in one place

Top repos for new developers all in one place. Contribute to bgoonz/awesome-4-new-developers development by creating an…github.com

### Platforms

Node.js — Async non-blocking event-driven JavaScript runtime built on Chrome’s V8 JavaScript engine.
Cross-Platform — Writing cross-platform code on Node.js.
Frontend Development
iOS — Mobile operating system for Apple phones and tablets.
Android — Mobile operating system developed by Google.
IoT & Hybrid Apps
Electron — Cross-platform native desktop apps using JavaScript/HTML/CSS.
Cordova — JavaScript API for hybrid apps.
React Native — JavaScript framework for writing natively rendering mobile apps for iOS and Android.
Xamarin — Mobile app development IDE, testing, and distribution.
Linux
Containers
eBPF — Virtual machine that allows you to write more efficient and powerful tracing and monitoring for Linux systems.
Arch-based Projects — Linux distributions and projects based on Arch Linux.
macOS — Operating system for Apple’s Mac computers.
Command-Line
Screensavers
Apps
Open Source Apps
watchOS — Operating system for the Apple Watch.
JVM
Salesforce
Amazon Web Services
Windows
IPFS — P2P hypermedia protocol.
Fuse — Mobile development tools.
Heroku — Cloud platform as a service.
Raspberry Pi — Credit card-sized computer aimed at teaching kids programming, but capable of a lot more.
Qt — Cross-platform GUI app framework.
WebExtensions — Cross-browser extension system.
RubyMotion — Write cross-platform native apps for iOS, Android, macOS, tvOS, and watchOS in Ruby.
Smart TV — Create apps for different TV platforms.
GNOME — Simple and distraction-free desktop environment for Linux.
KDE — A free software community dedicated to creating an open and user-friendly computing experience.
.NET
Core
Roslyn — Open-source compilers and code analysis APIs for C# and VB.NET languages.
Amazon Alexa — Virtual home assistant.
DigitalOcean — Cloud computing platform designed for developers.
Flutter — Google’s mobile SDK for building native iOS and Android apps from a single codebase written in Dart.
Home Assistant — Open source home automation that puts local control and privacy first.
IBM Cloud — Cloud platform for developers and companies.
Firebase — App development platform built on Google Cloud Platform.
Robot Operating System 2.0 — Set of software libraries and tools that help you build robot apps.
Adafruit IO — Visualize and store data from any device.
Cloudflare — CDN, DNS, DDoS protection, and security for your site.
Actions on Google — Developer platform for Google Assistant.
ESP — Low-cost microcontrollers with WiFi and broad IoT applications.
Deno — A secure runtime for JavaScript and TypeScript that uses V8 and is built in Rust.
DOS — Operating system for x86-based personal computers that was popular during the 1980s and early 1990s.
Nix — Package manager for Linux and other Unix systems that makes package management reliable and reproducible.

Programming Languages

JavaScript
Promises
Standard Style — Style guide and linter.
Must Watch Talks
Tips
Network Layer
Micro npm Packages
Mad Science npm Packages — Impossible sounding projects that exist.
Maintenance Modules — For npm packages.
npm — Package manager.
AVA — Test runner.
ESLint — Linter.
Functional Programming
Observables
npm scripts — Task runner.
30 Seconds of Code — Code snippets you can understand in 30 seconds.
Ponyfills — Like polyfills but without overriding native APIs.
Swift — Apple’s compiled programming language that is secure, modern, programmer-friendly, and fast.
Education
Playgrounds
Python — General-purpose programming language designed for readability.
Asyncio — Asynchronous I/O in Python 3.
Scientific Audio — Scientific research in audio/music.
CircuitPython — A version of Python for microcontrollers.
Data Science — Data analysis and machine learning.
Typing — Optional static typing for Python.
MicroPython — A lean and efficient implementation of Python 3 for microcontrollers.
Rust
Haskell
PureScript
Go
Scala
Scala Native — Optimizing ahead-of-time compiler for Scala based on LLVM.
Ruby
Clojure
ClojureScript
Elixir
Elm
Erlang
Julia — High-level dynamic programming language designed to address the needs of high-performance numerical analysis and computational science.
Lua
C
C/C++ — General-purpose language with a bias toward system programming and embedded, resource-constrained software.
R — Functional programming language and environment for statistical computing and graphics.
Learning
D
Common Lisp — Powerful dynamic multiparadigm language that facilitates iterative and interactive development.
Learning
Perl
Groovy
Dart
Java — Popular secure object-oriented language designed for flexibility to “write once, run anywhere”.
RxJava
Kotlin
OCaml
ColdFusion
Fortran
PHP — Server-side scripting language.
Composer — Package manager.
Pascal
AutoHotkey
AutoIt
Crystal
Frege — Haskell for the JVM.
CMake — Build, test, and package software.
ActionScript 3 — Object-oriented language targeting Adobe AIR.
Eta — Functional programming language for the JVM.
Idris — General purpose pure functional programming language with dependent types influenced by Haskell and ML.
Ada/SPARK — Modern programming language designed for large, long-lived apps where reliability and efficiency are essential.
Q# — Domain-specific programming language used for expressing quantum algorithms.
Imba — Programming language inspired by Ruby and Python and compiles to performant JavaScript.
Vala — Programming language designed to take full advantage of the GLib and GNOME ecosystems, while preserving the speed of C code.
Coq — Formal language and environment for programming and specification which facilitates interactive development of machine-checked proofs.
V — Simple, fast, safe, compiled language for developing maintainable software.

Front-End Development

ES6 Tools
Web Performance Optimization
Web Tools
CSS — Style sheet language that specifies how HTML elements are displayed on screen.
Critical-Path Tools
Scalability
Must-Watch Talks
Protips
Frameworks
React — App framework.
Relay — Framework for building data-driven React apps.
React Hooks — A new feature that lets you use state and other React features without writing a class.
Web Components
Polymer — JavaScript library to develop Web Components.
Angular — App framework.
Backbone — App framework.
HTML5 — Markup language used for websites & web apps.
SVG — XML-based vector image format.
Canvas
KnockoutJS — JavaScript library.
Dojo Toolkit — JavaScript toolkit.
Inspiration
Ember — App framework.
Android UI
iOS UI
Meteor
BEM
Flexbox
Web Typography
Web Accessibility
Material Design
D3 — Library for producing dynamic, interactive data visualizations.
Emails
jQuery — Easy to use JavaScript library for DOM manipulation.
Tips
Web Audio
Offline-First
Static Website Services
Cycle.js — Functional and reactive JavaScript framework.
Text Editing
Motion UI Design
Vue.js — App framework.
Marionette.js — App framework.
Aurelia — App framework.
Charting
Ionic Framework 2
Chrome DevTools
PostCSS — CSS tool.
Draft.js — Rich text editor framework for React.
Service Workers
Progressive Web Apps
choo — App framework.
Redux — State container for JavaScript apps.
webpack — Module bundler.
Browserify — Module bundler.
Sass — CSS preprocessor.
Ant Design — Enterprise-class UI design language.
Less — CSS preprocessor.
WebGL — JavaScript API for rendering 3D graphics.
Preact — App framework.
Progressive Enhancement
Next.js — Framework for server-rendered React apps.
lit-html — HTML templating library for JavaScript.
JAMstack — Modern web development architecture based on client-side JavaScript, reusable APIs, and prebuilt markup.
WordPress-Gatsby — Web development technology stack with WordPress as a back end and Gatsby as a front end.
Mobile Web Development — Creating a great mobile web experience.
Storybook — Development environment for UI components.
Blazor — .NET web framework using C#/Razor and HTML that runs in the browser with WebAssembly.
PageSpeed Metrics — Metrics to help understand page speed and user experience.
Tailwind CSS — Utility-first CSS framework for rapid UI development.
Seed — Rust framework for creating web apps running in WebAssembly.
Web Performance Budget — Techniques to ensure certain performance metrics for a website.
Web Animation — Animations in the browser with JavaScript, CSS, SVG, etc.
Yew — Rust framework inspired by Elm and React for creating multi-threaded frontend web apps with WebAssembly.
Material-UI — Material Design React components for faster and easier web development.
Building Blocks for Web Apps — Standalone features to be integrated into web apps.
Svelte — App framework.
Design systems — Collection of reusable components, guided by rules that ensure consistency and speed.
Inertia.js — Make single-page apps without building an API.
MDBootstrap — Templates, layouts, components, and widgets to rapidly build websites.

Back-End Development

Flask — Python framework.
Docker
Vagrant — Automation virtual machine environment.
Pyramid — Python framework.
Play1 Framework
CakePHP — PHP framework.
Symfony — PHP framework.
Education
Laravel — PHP framework.
Education
TALL Stack — Full-stack development solution featuring libraries built by the Laravel community.
Rails — Web app framework for Ruby.
Gems — Packages.
Phalcon — PHP framework.
Useful .htaccess Snippets
nginx — Web server.
Dropwizard — Java framework.
Kubernetes — Open-source platform that automates Linux container operations.
Lumen — PHP micro-framework.
Serverless Framework — Serverless computing and serverless architectures.
Apache Wicket — Java web app framework.
Vert.x — Toolkit for building reactive apps on the JVM.
Terraform — Tool for building, changing, and versioning infrastructure.
Vapor — Server-side development in Swift.
Dash — Python web app framework.
FastAPI — Python web app framework.
CDK — Open-source software development framework for defining cloud infrastructure in code.
IAM — User accounts, authentication and authorization.

Computer Science

University Courses
Data Science
Tutorials
Machine Learning
Tutorials
ML with Ruby — Learning, implementing, and applying Machine Learning using Ruby.
Core ML Models — Models for Apple’s machine learning framework.
H2O — Open source distributed machine learning platform written in Java with APIs in R, Python, and Scala.
Software Engineering for Machine Learning — From experiment to production-level machine learning.
AI in Finance — Solving problems in finance with machine learning.
JAX — Automatic differentiation and XLA compilation brought together for high-performance machine learning research.
XAI — Providing insight, explanations, and interpretability to machine learning methods.
Speech and Natural Language Processing
Spanish
NLP with Ruby
Question Answering — The science of asking and answering in natural language with a machine.
Natural Language Generation — Generation of text used in data to text, conversational agents, and narrative generation applications.
Linguistics
Cryptography
Papers — Theory basics for using cryptography by non-cryptographers.
Computer Vision
Deep Learning — Neural networks.
TensorFlow — Library for machine intelligence.
TensorFlow.js — WebGL-accelerated machine learning JavaScript library for training and deploying models.
TensorFlow Lite — Framework that optimizes TensorFlow models for on-device machine learning.
Papers — The most cited deep learning papers.
Education
Deep Vision
Open Source Society University
Functional Programming
Empirical Software Engineering — Evidence-based research on software systems.
Static Analysis & Code Quality
Information Retrieval — Learn to develop your own search engine.
Quantum Computing — Computing which utilizes quantum mechanics and qubits on quantum computers.
Theoretical Computer Science — The interplay of computer science and pure mathematics, distinguished by its emphasis on mathematical rigour and technique.

Big Data

Big Data
Public Datasets
Hadoop — Framework for distributed storage and processing of very large data sets.
Data Engineering
Streaming
Apache Spark — Unified engine for large-scale data processing.
Qlik — Business intelligence platform for data visualization, analytics, and reporting apps.
Splunk — Platform for searching, monitoring, and analyzing structured and unstructured machine-generated big data in real-time.

Theory

Papers We Love
Talks
Algorithms
Education — Learning and practicing.
Algorithm Visualizations
Artificial Intelligence
Search Engine Optimization
Competitive Programming
Math
Recursion Schemes — Traversing nested data structures.

Books

Editors

Sublime Text
Vim
Emacs
Atom — Open-source and hackable text editor.
Visual Studio Code — Cross-platform open-source text editor.

Gaming

Game Development
Game Talks
Godot — Game engine.
Open Source Games
Unity — Game engine.
Chess
LÖVE — Game engine.
PICO-8 — Fantasy console.
Game Boy Development
Construct 2 — Game engine.
Gideros — Game engine.
Minecraft — Sandbox video game.
Game Datasets — Materials and datasets for Artificial Intelligence in games.
Haxe Game Development — A high-level strongly typed programming language used to produce cross-platform native code.
libGDX — Java game framework.
PlayCanvas — Game engine.
Game Remakes — Actively maintained open-source game remakes.
Flame — Game engine for Flutter.
Discord Communities — Chat with friends and communities.
CHIP-8 — Virtual computer game machine from the 70s.
Games of Coding — Learn a programming language by making games.

Development Environment

Quick Look Plugins — For macOS.
Dev Env
Dotfiles
Shell
Fish — User-friendly shell.
Command-Line Apps
ZSH Plugins
GitHub — Hosting service for Git repositories.
Browser Extensions
Cheat Sheet
Pinned Gists — Dynamic pinned gists for your GitHub profile.
Git Cheat Sheet & Git Flow
Git Tips
Git Add-ons — Enhance the git CLI.
Git Hooks — Scripts for automating tasks during git workflows.
SSH
FOSS for Developers
Hyper — Cross-platform terminal app built on web technologies.
PowerShell — Cross-platform object-oriented shell.
Alfred Workflows — Productivity app for macOS.
Terminals Are Sexy
GitHub Actions — Create tasks to automate your workflow and share them with others on GitHub.

Entertainment

Databases

Database
MySQL
SQLAlchemy
InfluxDB
Neo4j
MongoDB — NoSQL database.
RethinkDB
TinkerPop — Graph computing framework.
PostgreSQL — Object-relational database.
CouchDB — Document-oriented NoSQL database.
HBase — Distributed, scalable, big data store.
NoSQL Guides — Help on using non-relational, distributed, open-source, and horizontally scalable databases.
Contexture — Abstracts queries/filters and results/aggregations from different backing data stores like ElasticSearch and MongoDB.
Database Tools — Everything that makes working with databases easier.
TypeDB — Logical database to organize large and complex networks of data as one body of knowledge.
Cassandra — Open-source, distributed, wide column store, NoSQL database management system.

Media

Creative Commons Media
Fonts
Codeface — Text editor fonts.
Stock Resources
GIF — Image format known for animated images.
Music
Open Source Documents
Audio Visualization
Broadcasting
Pixel Art — Pixel-level digital art.
FFmpeg — Cross-platform solution to record, convert and stream audio and video.
Icons — Downloadable SVG/PNG/font icon projects.
Audiovisual — Lighting, audio and video in professional environments.
VLC — Cross-platform media player software and streaming server.

Learn

CLI Workshoppers — Interactive tutorials.
Learn to Program
Speaking
Tech Videos
Dive into Machine Learning
Computer History
Programming for Kids
Educational Games — Learn while playing.
JavaScript Learning
CSS Learning — Mainly about CSS — the language and the modules.
Product Management — Learn how to be a better product manager.
Roadmaps — Gives you a clear route to improve your knowledge and skills.
YouTubers — Watch video tutorials from YouTubers that teach you about technology.

Security

Application Security
Security
CTF — Capture The Flag.
Malware Analysis
Android Security
Hacking
Honeypots — Deception trap, designed to entice an attacker into attempting to compromise the information systems in an organization.
Incident Response
Vehicle Security and Car Hacking
Web Security — Security of web apps & services.
Lockpicking — The art of unlocking a lock by manipulating its components without the key.
Cybersecurity Blue Team — Groups of individuals who identify security flaws in information technology systems.
Fuzzing — Automated software testing technique that involves feeding pseudo-randomly generated input data.
Embedded and IoT Security
GDPR — Regulation on data protection and privacy for all individuals within EU.
DevSecOps — Integration of security practices into DevOps.

Content Management Systems

Umbraco
Refinery CMS — Ruby on Rails CMS.
Wagtail — Django CMS focused on flexibility and user experience.
Textpattern — Lightweight PHP-based CMS.
Drupal — Extensible PHP-based CMS.
Craft CMS — Content-first CMS.
Sitecore — .NET digital marketing platform that combines CMS with tools for managing multiple websites.
Silverstripe CMS — PHP MVC framework that serves as a classic or headless CMS.

Hardware

Robotics
Internet of Things
Electronics — For electronic engineers and hobbyists.
Bluetooth Beacons
Electric Guitar Specifications — Checklist for building your own electric guitar.
Plotters — Computer-controlled drawing machines and other visual art robots.
Robotic Tooling — Free and open tools for professional robotic development.
LIDAR — Sensor for measuring distances by illuminating the target with laser light.

Business

Open Companies
Places to Post Your Startup
OKR Methodology — Goal setting & communication best practices.
Leading and Managing — Leading people and being a manager in a technology company/environment.
Indie — Independent developer businesses.
Tools of the Trade — Tools used by companies on Hacker News.
Clean Tech — Fighting climate change with technology.
Wardley Maps — Provides high situational awareness to help improve strategic planning and decision making.
Social Enterprise — Building an organization primarily focused on social impact that is at least partially self-funded.
Engineering Team Management — How to transition from software development to engineering management.
Developer-First Products — Products that target developers as the user.
Billing — Payments, invoicing, pricing, accounting, marketplace, fraud, and business intelligence.

Work

Slack — Team collaboration.
Communities
Remote Jobs
Productivity
Niche Job Boards
Programming Interviews
Code Review — Reviewing code.
Creative Technology — Businesses & groups that specialize in combining computing, design, art, and user experience.
Internships — CV writing guides and companies that hire interns.

Networking

Software-Defined Networking
Network Analysis
PCAPTools
Real-Time Communications — Network protocols for near simultaneous exchange of media and data.

Decentralized Systems

Bitcoin — Bitcoin services and tools for software developers.
Ripple — Open source distributed settlement network.
Non-Financial Blockchain — Non-financial blockchain applications.
Mastodon — Open source decentralized microblogging network.
Ethereum — Distributed computing platform for smart contract development.
Blockchain AI — Blockchain projects for artificial intelligence and machine learning.
EOSIO — A decentralized operating system supporting industrial-scale apps.
Corda — Open source blockchain platform designed for business.
Waves — Open source blockchain platform and development toolset for Web 3.0 apps and decentralized solutions.
Substrate — Framework for writing scalable, upgradeable blockchains in Rust.
Golem — Open source peer-to-peer marketplace for computing resources.
Stacks — A smart contract platform secured by Bitcoin.

Higher Education

Computational Neuroscience — A multidisciplinary science which uses computational approaches to study the nervous system.
Digital History — Computer-aided scientific investigation of history.
Scientific Writing — Distraction-free scientific writing with Markdown, reStructuredText and Jupyter notebooks.

Events

Creative Tech Events — Events around the globe for creative coding, tech, design, music, arts and cool stuff.
Events in Italy — Tech-related events in Italy.
Events in the Netherlands — Tech-related events in the Netherlands.

Testing

Testing — Software testing.
Visual Regression Testing — Ensures changes did not break the functionality or style.
Selenium — Open-source browser automation framework and ecosystem.
Appium — Test automation tool for apps.
TAP — Test Anything Protocol.
JMeter — Load testing and performance measurement tool.
k6 — Open-source, developer-centric performance monitoring and load testing solution.
Playwright — Node.js library to automate Chromium, Firefox and WebKit with a single API.
Quality Assurance Roadmap — How to start & build a career in software testing.

Miscellaneous

JSON — Text based data interchange format.
GeoJSON
Datasets
CSV — A text file format that stores tabular data and uses a comma to separate values.
Discounts for Student Developers
Radio
Awesome — Recursion illustrated.
Analytics
REST
Continuous Integration and Continuous Delivery
Services Engineering
Free for Developers
Answers — Stack Overflow, Quora, etc.
Sketch — Design app for macOS.
Boilerplate Projects
Readme
Design and Development Guides
Software Engineering Blogs
Self Hosted
FOSS Production Apps
Gulp — Task runner.
AMA — Ask Me Anything.
Answers
Open Source Photography
OpenGL — Cross-platform API for rendering 2D and 3D graphics.
GraphQL
Urban & Regional Planning — Concerning the built environment and communities.
Transit
Research Tools
Data Visualization
Social Media Share Links
Microservices
Unicode — Unicode standards, quirks, packages and resources.
Code Points
Beginner-Friendly Projects
Katas
Tools for Activism
Citizen Science — For community-based and non-institutional scientists.
MQTT — “Internet of Things” connectivity protocol.
Hacking Spots
For Girls
Vorpal — Node.js CLI framework.
Vulkan — Low-overhead, cross-platform 3D graphics and compute API.
LaTeX — Typesetting language.
Economics — An economist’s starter kit.
Funny Markov Chains
Bioinformatics
Cheminformatics — Informatics techniques applied to problems in chemistry.
Colorful — Choose your next color scheme.
Steam — Digital distribution platform.
Bots — Building bots.
Site Reliability Engineering
Empathy in Engineering — Building and promoting more compassionate engineering cultures.
DTrace — Dynamic tracing framework.
Userscripts — Enhance your browsing experience.
Pokémon — Pokémon and Pokémon GO.
ChatOps — Managing technical and business operations through a chat.
Falsehood — Falsehoods programmers believe in.
Domain-Driven Design — Software development approach for complex needs by connecting the implementation to an evolving model.
Quantified Self — Self-tracking through technology.
SaltStack — Python-based config management system.
Web Design — For digital designers.
Creative Coding — Programming something expressive instead of something functional.
No-Login Web Apps — Web apps that work without login.
Free Software — Free as in freedom.
Framer — Prototyping interactive UI designs.
Markdown — Markup language.
Dev Fun — Funny developer projects.
Healthcare — Open source healthcare software for facilities, providers, developers, policy experts, and researchers.
Magento 2 — Open Source eCommerce built with PHP.
TikZ — Graph drawing packages for TeX/LaTeX/ConTeXt.
Neuroscience — Study of the nervous system and brain.
Ad-Free — Ad-free alternatives.
Esolangs — Programming languages designed for experimentation or as jokes rather than actual use.
Prometheus — Open-source monitoring system.
Homematic — Smart home devices.
Ledger — Double-entry accounting on the command-line.
Web Monetization — A free open web standard service that allows you to send money directly in your browser.
Uncopyright — Public domain works.
Crypto Currency Tools & Algorithms — Digital currency where encryption is used to regulate the generation of units and verify transfers.
Diversity — Creating a more inclusive and diverse tech community.
Open Source Supporters — Companies that offer their tools and services for free to open source projects.
Design Principles — Create better and more consistent designs and experiences.
Theravada — Teachings from the Theravada Buddhist tradition.
inspectIT — Open source Java app performance management tool.
Open Source Maintainers — The experience of being an open source maintainer.
Calculators — Calculators for every platform.
Captcha — A type of challenge–response test used in computing to determine whether or not the user is human.
Jupyter — Create and share documents that contain code, equations, visualizations and narrative text.
FIRST Robotics Competition — International high school robotics championship.
Humane Technology — Open source projects that help improve society.
Speakers — Conference and meetup speakers in the programming and design community.
Board Games — Table-top gaming fun for all.
Software Patreons — Fund individual programmers or the development of open source projects.
Parasite — Parasites and host-pathogen interactions.
Food — Food-related projects on GitHub.
Mental Health — Mental health awareness and self-care in the software industry.
Bitcoin Payment Processors — Start accepting Bitcoin.
Scientific Computing — Solving complex scientific problems using computers.
Amazon Sellers
Agriculture — Open source technology for farming and gardening.
Product Design — Design a product from the initial concept to production.
Prisma — Turn your database into a GraphQL API.
Software Architecture — The discipline of designing and building software.
Connectivity Data and Reports — Better understand who has access to telecommunication and internet infrastructure and on what terms.
Stacks — Tech stacks for building different apps and features.
Cytodata — Image-based profiling of biological phenotypes for computational biologists.
IRC — Open source messaging protocol.
Advertising — Advertising and programmatic media for websites.
Earth — Find ways to resolve the climate crisis.
Naming — Naming things in computer science done right.
Biomedical Information Extraction — How to extract information from unstructured biomedical data and text.
Web Archiving — An effort to preserve the Web for future generations.
WP-CLI — Command-line interface for WordPress.
Credit Modeling — Methods for classifying credit applicants into risk classes.
Ansible — A Python-based, open source IT configuration management and automation platform.
Biological Visualizations — Interactive visualization of biological data on the web.
QR Code — A type of matrix barcode that can be used to store and share a small amount of information.
Veganism — Making the plant-based lifestyle easy and accessible.
Translations — The transfer of the meaning of a text from one language to another.
Scriptable — An iOS app for automations in JavaScript.

All Awesome Lists — All the Awesome lists on GitHub.
Awesome Indexed — Search the Awesome dataset.
Awesome Search — Quick search for Awesome lists.
StumbleUponAwesome — Discover random pages from the Awesome dataset using a browser extension.
Awesome CLI — A simple command-line tool to dive into Awesome lists.
Awesome Viewer — A visualizer for all of the above Awesome lists.
Track Awesome List — View the latest updates of Awesome lists.

DEV Community: Bryan C Guner

Disorganized List Of Everything A New Web Developer Needs To Know

Tree Data Structure 🌲🌴🌳🎋

The Tree data structure (In Javascript)

Definition

Complexity

The code

What is a relational database?

What is a relational database?

Relational vs NoSQL

When Do You Use NoSQL Versus a Relational Database?

PostgreSQL

SQL, Structured Query Language

Create a table with CREATE TABLE

Create a row with INSERT

Read rows with SELECT

Update rows with UPDATE

Delete rows with DELETE

Deleting entire tables with DROP

The WHERE Clause

AND, OR, and Parentheses

LIKE

Column Data Types

ACID and CRUD

ACID

CRUD

NULL and NOT NULL

COUNT

count

ORDER BY

GROUP BY

Keys: Primary, Foreign, and Composite

Primary Key

Foreign Keys

Composite Keys

Auto-increment Columns

Joins

Inner Join, The Most Common Join

Left Outer Join

Right Outer Join

Full Outer Join

Indexes

Transactions

The EXPLAIN Command

Quick and Dirty DB Design

Normalization and Normal Forms

Anomalies

First Normal Form (1NF)

Second Normal Form (2NF)

Third Normal Form (3NF)

More reading:

Node-Postgres

Security

PostgreSQL Password

Writing Client Software

Other Relational Databases

Assignment: Install PostgreSQL

Mac with Homebrew

Windows

Arch Linux

Assignment: Create a Table and Use It

Assignment: NodeJS Program to Create and Populate a Table

Assignment: Command-line Earthquake Query Tool

Assignment: RESTful Earthquake Data Server

Fundamental Data Structures in JavaScript

Fundamental Data Structures in JavaScript

(and a bit of python pseudo code)

Table Of Contents:

Resuorces:

Data Structures & Algorithms Resource List Part 1

Guess the author of the following quotes:

Update:

Algorithms

Data Structures:

Linked Lists

What is a Linked List?

Time and Space Complexity Analysis

Time Complexity — Access and Search

Scenarios

Discussion

The `WHERE` Clause

`AND`, `OR`, and Parentheses

`LIKE`