// =====================================================================
// OBJECTS / TYPE MANIPULATION
// =====================================================================

/**
 * Flatten a nested object
 * Turn a deeply nested object into a single-level object with
 * dot-notation keys, e.g. { a: { b: 1 } } -> { "a.b": 1 }
 *
 * Approach: recursion. For each key, if the value is itself a plain
 * object, recurse into it and prefix the child keys with the parent
 * key. Otherwise, assign the value directly.
 *
 * Time: O(n) where n = total number of leaf + intermediate keys
 * Space: O(n) for the result object, plus recursion stack depth
 */
function flattenObject(
  obj: Record<string, unknown>,
  prefix = ""
): Record<string, unknown> {
  const result: Record<string, unknown> = {};

  for (const key in obj) {
    const value = obj[key];
    const newKey = prefix ? `${prefix}.${key}` : key;

    // Only recurse into plain objects — arrays and null are treated
    // as leaf values, since flattening arrays is ambiguous
    const isPlainObject =
      typeof value === "object" && value !== null && !Array.isArray(value);

    if (isPlainObject) {
      Object.assign(result, flattenObject(value as Record<string, unknown>, newKey));
    } else {
      result[newKey] = value;
    }
  }

  return result;
}

/**
 * Deep clone
 * Create a fully independent copy of an object, including nested
 * objects/arrays, so mutating the copy never affects the original.
 *
 * Approach: recursively copy each level. (In real code, prefer
 * structuredClone() where available — this manual version is what
 * interviewers usually want you to demonstrate understanding of.)
 *
 * Time: O(n) — visits every property once
 * Space: O(n) for the copy, plus recursion stack depth
 */
function deepClone<T>(value: T): T {
  // Primitives (including null) are already immutable — return as-is
  if (value === null || typeof value !== "object") {
    return value;
  }

  // Arrays: clone each element recursively
  if (Array.isArray(value)) {
    return value.map((item) => deepClone(item)) as unknown as T;
  }

  // Plain objects: clone each property recursively
  const result = {} as T;
  for (const key in value) {
    result[key] = deepClone(value[key]);
  }

  return result;
}

/**
 * Deep equal
 * Check whether two values are structurally equal — same shape, same
 * values at every level — not just reference-equal (===).
 *
 * Approach: recursively compare. Primitives compare with ===. For
 * objects/arrays, compare keys first (same number, same names), then
 * recursively compare each value.
 *
 * Time: O(n) where n = total number of properties across both values
 * Space: O(d) recursion depth, where d = nesting depth
 */
function deepEqual(a: unknown, b: unknown): boolean {
  // Fast path: reference-equal or identical primitives
  if (a === b) return true;

  // If either isn't an object (or is null), and they weren't === above,
  // they're not equal
  if (typeof a !== "object" || typeof b !== "object" || a === null || b === null) {
    return false;
  }

  const keysA = Object.keys(a as object);
  const keysB = Object.keys(b as object);

  // Different number of keys means they can't be equal
  if (keysA.length !== keysB.length) return false;

  // Every key in A must exist in B with a deeply equal value
  return keysA.every((key) =>
    deepEqual((a as Record<string, unknown>)[key], (b as Record<string, unknown>)[key])
  );
}

// =====================================================================
// ASYNC PATTERNS
// =====================================================================

/**
 * Debounce
 * Delay invoking a function until a certain amount of time has passed
 * since the last time it was called. Classic use case: search-as-you-type,
 * so you don't fire a request on every keystroke.
 *
 * Approach: keep a timer reference in closure. Every call clears the
 * previous timer and starts a new one — only the last call within the
 * delay window actually runs.
 */
function debounce<Args extends unknown[]>(
  fn: (...args: Args) => void,
  delayMs: number
): (...args: Args) => void {
  let timer: ReturnType<typeof setTimeout> | undefined;

  return (...args: Args) => {
    // Cancel any pending invocation
    if (timer) clearTimeout(timer);

    // Schedule a fresh invocation after the delay
    timer = setTimeout(() => fn(...args), delayMs);
  };
}

