Dasturchi, frilanser, gik va introvert
Giant tech korporatsiyalardan biriga ishga kirish uchun tayyorgarlik jarayonida o’rganganlarim – algoritmlar, ma’lumot tuzilmalari haqida maqolalar
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.
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.
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.
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).
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.
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.
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?
Avvalgi maqolada maximum flow allaqachon topilgan graph’ni ko’rib o’tdik. Endi flow’ni qanday hisoblash haqida so’z yuritamiz.
Graph processing masalalarini o’rganishni davom ettiramiz. Minimum cut – graph’ni ikkiga shunday bo’lish kerakki, uning bo’linish edge’lari bir-biriga eng kam (kuchsiz) bog’langan joyi bo’lsin. Oddiyroq aytganda, graph’ni ikkiga bo’lish uchun eng kam harajat / kuch talab etilsin.
Ushbu maqolada biz negativ (manfiy) weight’larning graph’da shortest path’ni topishdagi ta’sirini ko’rib chiqamiz. Avvaldan aytib o’tish kerakki, negativ weight’lari bor graph’lar uchun bir ko’rib o’tgan Dijkstra algoritmi ishlamaydi.