Информация об изменениях

Сообщение Re: Обычный вопрос на собеседовании от 11.06.2019 20:56

Изменено 11.06.2019 21:23 Тёмчик

Re: Обычный вопрос на собеседовании
Здравствуйте, Ватакуси, Вы писали:

В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих

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

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


В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.

В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.

В>PS: Что придумал самый лучший кандидат, я покажу позже. А пока — прошу предлагать свои решения.

В>PPS: Язык питон + алхимия + постгрес, но можно на самом деле использовать всё, что угодно.

BFS по обоим сливаемым деревьям, path к узлу, priority queue.
Re: Обычный вопрос на собеседовании
Здравствуйте, Ватакуси, Вы писали:

В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих

В>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
2 указателя, BFS по документу и по шаблону;

вытаскиваем узел из queue документа, и вытаскиваем узлы из шаблона, пока не наступит совпадение пути. Копируем данные в список к узлу шаблона; вытаскиваем следующий узел документа. Это даст линейную сложность O(m+n).

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


В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.

очевидно, не нужно?
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
Т.е. удаление по маске пути? DFS это childs play.