Lists, Data Structures
In this challenge, you will create a “circular array” — like a normal array, but the end wraps around to the beginning (which makes for some interesting problems).
A circular array is defined by having a start and indexes (be sure to think about optimizing runtime for indexing, since we’ll do this so much more often than adding items to it):
>>> circ = CircularArray()
>>> circ.add_item('harry')
>>> circ.add_item('hermione')
>>> circ.add_item('ginny')
>>> circ.add_item('ron')
>>> circ.print_array()
harry
hermione
ginny
ron
>>> circ.get_by_index(2)
'ginny'
>>> print circ.get_by_index(15)
None
Because the last item circles back around to the first item, you can rotate the list and shift the indexes. Positive numbers rotate the list start (defined as the index 0) to the right (or higher indexes):
>>> circ = CircularArray()
>>> circ.add_item('harry')
>>> circ.add_item('hermione')
>>> circ.add_item('ginny')
>>> circ.add_item('ron')
>>> circ.rotate(1)
>>> circ.print_array()
hermione
ginny
ron
harry
>>> circ.get_by_index(2)
'ron'
And negative numbers rotate the list start to the left (or lower indexes):
>>> circ = CircularArray()
>>> circ.add_item('harry')
>>> circ.add_item('hermione')
>>> circ.add_item('ginny')
>>> circ.add_item('ron')
>>> circ.rotate(-1)
>>> circ.print_array()
ron
harry
hermione
ginny
>>> circ.get_by_index(2)
'hermione'
And you can also rotate more than once around the ring:
>>> circ = CircularArray()
>>> circ.add_item('harry')
>>> circ.add_item('hermione')
>>> circ.add_item('ginny')
>>> circ.add_item('ron')
>>> circ.rotate(-17)
>>> circ.get_by_index(1)
'harry'
If you add a new item after rotating, it should go at the end of the list in its current rotation:
>>> circ = CircularArray()
>>> circ.add_item('harry')
>>> circ.add_item('hermione')
>>> circ.add_item('ginny')
>>> circ.add_item('ron')
>>> circ.rotate(-2)
>>> circ.add_item('dobby')
>>> circ.print_array()
ginny
ron
harry
hermione
dobby
In circular_array.py, you will find the stub of the CircularArray class and the add_item, get_by_index, rotate and print_array methods:
class CircularArray(object):
"""An array that may be rotated, and items retrieved by index"""
def __init__(self):
"""Instantiate CircularArray."""
def add_item(self, item):
"""Add item to array, at the end of the current rotation."""
def get_by_index(self, index):
"""Return the data at a particular index."""
def rotate(self, increment):
"""Rotate array, positive for right, negative for left.
If increment is greater than list length, keep going around.
"""
def print_array(self):
"""Print the circular array items in order, one per line"""
Data Structure
Think about the data structure you’d want to use to store the items.
While it’s tempting to use something like a Linked List, the runtime to find an item by index in a linked list is O(n).
You can use a standard Python array to store the items, but you’ll need to think about how to keep track of the head and handle rotations.