Loading...
djc_bg2015 avatar djc_bg2015 923 Точки

[Exam] Data Structures 27-MARCH - Впечатления

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

ще ми е интересно да споделите как "видяхте" изпита.

Аз лично не съм доволен от представянето си, тотално забих на тези suffix-и и от 12:30 до 3 само това правих....

След десетки опити така и не можах да мина performance тестовете :|  и в крайна сметка набих една ламбда, колкото да минат поне correctness тестовете :)

Наистина жалко, че неможахме да си напишем (сами) първа задачка :P

 

От мен толкова:


 

Тагове:
4
Структури от данни и алгоритми 27/03/2016 18:24:24
krasi070 avatar krasi070 22 Точки

Здрасти,

И аз като теб доста се чудех на suffix-ите, но към края на изпита се сетих как да ги напарвя. Това, което не се сетих е как да направя detonate-а бърз(само половината от тестовете му за бързина ми минаха). Всичко друго мина на моя компютър и само този detonate ми остана:)

Иначе, ако някой иска да види как аз съм подходил, ето моето решението: 

https://github.com/krasi070/DataStructures/tree/master/Exam

2
HPetrov avatar HPetrov 822 Точки

20 минути сигурно убих за единия тест на Detonate докато се усетя, че всъщност напразно обхождам колекциите когато имаш само 1 team. Една бърза проверка в началото дали броя на отборите е <= 1 и всичко полетя в зелено за тоя метод :)

 

1
tilchev92 avatar tilchev92 Trainer 128 Точки

Май направихме темите по едно и също време. Няма смисъл според мен да се използва Reverse в компаратора при положение, че стриновете могат да се обходят с обратен фор. А ако все пак се ползва по-добре да е:

str = str.Reverse().ToString();

a не:

str = new string(str.Reverse().ToArray());

Като цяло задачата беше много готина - поздравления на авторите.

Ето го и моето решение ако някой му е интересно. Със сигурност имам някоя излишна структура - bunnysByTeam сравнително лесно може да се махне.

Тестовете (PerformanceDetonate_WithOneBunnyDetonatingMultipleTimes_With10000BunniesInOneRoomInDifferentTeams го подкарах след изпита)

3
27/03/2016 18:50:40
djc_bg2015 avatar djc_bg2015 923 Точки

char.MaxValue + suffix .... (как не се естих)

заспала работа моята :D, пробвах с RangeFrom, RangeTo, пробвах при добавянето да вкарвам всеки възможен съфикс в речник suffix,orderedset<bunny> ... но това не ми дойде на акъла :D

Здраве да е!

Наистина поздравления за задачката, беше забавна :)

 

2
HPetrov avatar HPetrov 822 Точки

Убии ме, това решение за suffix-а откъм performance нямаше да се сетя. PerformanceDetonate_WithOneBunnyDetonatingMultipleTimes_With10000BunniesInOneRoomInDifferentTeams  теста ми минаваше през по-голяма част от времето 50/50 (а мине а не) но в един момент реши да минава всеки път но доста близко до границата >_>

0
djc_bg2015 avatar djc_bg2015 923 Точки

Ще споделиш ли как си направил suffix-a?

ПС: имах същия проблем с детонейт

0
27/03/2016 20:39:44
supersane avatar supersane 234 Точки

Наистина беше интересна задачата и си падна бая главоблъскане, изгубих доста време в това да сменям структури, докато най-накрая оцеля тези, които всъшност ми бяха най-подходящи, и от там не ми остана време да си поблъскам главата повечко за performance на suffix-ите, може би ако имах още 30-40 минути, щях да ги хвана, просто не можех да си напасна правилното използване на рейндж. Гърмят ми и 2 performance теста на детонейта, там ми е бая мазало, трябва да разгледам някое решение с бърз детонейт.

1
ktodorov avatar ktodorov 42 Точки

Здравейте,

Ето и моето решение. Всички тестове ми минаха smiley

