Algorithms & Data Structures

// Bubble Sort Implementation
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// Example usage
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", array);
console.log("Sorted array:", bubbleSort([...array]));

// Quick Sort Implementation
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Example usage
const array = [10, 7, 8, 9, 1, 5];
console.log("Sorted array:", quickSort([...array]));

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

class BST {
  constructor() {
    this.root = null;
  }
  
  insert(val) {
    this.root = this.insertNode(this.root, val);
  }
  
  insertNode(node, val) {
    if (!node) return new TreeNode(val);
    
    if (val < node.val) {
      node.left = this.insertNode(node.left, val);
    } else if (val > node.val) {
      node.right = this.insertNode(node.right, val);
    }
    
    return node;
  }
  
  search(val) {
    return this.searchNode(this.root, val);
  }
  
  searchNode(node, val) {
    if (!node || node.val === val) return node;
    
    if (val < node.val) {
      return this.searchNode(node.left, val);
    }
    return this.searchNode(node.right, val);
  }
  
  inorderTraversal() {
    const result = [];
    this.inorder(this.root, result);
    return result;
  }
  
  inorder(node, result) {
    if (node) {
      this.inorder(node.left, result);
      result.push(node.val);
      this.inorder(node.right, result);
    }
  }
}

// Example usage
const bst = new BST();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
console.log("Inorder traversal:", bst.inorderTraversal());

// Depth-First Search Implementation
class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  
  dfs(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;
    
    function dfsHelper(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      
      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          return dfsHelper(neighbor);
        }
      });
    }
    
    dfsHelper(start);
    return result;
  }
}

// Example usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(v => graph.addVertex(v));
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log("DFS traversal:", graph.dfs('A'));

// Singly Linked List Implementation
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  append(val) {
    const newNode = new ListNode(val);
    
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }
  
  prepend(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }
  
  delete(val) {
    if (!this.head) return false;
    
    if (this.head.val === val) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
    
    let current = this.head;
    while (current.next && current.next.val !== val) {
      current = current.next;
    }
    
    if (current.next) {
      current.next = current.next.next;
      this.size--;
      return true;
    }
    
    return false;
  }
  
  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }
}

// Example usage
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
console.log("List:", list.toArray());
list.delete(2);
console.log("After deleting 2:", list.toArray());

// Project Euler Problem 1
// Find the sum of all the multiples of 3 or 5 below 1000

function multiplesOf3And5(limit) {
  let sum = 0;
  
  for (let i = 1; i < limit; i++) {
    if (i % 3 === 0 || i % 5 === 0) {
      sum += i;
    }
  }
  
  return sum;
}

// More efficient solution using arithmetic progression
function multiplesOf3And5Optimized(limit) {
  const sumDivisibleBy = (n) => {
    const p = Math.floor((limit - 1) / n);
    return n * (p * (p + 1)) / 2;
  };
  
  return sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15);
}

console.log("Brute force result:", multiplesOf3And5(1000));
console.log("Optimized result:", multiplesOf3And5Optimized(1000));

// Project Euler Problem 2
// Find the sum of the even-valued terms in the Fibonacci sequence
// whose values do not exceed four million

function evenFibonacci(limit) {
  let sum = 0;
  let a = 1, b = 2;
  
  while (b < limit) {
    if (b % 2 === 0) {
      sum += b;
    }
    
    [a, b] = [b, a + b];
  }
  
  return sum;
}

// Alternative approach generating only even Fibonacci numbers
function evenFibonacciOptimized(limit) {
  let sum = 0;
  let a = 2, b = 8; // First two even Fibonacci numbers
  
  sum += a; // Add the first even number (2)
  
  while (b < limit) {
    sum += b;
    [a, b] = [b, 4 * b + a]; // Formula for next even Fibonacci
  }
  
  return sum;
}

console.log("Even Fibonacci sum:", evenFibonacci(4000000));
console.log("Optimized result:", evenFibonacciOptimized(4000000));