Module 2: Caching

Caching is a technique used to store results of expensive operations for future use. This video explains the concept of caching and when to use it.

Key Concepts:

• What caching is and why it's important for performance
• Identifying expensive computations that benefit from caching
• Using objects as cache storage in JavaScript
• Understanding trade-offs between space and time complexity

Related Practice: LeetCode: LRU Cache - A more advanced caching implementation challenge.

This video focuses on planning a caching implementation, considering what data to cache and how to structure your cache.

Planning Steps:

• Identifying appropriate cache keys and values
• Designing the cache data structure
• Planning for cache validation and potential invalidation
• Considering edge cases in your caching strategy

Pseudocode Example:

/*
1. Create a cache object to store results
2. When function is called with input:
   a. Check if input exists as a key in the cache
   b. If exists, return the cached value
   c. If not, perform the calculation
   d. Store the result in cache with input as key
   e. Return the calculated result
*/
                    

In this video, you'll implement a caching solution in JavaScript, translating your plan into working code.

Key Implementation Concepts:

• Creating and maintaining a cache object
• Implementing cache lookup and storage logic
• Using closure to maintain a persistent cache
• Testing the cached solution against non-cached version

Code Example - Memoized Fibonacci:

// Without caching - exponential time complexity O(2^n)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// With caching - linear time complexity O(n)
function memoizedFibonacci() {
  // Cache object to store previously computed values
  const cache = {};
  
  // Inner function that uses the cache
  return function fib(n) {
    // Check if we have already calculated this value
    if (n in cache) {
      return cache[n];
    }
    
    // Base cases
    if (n <= 1) {
      return n;
    }
    
    // Calculate and cache the result
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
  };
}

// Create the memoized function
const fastFib = memoizedFibonacci();

// Compare performance
console.time('Without caching');
fibonacci(30); // Will be very slow
console.timeEnd('Without caching');

console.time('With caching');
fastFib(30);   // Will be very fast
console.timeEnd('With caching');
                    

Related Practice: LeetCode: Climbing Stairs - A problem well-suited for caching/memoization.

Big O notation is a mathematical notation used to describe the performance or complexity of an algorithm. This video will help you understand how to analyze and compare algorithm efficiency.

Common Big O Complexities:

• O(1) - Constant time: operations that take the same amount of time regardless of input size (e.g., accessing an array element by index)
• O(log n) - Logarithmic time: operations whose time grows logarithmically with input size (e.g., binary search)
• O(n) - Linear time: operations whose time scales linearly with input size (e.g., iterating through an array)
• O(n log n) - Linearithmic time: slightly worse than linear (e.g., efficient sorting algorithms like mergesort)
• O(n²) - Quadratic time: operations whose time scales with the square of input size (e.g., nested loops)
• O(2^n) - Exponential time: operations whose time doubles with each addition to input (e.g., recursive fibonacci without caching)

Examples in Code:

// O(1) - Constant time
function getFirstElement(array) {
  return array[0];
}

// O(n) - Linear time
function sum(array) {
  let total = 0;
  for (let i = 0; i < array.length; i++) {
    total += array[i];
  }
  return total;
}

// O(n²) - Quadratic time
function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]]; // Swap
      }
    }
  }
  return array;
}
                    

Related Practice: LeetCode: Contains Duplicate - Practice comparing O(n²) vs O(n) solutions.

Project Focus:

• Implementing memoization to optimize recursive functions
• Creating a caching layer for expensive operations
• Measuring and comparing performance improvements
• Analyzing time and space complexity trade-offs

Instead of using CodeSignal Arcade which is no longer available, we recommend the following LeetCode collections that follow the same principles and provide great alternatives for interview preparation:

• LeetCode: Dynamic Programming Problems - Many DP problems use memoization/caching techniques
• LeetCode: Fibonacci Number - Classic problem for practicing memoization
• LeetCode: Trees and Graphs Questions - Many problems benefit from caching visited nodes