Частта със suffix-ите съм я решил по малко бавен начин и в началото не минаваше всичко, но добавих оптимизация - като един suffix мине, след това, ако се повтори, вече го имам в dictionary :)

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

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

https://github.com/ktodorovv/Data-Structures-Exam-27-March-2016/

0
psdimitrov avatar psdimitrov 75 Точки

Здравейте,

И на мен ми хареса задачата.

Относно suffix-ите, като видях в условието, че трябва да са сортирани по ASCII кода на обърнатото име, ми дойде на акъла да пазя обърнатите имена в OrderedDictionary с обикновен Ordinal Comparator, който не се налага да си пиша сам и да сведа търсенето по суфикс, до търсене по префикс.

А относно това:

str = str.Reverse().ToString();

Няма да работи, защото ToString() ще върне нещо подобно:

System.Linq.Enumerable+<ReverseIterator>d__74`1[System.Char]

 Аз лично обръщах имената с:

reversedName = string.Join("", name.Reverse());

Ето го моето решение:

https://github.com/psdimitrov/DataStructures/tree/master/Exam/BunnyWars

 Поздрави!

3
tilchev92 avatar tilchev92 Trainer 128 Точки

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

0
butanfire avatar butanfire 32 Точки

Много забавно начало и много яка задача!! :Д

Да споделя и аз неволя :))
1) Неможах да си изтегля за доста дълго време Wintellect-a , заради прекаленото дълго име на пътя на проекта!!! :D

2) Още една обеца на ухото - Ползвах suffix функцията от First-Last, и не се усетих да махна цикъла tring.EndsWith" ", понеже дървото си ми ги дава подредени през компаратора :))
3) Също така не се усетих, че структурата OrderedDictionary<string,SortedSet<Bunny>> която ползвах за вземане на заек (ползвах я в почти всички функции свързани с BunnyName и т.н.- която ползваше компаратора, ми забави всичките функции.
Попитах Наско защо ми се забавиха всички функции - еми не трябва да се ползва тази структура освен за List Preffix-a! :D докато се усетя обаче - още загуба на време - и трябваше да си правя нова за вземането на зайци :))
Докато смелям всичко и неусетно времето мина, точно накрая мъчих само 3-те последни Performance за List Suffix - и не успях да си предам на време оправената функция от 2)

Готин изпит и много ценни уроци дава всеки път!

Поздрави и успех на занапред!

Владо

0
a_rusenov avatar a_rusenov 1103 Точки

Всички материали от изпита (условия, скелети, авторски решения) са качени в страницата на курса.

Резултати може да очаквате до началото на курса по Алгоритми.

Като обобщение решението е следното:

  • "Главната структура", в която пазим всички зайци е Dictionary<string, Bunny> за бързо добавяне / търсене / триене.
  • Оттук нататък ни трябват операциите AddRoom, RemoveRoom (бързо добавяне/триене на стая) и Previous/Next (трябва ни ред, за да достъпим съседните стаи). За да имаме подредба и бързо добавяне / търсене / триене на стаи, ползваме подредено дърво (Ordered-нещо си). Може би OrderedSet<int>.
    • Detonate (бие демидж на зайци от чужд отбор в стаята) -> очевидно изисква пазене на зайци за съотвена стая. Следоветелно горната структура може би е OrderedDictionary<int, List<Bunny>>. Обаче при детонация трябва да проверяваме всеки един заек дали е от различен тийм. При наличието на тестове от сорта 10000 заека от 1 тийм в 1 стая това ще е бавно. Затова я модифицираме на OrderedDictionary<int, List<Bunny>[]>. С други думи пазим стаите подредени и за всяка - масив от отборите (защото са винаги най-много 5). А за всеки един отбор пазим зайците в него.
    • По условие обаче Detonate може да убие зайци и те ще трябва да бъдат премахнати. Триенето в List е O(n), затова можем да жертваме памет за сметка на бързо триене като използваме LinkedList. И като резултат имаме OrderedDictionary<int, LinkedList<Bunny>[]>.

А как става next / previous? Понеже е OrderedDictionary и стаите са подредени, RangeFrom(roomId, false) връща всички стаи след текущата и с Take(1) можем да вземем следващата.

Същото е и с Previous, само че ползваме RangeTo(roomId, false), за да получим енумератор за всички стаи преди текущата. Даваме .Reversed(), за да обхожда енумераторът наобратно, и пак вземаме първата.

this.rooms.RangeFrom(roomId, false).Take(1);
this.rooms.RangeTo(roomId, false).Reversed().Take(1);

Друг вариант е да пазим стаите в един допълнителен OrderedSet<int> и да ползваме IndexOf(roomId), за да вземем индекса на стаята в черно-червеното дърво отдолу. Оттам нататък казваме roomsSet[index + 1] или roomsSet[index - 1].

Остават 2 метода:

  • ListBunniesByTeam по име в низходящ ред. Имаме фиксиран брой отбори и за всеки един трябва да пазим зайците подредени -> OrderedSet<Bunny>[]. В метода връщаме bunniesByTeam[team].Reversed().
  • ListBunniesBySuffix, сортирани по име в обратен ред (отзад-напред по стринга) -> ползваме OrderedSet<Bunny>. Тук подредбата е по-интересна и трябва да подадем custom comparator, който да сравнява както е описано в условието. Този comparator e де факто Ordinal, с тази разлика, че е наобратно. Tочно както на подготовката си написахме компаратор за префиксите, така и в тази задача правим същия, но сега цикълът започва от края на стринговете:
public class OrdinalSuffixComparator : IComparer<Bunny>
{
    public int Compare(Bunny bunnyX, Bunny bunnyY)
    {
        var x = bunnyX.Name;
        var y = bunnyY.Name;
        for (int iX = x.Length - 1, iY = y.Length - 1;
            iX >= 0 && iY >= 0; iX--, iY--)
        {
            if (x[iX] > y[iY]) return 1;
            if (x[iX] < y[iY]) return -1;
        }

        if (x.Length == y.Length) return 0;
        if (x.Length > y.Length) return 1;

        return -1;
    }
}

Имайки зайците подредени по това правило, можем да ги извлечем с един Range().

var low = new Bunny(suffix, 0, 0);
var high = new Bunny(char.MaxValue + suffix, 0, 0);

return this.bunniesOrderedBySuffix.Range(low, true, high, false);

Всички имена по-големи или равни на suffix или започват с него, или са с по-големи символи. За да не хванем и "по-големите" стрингове, слагаме горна граница char.MaxValue + suffix. По условие всички имена ще са с латински букви или цифри. Т.е. няма да има символ с по-голям ASCII код от MaxValue. Следователно, ако един стринг е по-голям от горната граница, то значи някой символ след MaxValue e по-голям -> има различен суфикс и затова попада извън горната граница.

Радвам се, че задачата ви е харесала. Мога само да съжалявам за първа, но пък нищо не пречи да си я решите сега (ще ви трябва за алгоритмите :D).

13
28/03/2016 13:11:19
supersane avatar supersane 234 Точки

Здравейте, тъй като трябваше да очакваме резултати до началото на круса по алгоритми, а курсът започва днес. Аз все още нямам резултат от изпита, и при другите явили се колеги ли е така?

0
djc_bg2015 avatar djc_bg2015 923 Точки

Не мисля че проблема е при теб, просто оценките не са излезли. (и при мен няма)

0
supersane avatar supersane 234 Точки

Значи, все още чакаме. :)

0
g_popov avatar g_popov 15 Точки

Колеги, мина доста време от изпита, все още ли нямате резултати?

4
evgenikolov avatar evgenikolov 304 Точки

Май се оказа доста трудоемко оценяването на 1 задача с написани Unit тестове при положение, че резултатите се очакваха са излязат около 5-ти, а днес сме 11-ти.

Някой с по-актуална информация кога да очакваме резултати? 

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