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

Oct 27, 2020 13:48

Всего было 5 пока ( Read more... )

quest, work

Leave a comment

Comments 39

veremeenko_alex October 27 2020, 11:51:33 UTC
Странные задачки. Какой-то хернёй маются.

Reply

brotherflame October 27 2020, 12:06:07 UTC
Про вторую скажу, что жизненная очень.

Первая фан

Reply


mikeofshadows October 27 2020, 12:25:45 UTC
Ну с шариками это типа 50, потом 25 либо 75, ну и тд, как то так надо делать

Reply

brotherflame October 27 2020, 12:44:52 UTC
Написал решение, оно настолько неочевидное, что даже по написанному мало кто поймет идею сходу

Если тыбросишь и разобьешь,с 50, то останется 1 шар и 49 этажей, которые им надо проверить. Это много

Reply

dennab October 27 2020, 13:34:41 UTC
Решение как раз очевидное, вот долбиться с рассчётами влом.

Reply

brotherflame October 27 2020, 13:54:01 UTC
Уже написал, конечно "очевидное"
Все сразу начинают или делить или умножать на 2.

Reply


thirty_lines October 27 2020, 20:21:50 UTC
обычно "обход дерева" - это академическая задача про деревья, где узел хранит список потомков. а "жизненные" деревья обычно хранятся в реляционной базе и узел хранит ссылку на родителя. на этом я бы и строил общение с интервьюером :)

Reply

brotherflame October 27 2020, 20:30:06 UTC
Не понял.
Есть сложность алгоритма и есть использование памяти.
Я предложил много памяти в обмен на низкую сложность.
Ты что предлагаешь?

Reply

thirty_lines October 27 2020, 20:37:03 UTC
я предлагаю принять во внимание, что роли редактируются редко, а проверяются часто и выбрать организацию данных заточенную под поиск. то есть, спросить интервьюера: "откуда дровишки про обход дерева, если мы можем просто пройти от листа к корню (ну или к роли, прописанной юзеру) по ссылкам на родителя"

Reply

brotherflame October 27 2020, 22:16:37 UTC
Это да, про редко.
Пройти от листа к корню это О(n)
Мы хотим О(1) или log(n),
Так что ответ пройти от листа до вершины не правильный

Reply


mikeofshadows October 28 2020, 04:07:30 UTC
Для второй задачи кстати внаверное можно нестед сетс (правые и левые ключи) применить, как раз учитывая что дерево ролей все же апдейтиться довльно редко и перестройки ключей каждый раз для всего дерева не сожрут много ресурсов

Reply

brotherflame October 28 2020, 04:17:06 UTC
Право лево не поможет, оно же не бинарное
Мой вариант с рангами и массивами родителей рабочий, будет сложность о(1) просто требует х2 памяти и перестройки дерева при добавлении роли.

1. Взвешиваем ранг каждой вершины. Корень 0, его потомки 1, и т.д.
Чем выше ранг, тем ниже роль.
1.1. Для каждой вершины создаем массив родительских. По индексу 0 лежит родитель, 1 -- родитель родителя и т.д. до корня вверх

2. На юзере роль U(g), как узнать, есть ли U(r)?
Если ранг r < g, роли нет, не смотрим. R старше g и проверять нечего.
Если ранг r = g, роли тоже нет, разные узлы дерева на одном уровне.
Если ранг r > g.
Берем разницу рангов r и g = n и в массиве родителей r берем элемент с индексом n и сравниваем с g. Если равны, то есть роль.

Reply

mikeofshadows October 28 2020, 04:51:33 UTC
Погугли таки Nested Sets, там и ветка парентов и все потомки получаются простым селектом с двумя сравнениями интов. Единственный минус такой иерархии долгтие апдейты и удаления

Reply

brotherflame October 28 2020, 07:59:05 UTC
Нам нужны все родители, а не все потомки.

Reply


lazy_glutton October 30 2020, 15:31:42 UTC
Пипец, мой математический мозг взорвался 🤯
Дам задачки ребенку, вдруг решит

Reply

brotherflame October 30 2020, 15:38:46 UTC
Бгг, ага ага, особенно вторую

Reply

lazy_glutton October 30 2020, 15:44:00 UTC
Вторую я не совсем поняла, если честно. Через круги Эйлера нельзя решить?

Reply

brotherflame October 30 2020, 15:50:34 UTC
Нет, это тут ни при чем.

Задача простая, есть иерархия, типа папок на компе.

На сотрудника назначается папка, например.

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

И мы хотим проверить права доступа: U(F) где F -- папка.
У сотрудника прописано в правах доступа: X. Нам нужно понять, F=X F > X, F < X, F!=X

Reply


Leave a comment

Up
[]