Python вопросы с собеседований

🖥 Задача о циклическом сдвиге



Циклический сдвиг массива — это когда каждый элемент кроме последнего сдвигается вправо, а последний элемент массива становится первым.



На вход подаются массив A и целое число K. Сделайте циклический сдвиг входного массива K раз и верните получившийся массив.



Например, для данных:



A = [2, 5, 1, 4, 6]

K = 3



Циклический сдвиг должен быть выполнен трижды:



[2, 5, 1, 4, 6] -> [6, 2, 5, 1, 4]

[6, 2, 5, 1, 4] -> [4, 6, 2, 5, 1]

[4, 6, 2, 5, 1] -> [1, 4, 6, 2, 5]



И программа должна вернуть



[1, 4, 6, 2, 5]



Если K = 0, то сдвиг не делается.



Для K = 5:



[2, 5, 1, 4, 6] -> [2, 5, 1, 4, 6]



Наивное решение:



1. Определяем, что такое ротировать массив один раз.

2. Делаем это K раз.



def rotate(A, K):

""" Rotates a list K times """

if not A:

return []



for i in range(K):

A = rotate_once(A)

return A





def rotate_once(A):

""" Rotates a list once """

A.insert(0, A[-1])

del A[-1]

return A



Это решение не оптимальное, потому что каждый insert() передвигает все элементы исходного списка. Также оно не учитывает, что после len(A) ротаций список возвращается в исходное состояние.



Индексы элементов в новом массиве несложно рассчитать аналитически, поэтому:



def rotate(A, K):

""" Rotates a list K times """

result = []

if K == 0:

return A

else:

for i in range(len(A)):

new_index = (i - K) % len(A)

result.append(A[new_index])

return result



Это лучше, потому что

▪ результат получается за один проход

▪ и время работы не увеличивается на больших K.



@python_job_interview