BrotherFlame (brotherflame) wrote,
BrotherFlame
brotherflame

Самый интересный собес

Всего было 5 пока.

#4. Собес в Райф. Конечно не прошел, но первый раз реально сложные и интересные вопросы.
С гуглом первую решит любой дурак, но я и без гугла ее решал год назад примерно, ща просто ответ подсмотрел и вспомнил. Решение нифига не очевидное, и надо считать много на бумажке и помнить формулы корней квадратного уравнения (мега подсказка). На собесе дается минута, две на подумать.
Вторая совсем неочевидная, решение придумал только сегодня, на собесе впал в ступор, но и то оно плохое по сжиранию памяти.

1. Есть два шара стеклянных.
И 100 этажное здание. Шар может разбиться при броске с какого-то этажа.
Какое минимальное число бросков можно сделать, чтобы найти этот этаж.

2. Есть пользователи и дерево ролей.
Роли могут быть вложены друг в друга.
Например А содержит Б и В.
Если на пользователя назначена роль А, значит Б и В тоже есть.
Как сделать проверку того, что на пользователя назначена роль, чтобы это было быстрее, чем полный обход дерева?

Upd.
Все равно первую никто из коллег не решит без гуголя, пишу схему решения.

В общих чертах выглядит как будто у нас нечто, что нужно умножать на 2 все время, чтобы получить сложность log(n). Но всего два шара, а не k>2 намекают на то, что это какой-то граничный случай и просто умножать на два этаж для след броска не прокатит.
2,4,8,16,32,64 -- 6 бросков. Если не разбился, остается 36 этажей. Шар бьется на 64.
Надо бросать оставшийся аж 32 раза еще. Эпик фейл.
Нужна другая схема бросков. Каждый следующий этаж должен сокращать количество вариантов на 1, по сравнению с предыдущим этажем.
И первый раз бросаем с некоторого этажа a1, так, чтобы если 1-й шар умрет, мы бросим второй шар с 1-го этажа по a1-1, пока не разобьется.
Но если шар 1 не разбился, мы поднимаемся вверх на а1-1 этажей, чтобы не увеличит число попыток, одна у нас уже была. Это похоже на арифметическую прогрессию.
Сумма = 100. Шаг = -1.
Остается написать уравнение.
Sn = (2*a1 - (n - 1))*n/2
В нем два неизвестных
A1 -- первый этаж, с которого бросаем
N -- количество бросков
Решаем его. Получаем значение для корней квадратного уравнения.
Выкидываем один, из второго получаем неравенство, в котором нужно найти минимальный a1:
a1*a1 + a1 > 200
Это 14-й этаж.
Соответственно, худший случай, 14 бросков, иначе поднимаемся на 13,12,11 и т.д. И если первый шар шар на очердном шаге разбился, возвращаемся на предыдущий этаж,где не разбился, и двигаемся по 1 вверх.

Вторую как решать хз. Может ввести уровни в дереве ролей 0,1,2...
Для каждой вершины хранить массив всех родителей в массиве, индекс 0 -- родитель, 1 -- родитель родителя. И тд
И при проверке U(r), смотрим ранг роли g непосредственно на юзере , сравниваем с рангом роли r.
Если g > r, не проверяем дальше. G вложена в r,как минимум, или в другой ветке дерева.
Разница рангов -- это индекс массива, для поиска родителя. Берем массив родительских ролей по этому индексу, и сравниваем с ролью пользака.
Сложность o(1). Но большие доп траты памяти и необходимость перестраивать дерево при добавлении ролей.
Tags: quest, work
Subscribe

  • Питер

    Первый раз в этом году. Выезжаем 6 августа утром, обратно 8-го. Вчера не удержался и хорошо так шлепнул по ее КМСной жопе прям посреди улицы. Не в…

  • Прохватил

    Легче не стало. Девчонке, которую катал, сказал, что в розовых шортах моя подруга (видела сторис в инсте), но че-то сомневаюсь, что она остановит…

  • 10 часов

    Ровно столько продлилась третья свиданка. Мы стартанули в 15. В 1.30 я дома. Решил так: сегодня все или ничего. Ну и что из этого вышло? Так и…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 35 comments

  • Питер

    Первый раз в этом году. Выезжаем 6 августа утром, обратно 8-го. Вчера не удержался и хорошо так шлепнул по ее КМСной жопе прям посреди улицы. Не в…

  • Прохватил

    Легче не стало. Девчонке, которую катал, сказал, что в розовых шортах моя подруга (видела сторис в инсте), но че-то сомневаюсь, что она остановит…

  • 10 часов

    Ровно столько продлилась третья свиданка. Мы стартанули в 15. В 1.30 я дома. Решил так: сегодня все или ничего. Ну и что из этого вышло? Так и…