## Shortcut to seniority

##### Home

Go to main page

##### Section level: Junior

A journey into the programming realm

##### Section level: Intermediate

The point of no return

##### Section level: Senior

Leaping into the unknown

You are not allowed to print this document.

Go to main page

A journey into the programming realm

The point of no return

Leaping into the unknown

Data structures and algorithms topics are tightly coupled, and both of them should be taken into account when designing our application.

An array is an area of allocated memory for a set of elements of a known (fixed) size. The data stored in the arrays is allocated in contiguous memory (memory blocks have consecutive addresses).

Let's say we have:

- an array with 4 elements (30, 34, 27, 68)
- the size of an element being 4 bytes
- the array starting from memory address 0xABCDEF00

The following table displays the memory address for the elements in the array.

Index | Value | Memory address |
---|---|---|

0 | 30 | 0xABCDEF00 |

1 | 34 | 0xABCDEF04 |

2 | 27 | 0xABCDEF08 |

3 | 68 | 0xABCDEF0C |

Because the memory is contiguous and that we know the starting memory address of the array, we can directly read/write a value by knowing its index. That is because we can calculate its memory address and go directly to it by using the following formula:

`Output = Starting memory address + (Size of element * index)`

A vector is similar to an array, but the memory for it is allocated dynamically (It’s like an array with grow/shrink functions).

The vector implementation also contains a data type called **capacity**, which keeps the maximum items the vector can hold. When we attempt to add more
items than the vector can hold, a new (and bigger) vector is created, and the data from the old one is moved / copied to the new one.

By having the flexibility of having dynamically allocated space, while still having contiguous memory for its elements, a vector is usually the go-to solution.

A list is another way to store a collection of elements.

Unlike vectors, the elements in a list are not subsequent in memory - each element in a list is stored in the form of a node. The node contains the value for that specific element, and a pointer to an address memory where we can find the next element.

The linked list name comes from the way the elements are linked to each other, like a chain.

The first node is always used as a reference to traverse the list, and it is called **head**.
The last node will always point to NULL.

In a list, each node is separately allocated, and all traversal operations chase pointers to their corresponding memory address, most likely causing a **cache miss** (the value is not stored anywhere close to the CPU, where
it would be easy to fetch it, but it needs to be read from the main memory, which is slow).

Inserting or removing an element in a list is as simple as changing two pointers, but in order to do that, we need to have access to the memory location of the node prior to the one we need to insert to or delete from, so we still need to make a list traversal up to that point.

In a single linked list, each node has a pointer towards the next one, allowing us to traverse only forward.

In a double linked list, each node has two pointers: one for the next element, and one for the previous one, allowing us to traverse both forwards and backwards.

Circular linked list is similar to the usual linked list (can be both single- and double- linked list), with the exception that the last element, instead of pointing to null, will point to the head of the list.

Stacks and Queues are both special-purpose lists, that restrict how the data can be accessed. Both data structures are very simple and can be implemented with either linked-lists or vectors.

**Stacks** are dynamic data structure that use the **LIFO principle (Last In First Out)**: the last block that was added is the first one to be removed. For example, if we have a stack of dishes in the sink,
the first dish that we take out of the stack is the one on the front, which is also the last one that was added.

In a stack, elements can be added or removed only from the top of the stack.

The insertion of an element in the stack is called `push()`

, while the removal is called `pop()`

.

**Queues** are dynamic data structures that use the **FIFO principle (First In First Out)**: the first element that was added is the first one to be removed.
As an analogy, a Queue can be explained as a line of people waiting for the bus: The person at the beginning of the line is the first one to enter the bus.

In a Queue, elements are always added at the back of the queue, and removed from the front of it.

The insertion of an element in the queue is called `enqueue()`

, while the removal is called `dequeue()`

.

**Hash tables** are data structures that utilize the concept of {key, value} pairs. The value is the data that we store in the container, whereas the key is something that is computed from the value, with the help of a hash function.

The idea of hashing is to distribute the pairs (entries) uniformly across an array.

When we attempt to add an element in the hash table, the hash function computes the key, which will point to an internal container called a **bucket**, in which we can find all the values that have the same key.

