Grokking algorithms

notes on the grokking algorithms illustrated book

Linked list over arrays for lots of writes and little reads

Quicksort. Alg recursivo de ordenamiento
Caso base es arreglo tiene <=1 elementos
Picks a pivot index

Particiona el arreglo en elementos menores y mayores que el pivot. Aplica quicksort a las particiones. Qs(menores) + pivot+ qs(mayores).

The quicksort implementatio presented on the quicksort chapter in memory inneficient. The benefit of quicksort over merge sort is that it doesn't need memory allocation. There is a better implementation.

Do they fix it in later chapters?

Hash functions receive a string and turn it into a number consistently. The number outputted represent ls where in memory a value is stored.

SHA1 for examples turns a string (or any data; photos, videos, files), into a 160 bit hash. If what is hashed is like a long file SHA executes in every 512 block of data. If a block has less than 512 bits padding is added (10000...0111).

Hashing most common use is  storing passwords. Where no one looking at a DB should be able to read users  passwords.

Im thinking just hashing isnt enough bc lets say a hacker gets access to a hashed password, he could just run

Hashing vs Encryption

Encryption transforms data with the goal to the retroeved back. The receiver of an ecrypted message needs to know de key/steps to decrypt.

Hashed data is not meant to be retrieved.

Graphs

Breadth first search. I want to find shortest path from a given node to a node that passses a condition.

Initialize a queue and a map for adding checked nodes. Add given node's neighbors to queue

Traverse queue, for each node
Get/pop current node from queue

Check that current node isnt checked and if passes condition end/return. Else add current node's neighbors to queue and add entry to checked map.

If everything is traversed return false.

This alg is O(V+E) vertices/nodes + edges