In Python, a list is an object, which means it has its own associated methods for your convenience. However, in algorithms interviews, there will be occasions where you will need to implement your own custom data structures. To prepare, let’s try and implement our own array data structure, and let’s name it Array.

class Array:
	pass

Abstract Data Types

Although we will be tackling abstract data types later in this course, let’s go through a quick rundown on what an abstract data type is. An Abstract Data Type (ADT) is a data type defined through its operations. In the context of an array, it is expected that an array contains the following methods:

__len__()

Python supports operator overloading. Operator overloading is how we can modify the behavior of operators and, in this case, functions. For example __len__() allows us to specify how Python’s len() function will behave when used on our custom Array class.

This method will return the length of the array. However, we will introduce certain constraints that will ensure that your Array class is implemented as efficiently as possible. For example, you are not allowed to iterate over the list when trying to figure out how many items the array has. Ergo, this method should run at constant time or $O(1)$.

To implement this, your custom Array class should hold some sort of state. You can add a count attribute to this class inside the constructor. Also, since we do need to hold a collection of elements, it is clear that we will need a list inside our custom Array class.

class Array:

	def __init__(self):
		self._count = 0
		self._array = []

You might be thinking that you can just use len(self._array) to get the length. However, in this case, we will be simulating fixed-size arrays found on almost every other programming language. While it may be nice to use Python’s built-in features, knowing how arrays really work will help ease your transition from one programming ecosystem to another.

So, in this case, our internal list will have a fixed size 6. As for the implementation of variadic-length arrays (vectors), we will go through this later in the course. So, our constructor (__init__) method will now be the following:

def __init__(self):
	self._count = 0
	self._array = [None, None, None, None, None, None]
	self._MAX_CAPACITY = 6

__getitem__(index)

This method is another operator overload. By implementing __getitem__(index), we can use the square brackets on our custom array class.

# Example
Array[3] # Access the element at index three.

This method takes an integer and returns the element at that index. If the index is invalid (below zero, or over the current size), raise an IndexError.

emplace_back(element)

Array.emplace_back allows us to place an element at the back of the array. Let’s use the animation below for reference:

The key to implementing this method is to use the length to identify where the back of the array is. In this case, since the length is two, we know that index two is the first empty element. We can place our new element 3 there and increment the _count by 1.

Hint: An equivalent for this operation in Python’s lists would be list.append(element).

If emplace_back is used when the length is already six, raise an ArrayFull exception.

Note: ArrayFull is pre-implemented by Interview Query. All you need to do is raise it through: raise ArrayFull()

emplace_front(element)

Array.emplace_front allows is the reverse of emplace_back, allowing you to place an element at the front of the array. However, this method is a bit more complicated compared to emplace_back. Let’s examine how it’s performed:

It’s a bit harder than to add an element at the index of the length. Since we already know where to place the element (i.e., index 0), the challenge now is how to retain the already existing data in the array. In the example above, initially, we have an array (excluding several None) in the form of [12, 9]. Since 12 is already at index 0, how can we move it such that 12 will be placed at index 1 and the element at index 1 will be at index 2?

The smart way to do this is to shift all the elements by one. As you have observed from the animation, we go to the back of the array (using length), and copy the element at index length-1 to the index at length.

Then, repeat this action, but this time, start shifting at length-1 and copy the element at length-2. Do this shifting again and again until we reach index 0. To make this easier, we can have two counters, a copy_from counter and a copy_to counter.

• copy_to will start at index, which we can get using len(Array).
• copy_from will start at index-1.

Of course, we will need to handle the case where the Array is empty. If it is empty, simply place the element at index 0.

After all this, you will also increment the count to reflect the current length.

If emplace_front is used when the length is already six, raise an ArrayFull exception.

# PSUEDOCODE

function emplace_front(element):
	# Handle the edge case where the array is empty
	if length of array is 0 then:
		array[0] = element
		length of array = length of array + 1
		return
	
	# Handle the case where the array is full
	if length of array == MAX CAPACITY:
		raise ArrayFull()

	# Initialize the two counters
	copy_to = length of array
	copy_from = length of array - 1

	# Do the shift
	while copy_to is not 0:
		array[copy_to] = array[copy_from] # the shifting occurs here
		copy_to = copy_to - 1
		copy_from = copy_from - 1

  # Now that we have shifted all the elements, we can now safely overwrite the element
	# at index 0
	array[0] = element
	length of array = length of array + 1
	return
	

emplace(element, index)

The emplace method allows us to append an element at a certain index. For example, let’s define an array as [1, 3]. Using Array.append(2, 1) on this array will morph the array into [1, 2, 3], emplacing the element 2 at index 1.

While this looks like a more complicated version of emplace_front (it is), the logic is not necessarily as different. To implement emplace, simply do the same thing as emplace_front, but this time, modify while copy_to is not 0 to while copy_to is not index. Of course, the edge cases are different. For example, instead of checking if the array is empty, you should check if the array’s length reaches the index.

If length of array = index, then just call emplace_back. If the length is less than the index, rather than raising an error, emplace_back the element