String-lər və immutability
String — mahiyyətcə simvolların ardıcıl massividir. s[3] O(1)-dir, s.length O(1)-dir, string-i gəzmək O(n)-dir — massivlə eyni məntiq.
Əsas fərq: JS, Kotlin (JVM) və Dart-da string-lər immutable-dır. Yəni yaradıldıqdan sonra dəyişdirilə bilmir. s.toUpperCase(), s.replace(...), s + "x" — heç biri s-i dəyişmir, hər biri yeni string qaytarır.
İmmutability-nin səbəbləri praktikdir:
- Təhlükəsiz paylaşma — eyni string-i çoxlu yerdə saxlamaq olar, kimsə onu altından dəyişə bilməz
- Keşlənə bilən hash — hash bir dəfə hesablanıb saxlanılır; buna görə string hash map açarı kimi idealdır
- String interning — eyni məzmunlu literal-lar bir obyekti paylaşa bilər
- Thread təhlükəsizliyi — sinxronizasiya lazım deyil
Dövr içində birləşdirmə niyə `O(n²)`-dir. İmmutability-nin ən vacib praktik nəticəsi budur.
result += word yazanda dil yeni string ayırır və hər iki tərəfi tam kopyalayır. Dövrün i-ci addımında artıq toplanmış uzunluq təxminən i-dir, deməli o addımın dəyəri O(i). Ümumi: 1 + 2 + 3 + ... + n = n(n+1)/2 — yəni `O(n²)`.
Həll — string builder yanaşması: parçaları bir yerdə (massivdə və ya buferdə) yığıb sonunda bir dəfə birləşdirmək. Bu, O(n)-dir.
- JS: parçaları massivə yığ, sonda
parts.join('') - Kotlin:
StringBuildervə yabuildString { } - Dart:
StringBuffervə yaparts.join()
Qeyd: müasir JS mühitləri (V8) qısa dövrlərdə +=-i "rope" optimizasiyası ilə xilas edə bilir, amma buna arxalanmaq olmaz və müsahibədə nəzəri cavab O(n²)-dir.
| Məsələ | Yanaşma | Time | Space |
|---|---|---|---|
| Tərsinə çevirmək | İki pointer (baş və son) və ya simvol massivinə çevirib tərsinə | O(n) | O(n) — string immutable olduğu üçün yeni buffer lazımdır |
| Palindrom yoxlaması | İki pointer mərkəzə doğru gedir; nüsxə çıxarmağa ehtiyac yoxdur | O(n) | O(1) |
| Anaqram yoxlaması | Simvol tezliklərini müqayisə et (map və ya 26 ölçülü massiv) | O(n) | O(k) — əlifba ölçüsü |
| Anaqram — sadə yol | Hər ikisini sırala və müqayisə et | O(n log n) | O(n) |
| Simvol saymaq | Bir gəzintidə hash map-də tezlik yığ | O(n) | O(k) |
| Ən uzun təkrarsız alt sətir | Sliding window + `Set`/`Map` | O(n) | O(k) |
Diqqət yetiriləsi incəliklər — müsahibədə bunları qeyd etmək fərq yaradır.
- Simvol ≠ bayt ≠ kod nöqtəsi. JS və Dart-da string UTF-16 kod vahidlərindən ibarətdir. Emoji və bəzi simvollar iki kod vahidi (surrogate pair) tutur, ona görə
"👍".length2-dir. Azərbaycan hərfləri (ə, ğ, ş, ç, ö, ü, ı) BMP-dədir və bir kod vahididir, amma böyük/kiçik hərf çevrilməsi dilə həssasdır (ı/Iproblemi türk və Azərbaycan dilində klassik səhv mənbəyidir). - Müqayisə: JS-də
===məzmunu müqayisə edir. Kotlin-də==(əslindəequals) məzmunu,===isə istinadı müqayisə edir — Java-dakı==tələsi Kotlin-də yoxdur. Dart-da==string üçün məzmun müqayisəsidir. - Alt sətir çıxarmaq (
substring,slice) adətənO(k)-dir, çünki nüsxə yaradılır — dövr içində çağırılanda gizliO(n²)mənbəyidir.
İnterview məsləhəti. "String-i tərsinə çevir" və "palindrom yoxla" ən çox verilən isinmə suallarıdır. Müsahib əslində üç şeyə baxır: (1) iki pointer texnikasını bilirsənmi, (2) mürəkkəbliyi deyirsənmi, (3) sərhəd hallarını soruşurmusan.
Kod yazmazdan əvvəl bu sualları ver: boşluqlar və durğu işarələri nəzərə alınır? Böyük/kiçik hərf fərqi vacibdir? Unicode/emoji ola bilər? Boş string nə qaytarmalıdır? Bu suallar tək başına səni namizədlərin əksəriyyətindən yuxarı qaldırır.
Ən çox rast gəlinən səhvlər: dövr içində += işlədib mürəkkəbliyi O(n) demək; palindrom üçün string-i tərsinə çevirib müqayisə etmək (işləyir, amma əlavə O(n) yaddaş tutur — iki pointer O(1)-dir); anaqram üçün sıralama seçib O(n) tezlik həllini heç ağla gətirməmək.
📚 Mənbələr və sənədlər
- Stringrəsmideveloper.mozilla.org