Складне запитання на інтерв’ю з JavaScript

Посадка на технічну роботу — це велике досягнення, але перш ніж перетнути фінішну лінію, вам доведеться пройти через неминучі "серйозні ворота": тест на кодування. Для багатьох кандидатів це може бути складним викликом, що випробовує не тільки ваші технічні навички, але й здатність зберігати спокій під тиском.

Підготовка до таких інтерв'ю може часто здаватись кошмаром, особливо коли ви не впевнені, на яких темах зосередитись або як підходити до складних задач. Але з правильною підготовкою ви зможете подолати цей етап із впевненістю. У цьому дописі я проведу вас через одну з таких задач з інтерв'ю.

Завдання

Гравець має різні карти в картковій грі. Вам дається масив карт, де кожен елемент представляє очки карти. Множинні карти можуть мати однакове значення очок.

Якщо гравець вирішує використати карту з балами cards[i], він не може використати будь-яку карту з балами cards[i]-2, cards[i]-1, cards[i]+1 або cards[i]+2.

Кожну карту можна використовувати лише один раз.

Поверніть максимальну кількість очок, яку може набрати гравець.

Приклад 1: Вхід: cards = [3, 3, 5, 6]
Вихід: 12
Пояснення: Максимальна можлива кількість очок, що дорівнює 12, отримується за допомогою карт з індексами 0, 1, 3 з балами 3, 3, 6.

Приклад 2: Вхід: cards = [10, 4, 9, 9]
Вихід: 22
Пояснення: Максимальна можлива кількість очок, що дорівнює 22, отримується за допомогою карт з індексами 1, 2, 3 з балами 4, 9, 9.

Обмеження:
1 <= cards.length <= 10⁵
1 <= cards[i] <= 10⁹

Розбір проблеми

Нам потрібно знайти максимальний бал, уникаючи вибору карт, значення яких занадто близькі (±1, ±2). Підхід включає:

1. Підрахунок частоти: Спочатку ми підрахуємо, скільки разів з'являється кожне значення карти.
2. Динамічне програмування (DP): Далі ми використовуємо підхід динамічного програмування, де dp[x] представляє максимальні очки, які ми можемо отримати, використовуючи карти зі значеннями до x.

План:

1. Підрахувати частоту кожного значення карти.
2. Використовувати таблицю DP, де:

• dp[x] = max(dp[x-1], dp[x-2] + x * frequency[x])
• Це рекурентне співвідношення базується на тому, чи вибираємо ми карту зі значенням x чи ні:
• Якщо ми не вибираємо x, то очки будуть рівні dp[x-1].
• Якщо вибираємо x, то додаємо x * frequency[x] до dp[x-2] (тому що ми повинні пропустити x-1 і x+1).

Рішення:

function maxPoints(cards) {  
 // Крок 1: Підрахунок частоти кожного значення карти  
 const freq = {};  
 for (let card of cards) {  
 freq[card] = (freq[card] || 0) + 1;  
 }  

 // Крок 2: Отримати відсортований список унікальних значень карт  
 const uniqueCards = Object.keys(freq).map(Number).sort((a, b) => a - b);  

 // Крок 3: Таблиця динамічного програмування  
 let dp = {};  
 dp[uniqueCards[0]] = uniqueCards[0] * freq[uniqueCards[0]]; // базовий випадок  

 // Крок 4: Заповнення таблиці DP  
 for (let i = 1; i < uniqueCards.length; i++) {  
 let card = uniqueCards[i];  
 if (card === uniqueCards[i - 1] + 1) {  
 dp[card] = Math.max(dp[uniqueCards[i - 1]], (dp[uniqueCards[i - 2]] || 0) + card * freq[card]);  
 } else {  
 dp[card] = dp[uniqueCards[i - 1]] + card * freq[card];  
 }  
 }  

 // Крок 5: Останній елемент у dp містить результат  
 return dp[uniqueCards[uniqueCards.length - 1]];  
}  

// Приклад 1  
const cards1 = [3, 3, 5, 6];  
console.log(maxPoints(cards1)); // Вихід: 12  

// Приклад 2  
const cards2 = [10, 4, 9, 9];  
console.log(maxPoints(cards2)); // Вихід: 22

Пояснення коду:

1. Підрахунок частоти: Ми підраховуємо, як часто з'являється кожне значення карти, використовуючи мапу частот (freq).
2. Унікальні відсортовані карти: Ми отримуємо унікальні значення карт з мапи частот і сортуємо їх у порядку зростання. Це важливо, оскільки наш підхід DP залежить від обробки карт у певній послідовності.
3. Налаштування DP:

• Базовий випадок — це перше унікальне значення карти.
  Якщо це єдина доступна карта, ми множимо її значення на її частоту та зберігаємо результат у dp.
• Для кожної наступної унікальної карти ми або:
• Пропускаємо її, і результат буде таким самим, як для попередньої карти (dp[card - 1]).
• Включаємо її, в такому випадку попередня валідна карта, яку ми можемо взяти, буде card - 2, тому ми додаємо очки за card * frequency[card] до dp[card - 2].

4. Остаточний результат: Остаточний результат — це значення dp для найбільшої карти.

Завершальні думки:

• Комбінація динамічного програмування (Dynamic Programming) та підрахунку частоти — це потужна техніка для розв'язання задач, що включають максимізацію або оптимізацію очок за певних обмежень.
• Орієнтуючись на унікальні значення карт та уникаючи зайвих ітерацій, ми можемо зробити рішення ефективним як за часом, так і за пам'яттю.
• Це рішення демонструє, як динамічне програмування (Dynamic Programming) може бути використане для розкладу задачі на керовані підзадачі, а також як мапа частот може спростити обробку дублікованих значень у масиві.

Застосовуючи ці принципи, ви зможете ефективно розв'язувати подібні задачі оптимізації, особливо в іграх чи сценаріях з обмеженнями на вибір значень із колекції.

Перекладено з: Advanced Javascript Interview Question