Реальные вопросы на собеседовании

Нет.

Нет

Питонщика ответ %)

Я бы оценил.

А что тут думать? Бинарное дерево поиска/бинарный поиск. 50 этаж, 25 или 75 и так далее, деля на пополам

Я бы делал n/2 при каждом шаге, где n — количество этажей, которое ещё не отброшено, и двигался вверх или вниз в зависимости от результата.

Опередил.

тогда можно 2 шара поломать и не определить точно

А если шар ломается на первом этаже?

А что тут думать?

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

Так важнее что будет в среднем, чем то, что в худшем или в лучшем случае.

алгоритм, который точно определяет этаж,

Задавайте только реальные вопросы с собеседования

Почему в байте 8 бит

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

ты сначала скажи в чем твоя «проблематика» :))) в организации просто кеша элементов? кеша пар «ключ-значение»? пары существуют заранее и на них можно ссылки брать или создаются при попадании в кеш? какого типа ключ хоть, или он у тебя вообще произвольный? какого размера кеш, насколько часто кеш обновляется, пару эту надо разрушать при выталкивании из кеша?

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

Так ты в конечном счёте его и определишь.

нет, у тебя шары закончатся

ты сначала скажи в чем твоя «проблематика»

зависит от конкретных условий работы

Многопоток. То, что ты не шаришь, уже ясно. Все твои вопросы абсолютно бессмысленные в контексте задачи.

Многопоток. То, что ты не шаришь, уже ясно.

все кеши расчитаны на многопоток. специальных кешей для «однопотоков» нет. дальше думай

Точняк.

все кеши расчитаны на многопоток

Какая чушь. Товарищ, больше не пиши мне, пожалуйста. Я очень нежный, меня слишком легко затроллить тупостью.

Какая чушь. Товарищъ больше не пиши мне, пожалуйста. Я очень нежный, меня слишком легко затроллить тупостью.

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

Ты непроходимый. Выше два вариата уже было. Забанься, плиз.

давай свое решение таинственной задачи, самых лучших кешей для 64 ядер, пар ключ-значение, неизвестного типа заметим!!!, для совершенно неизвестной стратегии доступа к элементам

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

И ты туда же.

Причём здесь референс, причём здесь бенчи? Тебе сказал нет, ибо задачки на собеседовани не решаются через «импорт збс». Нужно объяснить решение, т.е. ты должен знать реализацию и быть готовым её написать. Либо чот навелосипедить по-быстрому.

Худший случай. Надо на землю аккуратно класть.

А это вопрос к тому, как именно они деформируются при поломке. И на вывод эмпирической формулы у нас может уйти намного больше испытаний. Ну и надо подключать тогда и сопромат, но про него речи не было.

Видимо, всё же придётся сначал сбросить с 50, и в зависимости от результата идти с 1 или 51 вверх с n+1.

вероятность, что шар разобьётся, растёт вместе с этажом, нужно принимать это во внимание

проверяет знаешь ли ты теорию вероятностей и помнишь ли формулу Байеса.

На кого собеседовался? Если на преподавателя матана - то одно дело, если на младшего помощника ассистента javascript программиста - другое. Надо знать)

Нужно объяснить решение, т.е. ты должен знать реализацию и быть готовым её написать. Либо чот навелосипедить по-быстрому

ну так напиши. так что-то было про std::map… но это смешно. во первых не оговаривается как эта мапа реализвана внутри, и на каких деревьях, во вторых для реальных хешей берут обычно хештаблицы, поскольку они и быстрей и проще деревьев. то есть твое решение - типа стандартной мапы со спинлоками? кхекхе

сначала сбросить с 50, и в зависимости от результата идти с 1 или 51 вверх с n+1

Всё же с n+2. Если разбилось, то предыдущий этаж.

нужно принимать это во внимание

Как?

Тупица, ты надоел, выше в треде всё написано, открой глаза и прочти.

Как?

Обходить снизу вверх очевидно

На программиста, но аналитика данных у них не было и они искали 2 в одном. Я туда не пошел, вроде писал на ЛОР-е, как про ЗП узнавал на том собеседовании, они сначала заливали про то, какие там маленькие ЗП у сотрудников, а я заранее всё разведал и послал их лесом с такими предложениями. То что они хотели это не на 1000 баксов работа, за такие деньги я бы даже с дивана не встал, там рассчитывал на 2.5 штуки, ну 2 в худшем случае. Конечно у них ситуация плохая была видимо на тот момент и больше платить они не могли, так как теперь от некогда обещающего стартапа в несколько сотен сотрудников, меньше 10 человек осталось и вроде как собственник поменялся, а оставшиеся переквалифицировались на другой проект. А может просто искали на копейки аналитика и так и не нашли никого, а дальше с работой не справились.

ЗЫ

Это до обвала рубля было ещё.

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

Мы не шары экономим, а броски. Тьфу, пересмотрел, там 2 шара всего. Тогда чуть сложнее. Там надо балансировать худший вариант.

Всё равно за логарифмическое время не получается, будет за линейное

Как бы вы написали свой ассоциативный массив?

Даже не пытался бы.

Такой вариант подходит?

У второго яйца всегда линейный поиск будет. По этажу его двигать.

Пока первый цел, идём по принципу бинарного поиска, когда сломается, идём n+2 от нижнего не отброшенного. В среднем выиграем.

Можно лучше. Тут строгое решение есть. Надо систему с x-ами составлять и смотреть на минимум. Сейчас подумаю.

Пока первый цел, идём по принципу бинарного поиска, когда сломается, идём n+2 от нижнего не отброшенного. В среднем выиграем.

n+1, второго шара же уже нет :)

Почему?

Тупица, ты надоел, выше в треде всё написано, открой глаза и прочти.

Тебя уж трое небось спросили, про ответ на твой вопрос, ты все куда-то пальцем показываешь, ответа не даешь. Видимо и не знаешь. Или знаешь, но он слишком тривиален - типа мапа со спинлоком. Но это детсад, а не кеш.

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

что ты там такое всепобеждающее и универсальное придумал? пиши немедля, тебе может премию тюринга дадут.

и почему некий интервьюируемый должен это знать?

ну вот бросили с 50-го — разбился, бросили со 2-го — разбился, теперь мы не знаем, со 2-го или с 1-го этажа начинает разбиваться шар

http://risovach.ru/upload/2020/05/mem/prinyaty_240590662_orig_.jpg

Если первым шаром мы «двигаемся» вверх, начиная с земли, по S этажей за один шаг до тех пор, пока первый шар не разобьётся, тогда математическое ожидание количества бросков первого шара M1 составит 50 / S (правда, это только при определённых условиях).
Теперь у нас есть S этажей, добавленных последний раз, приведших к тому, что первый шар разбился.
Теперь будем увеличивать этаж по одному и математическое ожидание M2 бросков второго шара составит S / 2.
Осталось найти минимум функции 50 / S + S / 2. Находим производную, приравниваем к 0 (или просто подобором) видим, что S = 10.

Какой же ты тупорылый. В двух страницах потерялся.

Реальные вопросы на собеседовании (комментарий)

Ещё чуть была ссылка на lock-free, но так можно отвечать только если сможешь хотя бы приблизительную реализацию накидать.

Чёрт. А звучало так просто.

Ты не забывай, что худший случай смотришь, а не ожидаемый. Будет больше 10

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

Я так понял…тут главная идея раздробить доступ я для хранения можно и std::map???….ааааа… это просто и слишком очевидно чувак, это вообше не вопрос.

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

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

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

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