Задача с собеседования в Zalando

В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов.
Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи.

Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада.
Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае.

Пример 1:
Input: bills = [5,5,5,10,20]
Output: true

Пример 2:
Input: bills = [5,5,10,10,20]
Output: false

Чат алгоритмистов

Решение
Создаём переменные для хранения купюр, переменная twenty нам не нужна, потому что не будет использоваться в качестве сдачи.
Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной.
Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге:
При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена.

Сложность
O(n) - по времени
O(1) - по памяти

Код

class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0

for b in bills:
if b == 5:
five += 1
elif b == 10:
if five < 1:
return False
else:
five -= 1
ten += 1
else:
if five >= 1 and ten >= 1:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True

@algoses