Здравствуйте, на собеседовании задали такую задачку (оптимального ответа как потом признались не знают и сами кто проводил собеседование ), сут такая есть некая функция addValue(int64 nValue), которая вызывается много раз (порядка миллиарда) с различными значениям nValue (тоже неизвестно сколько различных может быть 1 может все ), необходимо предложить способ как можно точнее оценить сколько различных значений nValue было передано.
Я предложил несколько способов использовать дерево количество памяти O(n) от количество различных элементов, Хеш не многим лучше, как вариант битовый массив памяти потребуется меньше чем для дерева как минимум в 64 раза (без учета внутреннего устройства дерева), ну и последнее использовать фильтр Блума, но правда в последнем случае число различных элементов может быть меньше чем в реальности.
Возможно есть еще варианты?