Условия, решения и тестове от изпита по структури данни и алгоритми 2015


10

Здравейте,

тук можете да видите условията, решенията и тестовете от изпита https://github.com/TelerikAcademy/Data-Structures-and-Algorithms/tree/master/Exam/2015

В темата можете да коментирате и самия изпит (моля без спам :)).




Отговори



6

Здравейте колеги,
Сега ще ви разкажа нещо за разведряване, но няма да ми се смеете(много) :), трейнърите и без това вече са изпопадали от смях като гледат какво съм събмитвал по 6-та задача :) Та, става въпрос за неволите ми със Задача 6 - Words.
След като реших първа задача, видя ми се трудна, и реших, че изпитът явно ще е тотална касапница :) Видях, че няколко човека са избутали 6-та задача до 100 точки, за разлика от останалите задачи и реших да се захвана с нея.
В интерес на истината, не се бях задълбочил много в лекцията на Цъки за стрингове, бях запознат с решението на задачата на Дончо от подготовката. Считайки, че ще трябва да се имплементира някой от по-дебелите алгоритми, директно се хвърлих да имплементирам RabinKarp. Дори не прочетох докрай условието на и без това кратката задача. Мисля си Naive Search ще е за наивниците дето си мислят, че тази задача се решава лесно(ахахахахахаха)...
И така - първи събмит на RabinKarp- всичко гърми, три теста гърмят на време. Не...няма да се дам лесно :)
Правя тройно хеширане - събимтвам - отново всичко гърми, но без гърмежи по време...викам си браво, оптимизирах(ахахахахахаха), сега ще оправя и грешките :)
Тръгвам да оправям грешките...и почвам да се усещам(при вече имплементиран RobinKarp, ахахахахаха). Чакай бе, аз направих решение на съвсем друга задача...давай отначало...
Я си прочети условието...опс, имаме търсене по няколко патърна, общо колко пъти имаме съвпадение, моля...веднага едно AhoCorasick...няма проблеми...Правя AhoCorasick, което префектно връща сумата на всички съвпадения на патърните...викам си...олях се, това пак е друга задача, ама я да видим какво ще даде бгкодера...
Три събмита с леки вариации на AhoCorasick резултати...ОЧУДО - 20, 10 и 20 точки...
Този път обаче никой не е в състояние да ме заблуди, ахахахахахха, за какво се трепах толкова време:)
Време е за Naive Search...
Първи събмит на имплементацията ми на Naive Search - 100 от 100...
Часът е малко след 18.10...реших, че няма смиъсл да решавам друга задача, за да припадат трейнърте от смях..

Напуснах бойното поле около 18.15, 35-ти в текущото класиране с 215 точки.

Отивам да почивам, че имам нужда от сериозна почивка, както става ясно от по-горе :)


от MarinMarinov (912 точки)


1
Май бая сме направили 6 та от раз защото поне аз директно copy paste от демото на Цъки за kmp с минимални добавки и 100/100 :D

от Ilian987 (387 точки)

1

Браво Илиане :) Все пак на мен ми отне над 3 часа :)

П.П. Първи събмит в 13:21 последен(за 100 точки) 18:06...всъщност това нещо съм го борил близо 5 часа :(


от MarinMarinov (912 точки)



7
Само дето не разбрах колко пъти ники е бил мишето на топчета :D

от newmast (116 точки)


1

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

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


от simonspirit (412 точки)


0

Guys, забих и си забравих зарядното в залата на 2ет. Моля ако някой го намери / закачено е на контакта :D / да го остави на охраната и утре ще мина да го потърся. Черпя бира :) 

Благодаря :) 


от a.sideriss (450 точки)


0
Аз до последно се пробвах да реша 6та задача с алгоритъма "Knuth-Morris-Pratt", но нещо не ми излезнаха сметките. Изпита си беше тежък, аз лично научих доста от него. Успех на всички по траковете :)



0

При мен нещата се развиха така:

1. Реших, че ми трябва KMP

2. Гугъл + копи/пейст алгоритъма от милия човек, написал го тук

