Data Structures & Algorithms — Từ Cơ Bản Đến Phỏng Vấn

// Mảng — contiguous memory, O(1) access, O(n) insert/delete
const arr = [1, 2, 3, 4, 5];

// Two-pointer — kỹ thuật phổ biến
function twoSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

// Sliding window
function maxSubarraySum(nums: number[], k: number): number {
  let max = 0, window = 0;
  for (let i = 0; i < nums.length; i++) {
    window += nums[i];
    if (i >= k) window -= nums[i - k];
    if (i >= k - 1) max = Math.max(max, window);
  }
  return max;
}

class ListNode {
  constructor(public val: number, public next: ListNode | null = null) {}
}

// Reverse linked list
function reverseList(head: ListNode | null): ListNode | null {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Stack — LIFO (Last In, First Out)
// Dùng: undo, bracket matching, DFS
function isValidBrackets(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ')': '(', '}': '{', ']': '[' };

  for (const char of s) {
    if ('({['.includes(char)) {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

// Queue — FIFO (First In, First Out)
// Dùng: BFS, task processing, message queue
class Queue<T> {
  private items: T[] = [];
  enqueue(item: T) { this.items.push(item); }
  dequeue(): T | undefined { return this.items.shift(); }
  isEmpty(): boolean { return this.items.length === 0; }
}

// O(1) average lookup — dùng Map/Set
const countMap = new Map<string, number>();

// Đếm frequency
for (const char of str) {
  countMap.set(char, (countMap.get(char) || 0) + 1);
}

// Two Sum với Hash Map
function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement)!, i];
    map.set(nums[i], i);
  }
  return [];
}

class TreeNode {
  constructor(
    public val: number,
    public left: TreeNode | null = null,
    public right: TreeNode | null = null,
  ) {}
}

// DFS — Depth First Search
function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function dfs(node: TreeNode | null) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);   // In-order
    dfs(node.right);
  }
  dfs(root);
  return result;
}

// BFS — Level Order
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const queue = [root];
  const result: number[][] = [];

  while (queue.length) {
    const levelSize = queue.length;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// Validate BST
function isValidBST(root: TreeNode | null, min = -Infinity, max = Infinity): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

// Adjacency list
const graph = new Map<number, number[]>();
graph.set(1, [2, 3]);
graph.set(2, [4]);
graph.set(3, [4, 5]);

// DFS
function dfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const result: number[] = [];

  function explore(node: number) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph.get(node) || []) {
      explore(neighbor);
    }
  }
  explore(start);
  return result;
}

// BFS
function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>([start]);
  const queue = [start];
  const result: number[] = [];

  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

// Dijkstra — Shortest Path
function dijkstra(graph: Map<number, [number, number][]>, start: number): Map<number, number> {
  const distances = new Map<number, number>();
  const visited = new Set<number>();
  const pq: [number, number][] = [[start, 0]]; // [node, distance]

  distances.set(start, 0);

  while (pq.length) {
    pq.sort((a, b) => a[1] - b[1]);
    const [node, dist] = pq.shift()!;
    if (visited.has(node)) continue;
    visited.add(node);

    for (const [neighbor, weight] of graph.get(node) || []) {
      const newDist = dist + weight;
      if (newDist < (distances.get(neighbor) ?? Infinity)) {
        distances.set(neighbor, newDist);
        pq.push([neighbor, newDist]);
      }
    }
  }
  return distances;
}

// Quick Sort — O(n log n) average
function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

// Merge Sort — O(n log n) ổn định
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}