Author: cyrus2281

Data Structure

Content

• Array
  • 2-D Array
• Hash
• LinkedList
  • Singly LinkedList
  • Doubly LinkedList
• Stack
• Queue
  • Priority Queue
• Tree
  • Binary Tree
  • Heap
  • Trie
• Graph


• References

Array

top

lookup: O(1)
push: O(1)
insert: O(n)
delete: O(n)

static: they have specific size of elements
dynamic: their increases as new elements are added

class Array:
    
    def __init__(self):
        self.lenght=0
        self.data = {}
        
    def lookup(self,index):
        return self.data[index] 
    
    def insert(self,item):
        self.data[self.lenght]=item
        self.lenght+=1
        return self.lenght
    
    def pop(self):
        temp =self.data[self.lenght-1]
        del self.data[self.lenght-1]
        self.lenght -=1
        return temp
    
    def delete(self,index):
        temp =self.data[index]
        self._shiftItem(index)
        del self.data[self.lenght-1]
        self.lenght -=1
        return temp
    
    def _shiftItem(self,index):
        for i in range(index,self.lenght-1):
            self.data[i] = self.data[i+1]
            
    def getAll(self):
        return self.data

arr = Array()
arr.insert(5)
arr.insert(10)
arr.insert(15)
arr.insert(20)
arr.insert(25)
print(arr.lookup(0))
arr.pop()
arr.delete(2)
print(arr.getAll())

5
{0: 5, 1: 10, 2: 20}

Array > 2-D Array

top

An array that holds other arrays.

All the second dimension arrays must be identical in shape

UP : row - 1

RIGHT : col + 1

DOWN : row + 1

LEFT : col - 1

Hash

top

lookup: O(1) / O(n)
search: O(1)
insert: O(1)
delete: O(1)

Collision can slow down the hash table, multiple hash keys are stored in the same row
O(n/k) -> O(n) (k is the number of rows in hash table)

class Hash:
    def __init__(self,size=10):
        self.data = [None for i in range(size)]
        
    def _hash(self, key):
        hsh = 0
        for i in range(len(key)):
            hsh = (hsh + ord(key[i]) * i ) % len(self.data)
        return hsh
    
    def insert(self,key,value):
        address = self._hash(key)
        if not self.data[address]:
            self.data[address] = []
        self.data[address].append((key,value))
        
    def lookup(self,key):
        address = self._hash(key)
        for a,b in self.data[address]:
            if a == key:
                return b 
            
    def keys(self):
        keys= []
        for a in self.data:
            if a:
                for i,j in a:
                    keys.append(i)
        return keys
    
    def get_hash(self):
        return self.data

        
hsh = Hash(2)
hsh.insert("grapes",1000)
hsh.insert("oranges",500)
hsh.insert("apples",2000)
hsh.insert("pears",100)
print(hsh.get_hash())
print(hsh.lookup('oranges'))
print(hsh.keys())

[None, [('grapes', 1000), ('oranges', 500), ('apples', 2000), ('pears', 100)]]
500
['grapes', 'oranges', 'apples', 'pears']

Linked List

top

prepend O(1)
append O(1)
lookup O(n)
insert O(n)
delete O(n)

Linked List > Singly Linked List

top

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        
    def append(self,value):
        node = self.Node(value)
        if not self.head:
            self.head = self.tail = node
        self.tail.nxt = node
        self.tail = node
        self.size += 1
        
    def lookup(self, index):
        if index == 0:
            return self.head.value
        temp = self.head
        for i in range(index):
            temp = temp.nxt
        if not temp:
            return None
        return temp.value
        
    def delete(self,index):
        if index == 0:
            self.head = self.head.nxt
        temp = self.head
        for i in range(index):
            prev = temp
            temp = temp.nxt        
        prev.nxt = temp.nxt
        
    class Node:
        def __init__(self,value):
            self.nxt = None
            self.value = value

lst =  SinglyLinkedList()
lst.append("Hi")
lst.append("Hello")
lst.append("bye")
print(lst.lookup(0))
print(lst.lookup(1))
print(lst.lookup(2))
lst.delete(1)
print(lst.lookup(0))
print(lst.lookup(1))

Hi
Hello
bye
Hi
bye

Linked List > Doubly Linked List

