Arhn - архитектура программирования

Возврат подмножества строк из 10000 строк ascii

Мой колледж подходит к концу, поэтому я начал готовиться к собеседованиям, чтобы получить РАБОТУ, и я наткнулся на этот вопрос, когда готовился к собеседованию.

  1. У вас есть набор из 10000 строк ascii (загруженных из файла)
  2. Строка вводится со стандартного ввода.
  3. Напишите псевдокод, который возвращает (на стандартный вывод) подмножество строк в (1), содержащих те же различные символы (независимо от порядка), что и входные данные в (2). Оптимизация по времени.
  4. Предположим, что эту функцию нужно будет вызывать неоднократно. Однократная инициализация строкового массива и его сохранение в памяти допустимы. Пожалуйста, избегайте решений, которые требуют перебора всех 10000 строк.

Может ли кто-нибудь предоставить мне общий псевдокод/алгоритм, как решить эту проблему? Я чешу голову, думая о решении. Я в основном знаком с Java.

java substring algorithm
16.11.2012

  • Ну, сломай. Что здесь важно? Какие строки содержат те же различные символы, что и входная строка. Таким образом, простым (хотя и не обязательно лучшим) подходом будет преобразование каждой из 10000 строк в строку, содержащую только их отдельные символы. Затем сделайте то же самое для входной строки и, наконец, найдите, какая из 10000 строк соответствует ей. Выяснение такого преобразования, а также того, как на самом деле выполнить сопоставление, является забавной частью. И оттуда, возможно, вы сможете придумать более изобретательное и быстрое решение. 17.11.2012
  • Создайте структуру данных, которая может отображать отдельные символы в список строк (хеш-таблица, доступ O(1)). Когда у вас есть эта структура данных, все остальное тривиально. 17.11.2012
  • Пожалуйста, избегайте решений, требующих перебора всех 10000 строк — извините, что прерываю вас, но чтобы узнать, какие символы находятся в строке, вы должны пройти их хотя бы один раз. Вы можете оптимизировать для повторного доступа. 17.11.2012
  • Да, вопрос гласит, что нам нужно избегать решений, требующих зацикливания 10000 строк. 17.11.2012
  • @VincentSavard, можете ли вы предоставить мне пошаговый алгоритм или псевдокод, который я могу использовать для написания кода? 17.11.2012
  • Я не думаю, что можно узнать, содержится ли набор в другом наборе, не зацикливаясь 10 000 раз. Решение @VincentSavard является оригинальным подходом, но на самом деле оно, кажется, только перемешивает действия: вместо того, чтобы зацикливаться и сообщать, прошла ли строка тест, он сначала зацикливается, чтобы построить карту (что увеличивает потребление памяти), а затем смотрит на карта для вычисления результата. Я думаю, что он будет использовать ровно столько же ЦП и памяти, сколько и решение для dlev, только у него лучше платье :) 17.11.2012
  • Я не уверен, что имеется в виду под одними и теми же отдельными символами. Имеются ли в виду строки, которые только содержат эти символы? Разрешены ли повторы одного и того же символа или только перестановки? 17.11.2012
  • @Raffaele - см. ответ Bohemian для примера того, как будет использоваться карта: идея состоит в том, что при каждом поиске вам нужно только преобразовать входную строку, а не перебирать все 10 000 (помимо начального цикла для предварительного вычисления map -- это нормально, вы пытаетесь избежать последующих итераций). 17.11.2012
  • @NeilCoffey Я не думаю, что вы можете вычислить карту, не перебирая все символы в (возможно, скорректированной) исходной строке. Для меня это плохой вопрос. 17.11.2012
  • @NeilCoffey Пожалуйста, не добавляйте теги [homework] к сообщениям, так как это официально устарело 17.11.2012
  • ОК извините, пропустил это объявление! 17.11.2012

Ответы:


1

Вот алгоритм O (1)!

Инициализация:

  • Для каждой строки отсортируйте символы, удалив дубликаты — например, «деревья» станут «первыми».
  • загружать отсортированное слово в дерево trie, используя отсортированные символы, добавляя ссылку на исходное слово в список слов, хранящихся в каждом пройденном узле

Поиск:

  • сортировать входную строку так же, как инициализация для исходных строк
  • следуйте исходной строке, используя символы, в конечном узле возвращайте все слова, на которые есть ссылки
16.11.2012
  • Стоит добавить, что вам не обязательно СОРТИРОВАТЬ символы, если диапазон возможных значений символа довольно ограничен: вы можете просто подсчитать, сколько встречается каждого из них. Тогда ваш ключ может быть объектом, содержащим эти счетчики, или просто надежным хэшем счетчиков, соединенных по порядку. Отчасти из-за такого рода проблем я говорю в другом комментарии, что для оптимизации времени вам действительно нужно больше информации о том, как обычно выглядят входные данные. 17.11.2012
  • @NeilCoffey Я не согласен, это нужно отсортировать. см. отредактированный ответ - я улучшил (исправил) алгоритм. Сейчас качает :) 17.11.2012
  • Ах, хорошо, если вы используете trie, а не плоскую хеш-карту, тогда да, эффективно. (Потенциально узлы дерева могут быть счетчиками символов, но в этот момент я думаю, что вы можете также использовать метод, который я упоминаю, с плоской картой.) 17.11.2012
  • Я бы хотел, чтобы это было закодировано и протестировано, потому что мне кажется, что часть грубой силы перенесена только из прямого цикла в метод Trie.add(). Я считаю, что как только Trie обнаружил родительский узел для String, у вас уже есть решение, поэтому держать объекты рядом и перемещаться по дереву — пустая трата усилий. Но, возможно, я не понимаю эту идею, поэтому мне интересно, может ли кто-нибудь запрограммировать этот подход. 17.11.2012
  • @Raffaele на самом деле я бы хотел написать это для развлечения. чуть позже сделаю, сейчас занят 17.11.2012
  • @Bohemian, это было бы очень интересно :) Я разместил первоначальную суть онлайн. Надеюсь, вам будет полезно реализовать свой алгоритм. 17.11.2012

    • 2

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

    В этом случае вы можете выполнить начальный проход по 10000 строк и построить сопоставление каждого из уникальных символов, присутствующих в 10000, с их индексом (скорее, набором их индексов). Таким образом, вы можете задать сопоставлению вопрос, какие наборы содержат символ «x»? Назовите это отображение M> (порядок: O(nm), когда n — количество строк, а m — их максимальная длина)

    Чтобы снова оптимизировать время, вы можете сократить входную строку stdin до уникальных символов и поместить их в очередь, Q. (порядок O (p), p - длина входной строки)

    Начните новый непересекающийся набор, скажем, S. Затем пусть S = Q.extractNextItem.

    Теперь вы можете просмотреть остальные уникальные символы и найти наборы, содержащие их все.

    Пока (Q не пусто) (циклы O (p)) {

    S = S пересекает Q.extractNextItem (близко к O (1) в зависимости от вашей реализации непересекающихся множеств)

    }

    вуаля, верните С.

    Общее время: O(mn + p + p*1) = O(mn + p)

    (Все еще рано утром здесь, я надеюсь, что анализ времени был правильным)

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

    • 3

    Как говорит Богемиан, трие-дерево — это, безусловно, правильный путь!

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

    16.11.2012
    Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..