required
required

## HashTable

The Hash table data structure stores elements in key-value pairs where

• Key– unique integer that is used for indexing the values
• Value – data that are associated with keys.

The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table.

1. Hash function

As we’ve already seen, the hash function determines the index of our key-value pair. Choosing an efficient hash function is a crucial part of creating a good hash table. You should always ensure that it’s a one-way function, i.e., the key cannot be retrieved from the hash. Another property of a good hash function is that it avoids producing the same hash for different keys.

2. Array

The array holds all the key-value entries in the table. The size of the array should be set according to the amount of data expected.

## Collisions in hash tables & resolutions

collision occurs when two keys get mapped to the same index. There are several ways of handling collisions.

1. Linear probing

If a pair is hashed to a slot which is already occupied, it searches linearly for the next free slot in the table.

2. Chaining

The hash table will be an array of linked lists. All keys mapping to the same index will be stored as linked list nodes at that index.

3. Resizing the hash table

The size of the hash table can be increased in order to spread the hash entries further apart. A threshold value signifies the percentage of the hash table that needs to be occupied before resizing. A hash table with a threshold of 0.6 would resize when 60% of the space is occupied. As a convention, the size of the hashtable is doubled. This can be memory intensive.

## Time Complexity

Operation Average Worst
Search O(1) O(n)
Insertion O(1) O(n)
Deletion O(1) O(n)
Space O(n) O(n)

## Strengths:

• Fast lookups. Lookups take  time on average.
• Flexible keys. Most data types can be used for keys, as long as they’re  hashable .

## Weaknesses:

• Slow worst-case lookups. Lookups take  time  in the worst case .
• Unordered. Keys aren’t stored in a special order. If you’re looking for the smallest key, the largest key, or all the keys in a range, you’ll need to look through every key to find it.
• Single-directional lookups. While you can look up the value for a given key in  time, looking up the keys for a given value requires looping through the whole dataset— time.
• Not cache-friendly. Many hash table implementations use  linked lists , which don’t put data next to each other in memory.
public class MyHashMap<K, V> {

private int             size  = 10;
private MapNode<K, V>[] array = new MapNode[size];

public void put(K key, V value) {
int arrayIndex = hash(key);
putVal(key, value, arrayIndex);
}

private int hash(K key) {
int a = 20;
int b = 30;
int m = size;
int h = key.hashCode();
return ((a * h * b) % primeNumber) % m;
}

public V get(K key) {
int arrayIndex = hash(key);

return null;
}

while (null != currentNode && !currentNode.getKey().equals(key)) {
currentNode = currentNode.getNext();
}

if (currentNode == null) {
return null;
} else {
return currentNode.getValue();
}
}

public void putVal(K key, V val, int arrayIndex) {

array[arrayIndex] = head = new MapNode<>(key, val);
} else {

while (null != currentNode && !currentNode.getKey().equals(key)) {
prevNode = currentNode;
currentNode = currentNode.getNext();
}

if (currentNode == null) {
currentNode = new MapNode<>(key, val);
prevNode.setNext(currentNode);
} else {
currentNode.setValue(val);
}

}
}
}
@AllArgsConstructor
@ToString
@Data
public class MapNode<K, V> {
private K             key;
private V             value;
private MapNode<K, V> next;

public MapNode(K key, V value) {
this(key, value, null);
}
}

Source code on Github

November 24, 2019

## Graph

A graph data structure is a collection of nodes that have data and are connected to other nodes.

Let’s try to understand this through an example. On facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note…anything that has data is a node.

Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship.

A graph is a pair (V, E), where V is a set of nodes, called vertices, and E is a collection of pairs of vertices, called edges.

## Applications of Graphs

• Representing relationships between components in electronic circuits
• Transportation networks: Highway network, Flight network
• Computer networks: Local area network, Internet, Web
• Databases: For representing ER (Entity Relationship) diagrams in databases, for

representing dependency of tables in databases

November 12, 2019

## Trees

Tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of non- linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.

tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node

The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child.

### Tree Properties:

• Root is the topmost node of the tree
• Edge is the link between two nodes
• Child is a node that has a parent node
• Parent is a node that has an edge to a child node
• Leaf is a node that does not have a child node in the tree
• Height is the length of the longest path to a leaf
• Depth is the length of the path to its root ## General Tree

#### Properties ## Types of Tree

1.  Binary Tree
2.  Binary Search Tree
3.  AVL Tree
4.  B-Tree

## Binary Tree

A tree is called binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right subtrees of the root.

#### Properties

1. A left child precedes a right child in the order of children of a node. Or in other others, left side of tree is small than right side of tree #### Usage

Note that Strict Binary Tree is a binary tree with each node has exactly two children or no children. ## Full Binary Tree

A binary tree is called full binary tree if each node has exactly two children and all leaf nodes are at the same level. ## Complete Binary Tree

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.

### Properties 1. Every level is filled, except the last level.

2. All nodes are filled starting from left ## Applications of Binary Trees

Following are the some of the applications where binary trees play an important role:

• Expression trees are used in compilers.
• Huffman coding trees that are used in data compression algorithms.
• Binary Search Tree (BST), which supports search, insertion and deletion on a collection of items in O(logn) (average).
• Priority Queue (PQ), which supports search and deletion of minimum (or maximum)on a collection of items in logarithmic time (in worst case).
• Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
• Heap is a kind of tree that is used for heap sort.
• A modified version of a tree called Tries is used in modern routers to store routing information.
• Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
• Compilers use a syntax tree to validate the syntax of every program you write.
• In HTML, the Document Object Model (DOM) works as a tree.
@NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class TreeNode {

private User data;
private TreeNode left;
private TreeNode right;

public TreeNode(User data) {
this.data = data;
}
}

@ToString
@NoArgsConstructor
@AllArgsConstructor
@Data
class User implements Serializable, Comparable<User> {

/**
*
*/
private static final long serialVersionUID = 1L;
private String            name;
private Integer           rating;

@Override
public int compareTo(User other) {
// TODO Auto-generated method stub
return this.rating.compareTo(other.getRating());
}
}

### Insert data into Binary Tree

public TreeNode insert(TreeNode parent, User data) {
/**
* if node is null, put the data there
*/
if (parent == null) {
return new TreeNode(data);
}

User parentData = parent.getData();

/**
* if parent is greater than new node, go left<br>
* if parent is less than new node, go right<br>
*/
if (parentData.getRating() > data.getRating()) {
parent.setLeft(insert(parent.getLeft(), data));
} else {
parent.setRight(insert(parent.getRight(), data));
}

return parent;
}

public TreeNode insert(User data) {
if(root==null) {
root = new TreeNode(data);
return root;
}
return insert(root,data);
}
public class BinaryTreeMain {

public static void main(String[] args) {
// TODO Auto-generated method stub

TreeNode root = new TreeNode();

root.setData(new User("Folau", 20));

BinaryTree binaryTree = new BinaryTree(root);

binaryTree.insert(new User("Lisa", 30));
binaryTree.insert(new User("Laulau", 15));
binaryTree.insert(new User("Kinga", 12));
binaryTree.insert(new User("Fusi", 35));
binaryTree.insert(new User("Nesi", 34));
binaryTree.insert(new User("Melenesi", 32));

System.out.println("PreOrder Traversal");

binaryTree.preOrder(root, "root");

System.out.println("InOrder Traversal");

binaryTree.inOrder(root);

System.out.println("PostOrder Traversal");

binaryTree.postOrder(root);
}

}
PreOrder Traversal
root - User(name=Folau, rating=20)
left - User(name=Laulau, rating=15)
left - User(name=Kinga, rating=12)
right - User(name=Lisa, rating=30)
right - User(name=Fusi, rating=35)
left - User(name=Nesi, rating=34)
left - User(name=Melenesi, rating=32)
InOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Folau, rating=20)
User(name=Lisa, rating=30)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
PostOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
User(name=Lisa, rating=30)
User(name=Folau, rating=20)

Now that inserting elements into binary tree is done. We have ways to navigate through or traverse a tree data structure.

We have two options. Breadth-First Search(BFS) and Depth-First Search(DFS)

### Depth-First Search

DFS is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.