top

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        
    def append(self,value):
        node = self.Node(value)
        if not self.head:
            self.head = self.tail = node
        self.tail.nxt = node
        node.prev = self.tail
        self.tail = node
        self.size += 1
        
    def lookup(self, index):
        if index == 0:
            return self.head.value
        temp = self.head
        for i in range(index):
            temp = temp.nxt
        if not temp:
            return None
        return temp.value
        
    def delete(self,index):
        if index == 0:
            self.head = self.head.nxt
        temp = self.head
        for i in range(index):
            temp = temp.nxt        
        temp.prev.nxt = temp.nxt

    class Node:
        def __init__(self,value):
            self.nxt = None
            self.prev = None
            self.value = value

lst =  DoublyLinkedList()
lst.append("Hi")
lst.append("Hello")
lst.append("bye")
print(lst.lookup(0))
print(lst.lookup(1))
print(lst.lookup(2))
lst.delete(1)
print(lst.lookup(0))
print(lst.lookup(1))

Hi
Hello
bye
Hi
bye

Stack

top

lookup O(n)
pop O(1)
push O(1)
peek O(1)

LIFO
with either array or LinkedList
array: faster but predefined size
linked list: slower but with unlimited size

class Stack:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        
    def push(self,value):
        node = self.Node(value)
        if not self.head:
            self.head = self.tail = node
        self.tail.nxt = node
        node.prev = self.tail
        self.tail = node
        self.size += 1
        
    def peek(self):
            return self.tail.value
        
    def pop(self):    
        self.tail.prev.nxt = None
        self.tail = self.tail.prev
        self.size -= 1

    class Node:
        def __init__(self,value):
            self.nxt = None
            self.prev = None
            self.value = value

lst =  Stack()
lst.push("Hi")
lst.push("Hello")
lst.push("bye")
print(lst.peek())
lst.pop()
print(lst.peek())

bye
Hello

Queue

top

lookup O(n)
enqueue O(1)
dequeue O(1)
peek O(1)

FIFO
best to use with linked list (beacuse array has to shift all elements to left to remove the first element)

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        
    def enqueue(self,value):
        node = self.Node(value)
        if not self.head:
            self.head = self.tail = node
        self.tail.nxt = node
        node.prev = self.tail
        self.tail = node
        self.size += 1
        
    def peek(self):
            return self.head.value
        
    def dequeue(self):    
        self.head.nxt.prev = None
        self.head = self.head.nxt
        self.size -= 1

    class Node:
        def __init__(self,value):
            self.nxt = None
            self.prev = None
            self.value = value

lst =  Queue()
lst.enqueue("Hi")
lst.enqueue("Hello")
lst.enqueue("bye")
print(lst.peek())
lst.dequeue()
print(lst.peek())

Hi
Hello

Queue > Priority Queue

top

Priority Queues are like normal queue except instead of first in first out, it is the value with highest prioriy is out first

lookup: O(n)
insert; O(log N)
delete: O(log N)

Priority Queues are based on heaps (check Heaps)

class PriorityQueue:
    def __init__(self, comparator = lambda a,b : a>b):
        self._heap = []
        self._comparator = comparator
        
    def size(self):
        return len(self._heap)
    
    def isEmpty(self):
        return self.size() == 0
    
    def peek(self):
        if not self.isEmpty():
            return self._heap[0]
        else:
            return None
    
    def push(self, value):
        idx = self.size()
        self._heap.append(value)
        while idx > 0 and self._compare(idx,self._parent(idx)):
            self._swap(idx,self._parent(idx))
            idx = self._parent(idx)
        
    def pop(self):
        if not self.isEmpty():
            first = self._heap[0]
            self._heap = self._heap[1:] 
            idx = 0 
            while (self.size() > self._left(idx) and self._compare(self._left(idx),idx)) or (self.size() > self._right(idx) and self._compare(self._right(idx),idx)):
                if  (self.size() > self._left(idx) and self._compare(self._left(idx),idx)):
                    self._swap(self._left(idx),idx)
                    idx = self._left(idx)
                else:
                    self._swap(self._right(idx),idx)    
                    idx = self._right(idx)
            return first
        else:
            return None
        
    def print(self):
        print(self._heap)

    def _parent(self,idx):
        return (idx-1)//2
        
    def _left(self,idx):
        return (idx*2)+1     
        
    def _right(self,idx):
        return (idx*2)+2
        
    def _swap(self,i,j):
        self._heap[i],self._heap[j]=self._heap[j],self._heap[i]
            
    def _compare(self,i,j):
        return self._comparator(self._heap[i],self._heap[j])

