Welcome back! As we continue our exploration of data structures, our focus now turns to the versatile queue. Imagine being at your favorite coffee shop where orders are taken on a first-come, first-served basis. This process exemplifies how queues function in computer science, making them ideal for modeling scenarios such as printing documents, handling customer service requests, or managing tasks in computing. Today, we will tackle two common interview problems that utilize queues to demonstrate their practical application in solving real-world challenges.

We will be using a simple array to represent our queue, using the push method to add an element to the queue, and the shift method to dequeue an element from the queue.

When merging data from two different sources, we seek to alternate between each source fairly, much like traffic from two lanes merging on a highway. Cars from both lanes are expected to merge seamlessly, taking turns. In the world of data structures, we face a similar task of intertwining two queues.

Suppose you're working with two devices that send printing tasks to a shared printer. You would alternate print jobs from each device's queue to prevent one device from monopolizing the printer. We will combine two queues by alternating their elements.

Let's work through the implementation step by step, using TypeScript:

TypeScript
Copy to clipboard
1function interweaveQueues<T>(queue1: T[], queue2: T[]): T[] {
2  const resultQueue: T[] = [];
3  
4  while (queue1.length > 0 || queue2.length > 0) {
5    // Take turns removing elements from each queue (array) and adding them to the resultQueue.
6    if (queue1.length > 0) {
7      resultQueue.push(queue1.shift());
8    }
9    if (queue2.length > 0) {
10      resultQueue.push(queue2.shift());
11    }
12  }
13  return resultQueue;
14}

Through this method, we maintain a fair and balanced output, accurate to the input order. It's akin to taking turns in a game, ensuring each player receives an equal opportunity. Our queue operations ensure we only add or remove from the front, maintaining the integrity and sequence of each queue's items.

Let's move on to the next problem - calculating the moving average from a data stream. This often appears in technical interviews and is typically applied in real-time decision-making settings, such as a trader monitoring livestock prices for rapid buying or selling decisions. A Data Stream is a continuous, potentially infinite sequence of data values. A Moving Average is simply the average value for a fixed subset (or window) of data. In TypeScript, we can define our data types clearly, which is crucial for maintaining clean and reliable code.

A queue can provide an efficient solution to this problem. By utilizing TypeScript, we structure our solution with type annotations that define the data type of the stream and the moving window, facilitating correct calculations of moving averages.

Let's visualize the creation of a MovingAverage class that simulates the backend of our fitness tracking app. We will leverage TypeScript to compute the average of the last k heart rate readings.

TypeScript
Copy to clipboard
1class MovingAverage {
2    private size: number;
3    private window: number[];
4    private sum: number;
5
6    constructor(size: number) {
7        this.size = size;
8        this.window = []; // array to store values (acts as the queue)
9        this.sum = 0.0; // initial sum
10    }
11
12    next(val: number): number {
13        if (this.window.length === this.size) {
14            this.sum -= this.window.shift() as number; // remove oldest value
15        }
16
17        this.window.push(val); // add new value
18        this.sum += val; // update sum
19        return this.sum / this.window.length; // calculate average
20    }
21}

Below is an example of use for the class above. Visualize live data moving in and out, with the heart rate average dynamically adjusting after each new reading:

TypeScript
Copy to clipboard
1const movingAvg = new MovingAverage(3);
2console.log(movingAvg.next(1));     // returns 1.0 (like a single heart rate reading)
3console.log(movingAvg.next(10));    // returns 5.5 (the average after a short burst of activity)
4console.log(movingAvg.next(3));     // returns 4.6...67 (normalizing after the burst)
5console.log(movingAvg.next(5));     // returns 6.0 (the most recent average, taking into account the last three readings)

Today's session has brought the queue to life, advancing us beyond its simple definition to its powerful application in common interview problems. As we encounter more challenges using queues, remember that although each problem may demand a unique method, principles of data structures like queues remain our constant guide.