Skip to main content

DSA

Key concepts:

Data Structures​

  1. Arrays: A collection of elements, each identified by an index. Fixed size and same data type.
  2. Linked Lists: A sequence of nodes, each containing data and a reference to the next node.
  3. Stacks: LIFO (Last In, First Out) structure where elements are added and removed from the top.
  4. Queues: FIFO (First In, First Out) structure where elements are added at the rear and removed from the front.
  5. Trees: Hierarchical structure with nodes, where each node has a value and references to child nodes. Common types include binary trees and binary search trees.
  6. Graphs: A set of nodes connected by edges. Can be directed or undirected.
  7. Hash Tables: Data structure that maps keys to values for efficient lookup.

Algorithms​

  1. Sorting Algorithms:

    • Bubble Sort: Repeatedly swaps adjacent elements that are out of order.
    • Selection Sort: Repeatedly selects the smallest remaining element and swaps it to the correct position.
    • Insertion Sort: Builds the sorted array one element at a time.
    • Merge Sort: Divides the array into halves, recursively sorts them, and merges the sorted halves.
    • Quick Sort: Divides the array using a pivot, recursively sorts the partitions.

  2. Searching Algorithms:

    • Linear Search: Checks each element in the array until the target is found.
    • Binary Search: Efficiently searches a sorted array by repeatedly dividing the search interval in half.

  3. Graph Algorithms:

    • Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.
    • Breadth-First Search (BFS): Explores all neighbors at the present depth before moving on to nodes at the next depth level.
    • Dijkstra's Algorithm: Finds the shortest path between nodes in a graph.
    • A Algorithm*: Uses heuristics to improve the efficiency of pathfinding.

  4. Dynamic Programming: Solves problems by breaking them down into subproblems, solving each subproblem once, and storing their solutions.

    • Fibonacci Sequence: Classic example of dynamic programming.
    • Knapsack Problem: Optimizes the total value in a knapsack without exceeding the weight limit.

  5. Greedy Algorithms: Makes locally optimal choices at each step with the hope of finding a global optimum.

    • Huffman Coding: Uses greedy algorithms for lossless data compression.

Complexity Analysis​

  1. Time Complexity: Measures the amount of time an algorithm takes to complete as a function of the length of the input.
    • Big O Notation: Describes the upper bound of the time complexity (e.g., O(n), O(log n), O(n^2)).
  2. Space Complexity: Measures the amount of memory an algorithm uses as a function of the length of the input.

Advanced Concepts​

  1. Heaps: A special tree-based data structure that satisfies the heap property.

    • Min Heap: Parent nodes are smaller than their child nodes.
    • Max Heap: Parent nodes are larger than their child nodes.

  2. Trie: A tree-like data structure that stores a dynamic set of strings, used for efficient retrieval.

  3. Segment Trees: Used for storing intervals or segments and allows querying which of the stored segments contain a given point.

  4. Union-Find: Also known as Disjoint Set Union (DSU), a data structure that keeps track of elements partitioned into disjoint subsets, supporting union and find operations efficiently.