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


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Завдача, яку давали на співбесідах в 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

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *