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-а, не ми се занимаваше да трия ненужните неща.

Тагове:
dim4o avatar dim4o 288 Точки

Ето моят код за 2-ра задача. Префикса става с Range() върху OrderedSet()-а. Правя един "z" хак.

На 1-ва въпреки, че ги имаше тестовете не можах да докарам 3 от тях. Нe ми стигна времето да сложа някакви читави структури. Задачата е интересна, но не беше изобщо толкова лесна и проста като на лаба. В крайна сметка реших, че ще е по-добре да реша 2-ра, която ми се беше сторила по-лека. Според критериите за оценяване май излиза, че е по-добре една задача на 100% отколкото 2 на 80%,

Общото ми впечатлени от курса е, че задачите от изпитите нямаха почти нищо общо с тези от домашните. Реално само последната тема е достатъчна за изпита. Щеше да е хубаво ако имаше още подобни теми. В крайна сметка да се учиш да балансираш дървета и да обхождаш графи е много приятно, но изглежда не помага да се подготвиш за изпит от този вид. Не помага и да решиш единствената задача от подоготовката 5 пъти.

По принцип е хубаво да се учат непрекъснато нови неща, но за предпочитене е да не е на изпит, защото там човек е ограничен с времето. Интересен курс беше, научих много неща, но съм сигурен, че има много накъде да се подобри в следващите издания.

 

6
13/09/2015 21:03:35
Filkolev avatar Filkolev 4482 Точки

И аз по едно време пробвах с Range, ама явно днеска не съм бил много схватлив, щото не се сетих за тоя хак. Друг колега каза, че го е направил с RangeFrom и ръчно е проверявал кога да спре.

Не съм сигурен обаче, че твоят вариант е 100% коректен, ако в името на играта има други символи може да изпуснеш част от тях, които по лексикографска подредба са след префикса + "z". Доста странно име ще е и явно не е имало такива тестове.

Съгласен съм за подготовката, според мен задачите за домашно и подготовката за изпит бяха лесни и винаги е неприятно когато нивото на изпита е по-високо от това, с което разполагаш за тренировки. Но с всеки курс е така - всяко следващо издание е по-добро откъм съдържание. 

0
dim4o avatar dim4o 288 Точки

Да, аз затова му казвам "хак" - защото решава конкретен проблем по кратък и прост начин, но не и проблема в най-общия случай. По принцип на мястото на "z" ако се сложи най-големия char задачата трябва да върви и в общия случай. Все пак после се прави и допълнителен филтър. Просто за изпита това свърши работа и не съм се занимал да търся коя е най-подходящата стойност.

0
Filkolev avatar Filkolev 4482 Точки

Има char.MaxValue, което може би ще спести филтрацията и ще подобри малко скоростта.

1
Karlie avatar Karlie 438 Точки

И на мен изпитът ми се стори доста по-сложен от задачите от подготовките (и двете успях да ги реша напълно, а днес - пълен провал). Вероятно сгреших, че започнах от втора задача. Гледах да си оставя достатъчно време за първа, но тя пък се оказа неочаквано сложна и накрая не довърших нито една от двете.

В този ред на мисли - ще има ли поправителен изпит след като излязат оценките или чак със следващата инстанция на курса можем да се явим?

5
13/09/2015 22:04:57
Kamigawa avatar Kamigawa 750 Точки

Не мога да кажа, че съм доволен от себе си, така и не се сетих как да накарам префиксите да работят бързо на 2ра и триенето по 1ва да работи бързо. Като цяло от всичките 62 теста не ми минават 3, което е предостатъчно да хвана големия според така "добре" измислената система за оценяване, но каквото - такова. Ще се "поправям" явно - ако и покато има възможност. За сложност на задачите не бих казал, че бяха сложни, но явно писането на код за пърформънс ми куца.

0
RoYaL avatar RoYaL Trainer 6849 Точки

Изпитът беше супер. По един тест не ми мина на 2те задачи. На 1вата - перформънса при DeleteAll и на 2рата - 14ти тест, каквото и да има там като изход, не съм го набарал :D

Доволен съм от себе си, като човек, който никога не е разбирал алгоритмичните неща и повече се е осланял на технологиите. Дали курсът обаче имаше нещо общо с изпита - по-скоро не. Не съм сядал на уча за курса поради липса на време, но бях на повечето лекции - и да общо взето изпитът покрива темата за ефикастност на структурите от данни и в частност търсенето в хеш таблици и подреждането на дървета.

--

Относно префиксите - пробвах с Trie и нещо се омотах. Не я бях разучавал структурата и не ми се е случвало да я ползвам в практиката, така че сметнах за кауза пердута да я разучавам на изпита и я зарязах като вариант. При създаването на игра пълнех в два речника - един, в който за всеки префикс се слагаха възможните му игри и обратното - за всяка игра възможните префикси. После при изтриване на игра минавах през речниците и ги триех.

Демек тия структури:

        private Dictionary<string, SortedSet<String>> prefixes = new Dictionary<string, SortedSet<string>>();
        private Dictionary<string, List<String>> gamesPrefixes = new Dictionary<string, List<string>>();

Като добавям игра:

            for (int i = gameName.Length - 1; i >= 0; i--)
            {
                string pref = gameName.Substring(0, i + 1);
                if (!this.prefixes.ContainsKey(pref))
                {
                    this.prefixes.Add(pref, new SortedSet<string>());
                }
       
                this.prefixes[pref].Add(gameName);
                if (!this.gamesPrefixes.ContainsKey(gameName))
                {
                    this.gamesPrefixes.Add(gameName, new List<string>());
                }
                this.gamesPrefixes[gameName].Add(pref);
            }

 

