Interview question

[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 или нет. Все.

[АццкоМото]

Борискин, ты бредишь. Или в лучшем случае "понимаю, но сказать не могу".

Я сдаюсь

[Boriskin]

Аминь.

[АццкоМото]

Но таки интересно, если кто-то понял мысль и может пересказать на человечьем языке

[Larsonsager]

Но таки интересно, если кто-то понял мысль и может пересказать на человечьем языке

Возможно, Борискин рассматривает вариант, что 30 миллиардов телефонов не уникальны. А номера десятизначные. Тогда предлагается использовать битовый массив.

Правда, мне кажется, в таком случае еще экономнее было бы держать массив незатронутых номеров. При равномерном распределении вероятности подходящих номеров вероятность каждого 10-значного номера быть задействованным - 95%. То есть 1 - (1 - 1 / (10^10))^(3*10^10).

Получается, "неправильных" номеров будет лишь 1/20 часть от числа всех возможных (полмиллиарда). При кодировании Голомбом на число будет уходить бита по три. Ну, может, по 5 бит, с учетом накладных расходов: хранить не весь список целиком, а относительно небольшими группами, для скорости. Получается, такая структура данных будет раза в четыре экономнее битового массива.

[АццкоМото]

Но таки интересно, если кто-то понял мысль и может пересказать на человечьем языке

Возможно, Борискин рассматривает вариант, что 30 миллиардов телефонов не уникальны. А номера десятизначные. Тогда предлагается использовать битовый массив.

Т.е. в среднем 30 китайцев на один телефонный номер? Чюдны дела твои...

[major Major Major Major]

Но таки интересно, если кто-то понял мысль и может пересказать на человечьем языке

Возможно, Борискин рассматривает вариант, что 30 миллиардов телефонов не уникальны. А номера десятизначные. Тогда предлагается использовать битовый массив.

Т.е. в среднем 30 китайцев на один телефонный номер? Чюдны дела твои...

Я все больше удивляюсь. На работе что ли загоняли?
Смотри, у нас есть номера от 0 до 9. Можно хранить их списком, а можно флаги в битовом массиве. Скажем, есть номер 1 и 8. Наш битовый массив будет выглядеть как

[0100000010]

Теперь возьмем 30 миллиардов. Длина массива - 30 миллиардов битов. Сам подсчитаешь, сколько это в байтах?

[Boriskin]

Larsonsager
На одного китайца может приходиться и не 1 номер, а больше.

И мне не очень понятно, зачем что-то кодировать (даже не учитывая возможные worst case scenario), когда при простом битовом массиве на хранение одного номера уходит один бит, а ключом (коим является сам номер) является позиция этого бита в массиве ака сдвиг. Ака номер 0-123-456-789 - значит это бит в позиции 123456789, номер 9-876-543-210 - бит в позиции 9876543210.
Массив заполняется за один проход по оригинальному файлу и дальнейшая проверка не требует никаких дополнительных телодвижений, надо только сдвинуться на сколько-то миллионов (или миллиардов) бит и все.

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

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

[АццкоМото]

Но таки интересно, если кто-то понял мысль и может пересказать на человечьем языке

Возможно, Борискин рассматривает вариант, что 30 миллиардов телефонов не уникальны. А номера десятизначные. Тогда предлагается использовать битовый массив.

Т.е. в среднем 30 китайцев на один телефонный номер? Чюдны дела твои...

Я все больше удивляюсь. На работе что ли загоняли?
Смотри, у нас есть номера от 0 до 9. Можно хранить их списком, а можно флаги в битовом массиве. Скажем, есть номер 1 и 8. Наш битовый массив будет выглядеть как

[0100000010]

Теперь возьмем 30 миллиардов. Длина массива - 30 миллиардов битов. Сам подсчитаешь, сколько это в байтах?

Ой, ну это-то можно не объяснять. Но теперь процитируем Борискина:

Захерачиваем bit array длиной 10.000.000.000 бит

и вот эта ловкая оптимизация в три раза у меня никак не укладывается

[АццкоМото]

Кстати, если развить тему. Если в США на 300 миллионов рыл 10-значные номера, то на 30 ярдов китайцев могут быть и 12-значные. Сколько это там в битиках, 125ГБ чоле? Ох и матерый же нам контупер понадобится

[major Major Major Major]

Теперь возьмем 30 миллиардов. Длина массива - 30 миллиардов битов. Сам подсчитаешь, сколько это в байтах?

Ой, ну это-то можно не объяснять. Но теперь процитируем Борискина:

Захерачиваем bit array длиной 10.000.000.000 бит

и вот эта ловкая оптимизация в три раза у меня никак не укладывается

Я неправильно цифру то написал. длина массива это не количество китайцев а максимальный номер. 10 цифрованные номера это и есть 10 миллиардов. Если 11 то 100. У китайцев согласно википедии 10 значные обычные (с кодом уже) или без кода но на 1 начинающиеся 11 значные сотовые (то есть по факту таки 10 значные). Поскольку в задаче не задавалась длина то используем реально существующие ограничения. В этом случае храним два массива, но все равно это мало, на обычном десктопе будет летать.

[АццкоМото]

Я неправильно цифру то написал. длина массива это не количество китайцев а максимальный номер. 10 цифрованные номера это и есть 10 миллиардов. Если 11 то 100.

Ну можно не разжевывать эту банальщину.

У китайцев согласно википедии 10 значные обычные (с кодом уже)

Да что ж вас всех в википедию-то тянет! По условию задачи китайцев 30 миллиардов. Сверьтесь с википедией, ага.

[major Major Major Major]

У китайцев согласно википедии 10 значные обычные (с кодом уже)

Да что ж вас всех в википедию-то тянет! По условию задачи китайцев 30 миллиардов. Сверьтесь с википедией, ага.

Других условий у меня для вас нет (c)

[ALV00]

Long distance в Китае 11-значный, международный 12-ти

xxx xxxx Calls within the same area code
0yyy xxx xxxx Calls from other areas within China
+86 yyy xxx xxxx Calls from outside China

[ystar]

дел дубль

[ystar]

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

но ведь никто не запрещает каждому китайцу иметь по 10, 100, 200, 1^100000 симок (на случай, если кто-то думает, что у него комп с 8 ядрами и 64 гигами оперативы все быстро обратает, мы увеличим количество китайцев до 100 трлн и у каждого китайцев будет 10 трлн симок и каждый номер будет содержать 1 млн цифр).
Задача состоит в построении системы. Что подразумевает, что кроме поиска, возможно, в будущем потребуется менять данные, либо какие-то интеграционные задачи с другими сервисами могут появиться. Про это не мешало бы подумать.

[АццкоМото]

Я собственно на это и намекал, но остался в одиночестве

[Boriskin]

Задача состоит в построении системы. Что подразумевает, что кроме поиска, возможно, в будущем потребуется менять данные, либо какие-то интеграционные задачи с другими сервисами могут появиться. Про это не мешало бы подумать.

Добавился номер - подняли бит по соответствующему сдвигу, удалился номер - сбросили бит...
Для увлеченных сохранением памяти можно придумать массу способов этот битовый массив сжать, например - пройтись по этим самым вышеупомянутым сегментам какой нить lzma, чтобы иметь очень быструю декомпрессию.

[АццкоМото]

Задача состоит в построении системы. Что подразумевает, что кроме поиска, возможно, в будущем потребуется менять данные, либо какие-то интеграционные задачи с другими сервисами могут появиться. Про это не мешало бы подумать.

Добавился номер - подняли бит по соответствующему сдвигу, удалился номер - сбросили бит...
Для увлеченных сохранением памяти можно придумать массу способов этот битовый массив сжать, например - пройтись по этим самым вышеупомянутым сегментам какой нить lzma, чтобы иметь очень быструю декомпрессию.

Борискин, скажи, а ты начало поста специально не стал цитировать?

но ведь никто не запрещает каждому китайцу иметь по 10, 100, 200, 1^100000 симок (на случай, если кто-то думает, что у него комп с 8 ядрами и 64 гигами оперативы все быстро обратает, мы увеличим количество китайцев до 100 трлн и у каждого китайцев будет 10 трлн симок и каждый номер будет содержать 1 млн цифр).

Ну и вообще успехов в lzma-компресснутом битовом массиве быстро найти нужный битик. И еще больше успехов его поменять

[Boriskin]

Мотто, читай сильно выше. Количество китайцев никого ниибет, ибо важен только формат телефонного номера, бо только он и ограничивает кол-во вариантов номеров сверху.

Битовый массив на 125гиг для 12тизначного номера делается на коленке на простом лаптопе с одним терабайтным SSD. И если кто не понял идею про сегментацию хранения данных и то, что номера в разных диапазонах можно хранить и обновлять совершенно независимо друг от друга - это не ко мне, это к нейрохирургу.

[АццкоМото]

Мотто, читай сильно выше. Количество китайцев никого ниибет, ибо важен только формат телефонного номера, бо только он и ограничивает кол-во вариантов номеров сверху.

Для особо одаренных процитирую еще раз:

но ведь никто не запрещает каждому китайцу иметь по 10, 100, 200, 1^100000 симок (на случай, если кто-то думает, что у него комп с 8 ядрами и 64 гигами оперативы все быстро обратает, мы увеличим количество китайцев до 100 трлн и у каждого китайцев будет 10 трлн симок и каждый номер будет содержать 1 млн цифр).

ты все еще будешь нести пургу про 10 или 12 значный номер? Научись читать сначала, а то дорогу до нейрохирурга не найдешь

[Ann4Ann]

хорошее решение у Boriskin. по мне так даже компрессия битового массива - некое усложнение. пока не понятно нужное или нет. на domain всегда надо смотреть. в задаче телефонные номера а не произвольные числа... с произвольными - решение другое, а с номерами самое оно. как часто меняется формат телефонных номеров, и с какой скоростью дешевеет и становится доступнее память?
вначале чтоб 2 умножить на 2 хадуп кластер поднимаем, а потом, стартап приказывает долго жить... . последняя фраза ни в коем случае не ответ ни на чьи комментарии, просто наблюдение за стартапами возбуждающимися при словах "биг дата".

[Wolverene]

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

Похожая задача:
Игра домино, надо сохранить информацию о костях, выложенных на стол. Чтобы можно было сказать - была такая комбинация раньше или нет. Сделать функцию для быстрого поиска и проверки:

boolean check(int[] set)

[oshibka_residenta]

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

Похожая задача:
Игра домино, надо сохранить информацию о костях, выложенных на стол. Чтобы можно было сказать - была такая комбинация раньше или нет. Сделать функцию для быстрого поиска и проверки:

boolean check(int[] set)

Непонятно что ожидает интервьюер. Если это гугло-фейсбук, то кроме хранение в битиках может ожидаться решение с разнесением данных по нодам, а потом map/reduce. Просто битики - не масштабируется ( если китайцев очень много )
Ну и с домино, 28! - должно быть охренеть сколько битиков. Без hashmap вряд ли обойтись

[АццкоМото]

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

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