Leetcode 4. Median of Two Sorted Arrays
m va n uzunlikdagi tartiblangan nums1 and nums2 array’lar berilgan. Ikki array’ning medianini toping. Time complexity O(log(m + n)) bo’lsin.
Suffix array va matnni suffix array’da qayta ishlash
Bizga N belgiga ega matndan so’zni qidirib, barcha so’zlarni topish kerak bo’lsin. To’g’ri, so’zni topadigan tayyor sub-string funksiyalar allaqachon mavjud. Ammo texnik intervyu jarayonida qo’yiladigan masalada tayyor funksiyadan foydalanmaslik kerak bo’ladi. Bunda odatiy yechim – brute-force algoritmi yordamida matndagi barcha belgilar solishtirib chiqiladi. Ishlash vaqti – O(N2), tezkor yechim emas.
MSD Radix sort
LSD Radix sort’da string key’larni o’ngdan chapga tartiblab borgan edik. Albatta, chapdan o’ngga ham tartiblab borishning ham imkoni bor. Buning uchun ro’yhatdagi key’larning bosh harfi (belgisi) bo’yicha tartiblaymiz (Key indexed counting).
LSD Radix sort
Biz o’tgan maqolada ko’rib o’tganimiz – key indexed counting tartiblash boshqa algoritmlar uchun asos bo’lib xizmat qiladi. Shu jumladan, LSD (Least Significant Digit) radix sort algoritmi key indexed counting usulini bir xil uzunlikdagi tartiblanadigan string yoki integer qiymatlarning har bir belgisiga qo’llaydi.
Radix sort. Key indeksli sanoq bilan tartiblash
Key indeksli sanoq (bundan keyin Key indexed counting, KIC) bizga unikal bo’lmagan key’ga ega ro’yhatlarni tartiblash uchun asqotishi bois, dastlab biz tartiblash algoritmlari haqida eslab olamiz.
Minimum spanning tree’ni topish uchun Kruskal algoritmi
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
Heapsort. Binary Heap asosida tartiblash
Heapsort – binary heap ma’lumotlar tuzilmasi asosidagi tartiblash algoritmi. Biz heap har doim ma’lum bir tartibga rioya qilishini bilganimiz uchun, uning bu hususiyatidan tartiblashda foydalanishimiz – array’ning eng katta qiymatini olib uni array’ning ohiriga qo’yib borish orqali array’ni tartiblashimiz mumkin.
Dijkstra’ning uch tomonlama bo’lish (3-way partitioning) algoritmi
Quicksort bilan tanishib chiqqan bo’lsangiz, algoritmda bo’luvchi element (pivot) array’ni ikkiga bo’ladi. Bunda array[pivot]’ning chap tarafida undan kichkina qiymatlar, o’ng tarafida undan katta qiymatlar o’rin oladi. Ushbu algoritmning kamchiligi shundaki – ro’yhatda bir xil qiymatlar ko’p uchraydigan bo’lsa, ishlash vaqti orta boshlaydi.
Tartiblash. Quicksort
Mergesort kabi, Quicksort ham rekursiv algoritm, lekin Quicksort’ning Mergesort’dan farqi – rekursiya ish tugallangach ishga tushadi (Mergesort’da avval rekursiya, keyin ish boshlanardi).
Tartiblash. Mergesort
Mergesort tartiblash jarayonida ro’yhatni (array’ni) ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, … ikki tarafda bittadan son qolguncha bo’lishda davom etadi. Keyin ularni tartiblashni boshlaydi.