
Дізнайтесь більше про нові кар'єрні можливості в 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?