[Exam] Data Structures - 13 September 2015 - решения и впечатления
Здравейте,
Отварям тема за проведеният днес изпит по Стуктури от данни.
Как ви се сториха задачите? Според мен бяха интересни и научих доста неща. Като цяло, струва ми се, че ми беше нужна повече практика с подобни задачи с тестове за performance, за да упражня повече работа с речници (по-специално когато ключовете са референтен тип) и свързани списъци. Да видим колко точки ще се отнемат за 1 изпуснат тест.
На 2-ра мъчих известно време някакви бъгове по изхода, но в крайна сметка лесно се докарва до 80-90 точки ако се чете внимателно. Последната трудност за мен беше тест 20, който бях почти сигурен, че е заради търсенето по префикси. Нямаше къде другаде да е. Копирах кода на Trie от демата от лекциите и тестът мина, но пък се получиха грешни отговори заради сортировката. Това го мъчих доста време докато не открих къде се пазят елементите в това Trie, оказа се, че е някакъв обикновен речник май, просто го смених със сортиран такъв и заспа (ред 593 от кода, който събмитнах ако не се лъжа).
На 1-ва задача доста време се опитвах да подкарам последния тест за пърформанс. С другите нямах особени проблеми. Оказа се, че идеята ми е била правилна, но не съм ползвал правилната структура. Ползвах LinkedList за да пазя елементите; за да бъде бързо премахването (което по референция е константно), реших да сложа и речник, в който за всеки елемент да има списък от нодовете от свързания списък. Не работеше с референтни типове (продуктите) и така и не загрях защо до края на изпита, сега като се прибрах и се усетих, че ако ползвам SortedDictionary вместо обикновен речник всичко ще си дойде на мястото. Оправих го и всички тестове минаха.
Ето какви данни ползвах.
private readonly LinkedList<T> elements = new LinkedList<T>();
private readonly SortedDictionary<T, List<LinkedListNode<T>>> nodes = new SortedDictionary<T, List<LinkedListNode<T>>>();
private readonly OrderedBag<T> orderedElements = new OrderedBag<T>();
private readonly OrderedBag<T> reversedOrderedElements = new OrderedBag<T>((e1, e2) => e2.CompareTo(e1));
Свързаният списък за First и Last, nodes речника за триене от свързания списък, беговете за Min/Max методите.
Ето и пълния код на двете задачи:
Scoreboard - по-голямата част от кода е Trie-а, не ми се занимаваше да трия ненужните неща.