#algorithm #search
#алгоритм #Поиск
Вопрос:
Недавно мне задали вопрос в техническом интервью, который звучит примерно так.
Вам нужно найти определенную книгу в библиотеке, и в тот момент, когда вы зашли внутрь, вы увидели, что все книги разбросаны по всей библиотеке, то есть книги не расположены организованно внутри библиотеки. Как вы будете искать эту конкретную книгу? О книге нет никаких спецификаций, за исключением того, что вы знаете Name of the Book .
Я знаю, что это связано с некоторым алгоритмом поиска, но какой алгоритм можно использовать для поиска книги в этом случае?
Комментарии:
1. Ну, если нет системы, вам придется просматривать каждую книгу. Я предполагаю, что хитрость заключается в разработке системы, которая гарантирует, что в конечном итоге вы изучите каждую книгу и не будете просматривать одну и ту же книгу дважды.
2. @aix — Выбросьте книгу из окна, если она не является нужной: P
3. @Petar Minchev: Хорошее предложение. Может быть сложно, если вы находитесь в подвале, хотя 🙂
Ответ №1:
Выполните линейный поиск, начиная с первой книги и просматривая каждую книгу, пока не наткнетесь на первое вхождение нужной книги (конечно, может быть несколько копий).
Если вы являетесь единственным пользователем поиска и книг много, то сортировка их перед поиском книги покажется крайне неэффективной тратой времени — если только вы не собираетесь искать больше книг в будущем.
Вы всегда можете попросить библиотекаря сказать вам, где находится книга в их системе, или вы могли бы привлечь друзей, чтобы они помогли вам выполнить поиск, разделить проблему и работать параллельно.
РЕДАКТИРОВАТЬ Существует также квантовый алгоритм, называемый алгоритмом Гроверса (если вы занимаетесь подобными вещами), который быстрее, чем линейный поиск по несортированной базе данных, но, честно говоря, я не слишком много о нем знаю.
Комментарии:
1. Если вам нужны решения «из реальной жизни», я бы также погуглил название, чтобы узнать цвет обложки книги. Можно было бы немного сузить поиск.
Ответ №2:
В этом случае вы либо
- отсортируйте книги и выполните поиск с помощью алгоритма поиска (например, двоичный поиск). Это хороший метод, если вам иногда приходится искать другую книгу
- поиск книги, просмотрев весь список книг, вы можете остановиться, как только найдете ее