We can think of a bucket as a **linked list** in which all the nodes are elements with the same key computed by the hash function. We are using a list because there’s a many-to-one relation between keys and values => multiple values can have the same hash key.

**Hash tables** are very useful, because given a set of data big enough, we can still access the element of interest quite fast, by simply using the hash function. With an array, we were required to know the index of where we can find it, whereas with a linked list,
we would have needed to iterate through the list items to find it.

We see that we want to insert multiple values into our hash table.

We calculate the hash value for a specific item (with the help of the hash function), and that hash value will be the key / bucket entry.

**Collision** is a term used In case multiple keys return the same hash value. We can see that in this case, a solution will be to use a linked list in each bucket, so we can store multiple items in the same bucket.

Another solution would be to expand the number of buckets and recalculate the hash values for all objects, so we will not have collisions anymore.

**Example:**

- If we have 10 items and we want to store them into 1 bucket – all will go in the same bucket
- If there are 2 buckets – a few of them will go in one bucket, and the remaining ones in the other one
- If there are 10 buckets, there’s a chance that each item will go into a separate bucket
- If there are 100 buckets, there’s a very small chance that a collision will occur

A graph data structure is a connection of nodes (vertices) connected together through lines called edges. Each node can point to any number of nodes. A graph can also have some edge value assigned to each edge, to represent some specific attribute (cost, capacity, length, etc.).

There are two types of graphs: Directed graphs, and undirected graphs.

**Directed graphs** contain edges that are directed from one node to another. The nodes may be traversed only by following the assigned direction on each node.

**Undirected graphs** contain edges that do not have any direction, and can be traversed in both directions.

A cycle in a graph refer to a situation in which nodes are connected in a way that they form a closed structure.

If we traverse a cyclic graph and we don’t keep track of what vertices we visit, we will iterate through the same nodes infinitely.

Example: A -> B -> D -> C -> A -> B -> D -> C -> A ...

**A tree structure** can be defined as a collection of nodes, where each **node** is a data structure consisting of a value, and a list of references to its direct descendent nodes.

The first node (entry point) of the tree is called the **root**. If this root node (or any other node) is connected to another node, the root is called the parent node (ancestor), whereas the connected node is a child (descendent).

The last nodes (terminal nodes – nodes without children) are called **leaves**.
We call siblings all the nodes that are on the same tree level.
A subtree of a tree refer to a partion of a tree that can be viewed as a complete tree itself.

Other properties of a tree include:

**Node height**: The longest path towards a leaf**Tree depth**: The depth of a node refer to the distance from that node to the root**Tree level**: Defined as 1 + the number of connections between that node and the root (level is depth +1)

**A binary tree** is a tree where a parent node can only have 2 children: left and right. Each node contains the data (value) for the item, a pointer to the left child, and a pointer to the right child.

Common types of binary trees include:

**Full binary tree**: A binary tree in which all nodes except leaves7 have two children**Complete binary tree**: A binary tree in which all nodes except leaves have two children, and the last level has all keys as left as possible**Perfect binary tree**: A binary tree in which all nodes have two children and all leaves are at the same level**Balanced binary tree**: A binary tree that automatically keeps its height small after an arbitrary item insertions and deletions. This means that the tree will possibly readjust after an insertion has been made.

A **spanning tree** of a graph is a tree that connects together all the vertices, but not all the edges.
There can be multiple spanning trees in a graph.
The weight of a spanning tree is the sum of weights given to each edge of that spanning tree.

A **minimum spanning tree (MST)** is a spanning tree with the lowest weight, in comparison with all the other possible spanning trees. A MST has (V-1) edges, where V is the number of vertices in the graph.

**Binary Heap** is a Complete Binary Tree, in which nodes are arranged based on their value.
Every heap data structure has the following properties:

**Property #1 (Ordering)**: Nodes must be arranged in an order according to their values.**Property #2 (Structural)**: All levels in a heap must be full, except last level (leafs). Nodes must be filled strictly from left to right.

A Binary Heap is either a Min Heap or Max Heap.

