Задача про акції Apple

Завдача, яку давали на співбесідах в Apple. Від Вас вимагається написати функцію, яка повертає максимальний прибуток від однієї угоди з однією акцією (спочатку купівля, потім продаж). Початкові дані – масив вчорашніх котирувань stock_prices_yesterday з цінами акцій Apple.

Інформація про масив:

• Індекс дорівнює кількості хвилин з початку торговельної сесії (09.30).
• Значення в масиві дорівнює вартості акції на цей час.

Наприклад: якщо акція о 10.00 коштувала $20, то
stock_prices_yesterday[30] = 20.

Припустимо, маємо деякі умови:

stock_prices_yesterday =[10, 7, 5, 8, 11, 9]profit = get_max_profit (stock_prices_yesterday) #поверне 6 (купили за 5, продали за 11)

Масив може бути будь-яким, хоч за весь день. Треба написати функцію get_max_profit якомога ефективніше – з найменшими витратами часу виконання і пам’яті.

Розв’язання

Для розв’язання задачі недостатньо просто взяти максимальну і мінімальну ціни, оскільки Ви спочатку повинні купити за найнижчою ціною, а потім продати за найвищою, яка буде після ціни купівлі. Крім того, якщо ціна акції падає весь день, то кращою відповіддю буде негативне число.

Для кожної ціни перевірятимемо:

• можливість отримати великий прибуток при купівлі за min_price і продажу за current_price.
• чи оновилася min_price новим значенням після ітерації.

Ініціалізація:

• min_price дорівнює першій ціні дня.
• max_profit дорівнює першому отриманому прибутку.

Код розв’язання (на Python):

def get_max_profit (stock_prices_yesterday): # переконаємося, що кількість цін в масиві перевищує 2 if len (stock_prices_yesterday)  < 2: raise IndexError ('Отримання прибутку вимагає як мінімум двох цін в масиві')  # ініціалізували min_price і max_profit min_price = stock_prices_yesterday[0] max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0] for index, current_price in enumerate (stock_prices_yesterday): # пропустимо 0-ою елемент масиву, оскільки min_price ініціалізував. # Також продавати в 0-ій позиції не можна if index == 0: continue # обчислюваний потенційний прибуток potential_profit = current_price - min_price # оновлюваний максимальний прибуток max_profit = max (max_profit, potential_profit)
# оновлюємо мінімальну ціну min_price = min (min_price, current_price) return max_profit

Ефективність отриманого алгоритму – 0(n) за часом і 0(1) за пам’яттю. Цикл проходить по масиву тільки один раз.

Джерело: Interview Cake