Interview questions

CircularQueue.cs

public class CircularQueue
{
    // Motivation:
    //
    // We do not store count of items in the queue to avoid mutual blocking of enqueue and dequeu operaions.
    // In the current implementation enqueue and dequeue do not block each other,
    // but simultaneous calls of the same operations will be blocking.
    //
    // Alos we allocate array with size N + 1 to the logical capacity of the queue N,
    // this is made to distinguish between cases when the queue is empty or full
    // (with real capacity N + 1 to its logical capacity N it physically always not full).
    //
    // The additional properties Count and this[index] were added solely for testability.

    private readonly int[] _items;

    private int _head;
    private int _tail;

    // These extra variable isn't required, added only for readability.
    private readonly int _size;

    private readonly object _readsLock = new object();
    private readonly object _writesLock = new object();

    public int Count
    {
        get
        {
            int count = _tail - _head;

            if (count < 0)
                count += _size;

            return count;
        }
    }

    public int this[int index]
    {
        get
        {
            // Absolute index of item calculated from _head, and can be invalidated by a dequeue operation,
            // thus we share the lock with dequeue.
            lock (_readsLock)
            {
                if (index < 0 || index >= Count)
                    throw new IndexOutOfRangeException("The index is out of range.");

                return _items[(_head + index) % _size];
            }
        }
    }

    public CircularQueue(int capacity)
    {
        if (capacity < 0 || capacity == int.MaxValue)
            throw new ArgumentOutOfRangeException("capacity");

        // We do not store count of items in queue explicitly, to avoid mutual blocking of enqueue and dequeue operations.
        _head = 0;
        _tail = 0;
        
        // To distinguish between empty and full states, we adding one extra item to the size of array.
        _size = capacity + 1;

        _items = new int[_size];
    }

    public void Enqueue(int item)
    {
        lock (_writesLock)
        {
            // In case if _head is outdated by simultaneous dequeue, it's OK,
            // because it only decreases amount of items in queue, the test on fullness will be still correct.
            if ((_tail + 1) % _size == _head)
                throw new InvalidOperationException("The queue is full.");

            _items[_tail] = item;

            _tail = (_tail + 1) % _size;
        }
    }

    public int Dequeue()
    {
        // We aren't blocking the Enqueue operataons here.
        lock (_readsLock)
        {
            // Simultaneous enqueue can increase amount of items, but test on empty will be still correct.
            if (_head == _tail)
                throw new InvalidOperationException("The queue is empty.");

            int item = _items[_head];
            
            _head = (_head + 1) % _size;

            return item;
        }
    }
}

QueueTests.cs

[TestClass]
public class QueueTests
{
    [TestMethod]
    public void EmptyQueueHasZeroCountTest()
    {
        var queue = new CircularQueue(5);

        // Ensuring that the newly initialized queue returns count of elements as zero.
        Assert.AreEqual(0, queue.Count);
    }

    [TestMethod]
    public void EnqueueDequeueTest()
    {
        // Ensuring correctness of simple aequence of enqueue and dequeue operations.
        var queue = new CircularQueue(5);

        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        queue.Enqueue(4);

        Assert.AreEqual(4, queue.Count);
        AssertQueueEquals(queue, 1, 2, 3, 4);

        Assert.AreEqual(1, queue.Dequeue());
        Assert.AreEqual(2, queue.Dequeue());

        Assert.AreEqual(2, queue.Count);
        AssertQueueEquals(queue, 3, 4);
    }

    [TestMethod]
    public void EnqueueToFullDequeueToEmptyEnqueueTest()
    {
        const int queueSize = 5;

        // Ensuring correctness of series of sequences of enqueue and dequeue reaching 'full' and 'empty' queue states.
        var queue = new CircularQueue(queueSize);

        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        queue.Enqueue(4);
        queue.Enqueue(5);

        // The queue reached full state.
        Assert.AreEqual(queueSize, queue.Count);
        AssertQueueEquals(queue, 1, 2, 3, 4, 5);

        Assert.AreEqual(1, queue.Dequeue());
        Assert.AreEqual(2, queue.Dequeue());
        Assert.AreEqual(3, queue.Dequeue());
        Assert.AreEqual(4, queue.Dequeue());
        Assert.AreEqual(5, queue.Dequeue());

        // The queue reached empty state.
        Assert.AreEqual(0, queue.Count);

        queue.Enqueue(6);
        queue.Enqueue(7);

        Assert.AreEqual(2, queue.Count);
        AssertQueueEquals(queue, 6, 7);
    }

    [TestMethod]
    public void EmptyQueueThrowsOnDequeueTest()
    {
        var queue = new CircularQueue(5);

        Assert.AreEqual(0, queue.Count);

        // Ensuring that the attempt to dequeue an item from the empty queue leads to exception.
        try
        {
            queue.Dequeue();
            Assert.Fail("InvalidOperationException expected.");
        }
        catch (InvalidOperationException)
        {
            // Expected exception.
        }
        catch
        {
            Assert.Fail("InvalidOperationException expected.");
        }

        // Ensuring that the queue state wasn't broken after exception.
        Assert.AreEqual(0, queue.Count);

        queue.Enqueue(1);
        queue.Enqueue(2);

        Assert.AreEqual(2, queue.Count);
        AssertQueueEquals(queue, 1, 2);
    }

    [TestMethod]
    public void FullQueueThrowsOnEnqueueTest()
    {
        const int queueSize = 5;

        var queue = new CircularQueue(queueSize);

        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        queue.Enqueue(4);
        queue.Enqueue(5);

        // The queue reached full state.
        Assert.AreEqual(queueSize, queue.Count);

        // Ensuring that the attempt to enqueue an item to the full queue leads to exception.
        try
        {
            queue.Enqueue(6);
            Assert.Fail("InvalidOperationException expected.");
        }
        catch (InvalidOperationException)
        {
            // Expected exception.
        }
        catch
        {
            Assert.Fail("InvalidOperationException expected.");
        }

        // Ensuring that the queue state wasn't broken after exception.
        Assert.AreEqual(queueSize, queue.Count);
        AssertQueueEquals(queue, 1, 2, 3, 4, 5);

        Assert.AreEqual(1, queue.Dequeue());
        Assert.AreEqual(2, queue.Dequeue());

        Assert.AreEqual(3, queue.Count);
        AssertQueueEquals(queue, 3, 4, 5);
    }

    private static void AssertQueueEquals(CircularQueue queue, params int[] expected)
    {
        bool equal = queue.Count == expected.Length;

        for (int i = 0; equal && i < expected.Length; i++)
        {
            equal = queue[i] == expected[i];
        }

        Assert.IsTrue(equal, "The queue isn't equal to the expected sequence of items.");
    }
}