A **min heap** is a specialized full binary tree in which every parent node contains lesser or equal value than its child nodes. In a min heap, the root has the minimum value than all other nodes in the min heap.

A **max heap** is a specialized full binary tree in which every parent node contains greater or equal value than its child nodes. In a max heap, the root node has the maximum value than all other nodes in the max heap.

A **trie** is a data structure used to store data (usually strings), and it is used to represent the retrieval of data (thus, the name).

The prefix of a string refers to any substring of it, starting from the beginning of the string.

Example:

Prefixes for the word Shortcut:

S, Sh, Sho, Shor, Short, Shortc, Shortcu

Tries are used on groups of strings, and by receiving a prefix of a word, we can find all the possible words we can find starting with that prefix.

Using the entire dictionary of a language, and a single string, we can find the maximum length from the dictionary strings that matches that given string. We can also do autocomplete when we search something on the web, for example.

**Big O notation** helps us determine how complex an operation is. It provides information on how long an operation will take, based on the size of the data. It can also be used as a complexity measurement.

The following table contain a list of the common O notations, from fastest (best) to slowest (worst).

Notation | Name | Example |
---|---|---|

O(1) | Constant | Operations occur at the `same speed` , independent of the data set.Example: null pointer check, comparing a given value to a constant |

O(log n) | Logarithmic | Operations take `slightly longer` , as the size of the data set increases.Example: Finding an item in a sorted data set, using binary search |

O(n) | Linear | Operations take longer and they are `directly proportioned` to the data set sizeExample: adding all the values within a container |

O(n log n) | Linearithmic | As the data set doubles in size, operations take longer `by an increasing multiplier of one` Example: Quick sort |

O(n^{2}) |
Quadratic | Each time data set doubles in size, the operations take four `times longer` Example: Two nested loops through the container (a for inside another for, from 1 to length of data) |

O(2^{n}) |
Exponential | For every new element added in the data set, operations take `twice as long` Example: brute force |

O(n!) | Quadratic | Operations take `n! times longer` directly proportioned to the size of the dataExample: Calculating fibonacci numbers recursively |

O comes from the

Order of the function(growth rate), while n is the length of the data we work with.

Given the following formula:

`f(n) = 8n`

^{5} – 3n^{4} + 6:

As n approaches infinity (for very large sets of data), 8n^{5} is the only one that actually matters, so all the lesser terms will simply drop.
The constants drop as well, so the formula have a growth rate of `O(n`

.
^{5})

The running time describes how many operations an algorithm must do before it completes.

For the next example, the growth rate is` O(1)`

, which means that the lookup is `constant`

, no matter how big the container is.

```
vector<int> items = { 1, 2, 3, 4, 5, 6 };
bool isValueAtIndex(int index, int value) {
return items[index] == value;
}
```

For the next example, the growth rate is `O(n)`

because, for a vector with n=1000 (`1000 elements`

), the number of operations will also be `1000`

.

```
vector<int> items = { 1, 2, 3, 4, 5, 6 };
int sum = 0;
int calculateSum() {
for (int i = 0; i < items.size(); ++i) {
sum += items[i];
}
return sum;
}
```

For the next example, the growth rate is ` O(n`

because, for a vector with n=10 (^{2})`10 elements`

), the number of operations will be ` 10`

.
^{2}

- For each number i from 0 to 9 (Line 4)
- For each number j from 0 to 9 (Line 5)
- Display the values on screen([0][0], [0][1], …[9][9])

```
vector<int> items = { 1, 2, 3, 4, 5, 6 };
void printItemsAsMatrix() {
for (int i = 0; i < items.size(); ++i) {
for (int j = 0; j < items.size(); ++j) {
print(i, j);
}
}
}
void print(int i, int j) {
cout << "[" << i << "][" << j << "]";
}
```

The **space complexity** describes how much space must be allocated to run the algorithm.
For any algorithm, memory may be used for variables (constant, temporary variables), instruction, or execution.

Space Complexity is the sum of `Auxiliary space`

and `Input space`

.
Auxiliary space is the extra/temporary space that is used by the algorithm during its execution, whereas the Input space refer to the data received as input.

