Пары строк в обратном порядке в списке более миллиона строк?

Question

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

Для Eg str [1] =" abc ", мне нужно проверить"cba" точно, без анаграмм.

Метод 1. Сохраните все строки в хэш-наборе, начните обход с первой строки и проверьте, существует ли обратная форма в Hashset. Если да, то пара остальных переходит к следующемуelement.

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

Answer 1

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

Answer 2

Это мое мнение:

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

ключ = символ

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

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

Answer 3

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

Answer 4

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

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

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

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

Примечания:

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

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

// "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 - длина списка

Answer 5

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

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

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

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

Answer 6

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

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