Hackbright Code Challenges

Circular Array: Solution

Circular Array: Solution

Problem

Circular Array

Challenge

Medium

Concepts

Lists, Data Structures

Download

circular-array-solution.zip


The key decision for this challenge is how to store the data. Conceptually, it makes sense to think of the array as linked list nodes, where the last node points to the first node and we have a pointer to head. However, this does not optimize the runtime for getting data by index.

Instead, we store the data in a Python list, and we also store which index represents the current “head” for the circular array. As the array rotates, the head index changes, but the list remains the same.

For example, when a list is created:

0 harry
1 hermione
2 ginny
3 ron

Here, self.head is 0. But when the array is rotated, the indexes for the circular array shift. So if we rotate the array by one, the effective indexes for the circular array are:

3 harry
0 hermione
1 ginny
2 ron

But the way this is stored is that self.head has changed to 1. Note that nothing actually changes in self.array. We are just keeping track that the current head of our circuar array is being stored at index 1 of the Python list in self.array.

Another challenge: where to insert new items after the array has rotated. Since the description specifies that new items are to have a position at the end of the current list rotation, the easiest thing to do is to put it at the current head’s position, and then bump the head index up by one.

circular_array.py
class CircularArray(object):
    """An array that may be rotated, and items retrieved by index"""

    def __init__(self):
        """Instantiate CircularArray."""

        # START SOLUTION

        # using a list to store the array instead of linked-list
        # style nodes in order to optimize runtime for indexes
        self.array = []

        # track the current item at index 0 for the circular array
        # by storing that item's actual index in self.array.
        # Store None for an empty array.
        self.head = None

        # END SOLUTION

    def add_item(self, item):
        """Add item to array, at the end of the current rotation."""

        # START SOLUTION

        if self.head is None:
            # if there are currently no items in the array, set
            # `self.array` to contain our new item, and set the head
            # to point to that item (at index 0 in self.array).
            self.head = 0
            self.array = [item]
        else:
            # insert item. If we insert it at the self.head position,
            # it will  get inserted just before the head, which puts
            # it at the end of the current rotation
            self.array.insert(self.head, item)

            # reassign head --- it has shifted ahead by one thanks
            # to the insert for the new item.
            self.head += 1

        # END SOLUTION

    def get_by_index(self, index):
        """Return the data at a particular index."""

        # START SOLUTION

        # index doesn't exist the list, return None
        if index >= len(self.array):
            return None

        # this is the easy case -- the index doesn't go off the
        # end of self.array when you start from head
        if index + self.head < len(self.array):
            return self.array[index + self.head]

        # the fun case: we have to go round the twist (beyond end of
        # self.array). 
        # In this case, add index to self.head and then shift left by
        # the length of array to get back into self.array index space
        adjusted_index = index + self.head - len(self.array)
        return self.array[adjusted_index]

        # END SOLUTION

    def rotate(self, increment):
        """Rotate array, positive for right, negative for left.

        If increment is greater than list length, keep going around.
        """

        # START SOLUTION

        # if the array doesn't have any elements, don't do anything
        if not self.head:
            return

        # mod take care of cases where we've gone all the way around
        adjusted_index = (increment + self.head) % len(self.array)
        self.head = adjusted_index

        # END SOLUTION

    def print_array(self):
        """Print the circular array items in order, one per line"""

        # START SOLUTION

        for i in range(len(self.array)):
            print(self.get_by_index(i))