A collection of common interview problems that use the Python List, and strategies for how to construct optimal solutions.

Technical Interview Problems in Python: Lists

We'll explore a common trade-off: time vs. space.

Our previous solution used nested `for` loops to iterate through each element in the list and then iterate **again** for each element in the list to find their sum for a `O(N^2)` time complexity. 

On the bright side, that solution used `O(1)` space because we're not using any additional data structures.

If we sort the list **before** looking for pairs, we can reach `O(N * logN)` time complexity, but we're going to go for a `O(N)` solution by trading away a little space.

Engineering is about trade-offs! This is another opportunity to communicate benefits and drawbacks to the interviewer.

As with other naive solutions, we're doing more work than is necessary. Given the target integer, what information we can gather in a single iteration?

```py
# <> marks the current element
nums = [4, 2, 8, 9, 6]
target = 8

[<4>, 2, 8, 9, 6]
# target - 4 = 4
# we need another 4...

[4, <2>, 8, 9, 6]
# target - 2 = 6
# we need a 6...

[4, 2, <8>, 9, 6]
# target - 8 = 0
# we need a 0...

[4, 2, 8, <9>, 6]
# target - 9 = -1
# we need a -1...

[4, 2, 8, 9, <6>]
# target - 6 = 2
# we need a 2...
```

At each step of the iteration, we know the "complement" number needed to sum to the target. 

Use a dictionary to store that complement at each iteration and solve this problem with `O(N)` time complexity and `O(N)` space complexity.


Pair Sum: Optimized

Lists are a fundamental data structure for any program. When faced with a technical interview problem using lists, here are a few strategies to keep in mind:

* Be comfortable with variables which represent indices in the list, or _pointers_.
  * Accessing the first and last values with indices.
  * Modding by the list length will ensure a valid index. (`num % length_of_list`).
  * Pointers can sometimes substitute for copying a list.
* Ordered datasets unlock a lot of solutions.
  * Sorted data can be searched in `O(logN)` time using binary search.
  * Sorting can be done in `O(N*logN)` time.
* Find the "naive" solution and push to optimize.
  * Interviewers want the optimal solution, but at least talk through the inefficient approach.


Review

Lists are a fundamental data type in Python. Projects make extensive use of lists to store data in sequential order. You should expect **at least** one technical interview question that requires working with lists. 

This lesson introduces common interview problems that involve lists. We solve each question in two ways: an inefficient _naive_ solution and an optimized solution which improves the big O time and/or space efficiency.

The problems are meant to be open-ended: tests will pass with the correct output from a given input. Optimal implementations require that code executes within a time or space requirement. 

We detail **our** approach in the hint for each question.

Make a note of clarifications and ambiguities for each question. **This is a crucial step**. Interviewers often leave this to you so they can see how you problem-solve.

Introduction

We'll end with a classic interview question: given a list of integers and a "target" integer, **return a pair of indices whose values sum to the target**.

```py
nums = [4, 2, 8, 9, 6]
target = 8

pair_sum(nums, target)
# nums[1] + nums[4] == 8
# [1, 4]

pair_sum(nums, 17)
# nums[2] + nums[3] == 17
# [2, 3]

pair_sum(nums, 99)
# no pair sum exists...
# None
```

**Clarifying Questions:** 


* Are there constraints on time or space efficiency?
  * No! Any solution will do.
* Can the numbers be negative or 0?
  * Yes! Your solution should handle those inputs.
* Does the order of indices matter?
  * The earlier index comes first in the return list.
* Do we return all pairs that match a solution?
  * No! The first one that your solution finds will do!

Pair Sum: Naive

For the last problem our suggested solutions had `O(N)` time and/or `O(N)` space complexity.

We can't improve the time complexity. We have to visit each value to determine whether or not it is a duplicate.

We can reduce the space complexity to `O(1)` with an in-place solution. 

We'll adjust the problem to allow for this space complexity. Now we want to alter a **sorted** input list with **all duplicates moved to the end of the list.** 

The return value will be the index of the final unique value.

```py
duplicates = ['a', 'a', 'g', 't', 't', 'x', 'x', 'x']
remove_dups(duplicates)
# 3, index of the last unique value: 'x'
duplicates
# ['a', 'g', 't', 'x' 'a', 'x', 't', 'x']
```

**Clarifying Questions:** 

* Does the ordering of the duplicate(s) matter?
  * No! They can be in any order.


Remove Duplicates: Optimized

Our last problem had a sorted dataset as the input. Sure, it was rotated, but **it started out sorted.**

A sorted list gives us ways to leverage that ordering. After all, someone went through a lot of work putting that data in order!

_Binary search_ is an algorithm which finds a target value in sorted datasets in `O(logN)` time using knowledge of the dataset to guide the search. 

We check the middle value. If it matches our target, we've found the value. If the middle value is **greater than** our target, we can safely ignore everything with a larger index because those values will **also be greater**. This cuts the problem in half.

Our target is the element with a unique property: the **values at the previous and following index both have a greater value.**

