Сообщение Re: Обычный вопрос на собеседовании от 11.06.2019 20:56
Изменено 11.06.2019 21:23 Артём
Re: Обычный вопрос на собеседовании
Здравствуйте, Ватакуси, Вы писали:
В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
В>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
В>Предпологается, что шаблон можно менять (но нельзя удалять уже существующие разделы, если есть хотя бы один унаследованный документ).
В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
В>PS: Что придумал самый лучший кандидат, я покажу позже. А пока — прошу предлагать свои решения.
В>PPS: Язык питон + алхимия + постгрес, но можно на самом деле использовать всё, что угодно.
BFS по обоим сливаемым деревьям, path к узлу, priority queue.
В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
В>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
В>Предпологается, что шаблон можно менять (но нельзя удалять уже существующие разделы, если есть хотя бы один унаследованный документ).
В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
В>PS: Что придумал самый лучший кандидат, я покажу позже. А пока — прошу предлагать свои решения.
В>PPS: Язык питон + алхимия + постгрес, но можно на самом деле использовать всё, что угодно.
BFS по обоим сливаемым деревьям, path к узлу, priority queue.
Re: Обычный вопрос на собеседовании
Здравствуйте, Ватакуси, Вы писали:
В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
В>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
2 указателя, BFS по документу и по шаблону;
вытаскиваем узел из queue документа, и вытаскиваем узлы из шаблона, пока не наступит совпадение пути. Копируем данные в список к узлу шаблона; вытаскиваем следующий узел документа. Это даст линейную сложность O(m+n).
В>Предпологается, что шаблон можно менять (но нельзя удалять уже существующие разделы, если есть хотя бы один унаследованный документ).
В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.
очевидно, не нужно?
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
Т.е. удаление по маске пути? DFS это childs play.
В>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
В>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
2 указателя, BFS по документу и по шаблону;
вытаскиваем узел из queue документа, и вытаскиваем узлы из шаблона, пока не наступит совпадение пути. Копируем данные в список к узлу шаблона; вытаскиваем следующий узел документа. Это даст линейную сложность O(m+n).
В>Предпологается, что шаблон можно менять (но нельзя удалять уже существующие разделы, если есть хотя бы один унаследованный документ).
В>- Желательно, чтобы при изменении шаблона нужно было перестраивать все документы, от него унаследованные.
очевидно, не нужно?
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
Т.е. удаление по маске пути? DFS это childs play.