Question 1

İç-içə dövrə ilə O(n²) həllini hash strukturu ilə O(n)-ə necə çevirirsən? Nümunə ilə izah et.

Accepted Answer

Bu, müsahibədə ən çox işə yarayan tək cavabdır, ona görə onu bir şablon kimi hazır saxla. Əvvəl ümumi prinsipi de: "İç-içə dövrə əslində 'bu elementə uyğun gələn başqa element varmı?' sualını verir. Mən həmin sualı hər dəfə massivi gəzərək yox, artıq gördüklərimi bir Map/Set-də saxlayaraq O(1)-də cavablandırıram." Sonra two-sum nümunəsini göstər: "nums[i] üçün lazım olan tərəf-müqabil dəqiq məlumdur — target - nums[i]. Bir keçiddə gedirəm; hər addımda əvvəlcə map-da target - nums[i]-ni axtarıram, tapmasam cari dəyəri indeksi ilə map-a yazıram. Axtarışı yazmadan ƏVVƏL etmək vacibdir, yoxsa element özü ilə cütləşə bilər." Mürəkkəbliyi mütləq hər iki ölçü üzrə de: O(n) vaxt, O(n) əlavə yaddaş — və bunun şüurlu trade-off olduğunu vurğula. Sonda dürüstlük əlavəsi güclü təsir bağışlayır: "n çox kiçikdirsə, O(n²) həll sadəliyinə görə daha yaxşı seçim ola bilər — bu qərarı input ölçüsünə baxaraq verirəm."

Question 2

Massivdə təkrarlanan element olub-olmadığını necə tapardın? Bir neçə yanaşma müqayisə et.

Accepted Answer

Bu sual seçim etmək bacarığını yoxlayır, ona görə bir həll yox, üçünü müqayisə et: İç-içə dövrə: O(n²) vaxt, O(1) yaddaş. Sadədir və əlavə yaddaş tələb etmir — yaddaş həqiqətən çox məhduddursa yeganə variantdır. Sıralayıb qonşuları müqayisə etmək: O(n log n) vaxt, sıralama yerində aparılırsa O(1) əlavə yaddaş. Amma orijinal massivi dəyişir — bu, çox vaxt qəbuledilməzdir. Seen-set: O(n) vaxt, O(n) yaddaş. Bir keçiddə işləyir və ilk təkrarı tapan kimi dayanır, yəni praktikada çox vaxt n-ə də çatmır. Sonra seçimi əsaslandır: "Default seçimim Set-dir, çünki adətən vaxt yaddaşdan bahadır. Amma məhdud yaddaşlı mühitdə (embedded, çox böyük data) sıralama yanaşmasını seçərdim." İdiomatik detal əlavə etmək yaxşı təəssürat yaradır: Kotlin-də seen.add(n) false qaytarırsa element artıq var — ayrıca contains çağırışına ehtiyac yoxdur; Dart-da eyni davranış var. Bu, bir yoxlamanı bir əməliyyata yığır.

Question 3

"Cəmi k olan altmassivlərin sayını tap" tapşırığını necə həll edərdin?

Accepted Answer

Əvvəl sadəlövh həlli adlandır ki, müsahib düşüncə xəttini görsün: "Hər başlanğıc üçün hər bitiş nöqtəsini yoxlamaq O(n²)-dir." Sonra çevrilməni riyazi olaraq göstər — bu, cavabın nüvəsidir: "sum(i..j) = prefix[j] - prefix[i-1]. Mən = k istəyirəm, deməli prefix[i-1] = prefix[j] - k. Yəni j nöqtəsində dayanıb soruşuram: indiyə qədər prefix - k dəyərini neçə dəfə görmüşəm? Bu, hash map lookup-dır." Alqoritmi qısa ver: bir keçid, prefix toplanır, counts.get(prefix - k) cavaba əlavə olunur, sonra counts[prefix] bir artırılır. Vaxt O(n), yaddaş O(n). Mütləq seed-i qeyd et — müsahiblərin gözlədiyi detal budur: counts = {0: 1} başlanğıc dəyəri massivin əvvəlindən başlayan altmassivləri saymaq üçündür. Bunu unutmaq [1,1,1], k=2 kimi testlərdə səhv nəticə verir. Sonda mənfi/sıfır dəyərləri xatırlat: sliding window burada işləmir, çünki cəm monoton artmır — prefix + map yanaşması isə mənfi ədədlərlə də düzgün işləyir. Bu qeyd cavabı middle-dən yuxarı qaldırır.

