обычно "обход дерева" - это академическая задача про деревья, где узел хранит список потомков. а "жизненные" деревья обычно хранятся в реляционной базе и узел хранит ссылку на родителя. на этом я бы и строил общение с интервьюером :)
я предлагаю принять во внимание, что роли редактируются редко, а проверяются часто и выбрать организацию данных заточенную под поиск. то есть, спросить интервьюера: "откуда дровишки про обход дерева, если мы можем просто пройти от листа к корню (ну или к роли, прописанной юзеру) по ссылкам на родителя"
Для второй задачи кстати внаверное можно нестед сетс (правые и левые ключи) применить, как раз учитывая что дерево ролей все же апдейтиться довльно редко и перестройки ключей каждый раз для всего дерева не сожрут много ресурсов
Право лево не поможет, оно же не бинарное Мой вариант с рангами и массивами родителей рабочий, будет сложность о(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. Если равны, то есть роль.
Погугли таки Nested Sets, там и ветка парентов и все потомки получаются простым селектом с двумя сравнениями интов. Единственный минус такой иерархии долгтие апдейты и удаления
Задача простая, есть иерархия, типа папок на компе.
На сотрудника назначается папка, например.
Естественно, в папке есть вложенные папки, а есть родительская. Соответственно, если на сотрудника назначена папка, у него есть доступ к дочерним папкам, но нет к родительским.
И мы хотим проверить права доступа: U(F) где F -- папка. У сотрудника прописано в правах доступа: X. Нам нужно понять, F=X F > X, F < X, F!=X
Comments 39
Reply
Первая фан
Reply
Reply
Если тыбросишь и разобьешь,с 50, то останется 1 шар и 49 этажей, которые им надо проверить. Это много
Reply
Reply
Все сразу начинают или делить или умножать на 2.
Reply
Reply
Есть сложность алгоритма и есть использование памяти.
Я предложил много памяти в обмен на низкую сложность.
Ты что предлагаешь?
Reply
Reply
Пройти от листа к корню это О(n)
Мы хотим О(1) или log(n),
Так что ответ пройти от листа до вершины не правильный
Reply
Reply
Мой вариант с рангами и массивами родителей рабочий, будет сложность о(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
Reply
Reply
Дам задачки ребенку, вдруг решит
Reply
Reply
Reply
Задача простая, есть иерархия, типа папок на компе.
На сотрудника назначается папка, например.
Естественно, в папке есть вложенные папки, а есть родительская.
Соответственно, если на сотрудника назначена папка, у него есть доступ к дочерним папкам, но нет к родительским.
И мы хотим проверить права доступа: U(F) где F -- папка.
У сотрудника прописано в правах доступа: X. Нам нужно понять, F=X F > X, F < X, F!=X
Reply
Leave a comment