DFS explores a path all the way to a leaf before backtracking and exploring another path. There 3 types of DFS: pre-orderin-order, and post-order

## Inorder traversal

1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
* 1. Traverse the left subtree in Inorder.<br>
* 2. Visit the root.<br>
* 3. Traverse the right subtree in Inorder.<br>
* Time Complexity: O(n). Space Complexity: O(n).<br>
*/
public void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.getLeft());
System.out.println(node.getData().toString());
inOrder(node.getRight());
}
}

## Preorder traversal

1. Visit root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
* 1. Visit the root.<br>
* 2. Traverse the left subtree in Preorder.<br>
* 3. Traverse the right subtree in Preorder.<br>
* Time Complexity: O(n). Space Complexity: O(n).
*/
public void preOrder(TreeNode node) {
if (node != null) {
System.out.println(node.getData().toString());
preOrder(node.getLeft());
preOrder(node.getRight());
}
}

## Postorder traversal

1. Visit all the nodes in the left subtree
2. Visit all the nodes in the right subtree
3. Visit the root node

Time Complexity: O(n). Space Complexity: O(n).

/**
* 1. Traverse the left subtree in Postorder.<br>
* 2. Traverse the right subtree in Postorder.<br>
* 3. Visit the root.<br>
* Time Complexity: O(n). Space Complexity: O(n).<br>
*/
public void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.println(node.getData().toString());
}
}

BFS is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

BFS algorithm traverses the tree level by level and depth by depth.

public void bfs() {

int level = 1;

while (queue.isEmpty() != true) {
LevelNode levelNode = queue.poll();
TreeNode node = levelNode.getNode();

level++;

// 1. process node
System.out.println("level: "+levelNode.getLevel()+", data: "+ node.getData().toString());

// 2. push left and right child nodes onto queue
if(node.getLeft()!=null) {
}

if(node.getRight()!=null) {
}

}
}

Source code on Github

November 9, 2019

## Heap

1. Max-Heap: The value of a node must be greater than or equal to the values of its children. The greatest value is at the root. The same property must be true for all subtrees.
35 33 42 10 14 19 27 44 26 31 Max-Heap construction Max-Heap deletion @NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class MaxHeap {

private List<Integer> data = new ArrayList<>();

/**
* Function to return the position of the parent for the node currently at position
*/
private int parent(int position) {
if (position == 0) {
return 0;
}
return (position - 1) / 2;
}

/**
* Function to return the position of the left child for the node currently at position
*/
private int left(int position) {
return (2 * position) + 1;
}

/**
* Function to return the position of the right child for the node currently at position
*/
private int right(int position) {
return (2 * position) + 2;
}

private void swap(int firstPosition, int secondPosition) {
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
int tmp = this.data.get(firstPosition);
this.data.set(firstPosition, this.data.get(secondPosition));
this.data.set(secondPosition, tmp);
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));

}

// increase the size of an array Heap[++size] = element;
int current = getSize() - 1;

System.out.println("adding: " + item + " to position: " + current);

heapifyUp(current);
}

public int peek() {
return data.get(0);
}

/**
* Step 1 − Remove root node.<br>
* Step 2 − Move the last element of last level to root.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is less than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
public int poll() {

// replace the root of the heap with the last element
data.set(0, this.data.get(getSize() - 1));
data.remove(getSize() - 1);
// call heapify-down on the root node
heapifyDown(0);

}

/**
* Step 1 − Create a new node at the end of heap.<br>
* Step 2 − Assign new value to the node.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is less than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyUp(int position) {
int temp = this.data.get(position);

if (position > 0 && temp > this.data.get(parent(position))) {
System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position)));
// swap the two if heap property is violated
swap(position, parent(position));

// call heapify-up on the parent
heapifyUp(parent(position));
}
}

/**
* Step 1 − Remove root node.<br>
* Step 2 − Move the last element of last level to root.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is less than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyDown(int position) {

int largest = position;
int leftChild = left(position);
int rightChild = right(position);

// compare A[i] with its left and right child
// and find the largest value
int size = getSize();

if (leftChild < size && this.data.get(leftChild) > this.data.get(largest)) {
largest = leftChild;
}

if (rightChild < size && this.data.get(rightChild) > this.data.get(largest)) {
largest = rightChild;
}

if (largest != position) {

// swap with a child having lesser value
swap(position, largest);

// call heapify-down on the child
heapifyDown(largest);
}
}

public void print() {
System.out.println("\nList");
for (Integer d : data) {
System.out.println("data: " + d);
}
System.out.println("\nTree");
System.out.println("Root: " + data.get(0));
for (int i = 1; i <= getSize() / 2; i++) {

try {
System.out.print("Parent: " + this.data.get(i - 1));
} catch (Exception e) {

}

try {
System.out.print(", Left: " + this.data.get(this.left(i - 1)));
} catch (Exception e) {

}

try {
System.out.print(", Right: " + this.data.get((this.right(i - 1))));
} catch (Exception e) {

}
System.out.println();
}
System.out.println("\n");
}

public int getSize() {
return this.data.size();
}

}


2. Min-Heap: The value of a node is greater than or equal to the value of its parent. The smallest value is at the root. The same property must be true for all subtrees.
35 33 42 10 14 19 27 44 26 31 @NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class MinHeap {

private List<Integer> data = new ArrayList<>();

/**
* Function to return the position of the parent for the node currently at position
*/
private int parent(int position) {
if (position == 0) {
return 0;
}
return (position - 1) / 2;
}

/**
* Function to return the position of the left child for the node currently at position
*/
private int left(int position) {
return (2 * position) + 1;
}

/**
* Function to return the position of the right child for the node currently at position
*/
private int right(int position) {
return (2 * position) + 2;
}

private void swap(int firstPosition, int secondPosition) {
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
int tmp = this.data.get(firstPosition);
this.data.set(firstPosition, this.data.get(secondPosition));
this.data.set(secondPosition, tmp);
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));

}

// increase the size of an array Heap[++size] = element;
int current = getSize() - 1;

System.out.println("adding: " + item + " to position: " + current);

heapifyUp(current);
}

public int peek() {
return data.get(0);
}

public int poll() {

// replace the root of the heap with the last element
data.set(0, this.data.get(getSize() - 1));
data.remove(getSize() - 1);
// call heapify-down on the root node
heapifyDown(0);

}

