Welcome back! As we progress through our course on Advanced Data Structures - Stacks and Queues in Ruby, we will focus on leveraging queues to tackle algorithmic challenges often encountered in technical interviews. With their orderly structure, queues are excellent for representing sequential processes and managing streaming data. In this lesson, we'll explore two problems that highlight complex queue manipulations. Let's dive in and decode these intriguing interview problems, ensuring that the concepts are thoroughly understood with additional examples and detailed explanations.

To achieve queue interleaving, we can use two sub-arrays in Ruby, similar to having two sub-lines in the dance sequence or two lanes on the road. We maintain a clean and efficient interleaving by systematically dequeuing elements from these and enqueuing them back into the main array.

Let's build our solution:

We start by dividing the array into two groups, storing the first half in the first_half array and the second half in the second_half array. With elements neatly organized into two arrays, we merge them to form a new, interleaved sequence.

def interleave_queue(arr)
  raise ArgumentError, "The array must contain an even number of elements." if arr.size.odd?

  first_half = []
  second_half = []

  # Calculate midpoint of the array, and split it in half
  n = arr.size
  for i in 0...(n / 2)
    first_half << arr.shift
  end

  while !arr.empty?
    second_half << arr.shift
  end

  interleaved = []
  # Interleave elements from the first and second halve
  while !first_half.empty? || !second_half.empty?
    interleaved << first_half.shift unless first_half.empty?
    interleaved << second_half.shift unless second_half.empty?
  end
  
  interleaved
end

queue = [1, 2, 3, 4, 5, 6]
interleaved_queue = interleave_queue(queue)
puts "Interleaved queue:"
puts interleaved_queue.join(" ") # Output: 1 4 2 5 3 6

This Ruby code performs the queue interleaving by avoiding additional arrays, making it efficient and demonstrating the elegance of Ruby's data manipulation capabilities.

Next, let's shift our focus to the second problem: computing a moving average from a data stream. This concept is often tested in technical interviews and is crucial for real-time decision-making, such as a trader monitoring livestock prices for quick buying or selling decisions. Our mission is to determine the average of the last k items in a stream of data, which is critical for trend analysis in data analytics.

Alternatively, consider a fitness tracking app that continuously updates a user's average heart rate over the last 10 minutes. The app calculates the average heart rate to showcase the current health status, updating with each new reading received.

Using an array in Ruby allows us to efficiently manage a sliding window containing the most recent k elements, mimicking our fitness app's continuous cycle of heart rate readings where newer data replaces older entries.

Imagine creating a MovingAverage class that mimics the fitness tracking app's backend, providing the average of the last k heart rate readings dynamically:

class MovingAverage
  def initialize(size)
    @size = size
    @window = []
    @sum = 0.0
  end

  def next(val)
    @sum -= @window.shift if @window.size == @size
    @window.push(val)
    @sum += val
    @sum / @window.size
  end
end

m = MovingAverage.new(3)
puts m.next(1) # returns 1.0 (like a single heart rate reading)
puts m.next(10) # returns 5.5 (the average after a short burst of activity)
puts m.next(3) # returns 4.66667 (normalizing after the burst)
puts m.next(5) # returns 6.0 (the most recent average, considering the last three readings)

This Ruby version introduces a class, MovingAverage, efficiently maintaining a sliding window of the latest k readings, much like our app keeping pace with heart rate metrics.

In this lesson, we've uncovered the power of Ruby queues in streamlining complex data manipulations, whether mixing queues for interleaving or maintaining a sliding window for moving averages. Both problem types demonstrated how queues can reduce redundancy and boost efficiency — two key attributes in technical interviews.

After mastering these techniques and understanding the rationale behind using queues, you're now equipped with effective strategies to tackle real-world coding challenges. Using relatable analogies like dance sequences and fitness apps helps ground these abstractions, making them more accessible.