Trie ma’lumot tuzilmasida string amallari
Ushbu maqolada biz ba’zi string amallarini R-way trie ma’lumot tuzilmasida ko’rib o’tamiz.
Ternary search tries
Ternary search tries (TST, uchlamchi qidiruv trie) R-way tries’dagi kamchilikka yechim o’laroq tavsiya etiladi. TSTda belgilar indeks ko’rinishida emas, node ichida saqlanadi (R-way tries’da belgilar indeks nomer sifatida saqlanardi). Shuningdek har bir node uch child’ga ega: kichikroq (chap), teng (o’rtada), kattaroq (o’ngda).
R-way tries
Ushbu mavzu string key’lar qidiruvi uchun mo’ljallangan ma’lumotlar tuzilmasi – tries (trays) haqida bo’ladi. Shu vaqtgacha ko’rib o’tgan ma’lumotlar tuzilmalaridan qidiruv uchun eng yaxshisi red-black tree – key’ni qidirish / qo’shish / o’chirish uchun O(log N) vaqtni kafolatlardi.
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.
3-way Radix Quicksort
Dijkstra’ning 3-way partitioning quicksort algoritmi bilan tanishib chiqqan bo’lsangiz kerak. U quicksort’dagi bir xil key’lar uchragan holatida ishlash vaqti ortishini oldini oladi. Biz 3-way quicksort’ga qaytamiz, bu safar bo’luvchi element – pivot’ni key belgilaridan olamiz.
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.
Ford-Fulkerson algoritmini kodda ifodalash
Maximum flow’ni topish jarayonida, ba’zida yechimga erishish uchun allaqachon berilgan flow’ni kamaytirish hisobiga boshqa (parallel) edge’da flow’ni oshiriladi. Inson ko’zi bilan ko’rib, qaysi flow’ni kamaytirish, qaysi flow’ni oshirishni o’zi aniqlab olishi mumkin, lekin kodda nima qilishni qanday ifodalaymiz?
Maximum flow’ni topish uchun Ford-Fulkerson algoritmi
Avvalgi maqolada maximum flow allaqachon topilgan graph’ni ko’rib o’tdik. Endi flow’ni qanday hisoblash haqida so’z yuritamiz.