Data structures

linked list

double linked list

stack

space O(n)
push O(1)
pop O(1)
peek O(1) see what is on top

queue

enqueue
dequeueu

graph

tree

binary trees

trie

A trie, also known as a prefix tree or digital tree, is a type of search tree used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

Here are the key characteristics and components of a trie:

1. Nodes and Edges: Each node represents a single character of a key. The root is typically an empty node, and each subsequent level represents the characters of the keys in sequence.

2. Insertion: Keys are inserted by adding nodes along the path from the root to the leaf that spells out the key. If a prefix of the key is already present in the trie, only the remaining suffix is added.

3. Searching: To search for a key, start from the root and follow the edges corresponding to the characters of the key. If you reach a leaf node or the desired key node, the key is present.

4. Efficiency: Tries provide efficient O(m) time complexity for insertion, deletion, and search operations, where m is the length of the key. This makes them particularly suitable for autocomplete and spell-checking applications.

5. Memory Usage: While tries can be memory efficient for a small set of keys with common prefixes, they can become space-inefficient when keys are sparse or do not share prefixes.

Example

Consider inserting the words "bat", "ball", and "cat" into a trie:

        root
       /   \
      b     c
     / \     \
    a   a     a
   /     \     \
  t       l     t
           \
            l

• The path to "bat" is root -> b -> a -> t.
• The path to "ball" is root -> b -> a -> l -> l.
• The path to "cat" is root -> c -> a -> t.

Applications

1. Autocomplete Systems: Tries are used to suggest words based on prefixes typed by the user.
2. Spell Checkers: To validate words and suggest corrections.
3. IP Routing: Used in networking for longest prefix matching in IP routing tables.
4. Dictionary Implementation: Efficiently storing and searching words in a dictionary.

Would you like more details on any specific aspect of tries or their implementation?

hash table

also called dictionary.
key/value pairs.
hashes a value with a hash function and stores the value in a bucket.
it is a tradeoff of better time complexity for worse space complexity.

assuming there are no hash collision, time complexity is O(1) for search, insert and deletion.
if there is collision, the worst case can be O(n).

Set

list of unique values.
are implemented using hash tables.
unlike a dictionary, it has no key/value pairs, just values.

time complexity is O(1) for insert, delete and search.

algorithms

Search

binary search

best one for sorted arrays.

Sort

quick sort

choosing pivot -> placing all lesser values left and greater to the right until pivot is in right position.
repeat with left and right subarrays until all pivots are in the correct position.

worse case O(n^2) with bad luck. avg is O(nlogn) and a bit faster then merge sort in most cases.

merge sort

recursively divide array in 2 equal parts.
base case is when array is 1 or 0, it is considered sorted and returned up the stack.
when returned you merge both sorted subarrays into 1 sorted array, all the way back up.

bubble sort

double for loop. compare each 'i' num in the list against the rest of the list.
O(n^2)

Graphs traversal

DFS and BFS

Dijsktra