# Quick Tips

## Solving problems

### Think of data structures

Example:

## Hashtables

`collections.OrderedDict`

`collections.OrderedDict()`

can be used as a `stack`

with the help of `.popitem()`

and a queue with `.popitem(last=False)`

## Binary trees

### Definition of terms

A ** balanced binary tree** is a binary tree in which the height of the left and right subtree of any node

*differ by not more than 1*.

A ** complete binary tree** is a binary tree in which

*every level*,

*except possibly the last is completely filled*, and

*all nodes are as far left as possible*

A ** full binary tree** is a binary tree in which every node other than the leaves

*has two children*.

A ** perfect binary tree** is a full binary tree in which

*all leaves are at the same depth*, and in which

*every parent has two children*. (every level of the tree is completely full)

**Binary Search Tree**

The key lookup, insertion, and deletion take time proportional to the height of the tree, which can in the **worst-case be O(n)** if insertions and deletions are naively implemented. Eg if the tree looks like a linked list.

When we are talking about the *average case*, it is the time it takes for the operation on a **balanced tree**, and when we are talking about the *worst case*, it is the time it takes for the given operation on a **non-balanced tree**.

## Graphs

Vertex/Node & Edge/Arc

### Topological ordering

Vertices in a directed acyclic graph that have no incoming edges are referred to as *sources**.* Vertices that have no outgoing edges are referred to as *sinks***.

** Indegree** → count of incoming edges of each vertex/node or how many parents it has (used to determine sources)

**Representing Graphs in Code**

**Edge List**: well suited to performant lookups of an edge, or listing all edges

**Adjacency List:** this representation allows for constant-time lookup of adjacent vertices, which is useful in many query and pathfinding scenarios.

**Adjacency Matrix:** O(1) edge lookups. Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or 0

**DFS & BFS**

The Time complexity of BFS is `O(V+E)`

when Adjacency List is used and `O(V^2)`

when Adjacency Matrix is used, where V stands for vertices and E stands for edges.

`stack`

for DFS, imagine a vertical flow `queue`

for BFS, horizontal flow

Remember to unvisit nodes when doing DFS on a graph

### Dijkstra's Algorithm Time & Space complexity

`O((v + e) * log(v))`

time | `O(v)`

space - where v is the number of vertices and e is the number of edges in the input graph

## Searching

### Quick select

```
""" Time complexity
Best: O(n) time | O(1) space - where n is the length of the input array
Average: O(n) time | O(1) space
Worst: O(n^2) time | O(1) space
"""
```

## Sorting

### Bubble sort

```
# Best: O(n) time | O(1) space -> if already sorted
# Average: O(n^2) time | O(1) space
# Worst: O(n^2) time | O(1) space
```

### Insertion sort

- Take an element from the second and insert it to the first.
- Sort the first using something similar to Bubble sort.

```
# Best: O(n) time | O(1) space -> if already sorted
# Average: O(n^2) time | O(1) space
# Worst: O(n^2) time | O(1) space
```

### Selection sort

Divide the input array into two subarrays in place. The first subarray should be sorted at all times and should start with a length of 0, while the second subarray should be unsorted. **Select the smallest (or largest) element** in the unsorted subarray and insert it into the sorted subarray with a swap.

```
# Best: O(n^2) time | O(1) space
# Average: O(n^2) time | O(1) space
# Worst: O(n^2) time | O(1) space
```

### Merge Sort

two halves → merge. The time complexity of merge sort is `n log(n)`

### Quicksort

- We first select an element that we will call the
*pivot*from the array. - Move all elements that are
*smaller*than the pivot to the*left*of the*pivot*; move all elements that are*larger*than the*pivot*to the*right*of the*pivot*. This is called the**partition operation**. - Recursively apply the above 2 steps separately to each of the sub-arrays of elements with
*smaller*and*bigger*values than the last pivot.

```
# Average: O(nlog(n)) time | O(log(n)) space
# Worst: O(n^2) time | O(log(n)) space
```

### Heap Sort

*Heap sort* is the improved version of the Selection sort, which takes advantage of a heap data structure rather than a *linear-time search* to find the *max* value item. Using the heap, finding the *next largest element* takes ** O(log(n))** time, instead of

**for a**

`O(n)`

*linear*scan as in simple selection sort. This allows heap sort to run in

**time, and this is also the**

`O(n log(n))`

*worst-case*complexity.

Find the original version of this page (with additional content) on Notion here.

Created: November 20, 2021 07:19:02