Question 1

Linked list-də cycle olub-olmadığını necə yoxlayarsan?

Accepted Answer

Bu suala iki həllə cavab ver — bir həll deyən namizəd orta, iki həlli müqayisə edən namizəd yaxşı qiymətləndirilir. Həll 1 — hash set: gəzdiyin node-ları Set-ə əlavə edirsən; artıq gördüyün node-a rast gəlsən, cycle var. O(n) vaxt, O(n) yaddaş. Üstünlüyü: 5 sətirdir, səhv etmək çətindir, üstəlik dövrənin başlanğıcını birbaşa verir. Həll 2 — Floyd (tortoise and hare): slow bir addım, fast iki addım atır; görüşürlərsə cycle var, fast null-a çatırsa yoxdur. O(n) vaxt, O(1) yaddaş. Niyə Floyd işləyir — bunu izah etmək cavabın özəyidir: "İkisi də dövrənin içinə düşəndən sonra aralarındakı məsafə hər addımda düz 1 azalır, çünki fast 2, slow 1 addım atır. Tam ədəd azalaraq 0-a çatmalıdır — deməli üstündən tullanmadan görüşürlər." Kodda diqqət: while (fast != null && fast.next != null) — bu yoxlama olmadan fast.next.next null üzərində partlayır. Bu, ən çox tutulan səhvdir. Seçim: "Yaddaş məhdudiyyəti qeyd olunmayıbsa, hash set-lə başlayardım, çünki sadədir və oxunaqlıdır. Yaddaş kritikdirsə və ya intervyuer O(1) istəyirsə, Floyd-a keçərəm." Bu cümlə praktik mühakimə göstərir — real kodda oxunaqlılıq da bir meyardır. Davam sualına hazır ol: "Dövrə harada başlayır?" demək olar həmişə arxadan gəlir.

Question 2

Dövrənin başlanğıc node-unu necə taparsan və niyə bu üsul işləyir?

Accepted Answer

Alqoritm: pointer-lər görüşəndən sonra birini head-ə qaytar, digərini görüş nöqtəsində saxla, indi hər ikisini bir addımla apar. Görüşdükləri node dövrənin başlanğıcıdır. Niyə işləyir — bu hissə cavabı fərqləndirir. Məsafələri adlandır: a = head-dən girişə, b = girişdən görüş nöqtəsinə, c = görüş nöqtəsindən yenidən girişə. Dövrənin uzunluğu b + c. Yavaş a + b addım atıb; sürətli iki dəfə çox atıb və k dəfə dövrə vurub: a + b + k(b + c) = 2(a + b). Buradan a = (k−1)(b + c) + c. Yəni a ilə c tam dövrələr fərqi ilə bərabərdir — head-dən girişə qədər getmək, görüş nöqtəsindən girişə qədər getməklə eyni sayda addımdır. Ona görə eyni sürətlə gedən iki pointer məhz girişdə qarşılaşır. İnterview taktikası: bütün çıxarışı yazmağa ehtiyac yoxdur və vaxt itirmək riskidir. "Hesablama göstərir ki, a ilə c bərabər olur, ona görə işləyir" demək kifayətdir; intervyuer dərinləşmək istəsə, lövhədə açarsan. Əsas odur ki, bunu əzbərlədiyin bir hiylə kimi deyil, əsaslandırılmış nəticə kimi təqdim edəsən. Sadə alternativ: hash set ilə cycle-ı yoxlayanda ilk təkrar görülən node onsuz da dövrənin başlanğıcıdır — heç bir riyaziyyat lazım deyil, əvəzində O(n) yaddaş. Bu alternativi qeyd etmək "həmişə ən mürəkkəb həlli seçmirəm" siqnalı verir.

Question 3

"Happy number" məsələsi ilə linked list cycle detection arasında hansı əlaqə var?

Accepted Answer

Bu sual abstraksiya səviyyəsində düşünə bilməyini yoxlayır — cavabın dəyəri məhz oradadır. Əlaqə: Floyd alqoritmi əslində linked list haqqında deyil. Ona lazım olan yeganə şey — hər vəziyyətdən yalnız bir növbəti vəziyyətə keçid verən funksiyadır. Linked list-də bu funksiya node.next-dir. Happy number-də isə "rəqəmlərin kvadratları cəmi" funksiyasıdır: 19 → 82 → 68 → 100 → 1. Yəni hər ədəd bir node, next(x) isə pointer rolunu oynayır. Ardıcıllıq ya 1-ə çatır (xoşbəxt ədəd), ya da təkrarlanan dövrəyə düşür (xoşbəxt deyil). Üçüncü variant yoxdur, çünki dəyərlər məhduddur. Kod praktiki olaraq eynidir: slow = next(slow), fast = next(next(fast)), fast == 1 və ya slow == fast olana qədər. Ümumiləşdirmə — bu cümlə cavabı gücləndirir: "Bu pattern funksional qraf adlanır — hər node-un düz bir çıxan edge-i var. Belə qraf həmişə 'quyruq + dövrə' formasındadır. Ona görə Floyd bütün belə məsələlərdə işləyir: happy number, təkrarlanan psevdotəsadüfi ardıcıllıqlar, nums[i] → i keçidi ilə massivdə təkrarlanan ədədi tapmaq." Sonuncu nümunə xüsusilə dəyərlidir: 1..n diapazonunda n+1 ədəd verilib, təkrarlanan birini tap — massivi dəyişmədən və O(1) yaddaşla. i → nums[i] keçidi funksional qraf yaradır və təkrarlanan ədəd məhz dövrənin başlanğıcıdır. Bu bağlantını qura bilmək middle-dan yuxarı siqnaldır. Alternativ də de: hash set ilə görülmüş dəyərləri saxlamaq eyni nəticəni verir, O(n) yaddaşla — sadə və oxunaqlı.