This is only true at the index where the rotation "finished" because it marks the beginning of a sorted list.

```py
rotated = ['c', 'd', 'e', 'f', 'a', 'b']
# rotation index is 4

'a' < 'b'
# True
'a' < 'f'
# True
```

Use a modified binary search algorithm to improve our solution's time efficiency from `O(N)` to `O(logN)`.

Rotation Point: Binary Search

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.

```py
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.

```py
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']
```

List Rotation: Indices

We'll continue our theme of list rotation by flipping the problem: given a **sorted** list rotated `k` times, return the index where the "unrotated" list would begin.

```py
rotated_list = ['c', 'd', 'e', 'f', 'a']
rotation_point(rotated_list)
# index 4
# a sorted list would start with 'a'

another_rotated_list = [13, 8, 9, 10, 11] 
rotation_point(rotated_list)
# index 1
# a sorted list would start with 8
```

**Clarifying Questions:** 

* Are there constraints on time or space efficiency?
  * No! Any solution will do.
* Does the rotation direction matter?
  * This won't affect the return value.
* What if the input isn't rotated?
  * Return 0.


Rotation Point: Linear Search

For our first problem, we would like to "rotate" a list, or **move elements forward** in a list by a number of spaces, `k`.

Elements at the greatest index will "wrap around" to the beginning of the list.

```py
list = ['a', 'b', 'c', 'd', 'e', 'f']
rotate(list, 0)
# ['a', 'b', 'c', 'd', 'e', 'f']
rotate(list, 1)
# ['f', 'a', 'b', 'c', 'd', 'e']
rotate(list, 3)
# ['d', 'e', 'f', 'a', 'b', 'c']
```
**Clarifying Questions:** 
* Are there constraints on time or space efficiency?  
  * Nope! Just solve the problem.
* Should I account for negative inputs?  
  * The rotation input will always be positive.
* What if the rotation is greater than the list length? 
  * Continue wrapping! 
  *  The "rotated" list would be the same as the original when `k` is equal to the length.

List Rotation: Slice

Our next problem calculates sums within a list. 

Given a list of integers, return the **maximum sum possible from a contiguous sub-list**. A sub-list is an uninterrupted portion of the list (up to and including the entire list).

```py
nums = [1, -7, 2, 15, -11, 2]

maximum_sub_sum(nums)
# 17
# The sum of sub-list nums[2:4]
```

**Clarifying Questions:** 

* Are there constraints on time or space efficiency?
  * No! Any solution will do.
* Are all the numbers positive?
  * No! Negative numbers can be in the input.
* How big or small can the sub-list be?
  * From a single element to the entire list.

Max list sub-sum: Naive

Duplicate values? Who needs them!

Given a list of values with duplicates, return a list holding the same values in the same order **with all duplicates removed**.

```py
duplicates = ['a', 'a', 'x', 'x', 'x', 'g', 't', 't']
remove_dups(duplicates)
# ['a', 'x', 'g', 't']

more_duplicates = [3, 3, 1, 7, 7, 7]
remove_dups(more_duplicates)
# [3, 1, 7]


```

This is a great problem because there are **many different ways to solve it**. Questions with multiple solutions are an opportunity to discuss with the interviewer. 

Remember: the ability to communicate is essential!

**Clarifying Questions:** 

* Are there constraints on time or space efficiency?
  * No! Any solution will do.
* Is it okay to alter the input list?
  * You can alter the list or return a new list.


Remove Duplicates: Naive

Our last solution had a cubic time complexity: `O(N^3)`.

One iteration for the length of the list `O(N)`, inside **another** iteration for the length of the list `O(N^2)`, inside the inner loop, we copied a sub-list: `O(N^3)`.

Let's optimize using an important concept: **We don't always need to create every possible outcome to know what's best.** 

Do we need to make every sub-list? No! We can visit each value within the list and keep a running tally of sums.

Let's see what information we can gather in a single pass:

```py
# <> will mark the current element
nums = [1, -7, 2, 15, -11, 2]
most_seen = 0
current_max_sub_sum = 0

[<1>, -7, 2, 15, -11, 2]
most_seen = 1
current_max_sub_sum = 1

[1, <-7>, 2, 15, -11, 2]
most_seen = 1
current_max_sub_sum = -6

# our sum is negative
# anything positive which comes after
# will be better without this "sub-list"
# reset current max to 0!

current_max_sub_sum = 0

[1, -7, <2>, 15, -11, 2]
most_seen = 2
current_max_sub_sum = 2

[1, -7, 2, <15>, -11, 2]
most_seen = 17
current_max_sub_sum = 17

[1, -7, 2, 15, <-11>, 2]
most_seen = 17
current_max_sub_sum = 6

# current sum went down, but not negative
# no need to reset!

[1, -7, 2, 15, -11, <2>]
most_seen = 17
current_max_sub_sum = 8
```

Moving through the list **just once** is sufficient to find the maximum contiguous sub-sum.
