структура данных проблем

Question

Пожалуйста, помогите мне в поиске оптимальных решений для этих интересных вопросов структуры данных:

1. Учитывая файл, содержащий прибл 10 миллионов слов, разработать структуру данных для поиска анаграмм
2. Написать программу для отображения десяти наиболее часто встречающихся слов в файле, чтобы ваша программа была эффективной во всех мерах сложности.
3. У вас есть файл с миллионами строк данных. Только две линии идентичны; все остальное уникально. Каждая строка настолько длинная, что она может даже не вписываться в память. Какое наиболее эффективное решение для поиска идентичных строк?

Добавление еще некоторые вопросы:

4) (задан MS) Вам предоставляется массив строк длины 3. Один из строки в массив помечен как Start строку и другой, как End строка. Вам нужно преобразовать начальную строку в конец строки, учитывая условие, что промежуточная строка, которую вы сделаете, должна отличаться от предыдущей строки только одним символом, и строка должна присутствовать во входном массиве. например. Если вход

Array: {"fat", "tab", "eat", "see", "tub", "fab", "rat", "sel"} 
Start: "fat" 
End: "tub" 
Then the output should be 
fat -> fab -> tab -> tub 

я пытался решить третью и придумал два возможных appraoches: 1) Только чтение первого слова всех линий, а затем устранить все те строки, в которых первое слово не совпадают с первым словом любой другой строки. Продолжайте получать последовательные слова оставшихся строк таким образом, пока вы не останетесь с двумя строками. Вы получили свой ответ! 2) Преобразуйте каждую строку в меньшее представление. Это может быть достигнуто путем кодирования каждого слова в короткой двоичной форме, а затем для XORing битов, представляющих каждую строку.

Редактировать: У меня теперь есть хорошая коллекция проблем с структурой данных, если кто-то заинтересован в обсуждении их здесь, то я могу опубликовать еще несколько.

Answer 1

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

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

Обратите внимание, что вам нужно будет сначала изменить глубину поиска, чтобы сохранить путь, пройденный вами до сих пор. Для этого вместо того, чтобы нажимать узел, который посещается в Stack, я довел весь путь до этого момента до стека, так что, когда элемент будет найден, у меня есть полный путь от строки Start до строки End.

Answer 2

Я думаю, что ответом на Q2 может быть использование Hashmap или TRIE для хранения слова и его частоты. Обе эти структуры обеспечивают хороший порядок поиска. Для каждого слова в файле проверьте, существует ли слово. Если да, увеличьте свой счет, добавьте слово и инициализируйте счет до 1.

Этот вопрос был недавно задан одному из моих друзей в интервью Microsoft. Решение, которое он предложил, было аналогичным. Поддерживайте HashMap и дважды связанный список. DLL будет сортироваться по частоте слов. Каждый раз, когда в документ добавляется новое слово, DLL будет изменяться соответствующим образом, чтобы отразить текущий отсортированный список.

Я думаю, что наиболее эффективным решением является TRIE с дважды связанным списком.

Answer 3

Я думаю, что 4-й вопрос можно решить с помощью обратного отслеживания, но не уверен, что это было бы оптимальным, попробовав работать над этим вчера, похоже, что решение работает для меня.

Answer 4

Мы можем решить четвертый вопрос, используя гиперкубы (в теории графов), поэтому строки длины 3 могут быть представлены в Q3 с начальной строкой как «000», а строки, которые отличаются от начальной строки, могут быть представлены как « 001 ',' 100 'и' 010 'соответственно, конечная строка как' 111 '.

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