Data Structures & Algorithms: Refresher for Coding Interview

Since I prepare for upcoming coding interviews, I've decided to revisit the core concepts of Data Structures and Algorithms (DSA). This article will be the first refresher to me where I'll explain essential data structures in a straightforward way. Whether you're revising for interviews or brushing up on your fundamentals, I hope you find this helpful!

Common Data Structures

Understanding data structures is essential because choosing the right one directly impacts the efficiency of your solution.

1. Array

• Description: a collection of elements stored in contiguous memory locations.
• Access Time: O(1) for random access.
• Use Case: static data storage, lookup tables, buffers.

const arr = [1, 2, 3, 4]; 
console.log(arr[2]); // return 3
arr.push(5); // add 5 at the end
arr.splice(1, 2); // remove elements from index of 1 to 2; return [ 1, 4, 5 ]

2. Linked List

• Description: a linear collection where each element points to the next.
• Type: Singly, Doubly, and Circular Linked Lists.
• Access Time: O(n) for search; efficient insertions/deletions at the beginning.
• Use Case: dynamic memory allocation, real-time data streams.

class Node {
  constructor(val) {
    this.val = val; 
    this.next = null; 
  }
}

class LinkedList {
  constructor() {
    this.head = null; 
  } 

  push(val) {
    const node = new Node(val); 
    if (this.head === null) {
      this.head = node; 
    } else {
      let curr = this.head; 
      while (curr.next !== null) {
        curr = curr.next; 
      }
      curr.next = node; 
    }
  }

  print() {
    let curr = this.head; 
    let result = ''; 
    while (curr !== null) {
      result += curr.val + ' -> '; 
      curr = curr.next;
    }
    console.log(result + 'null'); 
  }
} 

const list = new LinkedList(); 
list.push(1); 
list.push(2); 
list.push(3); 
list.print(); // return 1 -> 2 -> 3 -> null

3. Stack (LIFO)

• Description: follows Last-In-First-Out (LIFO) principle.
• Operations: push(), pop(), peak().
• Use Case: undo functionality, expression evaluation, backtracking.

const stack = []; 
stack.push(1, 2, 3, 4); 

console.log(stack.pop()); // return 4 
console.log(stack); // return [1, 2, 3] 

4. Queue (FIFO)

• Description: follows First-In-First-Out (FIFO) principle.
• Variants: Circular Queue, Priority Queue, Deque.
• Use Case: task scheduling, BFS traversal, data buffering.

const queue = []; 
queue.push(1, 3, 4, 5); 
console.log(queue); // return [1, 3, 4, 5]
queue.push(2); 
console.log(queue); // return [1, 3, 4, 5, 2]
console.log(queue.shift()); // return 1

5. Hash Table / Hash Map

• Description: key-value pairs with constant-time average access.
• Operations: insert(), delete(), search() in O(1).
• Use Case: caching, frequency counting, fast lookup.

const map = new Map(); 
map.set('a', 1); 
map.set('b', 2); 
console.log(map.get('a')); // return 1

6. Tree

• Description: hierarchical data structure with nodes and children.
• Type:
  • Binary Tree
  • Binary Search Tree (BST): Left < Node < Right
  • Heap: Min-Heap / Max-Heap
  • Trie: Prefix tree for strings
• Use Case: Hierarchical storage (e.g., file systems), autocomplete, heap sort.

// Binary Search Tree
class TreeNode {
  constructor(val) {
    this.val = val; 
    this.left = null; 
    this.right = null; 
  }

  insert(newVal) {
    if (newVal < this.val) {
      this.left ? this.left.insert(newVal) : (this.left = new TreeNode(newVal)); 
    } else {
      this.right ? this.right.insert(newVal) : (this.right = new TreeNode(newVal)); 
    }
  }
}

const root = new TreeNode(10); 
root.insert(5); 
root.insert(15);

7. Graph

• Description: set of nodes (vertices) connected by edges.
• Type: directed, undirected, weighted, unweighted, cyclic, acyclic.
• Use Case: social networks, pathfinding (Dijkstra Algorithm), dependency resolution.

// Adjacency List
class Graph {
  constructor() {
    this.adjList = new Map(); 
  }

  addVertex(v, w) {
    this.adjList.get(v).push(w); 
    this.adjList.get(w).push(v); // undirected graph
  }  

  print() {
    for (let [key, val] of this.adjList) {
      console.log(`{key} -> ${val.join(', ')}`); 
    }
  }
}

const graph = new Graph(); 
graph.addVertex('A'); 
graph.addVertex('B'); 
graph.print(); 
// A -> B
// B -> A

Upcoming Posts

This article serves as a refresher for my DSA journey. In upcoming posts, I'll dive deeper into searching methods.
If you're also preparing for coding interviews or learning DSA, follow for more practical and concise DSA content. Feel free to leave comments for any questions!