В тази серия ще разрешим по-важните въпроси, които открихме в книгата Cracking the Coding Interview 6th Edition, използвайки един от най-известните езици за програмиране днес: Python. В книгата намираме 189 въпроса за интервю за програмиране, вариращи от основите до най-трудните проблеми с алгоритмите. Това е доста прилична книга за тези, които искат да се изправят пред някои предизвикателни въпроси относно кода и наистина си струва да бъде прочетена внимателно.
За първия въпрос възможният специалист по набиране на персонал ни моли да„Приложим алгоритъм, за да определим дали даден низ има всички уникални знаци“ и предлага да създадем поне едно решение без използване на структури от данни.
Тук ще използваме три различни подхода за решаване на проблема: Речници, функция Set и в крайното решение ще прегледаме азбуката, за да разберем дали символ вече е бил използван или не в нашия низ.
Практическо кодиране...
Първо, нека си представим, че имаме две групи низове, първият низ string01 има различни главни и неглавни знаци, докато във втората група string02 можем да видим изречение с повтарящи се знаци. За да сме сигурни, че четливостта на нашия низ е наред, ще дефинираме функция, която ще нормализиранизовете, като премахва празните интервали и главните букви.
В нашия първи подход ще използваме структурата от данни на речника, за да съхраним низа и да преминем през всеки знак.
Когато знакът все още не е вмъкнат в речника, програмата ще премине към следващата стъпка и ще добави стойността на „1“ в речника. След като стойността вече е съхранена в структурата на данните, отиваме на следващия знак и проверяваме дали съществува в речника, след като вече е там, просто връщаме False.
За да тестваме нашата програма, ще създадем две променливи, които ще получават нормализираните низове, наречени unique_string и non_unique_string и ще отпечатаме резултата от normalized извикване на функция и след това отпечатайте резултата за проверка на функцията dict_unique.
Нашият втори подход ще използва функция на Python, наречена Set. Модулът за набори предоставя класове за изграждане и манипулиране на неподредени колекции от уникални елементи и това е ключът към използването на набори за това решение. След като елементите най-накрая се нормализират, ще проверим дали дължината на нашия низ е същата като дължината на зададения низ, ако е същата, можем да гарантираме уникалността и след това да върнем True.
В нашия трети и последен подход преминаваме през списъка със знаци в низа, ако вече сме срещнали буква от азбуката в този низ, тя ще бъде премахната от променливата на азбуката, която сме дефинирали, замествайки буквата с “” и след това преминаваме към следващия знак, повтаряйки същия процес, докато стигнем до края.
Ако срещнем символа в нормализирания низ повече от веднъж, програмата ще върне False, след като буквата вече е била премахната от нашата променлива азбука.
Това бяха трите различни начина за решаване на проблема „е уникален“, открит в книгата Интервю за кракване на кодиране с Python. Можете да намерите решението за този и много други проблеми със структурите на данни в моя Github чрез връзката тази.
Очаквайте още проблеми със структурите на данни и решения с Python в моя профил в Medium!
Важно е да запомните, че съм отворен за препоръки и градивна критика, за да развия този комуникационен канал и да намеря по-добри начини за споделяне на подходящо съдържание с вас! До следващия път!
