Advanced Queue Manipulations in C#

Introduction to the Lesson

Welcome back! As we progress through our course on Advanced Data Structures - Stacks and Queues in C#, we focus on leveraging queues to crack 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 highlighting complex queue manipulations. Let's get started and decode these intriguing interview problems, ensuring that the concepts are thoroughly understood with additional examples and detailed explanations.

Problem 1: Queue Interleaving

a_1

Problem 1: Efficient Approach to Solving the Problem

We will use two auxiliary queues, akin to having two sub-lines in the dance sequence or two lanes on the road, to hold the divided sections of the original queue. We maintain a clean and memory-efficient interleaving without needing extra arrays by systematically dequeuing elements from these and enqueuing them back into the original queue.

Problem 1: Solution Building

First, consider a queue constructed of dancers (or elements). We want to divide this queue into two groups, with the first half entering the firstHalf queue and the second half into the secondHalf queue. This way, we can alternately choose a dancer from each group and form a new, interleaved queue. Let's construct our division: C# Queue<int> firstHalf = new Queue<int>(); Queue<int> secondHalf = new Queue<int>(); // Assume 'queue' is the original queue with 'n' elements int n = queue.Count; for (int i = 0; i < n / 2; i++) {firstHalf.Enqueue(queue.Dequeue());} while (queue.Count > 0) {secondHalf.Enqueue(queue.Dequeue());} By iterating over the original queue, we distribute the elements into two separate queues, simulating the splitting of dancers into two groups. With the first group ready, we proceed to the second, ensuring a balanced division. With both groups lined up, we alternately take a member from each group, thus combining them into the interwoven order: C# while (firstHalf.Count > 0 || secondHalf.Count > 0) {if (firstHalf.Count > 0) {queue.Enqueue(firstHalf.Dequeue());} if (secondHalf.Count > 0) {queue.Enqueue(secondHalf.Dequeue());}} Imagine this as a dance coordinator calling out to each group in turn, forming a new sequence. This approach ensures no auxiliary arrays are needed, thus elegantly solving the problem using only the queues.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 1: Complete Code

using System;
using System.Collections.Generic;

class Program
{
    static void InterleaveQueue(Queue<int> queue)
    {
        if (queue.Count % 2 != 0)
        {
            throw new ArgumentException("The queue must contain an even number of elements.");
        }

        Queue<int> firstHalf = new Queue<int>();
        Queue<int> secondHalf = new Queue<int>();

        int n = queue.Count;

        for (int i = 0; i < n / 2; i++)
        {
            firstHalf.Enqueue(queue.Dequeue());
        }

        while (queue.Count > 0)
        {
            secondHalf.Enqueue(queue.Dequeue());
        }

        while (firstHalf.Count > 0 || secondHalf.Count > 0)
        {
            if (firstHalf.Count > 0)
            {
                queue.Enqueue(firstHalf.Dequeue());
            }
            if (secondHalf.Count > 0)
            {
                queue.Enqueue(secondHalf.Dequeue());
            }
        }
    }

    static void Main(string[] args)
    {
        Queue<int> queue = new Queue<int>(new[] { 1, 2, 3, 4, 5, 6 });
        InterleaveQueue(queue);
        
        Console.WriteLine("Interleaved queue:");
        while (queue.Count > 0)
        {
            Console.Write(queue.Dequeue() + " ");
        }
    }
}

using System;
using System.Collections.Generic;

class Program
{
    static void InterleaveQueue(Queue<int> queue)
    {
        if (queue.Count % 2 != 0)
        {
            throw new ArgumentException("The queue must contain an even number of elements.");
        }

        Queue<int> firstHalf = new Queue<int>();
        Queue<int> secondHalf = new Queue<int>();

        int n = queue.Count;

        for (int i = 0; i < n / 2; i++)
        {
            firstHalf.Enqueue(queue.Dequeue());
        }

        while (queue.Count > 0)
        {
            secondHalf.Enqueue(queue.Dequeue());
        }

        while (firstHalf.Count > 0 || secondHalf.Count > 0)
        {
            if (firstHalf.Count > 0)
            {
                queue.Enqueue(firstHalf.Dequeue());
            }
            if (secondHalf.Count > 0)
            {
                queue.Enqueue(secondHalf.Dequeue());
            }
        }
    }

    static void Main(string[] args)
    {
        Queue<int> queue = new Queue<int>(new[] { 1, 2, 3, 4, 5, 6 });
        InterleaveQueue(queue);
        
        Console.WriteLine("Interleaved queue:");
        while (queue.Count > 0)
        {
            Console.Write(queue.Dequeue() + " ");
        }
    }
}

This code includes the InterleaveQueue method, which interleaves a given queue and checks that the number of elements is even before processing. The Main method demonstrates its usage, including an example where a queue of integers is interleaved and printed.

Problem 2: Complete Code

Here is the complete code for you to test, envisioning live data streaming in and out, with the heartbeat average updated after each new entry:

using System;
using System.Collections.Generic;

class MovingAverage
{
    private int size;
    private Queue<int> window;
    private double sum;

    public MovingAverage(int size)
    {
        this.size = size;
        this.window = new Queue<int>();
        sum = 0.0;
    }

    public double Next(int val)
    {
        if (window.Count == size)
        {
            sum -= window.Dequeue();
        }

        window.Enqueue(val);
        sum += val;
        return sum / window.Count;
    }
}

class Program
{
    static void Main(string[] args)
    {
        MovingAverage m = new MovingAverage(3);
        Console.WriteLine(m.Next(1)); // returns 1.0 (like a single heart rate reading)
        Console.WriteLine(m.Next(10)); // returns 5.5 (the average after a short burst of activity)
        Console.WriteLine(m.Next(3)); // returns 4.66667 (normalizing after the burst)
        Console.WriteLine(m.Next(5)); // returns 6.0 (the most recent average, taking into account the last three readings)
    }
}

using System;
using System.Collections.Generic;

class MovingAverage
{
    private int size;
    private Queue<int> window;
    private double sum;

    public MovingAverage(int size)
    {
        this.size = size;
        this.window = new Queue<int>();
        sum = 0.0;
    }

    public double Next(int val)
    {
        if (window.Count == size)
        {
            sum -= window.Dequeue();
        }

        window.Enqueue(val);
        sum += val;
        return sum / window.Count;
    }
}

class Program
{
    static void Main(string[] args)
    {
        MovingAverage m = new MovingAverage(3);
        Console.WriteLine(m.Next(1)); // returns 1.0 (like a single heart rate reading)
        Console.WriteLine(m.Next(10)); // returns 5.5 (the average after a short burst of activity)
        Console.WriteLine(m.Next(3)); // returns 4.66667 (normalizing after the burst)
        Console.WriteLine(m.Next(5)); // returns 6.0 (the most recent average, taking into account the last three readings)
    }
}

Try adding this code into a C# IDE, running it, and visualizing how the moving average changes dynamically, similar to our app's heart rate tracker.

Introduction to the Lesson

Problem 1: Queue Interleaving

Problem 1: Efficient Approach to Solving the Problem

Problem 1: Solution Building

Join the 1M+ learners on CodeSignal

Problem 1: Complete Code

Problem 2: Moving Average for Data Stream

Problem 2: Efficient Approach to Solving the Problem

Problem 2: Solution Building

Problem 2: Complete Code

Lesson Summary

Practice Exercises