Обычный вопрос на собеседовании
От: Ватакуси Россия  
Дата: 11.06.19 19:38
Оценка:
Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
б) Документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.

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

— Желательно, чтобы при изменении шаблона НЕ нужно было перестраивать все документы, от него унаследованные.
— Задача на звёздочку, обеспечить работу удаления разделов в шаблоне (без перестройки всех унаследованных документов).

PS: Что придумал самый лучший кандидат, я покажу позже. А пока — прошу предлагать свои решения.
PPS: Язык питон + алхимия + постгрес, но можно на самом деле использовать всё, что угодно.
Все будет Украина!
Отредактировано 12.06.2019 9:50 Ватакуси . Предыдущая версия .
Re: Обычный вопрос на собеседовании
От: % Австралия жж
Дата: 11.06.19 20:56
Оценка: 1 (1)
Здравствуйте, Ватакуси, Вы писали:

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

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

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

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


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

очевидно, не нужно?
В>- Задача на звёздочку, обеспечить работу удаления разделов в шаблоне.
Т.е. удаление по маске пути? DFS это childs play.
Отредактировано 11.06.2019 21:23 Артём . Предыдущая версия .
Re[2]: Обычный вопрос на собеседовании
От: Ватакуси Россия  
Дата: 12.06.19 09:53
Оценка:
В>>Придумайте структуру(ы) данных, алгоритм(ы) для слияния двух деревьев, представляющих
В>>а) Шаблон документа с разделами, имеющими 3 уровня вложенности (макс)
В>>б) документ, унаследованный от этого шаблона и который может добавлять свои разделы на любом уровне из пункта а), но не может их менять.
%>2 указателя, BFS по документу и по шаблону;
Какие указатели в базе?

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

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


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

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

Нет, ты просто в шаблоне удаляешь раздел. Но у тебя могут быьт документы, которые имеют подразделы этого шаблонного раздела. Или идущие с ним на одном уровне.
Все будет Украина!
Re: Обычный вопрос на собеседовании
От: alzt  
Дата: 12.06.19 10:25
Оценка: +3
Здравствуйте, Ватакуси, Вы писали:

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

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

Есть разные коллеги. У некоторых очень и очень хорошая алгоритмическая подготовка, у каких-та слабая или вообще никакой. Но я так и не заметил никакой корреляции знаний алгоритмов с тем, кто более полезен. Наибольшая полезность бывает у человека, который алгоритмы знает простенько. И часто человек имеющий просто феноменальные знания оказывается совсем никудышным работником.
Re[3]: Обычный вопрос на собеседовании
От: % Австралия жж
Дата: 12.06.19 10:49
Оценка: 1 (1)
Здравствуйте, Ватакуси, Вы писали:

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

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

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

В>Это слияние? А редактирование? Вопрос был про слияние.

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


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

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

В>Нет, ты просто в шаблоне удаляешь раздел. Но у тебя могут быьт документы, которые имеют подразделы этого шаблонного раздела. Или идущие с ним на одном уровне.

Так их типа "нельзя удалять"

Короче, что-то ты недоговаривпешь. Давай схему БД раз уж оно такое.
Re: Обычный вопрос на собеседовании
От: achmed Удмуртия https://www.linkedin.com/in/nail-achmedzhanov-9907188/
Дата: 12.06.19 12:49
Оценка:
Здравствуйте, Ватакуси, Вы писали:

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

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

У двух деревьев есть база общая основа, относительно которой можно вычислять изменения?
Re: Обычный вопрос на собеседовании
От: Буравчик Россия  
Дата: 12.06.19 13:36
Оценка:
Здравствуйте, Ватакуси, Вы писали:

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

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

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

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

Каждому разделу присваиваем глобальный идентификатор (UUID).
Дерево разделов храним в виде отображения (dict) родительских разделов на список дочерних — Dict[ParentSectionID, List[ChildSection]]
Для объединения шаблона и документа, берем "шаблон" и добавляем в него дочерние элементы из "документа", в соответствующие parent_id

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


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

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

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

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

Если нужно сохранять шаблоны и документы в БД, то я бы хранил в виде json: один документ/шаблон — одна строка таблицы.
При запросах вытаскивать json и делать слияние.
Best regards, Буравчик
Отредактировано 12.06.2019 13:40 Буравчик . Предыдущая версия . Еще …
Отредактировано 12.06.2019 13:38 Буравчик . Предыдущая версия .
Re: Обычный вопрос на собеседовании
От: achmed Удмуртия https://www.linkedin.com/in/nail-achmedzhanov-9907188/
Дата: 12.06.19 13:42
Оценка:
Здравствуйте, Ватакуси, Вы писали:

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

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

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


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

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

а) Шаблон — объект JSON https://www.json.org/
б) Документ — JSON Patch http://jsonpatch.com/

Слияние — применение б) к а). Алгоритм apply можно подпилить под особенности структуры документов.

С одной стороны задача довольно таки абстрактная, с другой стороны отсутствуют нефункциональные требования ...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.