To calculate the space complexity, we need to know the memory required for the type of variables, which generally is different for different operating systems.

```
int function() {
int a = 10, b = 5, c = 5;
int sum = a + b + c;
return sum;
}
```

Let’s assume that the space requirement for an int is 4 bytes.

Variables a,b,c and sum are integers, so they will take 4 bytes each, and that number will not change based on input, so 16 is the total number of bytes required by the function.

Because the space requirements is fixed, we call it to be constant.

```
vector<int> copy(const vector<int>& input) {
vector<int> output;
for(int i = 0; i < input.size(); i++) {
output.push_back(input[i]);
}
return output;
}
```

In the above example, we receive a vector and we copy each element of that vector into a new one.

Therefore, assuming the size of an integer is 4 bytes, we will need 4*n bytes of space for the elements, where n is the size of the original vector.

The memory is linearly increased based on the size of the vector, so the space complexity is linear => O(n).

**Sorting** means rearranging the elements within a data structure, in an ordered sequence, based on a specific criteria.

Sorting is required in order to improve the efficiency of the search (lookup), merging, or processing data.

The opposite operation of sorting is called **shuffling**, and it implies rearranging a sequence of items in a random order.

There are two types of sorting algorithms: integer sorts, and comparison sorts.

Let’s provide a simple example.

Assuming we have the following information about a given set of items:

Fruit | Available units | Price / kg |
---|---|---|

Apple | 1 | 2 $ |

Banana | 15 | 1.4 $ |

Orange | 3 | 5 $ |

Because sorting is done based on a specific criteria, we can choose how we want to display the items to the user.

For example, if we want to display in a descending order, based on the price, we would get the following table:

Fruit | Available units | Price / kg |
---|---|---|

Orange | 3 | 5 $ |

Apple | 1 | 2 $ |

Banana | 15 | 1.4 $ |

**Sorting** is usually performed before an algorithm that has sorting as a prerequisite. If the items are already sorted, we don’t need to iterate through the
entire data structure to find if a value is present in the data structure – if we check the middle of the structure directly and the value is smaller than what
we’re searching for, because the items are sorted (meaning that all the lowest values will be at the start and all the highest values will be at the end), we know
that the item we’re searching for is not in the first half.

This concept is called **binary search**, we’ll talk about it in the next chapter.

**Recursion** refer to a function that is calling itself.

Recursion as concept is quite easy to grasp, but it’s difficult to write a recursive solution – at least not on the first try, and that is because it involves a different way of thinking.

A recursive solution is one where the solution to a problem is reached through recursion.

If we write a function that returns the sum of all numbers from 1 to 9, you could write it like this:

```
int sum(int final) {
int sum = 0;
for (int i = 0; i < final; ++i)
sum += i;
return sum;
}
```

With recursion, you would write it like this:

```
int sum(int final, int current) {
if (current == final)
return current;
return current + sum(final, current + 1);
}
int total = sum(4, 0);
```

It works, but it’s ugly and hard to read. That’s because we needed to keep track of the current sum.

Let’s change the parameter and exit condition so it will start from the number and decrease to 0.

```
int sum(int current) {
if (current == 0) return 0;
return current + sum(current-1);
}
int total = sum(4);
```

So what happens?

- sum(4): Condition is not valid (4 is different than 0) => We return 4 + sum(3)
- sum(3): Condition is not valid (3 is different than 0) => We return 3 + sum(2)
- sum(2): Condition is not valid (2 is different than 0) => We return 2 + sum(1)
- sum(1): Condition is not valid (1 is different than 0) => We return 1 + sum(0)

For sum(0), the following things happen:

- Condition is valid (0 is equal to 0)
- We return 0 to the caller
- sum(1) is getting the control back, and returns 1 + 0 = (current + return from sum(0) ) = 1 to the caller
- sum(2) is getting the control back, and returns 2 + 1 = (current + return from sum(1) ) = 3 to the caller
- sum(3) is getting the control back, and returns 3 + 3 = (current + return from sum(2) ) = 6 to the caller
- sum(4) is getting the control back, and returns 4 + 6 = (current + return from sum(3) ) = 10 to the caller

