Сериализация дерева

Опубликовано Apr 27, 2012 в Тестовые проекты (2-3 часа) | 8 коммент.

, , , ,

Сериализация дерева

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

Постановка сериализация/десериализация дерева

Необходимо реализовать простую иерархию классов для хранения нескольких простых типов данных:  int (32 бита);  char[10];  double. 

Предполагается единственный абстрактный базовый класс – BaseHolder, и его наследники – IntHolder, CharArrayHolder и DoubleHolder.

Далее необходимо реализовать структуру данных – дерево указателей на базовый класс – и наполнить его в теле программы несколькими  произвольными элементами, используя разные типы (int , char[], double).

Пример такого дерева приведен на рисунке

В рамках тестового задания необходимо реализовать код сохранения и восстановления дерева.

  • Вариант 1. Бинарный файл – (можно применять любые API для чтения и записи).
  • Вариант 2. Текстовый файл – (можно применять любые API для чтения и записи).
  • Вариант 3. Непрерывная область памяти,  выделенная через  new char[N].

* Выбор варианта – на усмотрение исполнителя.

Стадии реализации

Стадия #1: Реализовать сохранение/восстановление списка (в некоторых случаях допускалось упрощение задачи).

Стадия #2: Реализовать сохранение/восстановление дерева – основная.

Дальше мы планируем полный разбор вариантов решения данной задачи и с их достоинствами и недостатками. 

Общие соображения

1) ООП и структура данных. Необходимый дизайн классов для узлов дерева описан в условии, – его и нужно реализовать. При этом в BaseHolder нужно добавить контейнер для хранения ссылок на дочерние узлы, а в производные классы – поле для данных подходящего типа. Это минимально необходимые данные, при наличии которых задача решаема. Очевидно, что необходим еще класс Tree, который реализует собственно дерево. Этот класс должен содержать открытый указатель на корень дерева, через этот указатель дерево должно полностью обходиться одним из стандартных способов. Разумеется, можно реализовывать более сложные и эффективные структуры данных для описания дерева, некоторые варианты далее будут рассмотрены.

2) Выбор типа сериализации. Мне нравится вариант под номером 2, так как текстовое представление наиболее наглядно, можно просто просматривать файл с результатами сериализации, а разобравшись в его формате, легко готовить тестовые данные для десериализации.

3) Тестирование. При наличии времени и желания, можно наполнить класс Tree всевозможной функциональностью для вставки и удаления узлов, отображения дерева на экране в структурированном виде и прочих полезных штук. Но в рамках задания достаточно прямо в коде создать тестовые данные, правильно сцепив ссылки узлов друг на друга хардкодом. Проверку того, что дерево построено правильно можно выполнять просто в отладчике, пройдя по ссылкам вручную.

Ссылки на посты с решениями

Решение задачи сериализации дерева на C#. Выбрана стандартная XML-сериализация с использованием функциональности из  System.Xml.Serialization.


Автор публикации: