Блог

Недавно во время какого-то интервью спросили: «Как найти обратное всех строк, если существует в списке из более чем миллиона строк?

Например, для str[1] = «abc» мне нужно точно проверить наличие «cba», никаких анаграмм.

Способ 1. Сохраните все строки в hashset, начните обход с первой строки и проверьте, существует ли в Hashset перевернутая форма. если да, то пара else переходит к следующему элементу.

Можете ли вы предложить какой-либо метод, если ограничением является память?

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

Вы можете использовать фильтр Блума, который сообщит вам, существует ли строка уже в структуре, подобной хэш-таблице, но каждый сегмент равен только 0 или 1, поэтому используется очень мало места.

Ровно 1 000 000 бит == 125 КБ

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

Это просто мое мнение:

Я бы создал хэш с

ключ = символ

значение = Список строк, которые начинаются с этого символа

• Теперь запустите цикл, внутри которого вам нужно начать с первой строки.
• переверните его
• Возьмите первый символ и найдите этот ключ в хэше
• затем в значении этого он содержит список строк и находит строку в этом списке

С «памятью как ограничением» я бы даже не стал использовать HashSet (который, afaik, также удалит дублированные строки в исходном списке), потому что вы будете использовать дополнительную структуру HashSet, которая занимает некоторое количество памяти.

Сортировка также не улучшит использование памяти.

Я бы использовал исходный список (который уже есть, поэтому дополнительная память не будет использоваться) 3-байтовую целочисленную переменную для итерации списка. 3 байта могут выполнять итерацию по списку из 2 ^ 24 = 16777216 строк

С «памятью как ограничением» я бы выбрал 2 цикла for. Я думаю, что псевдокод, подобный C, будет легче понять, что мой простой английский.

Примечания:

1. Из примера, приведенного в вопросе, на самом деле это не список, а массив, поэтому я буду работать со структурой, как если бы это был массив
2. Вопрос не ясен, как связать эти «abc», «def»,»cba»,»abc». Я буду соединять первый «abc» с «cba», а также этот «cba» со «вторым «abc» (намерение неясно в вопросе)
3. Я предполагаю, что мы не можем изменить исходный список

Вот код с наименьшим потреблением памяти, который я могу придумать:

 // "list" holds the original list (array)
for (int i = 0; i < length(list) - 1; i  ) {
    for (int j = i   1; j < length(list); j  ) {
        if (list[i] == reverse(list[j])) {
            print(list[i]   " reversed is " list[j])
        }
    }
}
  

Что касается использования памяти, это решение будет принимать 2 целочисленные переменные (обычно по 4 байта каждая) исходный список, от которого, я полагаю, мы не можем избавиться.

Что касается использования процессора (на самом деле, не имеет значения, исходя из вопроса), количество раз, когда строки будут отменены, будет: (N * (N 1)) / 2, где N — длина списка

Сначала я бы хэшировал строки, используя хэш, который не зависит от направления. Это может быть простая сумма символов, хотя, безусловно, существуют лучшие схемы, которые будут хэшировать с обоих концов. И чтобы «подсластить сделку», можно добавить длину строки к хэш-значению или иным образом включить ее в хэш.

Затем, когда строки будут разбиты на идентичные хэш-группы, выполните сравнение «длинной руки».

Обратите внимание, что, используя эту схему или ту, где вы просто используете хэш, зависящий от направления, вперед или назад, нужно не сразу вставлять строку в набор хэшей, а сначала проверить ее (с обратным хэшем, если необходимо), и если вы получите совпадение (ипоследующее длинное сравнение истинно) удалите уже хэшированную строку и соедините две. Вторая строка никогда не попадает в набор, и, если все строки имеют совпадения максимум, у вас будет только 500 000 записей в хэш-наборе, и, если строки были случайными, вероятно, ближе к 250 000 (я не садился, чтобы вычислить вероятности).

Таким образом, вам потребуется только один проход через набор строк, чтобы сделать все это.