Interview question

[Boriskin]

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

Что мешает разрезать охрененный битмассив на 1000 или 1000000 кусков, держать каждый кусок на отдельном сервере, а на входе иметь простую вычислялку, которая по заданному сколькитозначному номеру определяет сегмент, в котором этот номер находится и отправяет эапрос на соответствующий сервак? Причем что для проверки, что для добавки, что для удаления номера?

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

[Mod.: Хамство, грубость. 3 дня. ->10/09/2016]

[АццкоМото]

Что мешает разрезать охрененный битмассив на 1000 или 1000000 кусков, держать каждый кусок на отдельном сервере, а на входе иметь простую вычислялку, которая по заданному сколькитозначному номеру определяет сегмент, в котором этот номер находится и отправяет эапрос на соответствующий сервак? Причем что для проверки, что для добавки, что для удаления номера?

Ну если у тебя есть 1000000 серверов - то вперде

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

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

[Boriskin]

хорошее решение у Boriskin. по мне так даже компрессия битового массива - некое усложнение. пока не понятно нужное или нет. на domain всегда надо смотреть.

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

[Ann4Ann]

Разряженные матрицы при использовании методов конечных элементов - отличный пример такого рода.

yep. sparse matrix - наше все. но на интервью я б выдала простое решение (Ваше), уточнила бы про план разбиения по кластерам, если очень много, и дальше б можно было поговорить про всякие оптимизации.
влоб начинать с оптимизированного решения я б не стала просто чтоб за мыслью следили. интервьюеты тоже всякие попадаются .. не то чтоб они все до одного понимают то о чем спрашивают.

[Larsonsager]

хорошее решение у Boriskin. по мне так даже компрессия битового массива - некое усложнение. пока не понятно нужное или нет. на domain всегда надо смотреть.

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

Достаточно не 1 из 50, а примерно 1 из 5-7, чтобы энтропийное кодирование сделало хранение более эффективным, чем битовый массив. И блум в таком случае будет очень в тему (разумеется, если 49 запросов из 50 тоже будут неправильными. Если большинство запросов должны дать положительный результат, блум бесполезен).

[Boriskin]

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

[oshibka_residenta]

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

Если мы про домино, где число вариантов 28!, то битовый массив _не_ является решением, даже если у вас 1,000,000 серверов. Да хоть 1,000,000,000 серверов. Почему? Потому что, как я уже сказал, 28! - это охренительно много, примерно 10^29

[Boriskin]

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

Если мы про домино, где число вариантов 28!, то битовый массив _не_ является решением, даже если у вас 1,000,000 серверов. Да хоть 1,000,000,000 серверов. Почему? Потому что, как я уже сказал, 28! - это охренительно много, примерно 10^29

Насколько я знаю, в игре домино есть четкие правила, что с чем состыковывается при выкладывании, так что при чем тут 28! мне не понятно.
Как решить задачу с домино - надо думать.

[Larsonsager]

Откуда в домино 28! ?

Там вариантов меньше чем
28 * 6 * 6 * ... * 6 * 6 * 5 * 4 * 3 * 2 * 1, где шестерок всего 22 штуки.
Итого 5 * 10^20. Для хранения комбинации нужно 69 бит. Битовый массив тут, конечно, не подойдет. А что подойдет - сильно зависит от того, сколько комбинаций у нас уже встречалось. На первую тысячу лет игры, вероятно, хватит дерева в памяти одного компьютера.

[oshibka_residenta]

Откуда в домино 28! ?

Там вариантов меньше чем
28 * 6 * 6 * ... * 6 * 6 * 5 * 4 * 3 * 2 * 1, где шестерок всего 22 штуки.
Итого 5 * 10^20. Для хранения комбинации нужно 69 бит. Битовый массив тут, конечно, не подойдет. А что подойдет - сильно зависит от того, сколько комбинаций у нас уже встречалось. На первую тысячу лет игры, вероятно, хватит дерева в памяти одного компьютера.

Ну да, с 28! - лоханулся. Но то, что битовый массив для такого не подходит не меняется.

[Wolverene]

