Cracking The Coding Interview Together – Problem 7.9: Circular Array

Imagine you are building a high-performance audio streaming platform, a game engine HUD for revolving inventory items, or an operating system's round-robin process scheduler. In all of these systems, you frequently need to shift or rotate items in a sequence. If you have an array of 100,000 items and you need to shift every element to the right by one position every frame, doing a physical memory copy is disastrous for frame rates.

Naive array rotations force us into an O(N) linear time bound because every single memory address must be re-written. When operations happen millions of times per second, this performance bottleneck becomes unmanageable. But what if we didn't move the elements at all? What if, instead of physically shifting data, we shifted our perception of where the array begins?

Today, we are going to work through Problem 7.9: Circular Array from Cracking the Coding Interview. Together, we will design and build a robust, generic, dynamic, and fully iterable CircularArray class in Java that handles rotations in guaranteed O(1) constant time.

Problem Statement

The problem asks us to implement a CircularArray class that supports an array-like data structure capable of efficient rotation. Specifically, our design should satisfy the following core requirements:

• Generics Support: The class must work with any reference type (e.g., CircularArray<T>).
• Efficient Rotation: Shifting the array left or right by any integer amount must complete in $O(1)$ time.
• Random Access: Fetching and setting elements via a zero-based index (e.g., get(int index) and set(int index, T item)) must take $O(1)$ time and respect the current rotation state.
• Language-Native Iteration: The class must implement Java's Iterable<T> interface, allowing clean standard for-each loops that start from the logically rotated head index.

Analyze the Problem Together

Let's dissect what happens during a standard rotation versus a virtualized pointer offset rotation. Suppose we have an array of size 5: ["A", "B", "C", "D", "E"].

If we shift the array right by 2 positions, the physical layout should logically represent: ["D", "E", "A", "B", "C"].

If we physically rewrite elements using array copies, here is how the naive approach compares with our pointer arithmetic approach:

The core "Aha!" moment lies in abstracting index calculation. Instead of reordering elements inside memory, we keep the underlying array frozen in place. We track a single integer pointer, head, which indicates the physical location of logical index 0.

When someone asks for logical index i, we map it to physical index p using modular arithmetic:

$$\text{physicalIndex} = (\text{head} + i) \pmod N$$

However, we must be extremely cautious here with language-specific remainder behavior. In Java, the % operator is a remainder operator, not a true mathematical modulo. If head + i yields a negative number (e.g., when shifting backwards or querying with offset math), (head + i) % N will return a negative integer, causing an ArrayIndexOutOfBoundsException! We must craft a mathematical index conversion method that cleanly handles arbitrary positive and negative shifts.

Questions for the Interviewer

Before diving straight into implementation details, a senior engineer always clarifies boundary conditions with the interviewer. Here are the key questions we should ask:

1. Is the size of the array fixed upon construction, or does it need to dynamically resize like an ArrayList?
   Assumption: The size is fixed at creation time, matching standard fixed-capacity circular buffer requirements.
2. How should negative values in rotation be interpreted?
   Assumption: A positive shift moves logical index 0 to the right (clockwise), while a negative shift moves logical index 0 to the left (counter-clockwise).
3. What exception behavior is expected for invalid indices passed to get() or set()?
   Assumption: We should throw standard IndexOutOfBoundsException for logical indices outside the range $[0, N-1]$.
4. Should the iterator support removal operations via Iterator.remove()?
   Assumption: No, supporting removal in a fixed-size circular array alters capacity or creates gaps, so throwing UnsupportedOperationException is standard.

Think About the Solution

Let's map out our internal architecture before writing code:

