Learn

Technical Interview Problems in Python: Lists

List Rotation: Indices

Optimizing a solution means reducing the memory required (space complexity), or reducing the number of instructions the computer must execute (time complexity).

Sometimes this means entirely rethinking the approach to a question and it’s always meant to be a difficult task.

In the last exercise we created a new list using the slice operator. This requires `O(N)`

space, because a new list is made with **copies of each value**, and `O(N)`

time because **every value is visited** while copying. `N`

represents the number of values in the list.

We need to do better than `O(N)`

.

For time complexity, there’s not much we can do. Rotations could encompass the list, requiring us to iterate approximately `N`

times.

For space complexity, we can optimize by constructing *in-place* solutions, meaning **we don’t create any additional data structures for storing values**.

Single variable declarations are considered `O(1)`

, or *constant space*, because we’re not allocating memory **in relation to the input**.

This example function adds `"!"`

to each string in a list.

```
def constant_space(list_of_strings):
# variable the same regardless of input
exclamation = "!"
for element in list_of_strings:
element += exclamation
# input mutated but no more space used
return list_of_strings
def linear_space(list_of_strings):
exclamation_list = [] # new structure
exclamation = "!"
for element in list_of_strings:
# adding a new value each loop
exclamation_list.append(element + exclamation)
# holds as many new values as the input!
return exclamation_list
```

Given a list and a positive integer, return **the same list** “rotated” a number of times that match the input integer. This time, we’ll rotate the list **backward** and use `O(1)`

space.

```
list = ['a', 'b', 'c', 'd', 'e', 'f']
rotate(list, 1)
# ['b', 'c', 'd', 'e', 'f', 'a']
rotate(list, 4)
# ['e', 'f', 'a', 'b', 'c', 'd']
```

It’s always harder to optimize, so don’t get discouraged!

Write a function `rotate()`

, with the parameters `my_list`

and `num_rotations`

.

`rotate()`

should return the **same** input list rotated `num_rotations`

**backward**.