pq = PriorityQueue(lambda a,b : a>b)
for i in [3,15,7,10,5,20]:
    pq.push(i)
pq.print()
pq.pop()
pq.print()
pq.pop()
pq.print()

[20, 10, 15, 3, 5, 7]
[15, 10, 3, 5, 7]
[10, 3, 5, 7]

Tree

top

Tree > Binary Tree

top

Perfect Binary Tree: All branches have 2 leaf
Full Binary Tree: Each branch has either 2 leaves or no leaves

Balanced:
lookup: O(log N)
insert; O(log N)
delete: O(log N)

Unbalanced / Degenerate:
lookup: O(n)
insert; O(n)
delete: O(n)

class Node:
    def __init__(self,value):
        self.left = None
        self.right = None
        self.value = value

Binary Search Tree

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        leaf = Node(value)
        if not self.root:
            self.root = leaf
            return
        node = self.root
        while node:
            temp = node
            if leaf.value < node.value:
                node = node.left
                if not node:
                    temp.left = leaf
            else:
                node = node.right
                if not node:
                    temp.right = leaf
            
    #divide and conquer
    def lookup(self,value):
        if self.root.value == value:
            return True
        node = self.root
        while node:
            if value < node.value:
                node = node.left
            elif value == node.value:
                return True
            else:
                node = node.right
        return False
    
    def remove(self,value):
        node = self.root
        parent = node
        left = True
        while node:
            if value < node.value:
                parent = node
                node = node.left
                left = True
            elif value > node.value:
                parent = node
                node = node.right
                left = False
            else:
                if not (node.left and node.right):
                    print("no leaf")
                    print(parent)
                    print(node)
                    if left:
                        parent.left = None
                    else:
                        parent.right = None
                elif node.left and not node.right:
                    print("left leaf")
                    if left:
                        parent.left = node.left
                    else:
                        parent.right = node.left
                elif node.right and not node.left:
                    print("right leaf")
                    if left:
                        parent.left = node.right
                    else:
                        parent.right = node.right
                elif node.left and node.right:
                    print("both leaf")
                    nodeRight = node.right
                    nodeLeft = node.left
                    nodeLowest = node.left
                    nodeLowestParent = node
                    while nodeLowest.left:
                        nodeLowestParent = nodeLowest
                        nodeLowest = nodeLowest.left
                    if nodeLowest.right:
                        nodeLowestParent.left = nodeLowest.right
                    
                    nodeLowest.left = nodeLeft
                    nodeLowest.right = nodeRight
                    if left:
                        parent.left = nodeLowest
                    else:
                        parent.right = nodeLowest
                return True
        return False
"""
     9
   /   \
  4     20
 / \   /  \
1   6 15  170
"""
tree = BinarySearchTree()
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)

print(tree.lookup(15))
print(tree.lookup(10))
tree.remove(4)
print(tree.lookup(4))

True
False
both leaf
False

AVL and Red/Black trees perform auto balancing

Tree > Heap

top

lookup: O(n)
insert; O(log N)
delete: O(log N)

Max Heap: every child node has a lower value than the parent node
Min Heap: the root node is the smallest

heap is different from binary search tree as in BST nodes where in order (left for smaller, right for bigger),
but in heap both childern are either smaller or bigger. This is maintaned using up bubbling that each time the balanced is destroyed, the nodes swape with the parent and bubble up till the balance is restored

heaps are useful when we want a group of values, for example for values higher than 20, we would just pick all nodes above 20

Priority Queue is one of the uses of the heap

A heap can be written as an array as follows:

Max Heap: [100,40,50,10,15,50,40]

parent: floor((idx - 1) / 2)
=> parent of 15: ((4-1) / 2) = 1

left : (idx 2) + 1
=> left of 40 : (1 2) + 1 = 3

right : (idx 2) + 2
=> right of 40 : (1 2) + 2 = 4

Adding to heap:

Add the value to the last index, then Bubble up. The value should be smaller than all of its parent, if not, swap

Removing from heap:

remove the value, and swap it with its first child. The child should be bigger than its left and rigth children, if not swap.

Tree > Trie

top

Trie allows you to know if a word or part of a word exists in a body of text
AKA Prefix Tree

O (lenght of the word)

It is mainly used with strings. A use if this tree can be for auto-completion

