One Page to Crack Them All

What is DSA?

DSA involves the study of ways to organize and manipulate data to perform various tasks efficiently. DSA - A data structure is a way to store data.

  • Primitive Data Structures are basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.
  • Abstract Data Structures are higher-level data structures that are built using primitive data types and provide more complex and specialized operations. Some common examples of abstract data structures include arrays, linked lists, stacks, queues, trees, and graphs.

Algorithm - An algorithm is a set of step-by-step instructions to solve a given problem or achieve a specific goal.

Key Concepts in DSA

1. Data Structures

Data structures are ways to organize and store data. Here are some of the commonly used ones:

Arrays

A collection of elements of the same type, stored in contiguous memory locations.

# Example: Searching in an array (linear search)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Found the element
    return -1  # Element not found

arr = [1, 2, 3, 4, 5]
print(linear_search(arr, 3))  # Output: 2
Linked Lists

A linear collection where each element (node) points to the next node.

# Example: Linked List Node and Traversal
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = new_node
    
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # Output: 1 -> 2 -> 3 -> None
Stacks

Follows Last In, First Out (LIFO) principle.

# Example: Stack Implementation using List
stack = []
stack.append(1)  # Push
stack.append(2)
stack.append(3)
print(stack.pop())  # Output: 3 (Pop)
Queues

Follows First In, First Out (FIFO) principle.

# Example: Queue Implementation using List
queue = []
queue.append(1)  # Enqueue
queue.append(2)
queue.append(3)
print(queue.pop(0))  # Output: 1 (Dequeue)
Hash Tables

Stores key-value pairs for efficient lookup.

# Example: Hash Map (Dictionary in Python)
hash_map = {'a': 1, 'b': 2, 'c': 3}
print(hash_map['b'])  # Output: 2
Trees

Hierarchical structure with nodes connected by edges.

# Example: Binary Tree and Traversals
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=" ")
        in_order_traversal(root.right)

# Creating a simple tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
in_order_traversal(root)  # Output: 2 1 3

2. Algorithms

Sorting Algorithms

Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.

# Example: Bubble Sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [5, 2, 9, 1, 5, 6]
bubble_sort(arr)
print(arr)  # Output: [1, 2, 5, 5, 6, 9]

Merge Sort: Divides the array into two halves, sorts them, and merges them back.

# Example: Merge Sort
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(arr)  # Output: [5, 6, 7, 11, 12, 13]
Searching Algorithms

Binary Search: Finds the position of a target value within a sorted array.

# Example: Binary Search
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1, 2, 3, 4, 5]
print(binary_search(arr, 3))  # Output: 2
Dynamic Programming

Fibonacci Sequence: Using memoization to optimize the recursive Fibonacci calculation.

# Example: Fibonacci with Memoization
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55
Graph Algorithms

Depth First Search (DFS): Traverses as deep as possible before backtracking.

# Example: Depth First Search (DFS) using Recursion
def dfs(graph, node, visited=set()):
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
dfs(graph, 'A')  # Output: A B D E F C

Time and Space Complexity

Time complexity is a way to express how the running time of an algorithm changes with respect to the input size. Space complexity measures the amount of memory the algorithm uses.

  • O(1): Constant time (e.g., accessing an array element)
  • O(log n): Logarithmic time (e.g., binary search)
  • O(n): Linear time (e.g., looping through an array)
  • O(n²): Quadratic time (e.g., bubble sort)
  • O(n log n): Log-linear time (e.g., merge sort)