Interview question

[Larsonsager]

Чота мутно как-то. Непонятно, что за список неподходящих номеров. Типа для упрощения. Если подходящие - от 001 до 101 сплошняком, то неподходящие — от 102 до 999 что ли? Ничотаг оверхед. Хуже того, а как этот список создать? Ну и самое поганое — worst case scenario. Если хоть с какой-то вероятностью придется перебирать в лоб.... Фигня какая-то

заявлено, что 3*10^10 номеров подходят. Есть разумные основания ожидать, что номера там 11-значные (на самом деле, Википедия утверждает, что в целом так оно и есть, но не всегда). Это значит, что неподходящих номеров всего вдвое больше, чем подходящих.

Пусть так. Как вы найдете список неподходящих номеров? Не замечаете, что эта задача опасно близка к исходной?

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

[Larsonsager]

Хотя что-то я ступил. Если мы уверены, что номера ограничиваются 11-значными, то гораздо выгоднее будет просто хранить их в виде битового массива. 12 гигабайт. Влезет в память, быстрая проверка, гарантированный результат.

[ystar]

Хотя что-то я ступил. Если мы уверены, что номера ограничиваются 11-значными, то гораздо выгоднее будет просто хранить их в виде битового массива. 12 гигабайт. Влезет в память, быстрая проверка, гарантированный результат.

И так вдруг китайцев стало 3*10^1000 и номера стали 50 значными. и процессор один и оперативы только 2 гигабайта. а добавить 2 гигабайта оперативы стоит 2 трл баксов.
в общем я про то, что не стоит привязываться, к тому, что номера 11 значные или 7 значные. надо решать поставленную задачу.

[M. Ridcully]

И так вдруг китайцев стало 3*10^1000 и номера стали 50 значными. и процессор один и оперативы только 2 гигабайта. а добавить 2 гигабайта оперативы стоит 2 трл баксов.

Ну тогда как писал выше - B tree, или что-то подобное, HDD friendly, так сказать...

[Larsonsager]

задача была вами поставлена чётко: это номера телефонов, и китайцев было 3*10^10. В совсем общем случае задача, разумеется, никак не решается, необходимо делать какие-то разумные допущения.

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

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

Если подходящие номера более или менее равномерно распределены по какому-то диапазону (скажем, от 1*10^10 до 1*10^11), то самый лучший хэш для таких номеров - это они сами. Если в целом это так, но есть малый процент выбивающихся номеров (15-значных, например) - то имеет смысл обрабатывать их отдельно. Если же среди номеров многие имеют гораздо больше разрядов, чем нужно, то надо подобрать другую хэш-функцию.

Делать же общее решение на все случаи жизни бесполезно. Самое общее решение будет тупо отсортировать массив, разбить его на куски по какому-то хэшу, сжать эти куски и положить на диск. Вряд ли это то, что заинтересует кого-то на собеседовании. И вряд ли такая общая задача практична.

[M. Ridcully]

Самое общее решение будет тупо отсортировать массив, разбить его на куски по какому-то хэшу, сжать эти куски и положить на диск. Вряд ли это то, что заинтересует кого-то на собеседовании. И вряд ли такая общая задача практична.

Ну почему-же? Вполне себе решение.
Правда, тоже для более частного случая - очевидно, что _не_ для случая, когда номера часто добавляются / удаляются.

Но я согласен, что HW ограничения и типичный сценарий использования нужен, чтобы задача какой-то смысл имела.

[ystar]

задача была вами поставлена чётко: это номера телефонов, и китайцев было 3*10^10. В совсем общем случае задача, разумеется, никак не решается, необходимо делать какие-то разумные допущения.

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

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

Если подходящие номера более или менее равномерно распределены по какому-то диапазону (скажем, от 1*10^10 до 1*10^11), то самый лучший хэш для таких номеров - это они сами. Если в целом это так, но есть малый процент выбивающихся номеров (15-значных, например) - то имеет смысл обрабатывать их отдельно. Если же среди номеров многие имеют гораздо больше разрядов, чем нужно, то надо подобрать другую хэш-функцию.

Делать же общее решение на все случаи жизни бесполезно. Самое общее решение будет тупо отсортировать массив, разбить его на куски по какому-то хэшу, сжать эти куски и положить на диск. Вряд ли это то, что заинтересует кого-то на собеседовании. И вряд ли такая общая задача практична.

Задачка была построить систему при такой входящих условиях.

[major Major Major Major]

