Loading...
Filkolev avatar Filkolev 4482 Точки

[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 методите. 

Ето и пълния код на двете задачи:

FirstLastList

Scoreboard - по-голямата част от кода е Trie-а, не ми се занимаваше да трия ненужните неща.

Тагове:
Filkolev avatar Filkolev 4482 Точки

Здравейте колеги,

Ако все още не сте забелязали, по-рано днес бяха качени резултатите от изпита и оценките за курса.

Малко информация за оценяването:

На първа задача има два компонента - формална проверка (дали юнит тестовете минават) и ръчна проверка. При формалната проверка тежестта на тестовете за коректност е по-ниска от тази на тестовете за бързодействие. При ръчната проверка се проверява какви структури са ползвани и дали са използвани по правилен начин. 

На втора задача скалирането бе променено от първоначално планираното. Ощетени няма, но печелят само хората, които са се постарали и са успели да вземат поне част от тестовете за бързодействие. Резултатите са единствено на база постигнатото в Judge, тук (по замисъл) няма ръчна проверка. Ако желаете някаква обратна връзка по тази задача, може да споделите решението си тук, има достатъчно колеги, които биха се отзовали.

 

Фил

5
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.