3. Леко донагласяне

100/100


от ykomitov (584 точки)

1
Ето едно решение с KMP - Words. Обаче не можах да го направя да търси 1 символ в текста, затова направих отделна функция с 1 for цикъл да минава и да брои броя на един символ, който се среща.  

от DareDev1l (95 точки)


3
Мен Цъки ме изкефи. Бяха минали около 2 часа и беше с 400++ точки :D

от SDobrev (59 точки)


0
Този изпит е неговата територия :)



0
Много, тъпо се прецаках, пропуснах последната страница и не видях обяснението към нулевият тест  на 6та задача. Половин час си играх да разшифровам какво точно се иска и се отказах, а сега за 20мин. хванах 70т.

от kidroca (1498 точки)


0
Ми тя се решава на 5 реда тази 6-та задача. :D Поне при мен, но за 80 точки. Търсиш 2 стринга с regex и умножаваш броя срещания.
Цъки е машина. Като се опивах да качвам решенията на 2рата задача, която решавах, той вече беше решил 6. :D Хубави бяха задачките.
Лично аз зациклих вече на тази с паролите, оплетох се с рекурсията видях, че нищо вече не ми се получава и напуснах. На втората задача отначалото никакво динамично, реших да пробвам DFS да видя колко точки ще даде. После около 1 час се опитвах да оптимизирам и се получи - от 60 точки скочих на 62 :D
А за първа задача ме е срам да кажа колко време ми отне да се мъча по някакъв терикатски начин да правя remove, за да не отнема O(n) време при HashSet. Какво ли не правих, от string(понеже се remove по Nama) към Unit та обект, ама със същия Hashcode като подобен със същото име, някакъв HashSet от Dictionary<Unit>, накрая реших да пробвам какво толкова ме мъчи да обходя целия HashSet при всяко remove и се оказа, че точно си влиза във времето 0.50 и няколко милисекунди.



0

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


от Mirka (1454 точки)

0
namespace ConsoleApplication2 { using System; using System.Collections.Generic; public class Words { public static void Main() { string word = Console.ReadLine(); string text = Console.ReadLine(); int counter = 0; //make pref-suf pairs //foreach pair count each of the strings and multyply them //combine them in one result //add the count of the whole word in the text Dictionary<string, string> prefixSuffixPairs = new Dictionary<string, string>(); for (int i = 1; i < word.Length; i++) { prefixSuffixPairs[word.Substring(0, i)] = word.Substring(i, word.Length - i); } foreach (var pair in prefixSuffixPairs) { int prefixCount = (text.Length - text.Replace(pair.Key, "").Length) / pair.Key.Length; int sufixCount = (text.Length - text.Replace(pair.Value, "").Length) / pair.Value.Length; counter += prefixCount * sufixCount; } // somewhere from google i copied this regex to find occurences of string in text :) counter += (text.Length - text.Replace(word, "").Length) / word.Length; Console.WriteLine(counter); } } }



2

Брой участници 218, а къде изчезнаха над 160 онлайн, не покриха критериите за явяване или просто са решили да не се явяват?

Иначе задачите бяха добре имаше и лесни и трудни, малко излишно ми се струва това да се цикли по 10ч, така или иначе ако се направи сравнение с резултатите до 16:00 (6 часов изпит) няма да има големи размествания.


от bstaykov (528 точки)


0
Да цъкнеш едно копченце, че се записваш онлайн е много лесно. Да гледаш лекци, предадеш домашни и да отделиш поне 1 седмица за подготовка е друга работа.

от YordanGergov (297 точки)

1
Е не така, там си бяхме на изпита ! Поне за 3-ма гарантирам. Ако се обадят и останалите 157, ще се питаме къде бяха редовните :)

от Mirka (1454 точки)



0
В момента не мога да отворя репото. Коя задача беше с граф?



1
Аз лично реших втора с граф. С топологично сортиране, като задачата за заплатите.

от Mirka (1454 точки)

0
Можеш ли да качиш решението