The end result is 10 (1 + 2 + 3 + 4).

**Hashing** is a mathematical numerical representation of a given input. A hash function is used to take the input and produce a hash value, and even a small change in the input will produce a different hash value.

**A hash table** is a data structure that uses a Key and a Value to store elements. A hash function receives the Value and computes a hash value for that given data, which will be our key in the hash table.
Knowing the key, we can access the element directly, since the key will lead us to the position of the value in our data structure, independent of the size of the data in the structure.
Based on the internal implementation, some collisions may occur.

If we have a structure with 10000 elements in it, we can retrieve an element very easily if we know its value.

In comparison with an array, we will need to do a linear search through the elements until we find what we need, therefore a hash table is much faster when the number of elements is big.

For example, given a hash table that uses strings as key/values, we can compute the hash value by doing the sum of the ASCII codes of the string, and then do a modulo of that value based on the size of the internal array.

Given the following vector:

A | B | C | D | E |

If we need to retrieve the item D, we need to iterate through the vector one by one until we find it.

A -> B -> C -> D.

If we know that D is at index 3, we can simply access it through the data structure:

D = data[3];

Let’s assume that the hash function returns 0 for A, 1 for B, etc.

Now we’re back at the same problem, but the values were placed in the array based on the hash function, therefore we can calculate the hash value again and retrieve the index to where it was originally placed.

Index = hash_function(D) => index = 3

Since we know that index of D is 3, we can directly access the element and fetch it.

That is because there is a direct link between the value inserted and the value retrieved by the hash function, allowing us to retrieve the index, in comparison with the vector, that had the value inserted without any specific order.

An algorithm is a set of instructions to execute in a specific given order. Any work to be done can be thought as a series of steps.

A greedy algorithm has only one shot to compute the optimal solution, so one characteristic is that it **never goes back to reverses the decision**.

A **greedy** algorithm is always making the choice that seems to be the best at that moment.

In other words, this means that a `locally-optimal choice`

is made, which will `hopefully lead to a globally-optional solution`

to our problem.

**Creation of a greedy algorithm:**

Problem: You have a T time to do the work, and you are required to do the maximum number of jobs.

So, how would you make the maximum number of jobs in a given time? By doing only the smallest task possible, for as much as possible.

Input:

- An array A of integers, where each element indicates the time it takes to complete the job
- Time T, which indicates the time required to do things

Data to use:

- A variable to indicate the current time
- A variable to indicate the number of jobs done

Operations to perform:

- Sort the array (increasing order)
- Take each item one by one
- Increment current time to the time took to complete the item
- Increment with 1 the number of jobs successfully done

Repeat this as long as current time is smaller or equal to T (final time).

Let's take an example.

Input:

- A = {3, 5, 2, 1, 4}
- T = 5

Preparation: Sort the array.

Iteration | Value picked | Current time | Jobs done |
---|---|---|---|

1^{st} |
- | 0 | 0 |

2^{nd} |
1 | 0 + 1 = 1 | 1 |

3^{rd} |
2 | 1 + 2 = 3 | 2 |

4^{th} |
3 | 3 + 3 = 6 | 3 |

After the 4^{th} iteration, current time (6) is bigger than our max time T (4). Thus, the maximum number of jobs that can be performed in such time is 3.

A typical divide and conquer algorithm solves a problem through three steps:

**Divide**: Break the problem into sub-problems of the same type**Conquer**: Solve the sub-problems recursively**Combine**: Combine the answers

**Dynamic programming** is a technique that is based on a recurrent formula and one or multiple states. A sub-solution of the problem is constructed from previously found ones. (express the value of a function in terms of other values of that function).

The trick behind Dynamic Programming is that `we trade space for time`

(instead of calculating all the states takes a lot of time but no space, and we take up space for results of sub-problems to save time).

Most Dynamic programming problems can be categorized into two types:

- Optimization problems
- Combinatorial problems

**Optimization problems** expect you to find a solution so that the value of a function is minimized or maximized.
**Combination problems** expect you to figure out the number of ways to do something, or the probability of an event to happen.