0
malkstor avatar malkstor 348 Точки

И аз не съм доволен от представянето си, и двете задачи на пръв поглед звучат като лесни, ама има едни дребни подробности дето обръщат всичко. Домашните бяха по-лесни, както някой вече спомена :) Нищо, дано има поправка.

Аз на първата задача се засилих към Deque, но нещо не успях да се оправя и ми останаха 6 теста, половината performance. Тук ми е и надеждата за някакви точки, че втората успях да я докарам само до 36 точки, че така и не успях да си натаманя правилната структура от данни.

0
13/09/2015 23:04:36
MartinBorisov94 avatar MartinBorisov94 52 Точки

Задачите бяха по- сложни от подготовката, но това не е нищо ново под слънцето. Факта, че имаше 7 (по спомен) човека със 100 означава, че не е било и толкова сложно. На мен ми харесаха най- много тестовете как бяха написани. Правя нещо малко събмит и получавам точки (минал съм доста изпити и така направени тестове са рядкост). А относно структурите, мисля, че още малко желязо му трябва на judge и List ще е перфектната структура (в кръга на шегата го казвам!)

1
nelly.m.mincheva avatar nelly.m.mincheva 24 Точки

Изпитът беше интересен... Започнах с втора... 77 точки... После малко на първа (22 теста минаха) и накрая докарах до 95 точки втората.. :) ( Код )

Но нещо и много интересно ми направи впечатление - имам навика да си пращам решенията по два пъти от съобразения нещо да не би да не се е качило, но точките ми паднаха драстично от тези на миналия събмит... и се заиграх последните минути.

Снимката е на едно и също решение... Стига се до извода, че спрямо натовареността на системата се забелязват резултати между 80 и 95 точки...

Чак вече се питам как може да става "Fair play" в такива случаи...

 

1
AleksandurSeferinkin avatar AleksandurSeferinkin 333 Точки

nelly.m.mincheva, интересното е, че на 2ри и 3ти и на още няколко submit-и времето е еднакво (0.377), а резултатите от тестовете са различни. Казах му на г-н Захариев, че judge е бъгнат, нали? :D

2
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Да, има лека неточност при измерването на времето.Тя идва най-вече от енвъзможността да измериш I/O натовареността. CPU time лесно се мери, но ако дисковее са натоварени, входът и изходът са различно бързи. Затова може днаистина да събмитваш кода по няколко пъти, ако си на ръба.

Времената бяха сложини почти 2 пъти по-големи от авторското решение.

Наков

3
blizzardcon10 avatar blizzardcon10 11 Точки

А коя от двете задачи ще има по - голяма тежест при оценяване?

0
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Колеги, приканвам ви да разгледате и авторските решения и тестовете на двете задачи: Exam-Data-Structures-13-September-2015.zip.

Първата задача (FirstLastList) я решавам най-ефективно със следните структури:

  • LinkedList<T> - пази реда на елементите и може да трие бързо, стига на имаш pointer към елемента за изтриване
  • OrderedMultiDictionary<T, LinkedListNode<T>> - пази елементите сортирани + пази pointer към елемента от свързания списък

Има и други интересни решения, например с 2 броя OrderedBag<T> за min / max операциите, както и с Dictionary<int, T>, където като ключ се ползва глобалният брой добавени елементи откакто е създадена структурата.

Втората (Scoreboard) задача я решавам със следните структири:

  • Dictionary<string, string> - пази потребители и техните пароли
  • Dictionary<string, string> - пази игри и техните пароли
  • OrderedDictionary<string, OrderedBag<ScoreboardEntry>> - пази класиранията за всяка от игрите

Тънки моменти, които можем да съобразим:

  • Понеже никога не трием елементи от класирането (евентуално напълно трием цялото класиране), можем да пазим топ 10 резултата за всяка игра, а останалите да ги изтриваме. Така няма голямо значение дали ще пазим класирането в OrderedBag<T> или List<T> + сортировка + bool дали е сортиран списъкът (за да не повтаряме сортировката ако няма промени в класирането)
  • Търсенето по префикс става доста лесно, ако съобразим, че иманета на игрите са сортирани. Тогава ако вземем RangeFrom(prefix, true), елементите с дадения префикс ще са в началото на извадения range.

Видях, че има и други инересни решения, например с Trie<Т>.

Ще изкараме резултати от изпита и класиране за курса до няколко дни. Както ви обещах, при всички тестове без 1-2 ще имате висок резултат. Още не сме измислили формулата, но идеята е реализациите с List<T> да не получат повече от половината точки.

Наков

2
nikola.m.nikolov avatar nikola.m.nikolov 830 Точки

Както ви обещах, при всички тестове без 1-2 ще имате висок резултат.

Това общо за двете задачи ли се отнася или само за първата задача?

 

0
nakov avatar nakov SoftUni Team Trainer 5295 Точки

Отнася се и за двете задачи. Ще измислим честна формула, която ще дава половината точки за задачата при решение с List<T>, обаче ако минават повече тестове от тези елементарните, ще има повече точки, а при 100% тестове -> 100% точки.

Наков

0
alexandra.svilarova avatar alexandra.svilarova SoftUni Team Moderator Forum Admin 1077 Точки

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

Пиша ви, за да ви уведомя, че резултати и оценки от изпита по Структури от данни, който се проведе на 13 септември (неделя) ще бъдат качени в началото на другата седмица.

Извиняваме се за забавянето и ви пожелаваме слънчев и усмихнат следобед.

При въпроси - съм на разположение : )

- Алекс

4
Filkolev avatar Filkolev 4482 Точки

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

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

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

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

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

 

Фил

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