Думал что домино решается проще, но поразбирал ее c другом, итог:
- Каждую костяшку можно закодировать числом. Всего их 28 штук. Тогда сет можно закодировать битами 0..27
- Чисто сетов (без сохранения порядка костяшек) - это 2^27, число меньше 2^32. Т.е. индекс сета можно представить как int
- Берем битсет размером в 2^27. Влезет в память? Ну 2 это 2^24 байт, 1Мб это 2^10, значит 1Гб это 2^20, значит 2^24 это 16Гб. Влезет в память на более-менее нормальном компе. Ну, конечно, накладные расходы и т.п. - но получается реально не надо базы данных или что-то еще привлекать. И скорость вставки / поиска O(1).

А вот вариант с поддержанием порядка костяшек будет посложнее:
- Кодируем сет как piece1 + 29*piece2 + 29^2*piece3 + ... + 29^(n-1)*pieceN. Получим число меньше чем 2^5^28 = 2^33.
- Храним бит сет в 2^30 байт - будет 2^6 * 2^24 bytes = 64 * 16Gb. Используем распределенную систему, биты 27-33 будут указывать на индекс машины, а оставшиеся на номер бита в битсете.

[Larsonsager]

Непонятно.

1. Если вы знаете piece1 (0..27), дальше вам не нужно хранить полную piece2. Потому что первое число на костяшке определяется предыдущей костяшкой. От всей piece2 нам нужно только число от 0 до 6, причем на самом деле это число не может совпадать с тем, что было на предыдущей костяшке. Так что хранить придется только число от 0 до 5, но надо делать поправку на предыдущую костяшку. Получается как раз 2^69.

А у вас в арифметике где-то ошибка. 28^(n-1)*pieceN - это уже 28^27, то есть примерно 2^130. Возможно, вы это и имели в виду, когда писали 2^5^28: скобок нет, так что непонятно. Если вы имели в виду (2^5)^28, то всё правильно, но это не 2^33, а 2^140.
2^(5^28) еще гораздо больше

2. Даже допустим, что ошибки не было бы, и там действительно было бы 2^33. Вам правда кажется, что битсет в гигантских файлах на 2^7=128 машинах - это прекрасный вариант для хранения - ну, от силы миллиарда цепочек из 28 чисел каждая?

[ALV00]

Только следует учесть:
не все комбинации являются разрешенными (кстати, сколько их?)
позиция может быть разветвленной, т.е. надо кодировать графы

[Wolverene]

Непонятно.
1. Если вы знаете piece1 (0..27), дальше вам не нужно хранить полную piece2. Потому что первое число на костяшке определяется предыдущей костяшкой. От всей piece2 нам нужно только число от 0 до 6, причем на самом деле это число не может совпадать с тем, что было на предыдущей костяшке. Так что хранить придется только число от 0 до 5, но надо делать поправку на предыдущую костяшку. Получается как раз 2^69.

Не факт что костяшки связаны между собой. Это ведь может быть как и состояние игры, так и набор костяшек у игрока.

А у вас в арифметике где-то ошибка. 28^(n-1)*pieceN - это уже 28^27, то есть примерно 2^130. Возможно, вы это и имели в виду, когда писали 2^5^28: скобок нет, так что непонятно. Если вы имели в виду (2^5)^28, то всё правильно, но это не 2^33, а 2^140.
2^(5^28) еще гораздо больше

Ага, это накосячил. А я думаю - почему для варианта с сохранением порядка у нас число не так сильно меняется? Ну да, 2^130, подход смысла не имеет.

2. Даже допустим, что ошибки не было бы, и там действительно было бы 2^33. Вам правда кажется, что битсет в гигантских файлах на 2^7=128 машинах - это прекрасный вариант для хранения - ну, от силы миллиарда цепочек из 28 чисел каждая?

А тут вопрос оптимальности. Гигантские файлы? Зачем? 16Гб можно и в памяти хранить. Но для перестановок такой вариант уже не подойдет никак - надо другую структуру - смотреть в зависимости от размера входных данных.

[АццкоМото]

Я очень плохо помню правила домино, но чота мне кажется, что нужно тупо граф строить. Правда, тут много нюансов по части уточнить условия задачи.

[Boriskin]

Думал что домино решается проще, но поразбирал ее c другом, итог:

Я так думаю, что битовый массив здесь будет не эффективно, имхо, должно подходить чтото вроде дерева префиксов (ака trie) навроде того, что используется когда Гугель показывает популярные продолжения к набранному в поиске.

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