Dynamic Programming problems should be resolved through the following schema:

- Show that the problem can be broken down into optimal sub-problems.
- Recursively define the value of the solution by expressing it in terms of optimal solutions for smaller subproblems.
- Compute the value of the optimal solution.
- Construct an optimal solution from the computed information.

In Top-down, you start building the solution right away by explaining how you build it from smaller solution. In Bottom-up, you start with the small solutions, and then build up.

Analogy:

**Bottom up** – I’m going to learn programming. Afterwards, I will start practicing. Afterwards, I will participate in contests. Afterwards, I’ll practice further and try to improve. Afterwards, I’ll be a great coder.

**Top Down** – I’l be a great coder. How? I’ll practice further and try to improve. How? I’ll participate in contests. How? I’ll start practicing. How? I’m going to learn programming.

**Memoization** is an optimization technique used to speed up applications by storing the results of an expensive function call and returning the cached result when the same input occurs again.

Whenever we need a solution to a subproblem, we look into the lookup table. If it’s there, we retrieve it, and otherwise, we calculate the value and add the result in the lookup table to be easily retrieved later on.

```
int fibonacci_topDown(int n, vector<int>& lookup_table) {
if (n == 0) return 0;
if (n == 1) return 1;
if (lookup_table[n] != 0) {
return lookup_table[n];
}
else {
lookup_table[n] = fibonacci_topDown(n - 1, lookup_table) +
fibonacci_topDown(n - 2, lookup_table);
return lookup_table[n];
}
}
int main() {
int value = 10;
vector<int> lookup_table(value + 1, 0);
cout << fibonacci_topDown(value, lookup_table);
return 0;
}
```

In our case, the lookup table is found on line 17. We need to make sure we allocate enough memory to store the results.

First, we check the value of n in the lookup table (Lines 4-5). If the value is not found in the lookup table, we calculate it based on the previous results (Lines 8-9).

In the bottom-up approach, we calculate the small values, and then build larger values from them.

```
int fibonacci_bottomUp(int x) {
vector<int> results_table;
results_table.push_back(0);
results_table.push_back(1);
for (int i = 2; i <= x; i++) {
results_table.push_back(results_table[i - 1] + results_table[i - 2]);
}
return results_table[x];
}
```

Line 2 contains the results table, in which we add the values for 0 and 1 (Lines 3-4).

For each value starting from 2 to x, we add in the results table the solution from previously calculated values (Line 7).

**Backtracking** is a technique for solving problems recursively. It builds the solution by providing candidates, and it removes the candidate when it fails to satisfy the problem constraints. This usually results in visiting a previous stage of the process, and exploring new possibilities from that step.

Backtracking is used to solve three types of problems:

- Decision – searching for one possible solution
- Optimization – Searching for the best solution
- Enumeration – Searching for all possible solutions

Let’s give an example.

Assuming we are in a maze and we need to find our way out – we start moving in our path. In case there’s a bifurcation – we need to make a choice where we should go.

**With backtracking + recursion, we simply choose to go everywhere.**

We set left as our current road, and we move on that road. If we encounter a dead-end, we move back to the bifurcation, we set right as our current road, and we move on to that road. Each decision creates more sub-problems, and in most of them, we backtrack and revert our decision.

In code, this usually requires setting a value, calling the same function again, and in case the function returns fail, we unset the value and continue with the next option. The pseudo-code for backtracking (general algorithm) is at follows:

```
Prerequisites: Data input (items in a vector, for example)
For each item from Input
if (constraints are valid)
select the item
result = recursive call for the rest of the problem
if (result)
return true
else
deselect the item
return false
```

What we’re really doing is that we take each item one by one, check if the constraints are valid if we take such item, and we call the function again with the new information taking in. If at some point, the constraints are invalid, we deselect the item and check for the next one. The function should have a finish condition at start, if we reached the step we wanted, and should return false if it exhausted all the items without any success.

**The most important thing in backtracking is the selection of the item and deselection of it in case it doesn’t satisfy the problem constraints.**

A pointer references a location in memory.

NULL refer to the absence of a value, which means that it is not the same as having the value 0.