Код с собеседования: как купить подешевле и продать подороже? — Журнал «Код» программирование без снобизма

Вот типичная задачка на собеседованиях в ИТ-компании. Если вы решите её, будете королём собеседований (или королевой):

Есть список цен, сколько стоил некий товар в разные дни. Например, это ценная бумага. Нужно написать код, который скажет, в какой день нужно было покупать, а в какой — продавать этот товар, чтобы получить максимальную прибыль. Сначала товар нужно купить, потом продать. Если цены идут так, что прибыли не получается, — тоже сообщить об этом.

Примеры списка и ответов:

prices = [7,1,5,3,6,4] ← максимальная прибыль 5, если купить по цене 1 во второй день, а продать за 6 на пятый день;

prices = [7,6,4,3,1] ← прибыли нет (потому что цена всё время снижается).

Логика решения

Разобьём алгоритм на такие этапы:

Гигиена и безопасность. Проверяем, есть ли вообще цены в списке. Если нет — выводим сообщение.
Если цены есть, находим максимальную прибыль, которую можно получить. Для этого находим разницу между минимальным и максимальным значением, которые идут именно в таком порядке, слева направо.
Если прибыль в итоге равна нулю — тоже выводим сообщение, что нет смысла ничего покупать.
Если прибыль больше нуля — выводим дни, когда нужно покупать и продавать.

Первые три пункта простые, а в четвёртом есть подвох.

Проверяем, есть ли цены в списке

Начнём решение с очевидного: если цен в списке нет, то выводим сообщение про это и останавливаем скрипт:

# список цены на товар в разные дни
prices = [7,1,5,1,9,4]

# если список цен пустой — выводим сообщение
if len(prices) == 0: 
    print('Цен нет')
    # останавливаем скрипт
    exit()

Если мы поменяем список цен на пустой (prices = []) и запустим скрипт, то получим сообщение, что там нет цен:

Код с собеседования: как купить подешевле и продать подороже?

Если цены есть — находим прибыль

Теперь, раз цены есть, посчитаем прибыль. Для этого нам понадобятся три переменные:

profit — тут будет наша максимальная прибыль, которую можно получить;
minIndex — номер элемента с наименьшей ценой;
minBuy — минимальная цена, по которой нужно купить товар для максимальной прибыли.

Сделаем простой цикл, где на каждом шаге мы будем брать очередную пару цен и смотреть — будет ли с ними прибыль больше, чем раньше. Если будет — запоминаем прибыль и номер элемента с минимальной ценой. Добавим новый код к предыдущему условию:

# список цены на товар в разные дни
prices = [7,1,5,1,9,4]

# если список цен пустой - выводим сообщение
if len(prices) == 0: 
    print('Цен нет')
    # останавливаем скрипт
    exit()
# если цены есть
else:
    # прибыль на старте нулевая
    profit = 0
    # номер элемента с наименьшей ценой
    minIndex = 0
    # первая цена пусть будет на старте минимальной
    minBuy = prices[0]
    # перебираем все цены
    for i in range(len(prices)):
        # находим прибыль на текущем шаге
        # если она больше предыдущей — берём новую прибыль
        if profit < prices[i] - minBuy:
            profit = prices[i] - minBuy
            # запоминаем позицию минимальной цены
            minIndex = prices.index(min(minBuy, prices[i]))
        # устанавливаем минимальное значение, если текущее меньше минимального
        minBuy = min(minBuy, prices[i])

Сообщаем о нулевой прибыли

Здесь всё просто: если прибыль равна нулю, то выводим сообщение и тоже останавливаем программу:

# если прибыль нулевая if profit == 0: # выводим сообщение и останавливаем программу print('Нет оптимальных дней для покупки') exit()

Выводим оптимальные дни для покупки и продажи

А вот на этом этапе на собеседованиях часто допускают ошибку: раз мы знаем прибыль и минимальную стоимость, то легко узнать максимальную стоимость, сложив эти два числа. И раз мы знаем теперь эту стоимость, то можно найти индекс в списке по значению элемента.