• Internal Storage: A generic internal array T[] items. (Note: Java doesn't allow direct creation of generic arrays like new T[size], so we cast (T[]) new Object[size] safely).
• Head Index Tracking: An integer head initialized to 0.
• Logical-to-Physical Conversion: A helper function convert(int index) that translates a logical index into a physical array index:
  (head + (index % items.length) + items.length) % items.length
• Rotation Logic: To rotate by shiftRight, we update:
  head = convert(shiftRight)
• Custom Iterator: An inner class implementing Iterator<T> that maintains an offset _current from 0 to length - 1, returning get(_current) at each step.

Write Code and Explain

Here is our complete, production-grade Java implementation for CircularArray<T>:

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A generic circular array supporting constant O(1) time rotations.
 *
 * @param <T> The type of elements stored in the array.
 */
public class CircularArray<T> implements Iterable<T> {
    private final T[] items;
    private int head = 0;

    @SuppressWarnings("unchecked")
    public CircularArray(int size) {
        if (size <= 0) {
            throw new IllegalArgumentException("Size must be greater than zero.");
        }
        // Safe cast as internal array is private and never exposed directly
        this.items = (T[]) new Object[size];
    }

    /**
     * Maps a logical index (0 to length - 1) to its physical underlying array index.
     */
    private int convert(int index) {
        if (index < 0) {
            index = (index % items.length) + items.length;
        }
        return (head + index) % items.length;
    }

    /**
     * Rotates the circular array by shiftRight positions.
     * Positive values shift right; negative values shift left.
     */
    public void rotate(int shiftRight) {
        head = convert(shiftRight);
    }

    /**
     * Retrieves the element at the specified logical index.
     */
    public T get(int index) {
        validateIndex(index);
        return items[convert(index)];
    }

    /**
     * Sets the element at the specified logical index.
     */
    public void set(int index, T item) {
        validateIndex(index);
        items[convert(index)] = item;
    }

    public int length() {
        return items.length;
    }

    private void validateIndex(int index) {
        if (index < 0 || index >= items.length) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + items.length);
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new CircularArrayIterator();
    }

    /**
     * Inner iterator implementation for seamless for-each loop traversal.
     */
    private class CircularArrayIterator implements Iterator<T> {
        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < items.length;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T item = get(current);
            current++;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Remove operation is not supported.");
        }
    }
}

Code Walkthrough & Key Design Details

1. Safe Generic Array Creation: Java generics use type erasure, which prevents direct instantiation of generic arrays like new T[size]. We allocate an Object[] array and apply @SuppressWarnings("unchecked") on the cast. Because items is private and only accessed via typed methods, type safety is preserved.
2. Robust Index Mapping in convert(): Notice how convert() handles negative indices. If index is negative, index % items.length yields a negative value between -(N-1) and 0. Adding items.length guarantees a positive result in the range [1, N-1] before adding head.
3. Decoupled Rotation: The rotate() method simply reassigns head to convert(shiftRight). No array allocations or element moves occur, guaranteeing exact O(1) runtime execution regardless of array size.
4. Iterable Protocol: By implementing Iterable<T> and providing CircularArrayIterator, clients can write standard idiomatic Java code:
   for (String s : circularArray) { ... }

Time & Space Complexity

• rotate(int shiftRight):
  Time Complexity: O(1). Modulo arithmetic and integer assignment occur in constant clock cycles.
  Space Complexity: O(1). Zero additional memory overhead allocated.
• get(int index) / set(int index, T item):
  Time Complexity: O(1). Direct array offset calculation.
  Space Complexity: O(1).
• Iterator Traversal:
  Time Complexity: O(N) to iterate over all N elements, where each step executes in O(1) time.
  Space Complexity: O(1) auxiliary memory spent tracking state inside the iterator instance.

Why This Problem Matters (The Senior Perspective)

This problem is much more than a common interview puzzle. The technique of virtualizing memory locations via arithmetic mapping is fundamental to systems engineering and software architecture:

• Ring Buffers in Operating Systems & Networking: Hardware device drivers, network socket transmission queues (TCP buffers), and log aggregators rely on fixed-size circular buffers. Producers write at a tail index, consumers read from a head index, and both indices wrap smoothly without costly memory moves.
• Slide Window Analytics & Time Series Data: When tracking moving averages over the last 24 hours (with 1-hour ticks), a circular array enables efficient updating of historical data points by simply overwriting the oldest tick index.
• Thread Safety Considerations: In multi-threaded environments, if multiple threads access `rotate()`, `get()`, or `set()` concurrently, raw field modification on `head` causes race conditions. In production, we would wrap access using ReentrantReadWriteLock (permitting multiple concurrent readers while serializing rotators/writers) or utilize AtomicInteger pointer offsets.

Final Thoughts

By shifting our perspective from physically moving memory elements to mathematically shifting offset pointers, we reduced an O(N) operation down to a blazing fast $O(1)$ execution time. We also ensured clean API ergonomics by integrating Java's native Iterable<T> interface.

Next time you face a performance bottleneck involving sequence reordering or queue shifting, ask yourself: Can I solve this by virtualizing my head index instead of mutating memory?

How would you approach extending this class to support concurrent lock-free reads and writes? Let me know your thoughts, and keep coding clean!