/**
* Step 1 − Create a new node at the end of heap.<br>
* Step 2 − Assign new value to the node.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is greater than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyUp(int position) {
int temp = this.data.get(position);

if (position > 0 && temp < this.data.get(parent(position))) {
System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position)));
// swap the two if heap property is violated
swap(position, parent(position));

// call heapify-up on the parent
heapifyUp(parent(position));
}
}

/**
* Step 1 − Remove root node.<br>
* Step 2 − Move the last element of last level to root.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is greater than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyDown(int position) {

int smallest = position;
int leftChild = left(position);
int rightChild = right(position);

// compare A[i] with its left and right child
// and find the smallest value
int size = getSize();

if (leftChild < size && this.data.get(leftChild) < this.data.get(smallest)) {
smallest = leftChild;
}

if (rightChild < size && this.data.get(rightChild) < this.data.get(smallest)) {
smallest = rightChild;
}

if (smallest != position) {

// swap with a child having lesser value
swap(position, smallest);

// call heapify-down on the child
heapifyDown(smallest);
}
}

public void print() {
System.out.println("\nList");
for (Integer d : data) {
System.out.println("data: " + d);
}
System.out.println("\nTree");
System.out.println("Root: " + data.get(0));
for (int i = 1; i <= getSize() / 2; i++) {

try {
System.out.print("Parent: " + this.data.get(i - 1));
} catch (Exception e) {

}

try {
System.out.print(", Left: " + this.data.get(this.left(i - 1)));
} catch (Exception e) {

}

try {
System.out.print(", Right: " + this.data.get((this.right(i - 1))));
} catch (Exception e) {

}
System.out.println();
}
System.out.println("\n");
}

public int getSize() {
return this.data.size();
}

}


### Heap Data Structure Applications

• Heap is used while implementing a priority queue.
• Dijkstra’s Algorithm
• Heap Sort
November 3, 2019

## Priority Queue

Priority queue is a data structure that extends the queue data structure with a priority dimension. Queue is a list of elements taken in the same order as they arrived. For instance, a line of people waiting to pay at the Supermarket behaves like a queue: first-in, first-served, or FIFO (first in, first out).

Priority queue adds a priority to each element’s value. If we go back to the example of a line of people in a supermarket. You can add preferred lanes, for example, Seniors (65+ years old) and pregnant women. If you have Seniors in the line, you will take them first, even if other people arrived before them. That’s what a priority queue (PQ) does. If all elements in a PQ have the same priority, then it will behave like a regular queue. ### Applications of Priority Queue

There are many real-world applications for priority queues, such as:

• System to triage hospital patients and attend them by their severity order.
• Forward network packages in order of urgency (e.g., “real-time video call” should go before “time sync checks,” so to speak)
• Scheduling tasks in a system: “critical” goes before “shadow drawing” for instance.
• Asynchronous control flows like firing events (or notifying observers) in a certain order.
• Keeping track of top k elements efficiently
• Keeping track of median numbers in constant time
• Used in some graph algorithms like Dijkstra for finding the shortest path between two points. The distance among points is used as a priority.

## Implementations

• Let’s explore several possibilities for data structures we could use to implement a priority queue:
• Unordered array

A simple, yet inefficient implementation, as retrieving the max element would require searching the entire array.

• Sorted array

This is not a very efficient implementation either. Inserting a new element requires linearly searching the array for the correct position. Removing similarly requires a linear time: the rest of the elements need to be adjusted (shifted) into correct positions.

• Hash table

Although inserting into a hash table takes constant time (given a good hash function), finding the max element takes linear time. Therefore, this would be a poor choice for the underlying data structure.

• Heap

It turns out that that a heap makes an efficient priority queue.

Operation Unordered array Sorted array Hash table Binary heap

insert

maxElement

removeMaxElement public class MyPriorityQueueWithArray {

private int            count    = 0;
private int            capacity = 10;
private PriorityNode[] elements = new PriorityNode[capacity];

public void enqueue(PriorityNode node) {
if (node == null || node.getData() == null) {
return;
}
System.out.println("node: " + node.toString());
System.out.println("count: " + count);

int position = 0;

if (count == 0) {

/**
* tail has the highest priority
*/
elements[position] = node;

} else {

PriorityNode highestNode = elements[position];

while (highestNode != null && node.getPriority() <= highestNode.getPriority()) {

position++;
highestNode = elements[position];

}

}

System.out.println("insert position: " + position);
System.out.println("\n");
count++;
}

private void add(PriorityNode node, int position) {

if (count == capacity) {
/*
* when full, double its size
*/
capacity = capacity * 2;
}

PriorityNode[] temp = new PriorityNode[capacity];

int index = 0;
int lastIndex = count + 1;

while (index < lastIndex) {

if (index < position) {
/**
* front
*/
temp[index] = elements[index];
} else if (index == position) {
/**
* middle
*/
temp[position] = node;
} else {
/**
* back
*/
temp[index] = elements[index - 1];
}

index++;
}

elements = temp;
}

public PriorityNode removeAt(int position) {

PriorityNode[] temp = new PriorityNode[capacity];

PriorityNode removedNode = elements[position];

int index = 0;
int lastIndex = count + 1;

while (index < lastIndex) {

if (index < position) {
/**
* front
*/
System.out.println("front");
temp[index] = elements[index];
} else if (index == position) {
/**
* middle
*/
System.out.println("middle");
} else {
/**
* back
*/
System.out.println("back");
temp[index - 1] = elements[index];
}
if (temp[index] != null)
System.out.println("temp: " + temp[index].toString());

index++;
System.out.println("\n");
}

elements = temp;

return removedNode;
}

/**
* Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
*/
public PriorityNode peek() {
return elements;
}

/**
* Retrieves and removes the head of this queue, or returns null if this queue is empty.
*/
public PriorityNode dequeue() {
return removeAt(0);
}

public void print() {
int index = 0;
PriorityNode node = elements;
while (node != null && count > index) {
System.out.println((index + 1) + ". " + node.toString());
index++;
node = elements[index];
}
}
}


Source code on Github

November 2, 2019