Data Structures + Algorithms Flashcards
Linked List
Data structure that stores individual elements (nodes) at different places in memory. Each node contains a value and the location of the next node
Implementation:
class node:
def \_\_init\_\_(self, val, next=None):
self.val = val
self.next = next
Double Linked List
Special type of linked list where each node contains the location of the next node AND location of previous node.
Allowed for reverse transversals.
Implementation:
class double_linked:
def \_\_init\_\_ (self, val, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
Problems that involve being given numbers from range(1, n).
Generally involves arrays and require O(1) memory
Cyclic Sort
Implementation:
i = 0
nums = [2, 4, 1, 3]
while i < len(nums):
j = nums[i]
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
Sliding Window
Requires two pointers, one used in for loop, and then another to keep track of front.
Iterate front pointer with while loop
Tree Breadth First Search
Search algorithm that looks at all nodes at each current level before moving to next depth.
Time Complexity: Because iterating through each node once, O(n)
Space Complexity: O(n)
Implementation:
while queue is not empty:
Remove node from queue and add To current_level Check if left or right child exists And add to queue
Depth First Transversal Types
Inorder: Left, Root, Right
Preorder: Root, Left, Right
Postorder: Left, Right, Root
Cyclic Sort
Hint: Given array of numbers from range(1,n)
Iterate over each item in list, if it does not equal the index then move number to correct index
Initialize:
i=0
while i
Get each digit from number. Example:
num = 1657
Return 1, 6, 5, 7
num = 1657
while num % 10 >= 1:
digit = num % 10
print(digit)
num //= 10
Valid Palindromes
Use two pointers
Purpose: Fast and slow pointers
Used to detect cycles in iterable data
Coding:
Create coding solution for linked list.
Transverse the list, printing out elements.
Reverse the list.
class LinkedListNode:
def \_\_init\_\_(self, data, next=None):
self.data=data
self.next=next
class LinkedList:
def __init__(self):
self.head=None
def add_node(node):
if self.head:
node.next=self.head
self.head=node
else:
self.head=node
Code:
Detect a cycle in a linked list
Fast and slow pointers
slow, fast = head, head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return False
Recursive Functions
Base case: Every recursive function must have a base case. The base case is the simplest scenario that does not require further recursion. This is a termination condition that prevents the function from calling itself indefinitely. Without a proper base case, a recursive function can lead to infinite recursion.
Recursive case: In the recursive case, the function calls itself with the modified arguments. This is the essence of recursion – solving a larger problem by breaking it down into smaller instances of the same problem. The recursive case should move closer to the base case with each iteration.
Stacks
Stack: Linear data structure that operates with last in first out.
Push: Adds an element to the top of the stack.
Pop: Removes and returns the top element of the stack.
Peek (or Top): Returns the top element of the stack without removing it.
IsEmpty: Checks if the stack is empty.
Size: Returns the number of elements in the stack.
Queue
Linear data structure that has first in first out.
Enqueue: Adds an element to the end (rear) of the queue.
Dequeue: Removes and returns the front element of the queue.
Front (or Peek): Returns the front element of the queue without removing it.
IsEmpty: Checks if the queue is empty.
Size: Returns the number of elements in the queue.
Heap
(Min, Max)
A Binary Heap is a complete Binary Tree which is used to store data efficiently to get the max or min element based on its type. A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.
