Завдання про касира-програміста


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

Завдання, яке давали на співбесідах в Apple. Уявіть, що ви отримали роботу касира в магазині. Ваш бос випадково з’ясував, що ви маєте навички програміста, і захотів, щоб ви допомогли йому написати програму.

Вхідні дані:

  1. Вказана сума грошей.
  2. Масив з усіма доступними номіналами монет.

Треба написати функцію, яка на виході видасть кількість усіх можливих способів отримати вказану суму грошей за допомогою різних доступних номіналів монет. Наприклад, якщо вам треба отримати 4 центи з монет номіналами 1, 2 і 3 центи, то функція поверне 4 – саме стільки є можливих комбінацій з чисел 1, 2 і 3, щоб отримати в сумі 4:

  1. 1, 1, 1, 1.
  2. 1, 1, 2.
  3. 1, 3.
  4. 2, 2.

Рішення

Ми використовуємо динамічне програмування, щоб створити масив ways_of_doing_n_cents таким чином, що ways_of_doing_n_cents[k] містить значення кількості способів зібрати суму k, використовуючи доступні номінали. Спершу ми розпочнемо з відсутності номіналів, маючи лише один варіант – зібрати суму 0, потім ми додаватимемо по одному номіналу, за збільшенням, і одночасно редагувати наш масив з урахуванням нових номіналів.

Кількість нових варіантів, якими ми можемо зробити суму higher_amount з урахуванням нового номінала монети coin, обчислюється як вже існуюче значення ways_of_doing_n_cents[higher_amount - coin]. Нам вже відомі усі комбінації з попередніми номіналами, тому ми використовуємо цю інформацію при додаванні нового номінала. При додаванні першого номінала, ми вважаємо, що попередній номінал дорівнює 0.

Код рішення на Python:

def change_possibilities_bottom_up (amount, denominations): ways_of_doing_n_cents =[0] * (amount + 1) ways_of_doing_n_cents[0] = 1 for coin in denominations: for higher_amount in xrange (coin, amount + 1): higher_amount_remainder = higher_amount - coin ways_of_doing_n_cents[higher_amount] += ways_of_doing_n_cents[higher_amount_remainder]
return ways_of_doing_n_cents[amount]

Щоб було зрозуміліше, ось що містить масив ways_of_doing_n_cents у міру виконання ітерацій, при цьому сума дорівнює 5 і номінали дорівнюють 1, 3 і 5:

===========key:a = higher_amountr = higher_amount_remainder=======================for coin = 1 :============[1, 1, 0, 0, 0, 0] r a[1, 1, 1, 0, 0, 0] r a[1, 1, 1, 1, 0, 0] r a[1, 1, 1, 1, 1, 0] r a[1, 1, 1, 1, 1, 1] r a============for coin = 3 :=============[1, 1, 1, 2, 1, 1] r a[1, 1, 1, 2, 2, 1] r a[1, 1, 1, 2, 2, 2] r a============for coin = 5 :=============[1, 1, 1, 2, 2, 3] r afinal answer: 3

Складність алгоритму – O (n*m) за часом і O (n) по пам’яті, де n – це сума, а m – кількість різних номіналів.

Джерело: Interview Cake

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


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

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