Алгоритми и Комплексност - Дупликати и Сортирање

Задача на денот 1

• Функцијата has_duplicates(arr) ја проверува дали даден низ arr содржи дубликати.

• Се пресметува должината на низот n = len(arr).

• Внатрешен циклус се користи за итерирање низ низот.

• Внатрешен циклус се користи за споредба на елементите од низот.

• Ако се најде пар со еднакви елементи, функцијата ја враќа вредноста True.

• Доколку не се наоѓаат дубликати, функцијата ја враќа False.

Задача на денот 2

• Функцијата insertion_sort(arr) сортира даден низ arr со помош на метод на вметнување.

• Овој метод ја вметнува вредноста на секој елемент на соодветното место во сортираниот дел на низот.

• Циклусот се користи за итерирање низ несортираниот дел на низот.

• Вредноста на тековниот елемент се чува во променливата key.

• Елементи се споредуваат со key.

• Кога key е помалку од елементот на лево, елементите се поместуваат на десно, key се вметнува на соодветното место.

• Низот се враќа сортиран.

Алгоритми и Комплексност

• Темата е посветена на алгоритмите.

• Посебно се фокусира на битови алгоритми.

Извадок од "Счупување на интервјуто за кодирање"

• Google обрнува внимание на дизајнирање на скалабилни системи.

• Имплементирање на скалабилност и ограничувања на меморијата.

• Постојат многу прашања за манипулација на битови.

• Интервјуерите нудат повратни информации, кои се проследуваат до комисијата за наем.

• Комисијата за наем дава препораки за одлука.

Извадок од "Счупување на интервјуто за кодирање"

• Наведени се основни податоци:

• Листи од поврзани елементи

• Бинарни дрвја

• Трии

• Пребарување внатре во низи

• Брзо сортирање, сортирање со спојување, е.т.ц.

• Битова манипулација.

Битови

• Битот е основна единица од информации.

• Може да има вредности 0 или 1.

• Обично се користи децималната база за претставување на броевите, но други системи се корисни како бинарниот.

Манипулирање на битови

• Компјутерите ракуваат со нули и единици (битови).

• Битовите се основни елементи во компјутерскиот систем.

• Алгоритмите за манипулирање на битовете се важни.

Битови алгоритми

• Битови алгоритмите се однесуваат на работа со битовите како индивиддни елементи или групи во податочниот простор.

• Тие користат битови операции за манипулирање и добивање информации.

Битови алгоритми - Ефикасност

• Битовите алгоритми се побрзи и користат помалку меморија од редовните аритметички операции.

• Ова се должи на директната работа со битова претставата.

Битови оператори

• Ова се оператори за манипулирање на битови.

• Подобруваат ефикасност во програмите.

Битова оператор табела на вистина

• Табелата покажува како различни битови оператори работат со битови.

Битовски AND оператор (&)

• Оператор & (AND) се користи со битови, проследувајќи правилото дека само ако два битови се 1, rezult е 1; во спротивно, тоа е 0.

• Битовите се изразуваат во бинарниот.

Пример - Код

• a = 7 и b = 4.

• Извршените операции со &, дава резултат од 4.

Битовски OR оператор (|)

• Оператор | (OR) ги споредува битовите. Ако било кој од битовите е 1,, резултатот е 1.

Битовски XOR оператор (^)

• Оператор ^ (XOR) враќа 1 ако битовите се различни. Ако сушта битовите се еднакви, резултатот е 0.

Битовски NOT оператор (~)

• Оператор ~ (NOT) е уникатен оператор што работи на единечен бит.

• Секој бит е инвертиран (0 станува 1, а 1 станува 0).

Лево поместување (<<)

• Левото поместување ја поместува вредноста на битовите надесно.

• Заполнува нули во празните позиции.

Десно поместување (>>)

• Десното поместување го поместува вредноста на битовите налево.

• Обично се користи нула за полнење на празни позиции.

Примена на битовски оператори

• Се користат за подобрување на вградените системи.

• Овозможува проверка на интегритетот на податоците за време на пренесување.

• Се користат во криптографијата и компресијата на податоци.

Практични проблеми на битови алгоритми

• Наведени се проблеми од областа на битови алгоритмите.

Како да се постави бит во число

• Користење на OR (|) оператор за поставување на бит во одредена позиција.

• Лево поместување на 1 за итерирање низ битовите.

Како да се исклучи/исчисти бит во число

• Користење на AND (&) оператор за исклучување/исчистување бит во одредена позиција.

• Битовски NOT (~) оператор се користи за инвертирање на бита.

Смена на бит на nth позиција

• Оператор XOR (^) може да го смени битот на nth позиција.

Дополнително читање и вежби

• "Кракaње на интервјуто за кодирање" - глава 5 (постои како додатна литература, за проучување).