Question 4

Linked list-in ortasını bir keçiddə necə taparsan? İki keçidli həlldən nə ilə fərqlənir?

Accepted Answer

İki keçidli həll: əvvəlcə siyahını gəzib uzunluğu say (n), sonra yenidən başlayıb n/2 addım at. Sadədir və işləyir: O(n) vaxt, O(1) yaddaş. Bir keçidli həll: slow bir addım, fast iki addım atır. Fast sona çatanda slow ortadadır — çünki fast iki dəfə sürətlidir. Yenə O(n) vaxt, O(1) yaddaş. Fərq nədir? — sualın əsl mahiyyəti budur və cavabı dürüst vermək lazımdır: asimptotik olaraq heç bir fərq yoxdur. Hər ikisi O(n). Bir keçidli variant siyahını iki dəfə yox, bir dəfə gəzir — yəni sabit əmsal iki dəfə kiçikdir, amma Big O eynidir. Bəs onda nə vaxt həqiqətən vacibdir? Üç halda: Data axındırsa (stream) — məlumatı ikinci dəfə oxumaq mümkün deyil; bir keçid məcburidir Siyahı çox uzundursa və cache mühümdürsə — iki keçid iki dəfə yaddaş müraciəti deməkdir Uzunluq bilinmirsə və hesablamaq bahadırsa Vacib detal — cüt uzunluq: 4 node-luq siyahıda "orta" hansıdır, 2-ci yoxsa 3-cü? Standart şablon ikincisini qaytarır. Birincisi lazımdırsa döngə şərtini dəyişirsən. İnterview-da bunu soruşmaq lazımdır: "Cüt uzunluqda hansı ortanı istəyirsiniz?" Bu sual diqqətlilik siqnalıdır və çox namizəd onu vermir. Praktik istifadə: bu texnika linked list-i merge sort ilə sıralamağın və "palindromdurmu" məsələsinin ilk addımıdır — ortanı tapıb ikinci yarını çevirirsən. Bu bağlantını qeyd etmək texnikanın izolyasiya olunmuş hiylə olmadığını göstərir.

Question 5

Sondan k-cı elementi tapmaq üçün two pointers necə tətbiq olunur?

Accepted Answer

İdeya: iki pointer arasında sabit k məsafə saxlayırsan. Birincini k addım irəli apar, sonra hər ikisini birlikdə hərəkət etdir. Birinci sona çatanda ikinci sondan k-cı node-dadır. Niyə işləyir: aralarındakı fərq heç vaxt dəyişmir. Birinci n-ci mövqedədirsə, ikinci n − k-dadır. Bu, fast/slow-un "fərqli sürət" yox, "fərqli başlanğıc" variantıdır — eyni ailənin ikinci üzvü. Mürəkkəblik: O(n) vaxt, O(1) yaddaş, bir keçid. Edge case-lər — bunları ucadan sadala, çünki sual məhz onlara görə verilir: k siyahının uzunluğundan böyükdürsə? İlk pointeri k addım aparanda null-a çatırsan — null qaytar və ya xəta at, davranışı intervyuerlə dəqiqləşdir k == n (yəni birinci element) — bu, xüsusilə silmə məsələsində problem yaradır, çünki head-in özünü silmək lazım gəlir k == 0 və ya mənfi — girişin etibarlılığını yoxla Ən çox rast gəlinən davamı: "Sondan k-cı node-u SİL." Burada bir incəlik var: silmək üçün silinəcək node-un əvvəlkinə çatmalısan, yəni pointeri bir addım geridə saxlamalısan. Praktik hiylə — dummy head node-u əlavə etmək: dummy.next = head. Bu, "birinci elementi silmək" xüsusi halını adi hala çevirir və kodu 5 sətir qısaldır. Dummy head texnikasını bilmək linked list məsələlərində ciddi üstünlükdür və interview-da xüsusi qeyd olunur. İki keçidli alternativ: uzunluğu say, sonra n − k addım at. Eyni mürəkkəblik, iki keçid — axın datasında işləmir.

Məsələ	Necə tətbiq olunur	Yaddaş
Linked list-də cycle varmı?	slow 1 addım, fast 2 addım; görüşürlərsə cycle var	O(1)
Cycle harada başlayır?	Görüşdən sonra birini head-ə qaytar, ikisini də 1 addımla apar	O(1)
Siyahının ortası (bir keçiddə)	fast sona çatanda slow ortadadır	O(1)
Sondan k-cı element	Bir pointeri əvvəlcə k addım irəli apar, sonra ikisini birlikdə	O(1)
Happy number tipli məsələlər	"Növbəti dəyər" funksiyası gizli linked list yaradır; dövrə = xoşbəxt deyil	O(1)
Massivdə təkrarlanan ədədi tapmaq (1..n)	`i → a[i]` keçidi qraf yaradır; təkrar dövrənin başlanğıcıdır	O(1) — massivi dəyişmədən
Linked list palindromdurmu?	Ortanı tap, ikinci yarını çevir, müqayisə et	O(1)

Fast/slow pointers və cycle detection