Arrays and Lists

Question 1

What is an implementation of a shuffle algorithm?

Answer 1

This is an implementation of the Inside-Out variation of the Fisher-Yates shuffle:

To initialize an array a of n elements to a randomly shuffled copy of “source”, both 0-based

for i from 0 to n - 1 do:
j = random integer such that 0 <= j <= i
if j != i, then a[i] = a[j]
a[j] = source[i]

Question 2

Time complexity of python list copy

Answer 2

O(n)

Question 3

Time complexity of python list append[1]

Answer 3

O(1)

Question 4

Time complexity of python list insert

Answer 4

O(n)

Question 5

Time complexity of python list get item

Answer 5

O(1)

Question 6

Time complexity of python list set item

Answer 6

O(1)

Question 7

Time complexity of python list delete item

Answer 7

O(n)

Question 8

Time complexity of python list get slice[k]

Answer 8

O(k)

Question 9

Time complexity of python list del slice

Answer 9

O(n)

Question 10

Time complexity of python list set slice[k]

Answer 10

O(k+n)

Question 11

Time complexity of python list extend

Answer 11

O(k)

Question 12

Time complexity of python list sort

Answer 12

O(n log n)

Question 13

Time complexity of python list multiply []*k

Answer 13

O(nk)

Question 14

Time complexity of python list x in s

Answer 14

O(n)

Question 15

Time complexity of python list min/max

Answer 15

O(n)

Question 16

Time complexity of python list get length

Answer 16

O(1)

Question 17

Time complexity of python dict get item

Answer 17

O(1), amortized worst case O(n)

Question 18

Time complexity of python dict set item

Answer 18

O(1), amortized worst case O(n)

Question 19

Time complexity of python dict delete item

Answer 19

O(1), amortized worst case O(n)

Question 20

what is the algorithm for rotating an array left by r?

What is the complexity of the algorithm, and what other algorithmic options are there?

Answer 20

The simplest possible way to rotate an array can be done with a copy.  Time O(N), Space O(N), which is not that bad.
def rotate_copy(s, r):
    N = len(s)
    out = [None]*N
    for i in range(0, len(s)):
        out[i] = s[(i+r)%N]
    return out

In-place rotation is a bit more complicated, but uses slightly less space. However, a simple inplace algorithm still requires O(N) space

We can get space down to O(1) by using the Juggling algorithm, which requires a constant temporary space. The juggling algorithm might come in handy in the case where you want to visit every item in a particular order of fixed skips, like a rotation.