задача была вами поставлена чётко: это номера телефонов, и китайцев было 3*10^10. В совсем общем случае задача, разумеется, никак не решается, необходимо делать какие-то разумные допущения.

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе 300 гигов. Взводится 9 простеньких машинок по 64 гига памяти (с запасом), на них взводится монгоdb с шардингом по первой цифре (или 10 если есть номера на 0).
Все в памяти, реально будет летать. Если распределение номеров очень уж неравное то шардинг можно сделать и более хитрый, принцип тот же.
Надо конечно все мерять на практике, ибо компрессию никто не отменял и индекс по размерам будет меньше чем суммарные данные

[АццкоМото]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе

Это что-то в районе фантастики

[fruit6]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе

Это что-то в районе фантастики

кто их знает, может у китайцев один номер на деревню, а номер надо иметь каждому.

нормальный вопрос кстати. его можно упростить до "какое число я загадал".

[major Major Major Major]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе

Это что-то в районе фантастики

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

[Boriskin]

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

Эта память как бы ужа дана. А вообще - для перенумерации 30.000.000.000 номеров понадобится битовый массив длинной 35 бит, если предположить, что номер 11тизначный - то 37 бит.

[АццкоМото]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе

Это что-то в районе фантастики

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

При чем тут вообще 1024? Номера телефонов в десятичной системе. 3 * 10^10 это 11 знаков. Причем в номере их может быть и больше, ибо 30000000000 это их количество, а из-за всяких эриа кодов они могут быть и 12 и 13 символов. Или даже больше.

[АццкоМото]

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

Эта память как бы ужа дана. А вообще - для перенумерации 30.000.000.000 номеров понадобится битовый массив длинной 35 бит, если предположить, что номер 11тизначный - то 37 бит.

Вот так вот 300 мульярдов записей упаковали в 35-37 бит? Да вы монстр!

[АццкоМото]

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

Эта память как бы ужа дана. А вообще - для перенумерации 30.000.000.000 номеров понадобится битовый массив длинной 35 бит, если предположить, что номер 11тизначный - то 37 бит.

Да и даже если не придираться и понимать вас как "битовый массив из тридцать мульярдов раз по 35 бит", это невозможно.

[major Major Major Major]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе

Это что-то в районе фантастики

Хм, 3*10^10 это 30000000000, * 10 / 1024 / 1024 / 1024 = ~280
Где то нолик пропустил? Где?

При чем тут вообще 1024? Номера телефонов в десятичной системе. 3 * 10^10 это 11 знаков. Причем в номере их может быть и больше, ибо 30000000000 это их количество, а из-за всяких эриа кодов они могут быть и 12 и 13 символов. Или даже больше.

Еще раз, 3*10^10 это 30000000000, 11 знаков. Каждый номер это 10 знаков (Поглядел в вики, обычные номера в Китае с кодами 10 цифр, мобильные 11 но начинаются строго на 1. То есть по факту 10, можно хранить отдельно), поэтому * 10. это столько у нас байтов всего если хранить как строку. Можно хранить как int64, будет 8 редко 9. делим на кило,мега и гига получаем общий обьем данный в 280 гигабайт. Не компрессированных. Индекс по ним реально будет меньше. На 10 скромных машинах все будет в памяти. Может ради интереса на неделе сгенерю одну десятую обьема и посмотрю реальный размер.

[АццкоМото]

1, я не понимаю ловкого перехода от 11 знаков к 10
2. Википедия тут вообще не причем. Это же гипотетическая задача.
3. Индекс еще надо построить
4. Решение в лоб, неинтересно
5. Построить тот индекс — все равно, что тупо отсортировать данные и искать бинарными поиском
6. Это может быть оффтоп, но вроде в оригинале задачи уточнялось про ограниченную память и относительно медленный сторидж

[АццкоМото]

Да и вообще, в Википедии написано, что китайцев не 30 миллиардов

[mskmel]

Ну если интересует практическая система, то 3*10^10 при условии 10 значного номера (код + номер) это что то в районе 300 гигов. Взводится 9 простеньких машинок по 64 гига памяти (с запасом), на них взводится монгоdb с шардингом по первой цифре (или 10 если есть номера на 0).

зачем так сложно? Монго, шардинг...

sqllite, правда на в 10раз меньшем объеме (лень было ждать ), что вобщем то рядом:

Code: Select all

sqlite> create table n(n bigint primary key);
 
sqlite> insert into n with recursive q(n) as (VALUES(123467890) union all SELECT n+1 FROM q WHERE n < 3123456789) select * from q;

