search-suggestions-system.md

Search Suggestions System

Aug 17, 2020 · 5 min read

Дан массив products и поисковый запрос searchWord. Задача написать программу, которая будет подсказывать три продукта из списка, которые подходят лучше всего поисковому запросу.

Что значит «лучше всего подходит по запросу»? Общий префикс.

Если продуктов с общим префиксом больше трёх — вернуть первые три лексикографически наименьших продукта.

Представьте, что пользователь печатает по одной букве слова, пока не получит весь запрос целиком. Нужно вернуть подсказки для каждого префикса.

Пример.

Input:
products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"

Output:
[
    ["mobile","moneypot","monitor"],
    ["mobile","moneypot","monitor"],
    ["mouse","mousepad"],
    ["mouse","mousepad"],
    ["mouse","mousepad"]
]

Для каждого префикса: m, mo, mou, mous, mouse, которые вводит пользователь мы возвращаем массивы продуктов в качестве «подсказок» (например, которые можно вывести в UI теперь). В итоге, получаем массив из 5 массивов.

Задача на LeetCode.

Решение #

Сперва напишем общий скелет решения, который нужен в любом случае.

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
  const result = [];

  for (let i = 1; i <= searchWord.length; i++) {
    // запускаем поиск для каждого префикса
    result.push(search(products, searchWord.slice(0, i)));
  }
  return result;
};

/**
 * @param {string[]} prodcuts
 * @param {string} prefix
 * @return {string[]}
 */
function search(products, prefix) {
  // надо реализовать поиск...
}

Итак, надо реализовать функцию search. Решение «в лоб»:

• бежим по всем продуктам;

• собираем слова с данным префиксом;

• сортируем в конце и берём первые три.

  /**

  • @param {string[]} products
  • @param {string} prefix
  • @return {string[]} */ function search(products, prefix) { const result = [];

  // O(N) чтобы пробежать все продукты for (let i = 0; i < products.length; i++) { // ещё один O(N) для проверки префикса if (products[i].startsWith(prefix)) { result.push(products[i]); } } // O(N * log N) на сортировку return result.sort().slice(0, 3); }

Сложность функции поиска O(N^2) (N это количество продуктов), чтобы собрать все слова. O(N * log N) чтобы отсортировать в конце. В итоге, O(N^2 + N * log N) или O(N^2 * log N).

Вспоминаем как решали пределы в началах анализа. Перепишем как N * (N + 1) * log N. При N стремящемся к бесконечности + 1 — никакого вклада в порядок роста не даёт, соответственно можно опустить.

Поиск мы запускаем M раз (M это длина поискового запроса, т.е. количество префиксов). Получаем общую сложность O(M * N^2 * log N).

Как можно лучше?

Бинарный поиск #

Где лишняя работа? Мы бегаем по всему списку продуктов, собирая слова с нужными префиксами, а после сортируем каждый раз. А что если отсортировать один раз весь список продуктов?

Если список отсортированный, то искать слова с нужными префиксами можно эффективнее, не надо бегать каждый раз сначала. Запустим бинарный поиск!

function search(products, prefix) {
  const result = [];
+ // O(log N)
+ const pivot = binSearch(products, prefix);

- // O(N) чтобы пробежать все продукты
- for (let i = 0; i < products.length; i++) {
+ for (
+   let j = pivot;
+   // максимум 3 элемента, начиная с pivot,
+   // но не выходим за границу массива
+   j < Math.min(pivot + 3, products.length);
+   j++
+ ) {
-   // ещё один O(N) для проверки префикса
+   // теперь элементов максимум три, поэтому это O(1)
    if (products[i].startsWith(prefix)) {
      result.push(products[i]);
    }
  }
- // O(N * log N) на сортировку
- return result.sort().slice(0, 3);
+ return result;
}

Вместо того, чтобы бежать по всему списку мы запускаем бинарный поиск, который находит индекс, начиная с которого начинаются слова с определённым префиксом. Дальше остаётся только взять первые три.

Остаётся реализовать сам поиск, функцию binSearch.

/**
 * @param {string[]} arr
 * @param {string} target
 * @return {number}
 */
function binSearch(arr, target) {
  let left = -1;
  let right = arr.length;

  while (right - left > 1) {
    // просто делим нацело,
    // можно и Math.floor,
    // никакой особенной магии
    // с бинарным сдвигом здесь нет
    const mid = (left + right) >> 1;

    if (target > arr[mid]) {
      left = mid;
    } else {
      right = mid;
    }
  }
  return left + 1;
}

Есть несколько различных шаблонов для бинарного поиска. Мне нравится тот, который мне показал Фёдор Меньшиков.

То, что получилось — аналог lower_bound из стандартной библиотеки C++.

Отлично, это решение получилось быстрее. В тестах на LeetCode количество продуктов не превышает 1000, поэтому разница не большая, но с увеличением количества продуктов — все сильно изменится.

Как изменилась сложность? O(M * log N). Так значительно лучше, мы полностью избавились от N^2.

На самом деле, ещё нужно учитывать длину слова, потому что сравнение < или > тоже не бесплатное, и работает аналогично startsWith. Однако, в сравнении с количеством всех слов — считаем, что это очень малая величина, которой можно пренебречь.

На самом деле, на данном этапе можно успешно закончить собеседование. Для интереса, можно ли ещё лучше?

Префиксные деревья #

Можно построить префиксное дерево из всех продуктов в списке, что значительно ускорит последующий поиск.

Источник.

По сути, чтобы найти нужные слова нужно будет искать в глубину, совершив не более высоты дерева итераций. Соответственно, здесь мы ограничены длиной самого большого слова.

Если любопытно разобраться с префиксными деревьями, я делал отдельное видео на эту тему:

На самом деле построить префиксное дерево так же не бесплатно, это трейд-офф: надо ли нам быстрее начать искать, зато сам поиск будет медленнее, или можно потратить чуть больше времени в начале, зато потом быстрее искать.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.