/**
 * Throttle
 * Ensure a function runs at most once per fixed time window, no matter
 * how often it's called. Classic use case: scroll/resize handlers.
 *
 * Approach: track whether we're currently "on cooldown". If not, run
 * immediately and start the cooldown; calls during the cooldown are
 * dropped.
 */
function throttle<Args extends unknown[]>(
  fn: (...args: Args) => void,
  limitMs: number
): (...args: Args) => void {
  let onCooldown = false;

  return (...args: Args) => {
    if (onCooldown) return; // drop calls while on cooldown

    fn(...args);
    onCooldown = true;

    setTimeout(() => {
      onCooldown = false;
    }, limitMs);
  };
}

/**
 * Promise-based retry wrapper
 * Retry an async operation up to N times with a delay between attempts,
 * useful for flaky network calls (e.g. a service-to-service request
 * that might transiently fail).
 *
 * Approach: recursive/looping async function. Try the operation; on
 * failure, if attempts remain, wait and try again; otherwise, throw.
 */
async function retry<T>(
  operation: () => Promise<T>,
  maxAttempts: number,
  delayMs: number
): Promise<T> {
  let lastError: unknown;

  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    try {
      return await operation();
    } catch (err) {
      lastError = err;

      // Only wait before retrying if we have attempts left
      if (attempt < maxAttempts) {
        await new Promise((resolve) => setTimeout(resolve, delayMs));
      }
    }
  }

  // Every attempt failed — surface the last error
  throw lastError;
}

/**
 * Promise.all with a concurrency limit
 * Run a batch of async tasks with at most N running at the same time,
 * instead of firing all of them at once (which can overwhelm an API
 * or database connection pool).
 *
 * Approach: maintain a pool of "in-flight" promises. Whenever the pool
 * has room, start the next task. Each task removes itself from the
 * pool when it settles.
 *
 * Time: O(n) tasks total; wall-clock time depends on concurrency limit
 * Space: O(n) for results, O(limit) for the active pool
 */
async function promiseAllWithLimit<T>(
  tasks: Array<() => Promise<T>>,
  limit: number
): Promise<T[]> {
  const results: T[] = new Array(tasks.length);
  let nextIndex = 0;

  // A single "worker" repeatedly pulls the next task until none remain
  async function worker() {
    while (nextIndex < tasks.length) {
      const currentIndex = nextIndex++;
      results[currentIndex] = await tasks[currentIndex]();
    }
  }

  // Start `limit` workers running concurrently; each drains the shared queue
  const workers = Array.from({ length: limit }, () => worker());
  await Promise.all(workers);

  return results;
}

// =====================================================================
// BASIC TREE / GRAPH
// =====================================================================

/** A generic tree node — think of this as a simplified workflow step. */
interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

/**
 * Flatten a tree (BFS version)
 * Convert a nested tree structure into a flat array of values, in
 * level order (breadth-first) — top-to-bottom, left-to-right.
 *
 * Approach: use a queue. Start with the root; repeatedly dequeue a
 * node, record its value, and enqueue its children.
 *
 * Time: O(n) — visits every node once
 * Space: O(n) — for the result array and the queue
 */
function flattenTreeBFS<T>(root: TreeNode<T>): T[] {
  const result: T[] = [];
  const queue: TreeNode<T>[] = [root];

  while (queue.length > 0) {
    // Dequeue from the front (shift) — this is what makes it BFS
    // rather than DFS (which would pop from the end instead)
    const node = queue.shift()!;
    result.push(node.value);

    // Enqueue all children to be processed after the current level
    queue.push(...node.children);
  }

  return result;
}

/**
 * Flatten a tree (DFS version)
 * Same goal as above, but depth-first: fully explore one branch before
 * moving to the next sibling.
 *
 * Approach: recursion (or an explicit stack). Visit the node, then
 * recurse into each child in order.
 *
 * Time: O(n)
 * Space: O(n) result + O(h) recursion stack, where h = tree height
 */
function flattenTreeDFS<T>(root: TreeNode<T>): T[] {
  const result: T[] = [];

  function visit(node: TreeNode<T>) {
    result.push(node.value);
    for (const child of node.children) {
      visit(child);
    }
  }

  visit(root);
  return result;
}