Real-world Problem

Part 1: Static File

You are given a static log file containing billions of entries. Each entry contains a timestamp and the name of a food order. The entries in the log file appear in order of increasing timestamp. Design a method getCommon(k) to determine the k most common food orders found in the log file.

1595268625,Hamburger
1595268626,Salad
1595268627,HotDog
1595268628,Hamburger
1595268629,HotDog
1595268630,HotDog
...

Answer

import * as fs from "fs";
import path from "path";
import * as readline from "readline";

interface FoodOrder {
  food: string;
  count: number;
}

class MinHeap {
  private heap: FoodOrder[];

  constructor(private capacity: number) {
    this.heap = [];
  }

  insert(order: FoodOrder): void {
    if (this.heap.length < this.capacity) {
      this.heap.push(order);
      this.heapifyUp();
    } else if (order.count > this.heap[0].count) {
      this.heap[0] = order;
      this.heapifyDown();
    }
    console.log("heap", this.heap);
  }

  extract(): FoodOrder | undefined {
    if (this.heap.length === 0) return undefined;
    const root = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown();
    }
    return root;
  }

  size(): number {
    return this.heap.length;
  }

  private heapifyUp(): void {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex].count <= this.heap[index].count) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  private heapifyDown(): void {
    let index = 0;
    while (index < this.heap.length) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let smallest = index;

      if (
        leftChild < this.heap.length &&
        this.heap[leftChild].count < this.heap[smallest].count
      ) {
        smallest = leftChild;
      }
      if (
        rightChild < this.heap.length &&
        this.heap[rightChild].count < this.heap[smallest].count
      ) {
        smallest = rightChild;
      }
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }
}

async function getCommon(filePath: string, k: number): Promise {
  const foodCount: Map = new Map();
  const heap = new MinHeap(k);

  const fileStream = fs.createReadStream(filePath);
  const rl = readline.createInterface({ input: fileStream });

  // Count occurrences directly
  for await (const line of rl) {
    const [, food] = line.split(","); // Assuming log format: "timestamp,food"
    foodCount.set(food, (foodCount.get(food) || 0) + 1);
  }

  // Maintain top K in the heap
  for (const [food, count] of foodCount) {
    heap.insert({ food, count });
  }

  // Extract top K from the heap
  const result: string[] = [];
  while (heap.size() > 0) {
    result.push(heap.extract()!.food);
  }

  return result.reverse(); // Reverse to get descending order
}

// Usage example
(async () => {
  const k = 3;
  const topK = await getCommon(path.resolve(__dirname, "log.txt"), k);
  console.log("Top food orders:", topK);
})();

Part 2: Streaming

We now want to analyze food orders in a real-time streaming application. All food orders may not have been received at the time the top k most common ones need to be computed. Given the addition of this requirement, how would you handle processing incoming food orders and computing the top k?

Your solution should have two functions: ingestOrder(order) and getCommon(k). Expect the number of function calls to ingestOrder(order) and getCommon(k) to be roughly equal.

Answer

type MenuItemType = "CATEGORY" | "DISH" | "OPTION";

interface MenuItem {
  id: number;
  type: MenuItemType;
  name: string;
  price?: number;
  linkedItems: number[];
}

class Category implements MenuItem {
  id: number;
  type: "CATEGORY";
  name: string;
  linkedItems: number[];

  constructor(id: number, name: string, linkedItems: number[]) {
    this.id = id;
    this.type = "CATEGORY";
    this.name = name;
    this.linkedItems = linkedItems;
  }
}

class Dish implements MenuItem {
  id: number;
  type: "DISH";
  name: string;
  price: number;
  linkedItems: number[];

  constructor(id: number, name: string, price: number, linkedItems: number[]) {
    this.id = id;
    this.type = "DISH";
    this.name = name;
    this.price = price;
    this.linkedItems = linkedItems;
  }
}

class OptionItem implements MenuItem {
  id: number;
  type: "OPTION";
  name: string;
  price: number;
  linkedItems: number[];

  constructor(id: number, name: string, price: number) {
    this.id = id;
    this.type = "OPTION";
    this.name = name;
    this.price = price;
    this.linkedItems = [];
  }
}

class Menu {
  items: MenuItem[];

  constructor() {
    this.items = [];
  }

  // Method to add a menu item
  addItem(item: MenuItem) {
    this.items.push(item);
  }

  // Method to reconstruct the menu stream from the object
  reconstructMenuStream(): string {
    return this.items
      .map((item) => {
        let base = `${item.id}\n${item.type}\n${item.name}`;
        if (item.type === "DISH" || item.type === "OPTION") {
          base += `\n${item.price?.toFixed(2)}`;
        }
        if (item.linkedItems.length > 0) {
          base += `\n${item.linkedItems.join("\n")}`;
        }
        return base;
      })
      .join("\n\n");
  }
}

function parseMenuStream(menuStream: string): Menu {
  const lines = menuStream.split("\n");
  const menu = new Menu();
  let i = 0;

  while (i < lines.length) {
    const id = parseInt(lines[i]);
    const type = lines[i + 1] as MenuItemType;
    const name = lines[i + 2];
    const linkedItems: number[] = [];
    let price: number | undefined;

    if (type === "DISH" || type === "OPTION") {
      price = parseFloat(lines[i + 3]);
      i += 4;
    } else {
      i += 3;
    }

    // Collect linked items
    while (i < lines.length && lines[i].trim() !== "") {
      linkedItems.push(parseInt(lines[i]));
      i++;
    }

    let menuItem: MenuItem;
    if (type === "CATEGORY") {
      menuItem = new Category(id, name, linkedItems);
    } else if (type === "DISH") {
      menuItem = new Dish(id, name, price!, linkedItems);
    } else {
      menuItem = new OptionItem(id, name, price!);
    }

    menu.addItem(menuItem);

    // Skip over the blank line between items
    i++;
  }

  return menu;
}

// Example usage:

const menuStream = `
4
DISH
Spaghetti
10.95
2
3

1
CATEGORY
Pasta
4
5

2
OPTION
Meatballs
1.00

3
OPTION
Chicken
2.00

5
DISH
Lasagna
12.00

6
DISH
Caesar Salad
9.75
3
`;

const myMenu = parseMenuStream(menuStream.trim());
console.log(myMenu.items);
console.log(myMenu.reconstructMenuStream());