Ошибка здесь в том, что это работает только для случаев, когда в списке максимальная нужная стоимость стоит после минимальной. Но если она встречается два раза — до и после минимальной, — то такая логика даёт сбой.

Допустим, у нас список цен выглядит так:

prices = [7,1,5,1,7,4]

Семёрка здесь встречается два раза — в начале и в середине. Если мы будем использовать такую логику, то команда [prices.index[profit+prices[minIndex]] вернёт только первый найденный элемент, а это будет неправильно.

Чтобы избежать этой ошибки, нам нужно проверять, стоит ли индекс максимальной стоимости после минимальной. Если стоит — его можно заменить на ноль, чтобы он не мешал при дальнейших расчётах. Для этого сделаем копию списка цен и будем менять значения в нём, чтобы не трогать исходные цены:

# копируем список цен
prices_copy = prices
# перебираем все цены
for i in range(len(prices)):
    # находим первый индекс максимальной цены
    sell = prices_copy.index(profit+prices[minIndex])
    # если максимальная цена стоит раньше минимальной
    if sell < minIndex:
        # меняем её на нулевую, чтобы не учитывать её на следующих шагах, и переходим к следующему шагу цикла
        prices_copy[sell] = 0
        pass
    # если максимальная цена стоит после минимальной — останавливаем цикл, мы нашли то, что хотели
    else:
        break

# выводим результаты
print('Покупка: на ' + str(minIndex+1) + ' день по цене ' + str(prices[minBuy]))      
print('Продажа: на ' + str(sell+1) + ' день по цене ' + str(prices_copy[sell]))      
print('Прибыль — ' +str(profit))

При выводе мы прибавляем единицу для того, чтобы компенсировать отчёт элементов списка с нуля — компьютер считает так, а мы считаем с единицы.

Запустим скрипт с исходными данными (7,1,5,1,9,4) и посмотрим, что получилось:

# список цены на товар в разные дни
prices = [7,1,5,1,9,4]

# если список цен пустой - выводим сообщение
if len(prices) == 0: 
    print('Цен нет')
    # останавливаем скрипт
    exit()
# если цены есть
else:
    # прибыль на старте нулевая
    profit = 0
    # номер элемента с наименьшей ценой
    minIndex = 0
    # первая цена пусть будет на старте минимальной
    minBuy = prices[0]
    # перебираем все цены
    for i in range(len(prices)):
        # находим прибыль на текущем шаге
        # если она больше предыдущей — берём новую прибыль
        if profit < prices[i] - minBuy:
            profit = prices[i] - minBuy
            # запоминаем позицию минимальной цены
            minIndex = prices.index(min(minBuy, prices[i]))
        # устанавливаем минимальное значение, если текущее меньше минимального
        minBuy = min(minBuy, prices[i])

# если прибыль нулевая
if profit == 0:
    # выводим сообщение и останавливаем программу
    print('Нет оптимальных дней для покупки')
    exit()

# копируем список цен
prices_copy = prices
# перебираем все цены
for i in range(len(prices)):
    # находим первый индекс максимальной цены
    sell = prices_copy.index(profit+prices[minIndex])
    # если максимальная цена стоит раньше минимальной
    if sell < minIndex:
        # меняем её на нулевую, чтобы не учитывать её на следующих шагах, и переходим к следующему шагу цикла
        prices_copy[sell] = 0
        pass
    # если максимальная цена стоит после минимальной — останавливаем цикл, мы нашли то, что хотели
    else:
        break

# выводим результаты
print('Покупка: на ' + str(minIndex+1) + ' день по цене ' + str(prices[minBuy]))      
print('Продажа: на ' + str(sell+1) + ' день по цене ' + str(prices_copy[sell]))      
print('Прибыль — ' +str(profit))

Любишь Python? Зарабатывай на нём!

Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.

Попробовать бесплатно