[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-а, не ми се занимаваше да трия ненужните неща.
И аз по едно време пробвах с Range, ама явно днеска не съм бил много схватлив, щото не се сетих за тоя хак. Друг колега каза, че го е направил с RangeFrom и ръчно е проверявал кога да спре.
Не съм сигурен обаче, че твоят вариант е 100% коректен, ако в името на играта има други символи може да изпуснеш част от тях, които по лексикографска подредба са след префикса + "z". Доста странно име ще е и явно не е имало такива тестове.
Съгласен съм за подготовката, според мен задачите за домашно и подготовката за изпит бяха лесни и винаги е неприятно когато нивото на изпита е по-високо от това, с което разполагаш за тренировки. Но с всеки курс е така - всяко следващо издание е по-добро откъм съдържание.
Да, аз затова му казвам "хак" - защото решава конкретен проблем по кратък и прост начин, но не и проблема в най-общия случай. По принцип на мястото на "z" ако се сложи най-големия char задачата трябва да върви и в общия случай. Все пак после се прави и допълнителен филтър. Просто за изпита това свърши работа и не съм се занимал да търся коя е най-подходящата стойност.
Има char.MaxValue, което може би ще спести филтрацията и ще подобри малко скоростта.