Question 4

Hash əsaslı həll nə vaxt YANLIŞ seçimdir?

Accepted Answer

Bu sual namizədin aləti kor-koranə tətbiq edib-etmədiyini yoxlayır, ona görə konkret hallar say: Sıralı çıxış lazımdırsa: hash heç bir sıra saxlamır. "Ən kiçik 10 element", "k-dan böyük bütün açarlar" kimi tələblərdə balanslaşdırılmış ağac (TreeMap/SplayTreeMap), sıralı massiv və ya heap düzgün seçimdir. Diapazon sorğuları: [a, b] aralığındakı açarları hash ilə tapmaq üçün hamısını gəzmək lazımdır — O(n). Sıralı struktur bunu O(log n + k) edir. Yaddaş kritikdirsə: O(n) əlavə yaddaş həmişə mövcud olmur. Embedded mühitdə və ya çox böyük datada sıralama + iki göstərici yanaşması daha uyğundur. Prefiks axtarışı: "'ka' ilə başlayan bütün sözlər" sualında hash faydasızdır — bu, trie-nin işidir. Çox kiçik n: 10-20 element üçün hash qurmağın overhead-i sadə xətti axtarışdan baha ola bilər. Pis hal zəmanəti tələb olunursa: hash orta halda O(1)-dir; real-time və ya təhlükəsizlik kritik sistemlərdə pis halın O(n) olması qəbuledilməz ola bilər — orada balanslaşdırılmış ağacın O(log n) zəmanəti üstündür. Bağlayıcı cümlə güclü təsir bağışlayır: "Hash-i default seçim kimi götürürəm, amma tələbdə sıra, diapazon və ya prefiks sözlərini eşidəndə dərhal ağac və ya trie tərəfə baxıram."

Question 5

Hash əsaslı həllin mürəkkəbliyini müsahibədə necə düzgün ifadə edərsən?

Accepted Answer

Burada üç dəqiqləşdirmə səni orta namizəddən ayırır. Birincisi — orta halı pis haldan ayır. "O(1)" demək yarımçıqdır. Düzgün forma: "Hash lookup orta halda O(1)-dir; pis halda, bütün açarlar eyni bucket-a düşərsə, O(n) ola bilər. Praktikada müasir runtime-lar hash randomization və tree-ification ilə bunu qorumur." İkincisi — yaddaşı da de. Vaxt mürəkkəbliyini deyib yaddaşı susmaq ən çox buraxılan şeydir. Həmişə cüt kimi ifadə et: "O(n) vaxt, O(n) əlavə yaddaş." Üçüncüsü — açarın hash-lənməsinin qiymətini unutma. Açar string-dirsə, hash uzunluqdan asılıdır: n sözü hash-ləmək əslində O(n·L)-dir, L orta söz uzunluğudur. Anagram bucketing-də isə hərfləri sıralamaq əlavə O(k log k) gətirir — ümumi O(n·k log k). Bu detalı özün qeyd etsən, müsahib dərhal görür ki, sən mürəkkəbliyi əzbərləmirsən, hesablayırsan. Bir də amortizə olunmuş dəyəri düzgün adlandır: map böyüyəndə rehash O(n) çəkir, amma n əməliyyata bir dəfə olduğu üçün əməliyyat başına amortizə olunmuş dəyər O(1) qalır.

Pattern	Struktur	Nə vaxt tanıyırsan	Mürəkkəblik
Frequency counter	Map: dəyər → say	"neçə dəfə", "ən çox təkrarlanan", "anagram-dırmı"	O(n) vaxt / O(k) yaddaş
Complement lookup	Map: dəyər → indeks	"cəmi target olan iki ədəd"	O(n) / O(n)
Bucketing / grouping	Map: normallaşdırılmış açar → siyahı	"qruplaşdır", "eyni ... olanları birləşdir"	O(n·k) / O(n)
Seen-set	Set: görülmüş elementlər	"təkrar varmı", "dövr varmı", "unikal"	O(n) / O(n)
Prefix sum + map	Map: prefiks cəmi → say/indeks	"cəmi k olan altmassivlərin sayı"	O(n) / O(n)

Hash ilə interview pattern-ləri