Q&A - data-structures-algorithms Page 6

61. How to simulate event propagation in a DOM-like tree?

Problem: Simulate DOM event propagation using capturing and bubbling phases through a custom DOM tree structure.

Key Concepts:

Traverse from the root to the target node.
Collect capture-phase listeners top-down.
At the target node, collect both capture and bubble listeners.
Collect bubble-phase listeners bottom-up.


const domTree = {
  id: "root",
  listeners: { capture: ["logRootCapture"], bubble: ["logRootBubble"] },
  children: [
    {
      id: "parent",
      listeners: { capture: ["logParentCapture"], bubble: ["logParentBubble"] },
      children: [
        {
          id: "child",
          listeners: { capture: ["logChildCapture"], bubble: ["logChildBubble"] },
          children: []
        }
      ]
    }
  ]
};

const targetId = "child";

Expected Output:

[
  "logRootCapture",
  "logParentCapture",
  "logChildCapture",
  "logChildBubble",
  "logParentBubble",
  "logRootBubble"
]


type Node = {
  id: string;
  listeners?: { capture?: string[]; bubble?: string[] };
  children: Node[];
};

function simulateEventPropagation(tree: Node, targetId: string): string[] {
  const path: Node[] = [];

  function dfs(node: Node, currentPath: Node[]): boolean {
    currentPath.push(node);
    if (node.id === targetId) {
      path.push(...currentPath);
      return true;
    }
    for (const child of node.children) {
      if (dfs(child, [...currentPath])) return true;
    }
    return false;
  }

  dfs(tree, []);
  const result: string[] = [];

  for (const node of path) {
    if (node.listeners?.capture) {
      result.push(...node.listeners.capture);
    }
  }

  for (let i = path.length - 1; i >= 0; i--) {
    const node = path[i];
    if (node.listeners?.bubble) {
      result.push(...node.listeners.bubble);
    }
  }

  return result;
}

Explanation: This algorithm mimics the browser's event model using a depth-first traversal to collect listeners in the correct order.

62. How to implement a moving average from a data stream?

Problem: Build a class that efficiently computes the moving average of the last k stream values.

Use a queue to store recent elements.
Maintain a running sum.
Ensure O(1) time per update.


const m = new MovingAverage(3);
console.log(m.next(3));   // 3.0
console.log(m.next(9));   // 6.0
console.log(m.next(4));   // 5.33
console.log(m.next(2));   // 5.0


class MovingAverage {
  private size: number;
  private queue: number[] = [];
  private sum: number = 0;

  constructor(size: number) {
    this.size = size;
  }

  next(val: number): number {
    if (this.queue.length === this.size) {
      const removed = this.queue.shift()!;
      this.sum -= removed;
    }
    this.queue.push(val);
    this.sum += val;
    return this.sum / this.queue.length;
  }
}

Explanation: The queue limits stored items to size k, while the running sum keeps computation efficient. This pattern is known as a sliding window average.

←