Join our mailing list Subscribe Us
Home
cheat_sheet
code

DSA Cheat sheet

 Data Structures and Algorithms (DSA) are foundational concepts in computer science, critical for solving complex problems efficiently. Mastering DSA is essential for anyone aspiring to excel in technical interviews and software development. A well-organized DSA cheatsheet is a quick reference guide, offering an overview of key concepts, algorithms, and their time complexities. This article presents a comprehensive DSA cheat sheet covering various programming languages like Python, Java, C++, and JavaScript, focusing on the most important topics for interviews.




Key Data Structures and Their Operations

Array DSA Cheat Sheet:

  • Definition: 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 subarray)

Linked Lists:

  • Definition: A 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

Stacks:

  • Definition: A 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

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:

  • Definition: A 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

Graphs:

  • Definition: A collection of nodes connected by edges.
  • Types:
    • Directed Graph
    • Undirected Graph
    • Weighted Graph
    • Unweighted
    • Cyclic
    • Acyclic
  • Common Algorithms:
    • 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

  1. Sorting Algorithms:
    • Bubble Sort: O(n^2)
    • Selection Sort: O(n^2)
    • Insertion Sort: O(n^2)
    • Merge Sort: O(n log n)
    • Quick Sort: O(n log n) on average
    • Heap Sort: O(n log n)

Python Example:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Java Example:

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  1. Searching Algorithms:
    • Linear Search:O(n)
    • Binary Search: O(n log n) (requires sorted array)

Python Example:

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

Java Example:

int binarySearch(int arr[], int x) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

DSA Time Complexity Cheat Sheet

Understanding the time complexity of algorithms is crucial for evaluating their efficiency. Below is a cheat sheet for the time complexities of common operations in different data structures and algorithms:

  1. Arrays:
    • Access: O(1)
    • Search: O(n)
    • Insertion (at end): O(1) / O(n) (at arbitrary position)
    • Deletion: O(n)
  2. Linked Lists:
    • Traversal: O(n)
    • Insertion: O(1) (at the head)
    • Deletion: O(1) (at the head)
  3. Stacks:
    • Push: O(1)
    • Pop: O(1)
    • Peek: O(1)
  4. Queues:
    • Enqueue: O(1)
    • Dequeue: O(1)
    • Peek: O(1)
  5. Binary Trees:
    • Search: O(log n)
    • Insertion: O(log n)
    • Deletion: O(log n)
  6. Graphs:
    • DFS/BFS: O(V + E) where V is the number of vertices and E is the number of edges.
  7. Sorting Algorithms:
    • Bubble Sort: O(n^2)
    • Quick Sort: O(n log n) (average)
    • Merge Sort: O(n log n)
    • Heap Sort: O(n log n)
  8. Searching Algorithms:
    • Linear Search: O(n)
    • Binary Search: O(log n)

DSA Cheat Sheets for Specific Languages

Python DSA Cheat Sheet:

  • Arrays: arr = [1, 2, 3, 4]
  • Linked Lists:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  • Stacks: stack = []
  • Queues: queue = []
  • Trees:
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
  • Graphs:
graph = { "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], }

Java DSA Cheat Sheet:

  • Arrays: int[] arr = {1, 2, 3, 4};
  • Linked Lists:
class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}
  • Stacks: Stack<Integer> stack = new Stack<>();
  • Queues: Queue<Integer> queue = new LinkedList<>();
  • Trees:
class Node {
    int key;
    Node left, right;
    Node(int item) {
        key = item;
        left = right = null;
    }
}
  • Graphs:
HashMap<String, List<String>> graph = new HashMap<>();

C++ DSA Cheat Sheet:

  • Arrays: int arr[] = {1, 2, 3, 4};
  • Linked Lists:
struct Node {
    int data;
    Node* next;
};
  • Stacks: stack<int> s;
  • Queues: queue<int> q;
  • Trees:
struct Node {
    int key;
    Node* left;
    Node* right;
};
  • Graphs:

std::map<int, std::list<int>> graph;

JavaScript DSA Cheat Sheet:

  • Arrays: let arr = [1, 2, 3, 4];
  • Linked Lists:
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
  • Stacks: let stack = [];
  • Queues: let queue = [];
  • Trees:
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
  • Graphs:

const graph = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"], };

Conclusion

A well crafted DSA cheat sheet is a powerful tool for both learning and revising key concepts in data structures and algorithms. Whether preparing for an interview or solving complex coding problems, this guide provides a quick reference to the most important operations, algorithms, and their time complexities across multiple programming languages like Python, Java, C++, and JavaScript.