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

Опубликовано 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.


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

8 Коммент. : “Сериализация дерева”

  1. чем же “хороша” эта задача как тестовая при приеме на работу:

    1. В процессе реализации кандидат неминуемо сталкивается с применением ООП. Ожидается, что сериализация будет выполнена путем использования полиморфизма.
    2. При восстановлении разнотипных данных из файла – кандидат вынужден реализовать паттерн фабрика (пусть и упрощенный)
    3. Работа с деревом требует определенных алгоритмических знаний
    4. Работа с файлами – тоже хорошая проверка

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

    • нанято 3 сотрудника, среди которых как начинающие программисты(минимум 2), так и разработчики с опытом работы(минимум 2)? куда 1 пропал?

      • Реальные данные – 2 юниора (вообще без опыта, только академический) и один с опытом около года. Внимание к деталям – очень положительное качество :)

  2. WorkSeeker says:

    3 человека принято – это ценная информация. Интереснее, однако сколько не принято и почему? Объясняются недостатки по выполнению задания? Или в лучшем случае “… задание выполнено на недостаточно высоком уровне, спасибо за потраченое время…”

    • Галина says:

      Если дело доходит до выполнения тестового задания и в результате получается работающий код и он в основном функционально верный, но не удовлетворителен по каким-либо причинам – то это указывается в письме всегда достаточно подробно. Вплоть до демонстрации конкретных тестовых данных.
      Самый частый здесь прокол для C++ – ошибки в управлении памятью.

      Если же в результате получается нечто, что представляет собой только каркасы классов и алгоритмические эксперименты, то обычно никто на объяснениях не настаивает.

      • Александр says:

        позвольте поинтересоваться – что в вашем понимании “алгоритмические эксперименты”?

  3. Владимир says:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Xml.Linq;
    using System.IO;
     
     
    namespace Tree1
    {
        public abstract class BaseHolder
        {
            internal List<BaseHolder> Nodes { get; set; }
     
            public BaseHolder()
            {
                Nodes = new List<BaseHolder>();
            }
     
            public virtual string GetValue()
            {
                return string.Empty;
            }
        }
     
        public class IntHolder : BaseHolder
        {
            private int Value { get; set; }
     
            public IntHolder(int value)
            {
                Value = value;
                Nodes = new List<BaseHolder>();
            }
     
            public override string GetValue()
            {
                return Value.ToString();
            }
        }
     
        public class StringHolder : BaseHolder
        {
            private new string Value { get; set; }
     
            public StringHolder(string value)
            {
                Value = value;
                Nodes = new List<BaseHolder>();
            }
     
            public override string GetValue()
            {
                return Value.ToString();
            }
        }
     
        public class DoubleHolder : BaseHolder
        {
            private new double Value { get; set; }
     
            public DoubleHolder(double value)
            {
                Value = value;
                Nodes = new List<BaseHolder>();
            }
     
            public override string GetValue()
            {
                return Value.ToString();
            }
        }
     
        public class Tree
        {
            public BaseHolder Root { get; set; }
     
            public Tree() { }
     
            public Tree(BaseHolder root)
            {
                Root = root;
            }
     
            public void SetRoot(BaseHolder root)
            {
                Root = root;
            }
     
            //Serialize method itself
            public void Serialize(string fileName)
            {
                if (Root != null)
                {
                    {
                        using (StreamWriter writer = new StreamWriter(fileName))
                        {
                            XElement xml = _serializeNode(Root);
                            xml.Save(writer);
                        }
                    }
                }
                else
                {
                    throw new ArgumentNullException();
                }
            }
     
            #region Serialize support methods and TestTree
            //Used by Serialize method to recursively serialise each node in hierarchy(tree structure)
            private XElement _serializeNode(BaseHolder node)
            {
                return new XElement("Node",
                    new XAttribute("type", node.GetType()),
                    new XAttribute("Value", node.GetValue()),
                    from el in node.Nodes
                    select _serializeNode(el));
            }
     
            public static Tree GetTestTree()
            {
                IntHolder el1, el2, el3, el4, el5;
                StringHolder el6, el7, el8, el9;
                DoubleHolder el10;
     
                el1 = new IntHolder(1);
                el2 = new IntHolder(2011);
                el3 = new IntHolder(9);
                el4 = new IntHolder(6);
                el5 = new IntHolder(7);
     
                el6 = new StringHolder("C++");
                el7 = new StringHolder("Falcrum");
                el8 = new StringHolder("TEST");
                el9 = new StringHolder("Linux");
     
                el10 = new DoubleHolder(3.14);
     
                el1.Nodes = new List<BaseHolder> { el2, el6, el10 };
                el2.Nodes = new List<BaseHolder> { el7 };
                el7.Nodes = new List<BaseHolder> { el5, el9 };
                el10.Nodes = new List<BaseHolder> { el3, el4, el8 };
     
                return new Tree(el1);
            }
            #endregion
     
     
            public static Tree DeSerialize(string fileName)
            {
                Tree tree = new Tree();
                XElement xmlElem;
     
                using (StreamReader reader = new StreamReader(fileName))
                {
                    xmlElem = XElement.Load(fileName);
                }
     
                BaseHolder root = _deserilizeNode(xmlElem);
     
                _recursivelyDeserialize(xmlElem, root);
                tree.SetRoot(root);
     
                return tree;
            }
     
            #region DeserializeSupportMethods
            /// <summary>
            /// Used to recursively dserialize each node by passing XElement of higher level of hierarchy and pasing root of current subtree
            /// </summary>
            /// <param name="xRoot">XElement that represents a higher level to access on lower level of xml elements hierarchy</param>
            /// <param name="holderRoot">Root element of current subtree</param>
            private static void _recursivelyDeserialize(XElement xRoot, BaseHolder holderRoot)
            {
                foreach (var elem in xRoot.Elements())
                {
                    BaseHolder temp = _deserilizeNode(elem);
                    holderRoot.Nodes.Add(temp);
                    _recursivelyDeserialize(elem, temp);
                }
            }
     
            //Used by Deserialize nethod tom get one node from XElement
            private static BaseHolder _deserilizeNode(XElement xElem)
            {
                XAttribute xmlAttr = xElem.Attribute("type");
                BaseHolder node;
     
                if (xmlAttr.Value.ToString() == "Tree1.IntHolder")
                {
                    node = new IntHolder(Int32.Parse(xElem.Attribute("Value").Value.ToString()));
                }
                else if (xmlAttr.Value.ToString() == "Tree1.StringHolder")
                {
                    node = new StringHolder(xElem.Attribute("Value").Value.ToString());
                }
                else
                {
                    node = new DoubleHolder(double.Parse(xElem.Attribute("Value").Value.ToString()));
                }
     
                return node;
            }
            #endregion
        }
    }
            static void Main(string[] args)
            {
                Tree tree;
     
                //tree = Tree.GetTestTree();
                //tree.Serialize("newFile.xml");
                tree = Tree.DeSerialize("newFile.xml");
     
                Console.ReadKey();
            }
  4. Maksym says:
    #include<vector>
    #include<iostream>
    #include<fstream>
    #include<string>
    #include<queue>
    #include<set>
    #include<cmath>
    using namespace std;
    struct BaseHolder {
    	vector<BaseHolder*> children;
    	BaseHolder()
    	{
    	}
    	virtual ~BaseHolder(){};
    };
    class IntHolder: public BaseHolder{
    public: int value;
    		void getval(){
    		cout<<value;
    		}
    		IntHolder(int val)
    		{
    			value=val;
    		}
    };
    class CharHolder: public BaseHolder{
    public: char value[10];
    		CharHolder(string val)
    		{
    			int size=min(10, (int)val.length());
    			for(int i=0; i<size; i++)
    				value[i]=val[i];
    			if(size<10)
    			{
    				for(int i=size; i<9; i++)
    					value[i]='';
    			}
    		}
    };
    class DoubleHolder: public BaseHolder{
    public: double value;
    		DoubleHolder(double val)
    		{
    			value=val;
    		}
    };
    class Tree{
    public:
    	//Pointer to the root node
    	BaseHolder* root;
    	//Vector to store pointers to all nodes
    	vector<BaseHolder*> nodes;
    	//Vector to store numbers of verticies adjacent to given one.
    	vector<vector<int>>adjacency_list;
    	//Function to create a txt.file with all the information about the graph
    	void Serialize(string filename);
    	//Vector to read all the info to create a graph
    	void Decerialize(string filename);
    	//To print value stored in a node
    	void ob_val_print(BaseHolder*);
    	//To print values, stored in all nodes according to the BFS search
    	void Print_vertices();
    };
    void Tree::Decerialize(string filename)
    {
    	int vertex_count;
    	try{
    		ifstream in(filename);
    		if (!in.is_open()) throw 1;
    		in>>vertex_count;
    		int current_vertex=0;
    		while(!in.eof()&&current_vertex!=vertex_count){
    			int vert_num;
    			int type;
    			//We read into the type variable the data type. 1- integer, 2-char[10], 3-double
    			in>>vert_num>>type;
    			switch(type){
    					case 1: {int val;
    							in>>val;
    							nodes.push_back(new IntHolder(val));
    							break;
    							}
    					case 2: {
    						string val;
    						in>>val;
    						nodes.push_back(new CharHolder(val));
    						break;
    							}
    					case 3: {
    						double val;
    						in>>val;
    						nodes.push_back( new DoubleHolder(val));
    							}
    			};
    			int  temp;
    			vector<int> vector_temp;
    			//Here we fill in the adjacency_list vector  to store the numbers of verticies adjacent to the given one.
    			do{
    					in>>temp;
    					if(temp==-1) break;
    					vector_temp.push_back(temp);
    			} while(1);
    			adjacency_list.push_back(vector_temp);
    			current_vertex++;
    		}
    		in.close();
    		for(int i=0; i<vertex_count; i++)
    			for(unsigned int k=0; k<adjacency_list[i].size(); k++){
    					int temp=adjacency_list[i].size();
    					nodes[i]->children.push_back(nodes[adjacency_list[i][k]]);
    				}
    	}catch(...){
    		cout<<"Can not open a file"<<"\n";
    	};
    }
    void Tree::Serialize(string filename)
    {
    	try{
    		ofstream out(filename);
    		int adj_size=adjacency_list.size();
    		if (adj_size==0) throw 1;
    		out<<adj_size<<"\n\r";
    		for(int i=0; i<adj_size; i++){
    			out<<i<<"\t";
    			string ob_type=typeid(*nodes[i]).name();
    			if(ob_type=="class IntHolder"){
    				out<<1<<"\t";
    				IntHolder *p1 = dynamic_cast< IntHolder* >(this->nodes[i]);
    				out<<p1->value<<"\t";
    			}		
    			if(ob_type=="class CharHolder"){
    				out<<2<<"\t";
    				CharHolder *p2 = dynamic_cast< CharHolder* >(this->nodes[i]);
    				out<<p2->value<<"\t";
    			}
    			if(ob_type=="class DoubleHolder"){
    				out<<3<<"\t";
    				DoubleHolder *p3 = dynamic_cast<DoubleHolder* >(this->nodes[i]);
    				out<<p3->value<<"\t";
    			}
    		for(unsigned int j=0; j<adjacency_list[i].size(); j++){
    			out<<adjacency_list[i][j]<<"\t";
    		}
    		//We end each line by -1 symbol, separating	it from the info for the next vertex
    		out<<-1;
    		out<<"\n\r";
    		}
    		out.close();
    		} catch(...){
    			cout<<"Graph is not initialized"<<endl;
    		}
    }
    void Tree::ob_val_print(BaseHolder* node){
    		string ob_type=typeid(*node).name();
    		if(ob_type=="class IntHolder"){
    				IntHolder *p1 = dynamic_cast< IntHolder* >(node);
    				cout<<p1->value<<"\t";
    		}		
    		if(ob_type=="class CharHolder"){
    				CharHolder *p2 = dynamic_cast< CharHolder* >(node);
    				cout<<p2->value<<"\t";
    		}
    		if(ob_type=="class DoubleHolder"){
    				DoubleHolder *p3 = dynamic_cast<DoubleHolder* >(node);
    				cout<<p3->value<<"\t";
    		}
    }
    void Tree::Print_vertices()
    {
    	try{
    		int adj_size=adjacency_list.size();
    		if (adj_size==0) throw 1;
    		//We implement breadth-first search
    		queue<BaseHolder*> q;
    		q.push(nodes[0]);
    		//Used vertices
    		set<BaseHolder*> covered;
    		set<BaseHolder*>::iterator it=covered.end();
    		while(!q.empty()){
    			BaseHolder* parent=q.front();
    			if(covered.find(parent)==it){
    				ob_val_print(parent);
    				q.pop();
    				for(unsigned int i=0; i<parent->children.size(); i++)
    					if(covered.find(parent->children[i])==it)q.push(parent->children[i]);
    				covered.insert(parent);
    			}
    		}
    	}
    	catch(...){
    	cout<<"No vertices to print";
    	}
    }
    int main()
    {	
    	Tree first;
    	first.Decerialize("Test_Fulcrum.txt");
    	//We store the current graph in the Out.txt file
    	first.Serialize("Out.txt");
    	//We print out all verticies according to the BFS search
    	first.Print_vertices();
    	getchar();
    	getchar();
    	return 0;
    }
     
    Input test file for the Deserialize function:
    10
    0 1 1 1 2 3 -1
    1 1 2011 4 -1
    2 2 C++ -1
    3 3 3.14 5 6 7 -1
    4 2 FULCRUM 8 9 -1
    5 2 TEST -1
    6 1 9 -1
    7 1 6 -1
    8 2 LINUX -1
    9 1 7 -1

Оставить комментарий

Ваш адрес email не будет опубликован.


*