Последовательные целые числа дают идеальный выбор для хэш-карты, но она имеет только одну проблему, так как не имеет многопоточного доступа по умолчанию. Также, поскольку Amazon был упомянут в вашем вопросе, я могу подумать, что вам необходимо принять во внимание проблемы параллелизма и ограничения ОЗУ.
Что вы можете сделать в ответе на такой вопрос, это объяснить, что с
вам не разрешено использовать любые встроенные схемы хранения данных, все, что вы можете сделать, это «эмулировать» одну.
Итак, допустим, у вас есть M = 10 ^ 20 товаров с их номерами и описаниями.
Вы можете разбить этот набор на группы из N подмножеств.
Затем вы можете организовать M / N контейнеры, которые значительно сократили количество элементов. Использование этой идеи рекурсивно даст вам возможность хранить весь набор в контейнерах с таким свойством, что доступ к ним будет иметь приемлемый уровень производительности.
Чтобы проиллюстрировать эту идею, рассмотрим меньший пример только из 20 элементов.
Я хотел бы, чтобы вы представили файловую систему с каталогами «1», «2», «3», «4».
В каждом каталоге вы сохраняете описания продуктов в виде файлов следующим образом:
folder 1: files 1 to 5
folder 2: files 6 to 10
...
folder 4: files 16 to 20
Тогда для поиска файла потребуется всего два шага.
Сначала вы ищете нужную папку, разделив 20/5 (ваш M / N).
Затем вы используете указанный идентификатор, чтобы прочитать описание продукта, хранящееся в файле.
Это просто очень грубое описание, однако идея очень интуитивна.
Так что, возможно, именно это хотел услышать ваш интервьюер.
Что касается меня, когда я сталкиваюсь с такими вопросами на собеседовании, даже если мне не удается правильно ответить на вопрос (что является наихудшим случаем :)), я всегда стараюсь получить правильный ответ от интервьюера.