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

  • Вакансии

    Продолжают какие-то вакансии по инерции долетать, готовиться к собесам не собираюсь, но планку еще на 20р поднял. До уровня зп архитектора. Если так…

  • Пустота

    Хозяйка прислала счет за комуналку и написала, что заедет завтра вечером, и я удивился, ведь она вроде пару дней назад присылала. Нет, она права, это…

  • Где мой оффер, чувак?

    Походу меня переместили, но забыли сказать об этом :) Предыстория всего этого экшена грустная, но поучительная. Конец 2019 -- начало 2020. Разгар…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 35 comments

  • Вакансии

    Продолжают какие-то вакансии по инерции долетать, готовиться к собесам не собираюсь, но планку еще на 20р поднял. До уровня зп архитектора. Если так…

  • Пустота

    Хозяйка прислала счет за комуналку и написала, что заедет завтра вечером, и я удивился, ведь она вроде пару дней назад присылала. Нет, она права, это…

  • Где мой оффер, чувак?

    Походу меня переместили, но забыли сказать об этом :) Предыстория всего этого экшена грустная, но поучительная. Конец 2019 -- начало 2020. Разгар…