YouTube Summaries | Top 8 Data Structures for Coding Interviews

October 28th, 2023

TL;DW:

  • Arrays: Contiguous storage, efficient for random access, but slow for insertions in the middle.

  • Linked Lists: Non-contiguous storage with efficient insertions and deletions.

  • Hash Maps: Key-value pairs for efficient insertion, removal, and searching.

  • Queues: Used for FIFO processing with fast push and pop operations.

  • Binary Trees: Binary Search Trees for efficient searching, insertion, and deletion (O(log n)).

  • Prefix Trees (Tries): Ideal for word storage and autocomplete functionality.

  • Heaps: Visualized as trees but implemented with arrays for efficient minimum value retrieval.

  • Graphs: General data structures for nodes connected by edges, used in various algorithms.

Arrays:

  • Stored in contiguous memory.
  • Efficient for accessing elements using indices.
  • Insertion and deletion at the end are efficient (O(1)), but insertion and deletion in the middle is less efficient (O(n)).

Linked Lists:

  • Elements are not stored contiguously in memory; they are connected via pointers.
  • Efficient for insertion and deletion at the beginning, end, and in the middle (O(1)).
  • Less efficient for random access (O(n)).

Hash Maps:

  • Key-value pairs.
  • Efficient for insertion, removal, and searching (O(1)) with keys mapping to values.
  • Unordered data structure.

Queues:

  • Typically implemented using linked lists.
  • Useful for processing elements in a first-in-first-out (FIFO) order.
  • Efficient for push and pop operations at both ends (O(1)).

Binary Trees:

  • Binary Search Trees (BST) have nodes with values, and the left subtree has values less than the current node, and the right subtree has values greater.
  • Efficient for searching, insertion, and deletion when the tree is balanced (O(log n)).

Prefix Trees (Tries):

  • Used for storing and searching words, especially with shared prefixes.
  • Insertion and searching for words are efficient (O(word length)).
  • Useful for autocomplete functionality.

Heaps:

  • Typically visualized as binary trees but implemented using arrays.

  • Min heaps have the minimum value as the root, and max heaps have the maximum.

    • Efficient for finding the minimum (O(1)) and removing the minimum (O(log n)).

  • In a binary heap the indices are organized in a way that allows for efficient parent-child navigation. The formula to map a node at index i to its parent, left child, and right child is as follows:

    • For a node at index i:
      • Its parent is at index (i - 1) / 2.
      • Its left child is at index 2 * i + 1.
      • Its right child is at index 2 * i + 2.

Graphs:

  • A more general data structure representing nodes connected by edges.
  • Graphs can be directed or undirected.
  • Represented using adjacency lists, where each node has a list of its neighbors.
  • Various algorithms can be applied to graphs with varying time complexities.