Data Structures Algorithms Cheat Sheet in Python

DSA Cheat Sheet for interview prep in Python

Key Data Structures and Their Operations:

For all new updates: Subscribe

Array

A collection of elements identified by index or key.

Common Operations:

• Access: O(1)
• Search: O(n)
• Insertion: O(n) (at an arbitrary position)
• Deletion: O(n)

Use Cases: Storing sequential data, performing quick access operations.

Common Problems:

• Two-pointer technique (e.g., finding pairs with a given sum)
• Sliding window (e.g., finding the maximum sum sub-array)

For all new updates: Subscribe

Linked Lists

Linear collection of data elements where each element points to the next.

Types:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Operations:

• Traversal: O(n)
• Insertion: O(1) (at the head)
• Deletion: O(1) (at the head)

Use Cases: Dynamic memory allocation, managing hierarchical data, implementing stacks, and queues.

Common Problems:

• Reversing a linked list
• Detecting cycles using Floyd’s cycle detection algorithm

For all new updates: Subscribe

Stacks

Collection of elements that follows the Last In, First Out (LIFO) principle.

Operations:

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• IsEmpty: O(1)

Use Cases: Function call management, undo mechanisms in text editors, evaluating expressions.

Common Problems:

• Validating balanced parentheses
• Implementing a stack using queues

For all new updates: Subscribe

Queues:

• Definition: A collection of elements that follows the First In, First Out (FIFO) principle.
• Operations:
• Enqueue: O(1)
• Dequeue: O(1)
• Peek: O(1)

Use Cases: CPU scheduling, breadth-first search, managing tasks in a printer queue.

Common Problems:

• Implementing a queue using stacks
• Handling tasks with different priorities using a priority queue

Trees

Hierarchical data structure consisting of nodes.

• Types:
• Binary Tree
• Binary Search Tree (BST)
• AVL Tree
• Red-Black Tree

Operations:

• Insertion: O(log n) for balanced trees
• Deletion: O(log n) for balanced trees
• Search: O(log n) for balanced trees
• Traversal (Inorder, Preorder, Postorder): O(n)

Use Cases: Hierarchical data storage (e.g., file systems), efficient searching and sorting (BSTs), and implementing decision-making algorithms.

Common Problems:

• Finding the lowest common ancestor (LCA)
• Implementing a balanced BST

Binary Trees

• Search: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)

Graphs

Collection of nodes connected by edges.

Types:

• Directed Graph
• Undirected Graph
• Weighted Graph
• Unweighted
• Cyclic
• Acyclic

Common Algorithms:

V is the number of vertices and E is the number of edges.

• Depth-First Search (DFS): O(V + E)
• Breadth-First Search (BFS): O(V + E)
• Dijkstra’s Algorithm: O((V + E) log V) (Shortest path in weighted graph)
• Kruskal’s/Prim’s Algorithm: O(E log V) (Minimum Spanning Tree)

Use Cases: Modeling networks (social networks, transportation systems), finding the shortest path, web crawling.

Common Algorithms:

Sorting Algorithms

• Bubble Sort: O(n²) → (Inefficient for large datasets)
• Selection Sort: O(n²) →(Inefficient for large datasets)
• Insertion Sort: O(n²) →(Efficient for partially sorted arrays)
• Merge Sort: O(n log n) →(Efficient for large datasets, stable)
• Quick Sort: O(n log n) on average, O(n²) worst case →(Efficient for large datasets, unstable)
• Heap Sort: O(n log n) →(Efficient for large datasets, in-place)
• Radix Sort: O(nk) →(Efficient for integer arrays with a known range of values)
• Counting Sort: O(n + k) →(Stable sorting algorithm for integers in a known range)

Searching Algorithms

• Linear Search: O(n) (Simple but inefficient for large datasets)
• Binary Search: O(log n) (Efficient for sorted arrays)
• Interpolation Search: O(log n) (Faster than binary search for uniformly distributed data)
• Jump Search: O(√n) (Efficient for large arrays with sorted data)

Graph Algorithms

|V| represents the number of vertices (nodes) in a graph — — —> |E| represents the number of edges in a graph.

• Breadth-First Search (BFS): O(|V| + |E|) (Finds shortest path in unweighted graphs)
• Depth-First Search (DFS): O(|V| + |E|) (Traverses a graph in a depth-first manner)
• Dijkstra’s Algorithm: O((|V| + |E|) log |V|) (Finds shortest paths in weighted graphs)
• Bellman-Ford Algorithm: O(|V| * |E|) (Finds shortest paths in weighted graphs with negative cycles)
• Floyd-Warshall Algorithm: O(|V|³) (Finds all pairs shortest paths in a weighted graph)

Dynamic Programming

• Memoization: Store results of subproblems to avoid redundant calculations.
• Tabulation: Create a table to store intermediate results and fill it in a bottom-up manner.

Python Quick Implementations

Cheat sheet with basic implementations for some common data structures:

Python DSA Cheat Sheet: Quick Implementations

Building upon the previous explanations, here’s a cheat sheet with basic implementations for some common data structures:

Arrays

• Operations:
• Accessing Elements: arr[index]
• Slicing: arr[start:end:step]
• Iterating: for item in arr:
• Searching: index = arr.index(value) (linear search)
• Sorting: arr.sort() (built-in function)

Linked Lists:

Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    # Other operations: append, insert at position, delete at position, search, traverse

• Doubly Linked List: (Modify Node and LinkedList classes to include prev pointer in Node and modify operations accordingly)

Stacks

stack = []
def push(data):
    stack.append(data)
def pop():
    if not is_empty():
        return stack.pop()
    else:
        print("Stack Underflow")  # Handle empty stack
def is_empty():
    return len(stack) == 0
# Other operations: peek (top element)

Queues

queue = []

def enqueue(data):
    queue.append(data)
def dequeue():
    if not is_empty():
        return queue.pop(0)
    else:
        print("Queue Underflow")  # Handle empty queue
def is_empty():
    return len(queue) == 0
# Other operations: peek (front element)

Trees: (Basic binary tree implementation)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
  def insert(root, data):
    if root is None:
        return Node(data)
    elif    data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    return root   
# Other operations: search, delete, preorder/inorder/postorder traversal

Remember: These are just basic implementations for demonstration purposes. For real-world use cases, you might need more complex implementations with error handling and optimizations.

— — — — — — — — — —

If you like the article and would like to support me, make sure to:

• 👏 Clap for the story (10000 + 1 clap) to help this article be featured
• 📰 For all new updates: Subscribe
• 🔔 Follow Me: LinkedIn | Youtube | GitHub

— — — — — — — — — —

Day-1: Why Data Structure and Algorithm

Day-2: Nodes : Most basic building blocks of data structures

Day-3: Implementing Nodes : Most basic building blocks of data structures

Day-4: Data Structures: The Building Blocks of Coding Mastery