class Trie:
    class Node:
        def __init__(self):
            self.end = False
            self.keys = {}

    def __init__(self):
        self.root = self.Node()
        

    def insert(self, word: str) -> None:
        lst = list(word)
        node = self.root
        for index,char in enumerate(lst):
            if char not in node.keys:
                node.keys[char] = self.Node()
            if index == len(lst)-1:
                node.keys[char].end = True
            node = node.keys[char]
        

    def search(self, word: str) -> bool:
        lst = list(word)
        node = self.root
        for index,char in enumerate(lst):
            if char not in node.keys:
                return False
            if index == len(lst)-1:
                return node.keys[char].end
            node = node.keys[char]
        

    def startsWith(self, prefix: str) -> bool:
        lst = list(prefix)
        node = self.root
        for index,char in enumerate(lst):
            if char not in node.keys:
                return False
            node = node.keys[char]
        return True

trie = Trie()
trie.insert("apple")
print(trie.search("apple"))#returns true
print(trie.search("app"))# returns false
print(trie.startsWith("app"))# returns true

True
False
True

Graph

top

A set of values that are related in a pair wise passion
Node (Vertex) are connected with Edges

Types of Graphs

Directed/Undirected

Directed Graphs: A kind of system where the movement is not bio directional, eg traffic flow, Twitter
Undirected Graphs: A system where the movement is bio directional, eg Highways, FaceBook

Wieghted/ Unwieghted

Wieghted Graphs: only the nodes have values
Unwieghted Graphs: Information can be also added to the edges

Cyclic/ Acyclic

Cyclic Graphs: A system where there is a cycle and you can reach the first node by only moving forward. System with loops.
Acyclic Graphs: A system where there is no cycle. You can not reach the fist node by just moving forward. System without loops.

Implementing Graphs

Edge List

An Edge list graph can be create using an array of pair holding the values of the edges

"""
    2 --- 0 
   / \
  /   \
 1 --- 3
"""
graph = [[0,2],[2,1],[2,3],[1,3]]

Adjacent List

An Adjacent list graph can be create using an array where the index is the node and the value is the nodes neighbors

"""
    2 --- 0 
   / \
  /   \
 1 --- 3
"""
graph = [[2],[2,3],[0,1,3],[1,2]] #The index of the array is the value of the actual graph node

Adjacent Matrix

An Adjacent Matrix graph can be create using a matrix, each index has an array representing all the other value.
1 for has a conection and 0 for no connection. if weighted, the weights instead of 0 or 1.

"""
    2 --- 0 
   / \
  /   \
 1 --- 3
"""
graph = [
    [0,0,1,0],
    [0,0,1,1],
    [1,1,0,1],
    [0,1,1,0]
        
        ] #The index of each array is the value of the actual graph node

# Undirected Unweighted Graph
class Graph:
    def __init__(self):
        self.numberOfNodes = 0
        self.adjacentList = {}
        
    def addVertex(self,node):
        self.adjacentList[node]= []
        
    def addEdge(self, node1,node2):
        self.adjacentList[node1].append(node2)
        self.adjacentList[node2].append(node1)
        
    def showConnections(self):
        allNodes = self.adjacentList.keys(); 
        for node in allNodes: 
            nodeConnections = self.adjacentList[node]; 
            connections = ""; 
            for vertex in nodeConnections:
                connections += vertex + " ";
            print(node + "-->" + connections); 

"""
 3 --- 4 --- 5
 |     |     |
 1 --- 2     6
  \   /
    0
"""
myGraph = Graph();
myGraph.addVertex('0');
myGraph.addVertex('1');
myGraph.addVertex('2');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addEdge('3', '1'); 
myGraph.addEdge('3', '4'); 
myGraph.addEdge('4', '2'); 
myGraph.addEdge('4', '5'); 
myGraph.addEdge('1', '2'); 
myGraph.addEdge('1', '0'); 
myGraph.addEdge('0', '2'); 
myGraph.addEdge('6', '5');

myGraph.showConnections(); 

0-->1 2 
1-->3 2 0 
2-->4 1 0 
3-->1 4 
4-->3 2 5 
5-->4 6 
6-->5 

References

top

Instructors

• Andrei Neagoie: Master the Coding Interview: Data Structures + Algorithms

  https://academy.zerotomastery.io/p/master-the-coding-interview-data-structures-algorithms

• Yihua Zhang: Master the Coding Interview: Big Tech (FAANG) Interviews

  https://academy.zerotomastery.io/p/master-the-coding-interview-faang-interview-prep

Aditional Resources

• http://stoimen.com/2012/08/31/computer-algorithms-graphs-and-their-representation/