sqlite> select count(*) from n;
2,999,988,900
Run Time: real 218.776 user 3.144268 sys 46.427018

sqlite>  EXPLAIN QUERY PLAN select count(*) from n where n=12399789;;
0|0|0|SEARCH TABLE n USING COVERING INDEX sqlite_autoindex_n_1 (n=?)

sqlite> select n from n where n=3123456766;
3123456766
Run Time: real 0.005 user 0.000102 sys 0.000428

sqlite> select n from n where n=2123456766;
2123456766
Run Time: real 0.002 user 0.000082 sys 0.000204

[АццкоМото]

Блин, какие все простые. Данные в текстовом файле. Иммютабл.

Кто бы стал задавать этот вопрос, если бы такие тривиальные ответы проходили

[mskmel]

Блин, какие все простые. Данные в текстовом файле. Иммютабл.

В исходном условии не написано что они сортированные. Если уж надо сортировать отдельно, то открывается простор для самодеятельности.

Кто бы стал задавать этот вопрос, если бы такие тривиальные ответы проходили

"— Пришивайте подворотничок к воротничку.
— А мы не умеем.
— Никто не умеет… Дело не в умении, не в желании, и вообще ни в чём. Дело в самом пришивании подворотничка."

Интервьирующий не хочет бинарный поиск, он хочет то, что в чем себя убедил, как в правильном ответе

Варианты:
1. ожидает быстрого и легко поддерживаемого решения
- так он теперь будет сидеть 3 дня программировать бинарный поиск (по csv файлу с переменной длинной записи) вместо того чтобы загрузить в RDBMS и с ней работать
- запрограммирует - свалит, найди мне такого же гения, который его кусок кода поддерживать будет
2. ожидает от соискателя дискуссии по поводу задачи, а не сразу хвататься за клавиатуру

[fruit6]

дискуссиями в ойти занимаются: Developer Advocate, Technology Evangelist, Enterprise Architect.
остальные молча программируют бинарные поиски, базы, и что скажут.

[Boriskin]

Эта память как бы ужа дана. А вообще - для перенумерации 30.000.000.000 номеров понадобится битовый массив длинной 35 бит, если предположить, что номер 11тизначный - то 37 бит.

Да и даже если не придираться и понимать вас как "битовый массив из тридцать мульярдов раз по 35 бит", это невозможно.

Предполагаем, что номер 10тизначный, то есть любой номер представляется как нечто между 0-000-000-000 и 9-999-999-999.
Каждый номер можно закодировать числом, представляющим его место в последовательности от 0 до 9.999.999.999, и это число и будет иметь длину 35 бит.

[АццкоМото]

Эта память как бы ужа дана. А вообще - для перенумерации 30.000.000.000 номеров понадобится битовый массив длинной 35 бит, если предположить, что номер 11тизначный - то 37 бит.

Да и даже если не придираться и понимать вас как "битовый массив из тридцать мульярдов раз по 35 бит", это невозможно.

Предполагаем, что номер 10тизначный, то есть любой номер представляется как нечто между 0-000-000-000 и 9-999-999-999.
Каждый номер можно закодировать числом, представляющим его место в последовательности от 0 до 9.999.999.999, и это число и будет иметь длину 35 бит.

Да нельзя 3*10^10 уложить в 10 десятичных знаков, сколько можно! Давайте вообще предположим, что номера двухзначные, ага, еще легче будет, ура, 7 бит хватит!!! Гениально, блдж

[Boriskin]

Да нельзя 3*10^10 уложить в 10 десятичных знаков, сколько можно! Давайте вообще предположим, что номера двухзначные, ага, еще легче будет, ура, 7 бит хватит!!! Гениально, блдж

Блин, Мотто, ну ты же подкованный гондурасец, намекаешь тебе намекаешь...

Пусть номера 10тизначные, то бишь от 0-000-000-000 до 9-999-999-999. Общее количество - 10.000.000.000
Захерачиваем bit array длиной 10.000.000.000 бит (итого ~ 1.25 гига), делаем один проход по исходному файлу, читаем записи типа
СамСуньХуй - номер (N) 3-141-592-653. В битном массиве взводим бит в полиции N в единичку и продолжаем так же читать до конца файла.
Прочитали - забыли нах про файл.

И когда на входе приходит номер (K) 2-718-281-828 - просто смотрим, взведен ли бит в массиве в позиции K или нет. Все.