🧩 8.6: Hash Table Örnek Sorular

# =========================================
# KELİME FREKANS SAYICI
# =========================================

def kelime_frekans(metin):
    """
    Metindeki her kelimenin kaç kez geçtiğini say
    Zaman: O(n) - n kelime sayısı
    Alan: O(k) - k unique kelime sayısı
    """
    frekans = {}  # Hash table
    
    # Metni kelimelere ayır
    kelimeler = metin.lower().split()
    
    for kelime in kelimeler:
        # Noktalama işaretlerini temizle
        kelime = kelime.strip('.,!?;:"')
        
        # Hash table'da say
        if kelime in frekans:
            frekans[kelime] += 1
        else:
            frekans[kelime] = 1
    
    return frekans

# Test
metin = """
Python programlama dilini öğreniyorum. Python çok güzel bir dil.
Python ile veri yapıları öğrenmek eğlenceli. Veri yapıları önemli.
"""

frekans = kelime_frekans(metin)

print("=== Kelime Frekansları ===")
# En sık kullanılandan az kullanılana sırala
sirali = sorted(frekans.items(), key=lambda x: x[1], reverse=True)

for kelime, sayi in sirali:
    print(f"{kelime:15} : {'█' * sayi} ({sayi})")

# En çok kullanılan 3 kelime
print("\n🏆 En Çok Kullanılan 3 Kelime:")
for i, (kelime, sayi) in enumerate(sirali[:3], 1):
    print(f"{i}. {kelime} ({sayi} kez)")

# Alternatif: Counter kullan (yerleşik)
from collections import Counter
frekans2 = Counter(metin.lower().split())
print(f"\n✅ Counter ile: {frekans2.most_common(3)}")

# =========================================
# TWO SUM - KLASİK MÜLAKAT SORUSU
# =========================================

def two_sum_brute(nums, target):
    """
    Yöntem 1: Brute Force
    Zaman: O(n²) - iki döngü
    Alan: O(1)
    """
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_hash(nums, target):
    """
    Yöntem 2: Hash Table
    Zaman: O(n) - tek geçiş
    Alan: O(n) - hash table
    """
    # değer → indeks eşlemesi
    seen = {}
    
    for i, num in enumerate(nums):
        tamamlayici = target - num
        
        # Tamamlayıcı daha önce görüldü mü?
        if tamamlayici in seen:
            return [seen[tamamlayici], i]
        
        # Bu sayıyı hash'e ekle
        seen[num] = i
    
    return []  # Bulunamadı

# ============ TEST ============
print("🎯 TWO SUM")
print("=" * 50)

test_cases = [
    ([2, 7, 11, 15], 9),
    ([3, 2, 4], 6),
    ([3, 3], 6),
    ([1, 5, 8, 3, 9, 2], 7)
]

for nums, target in test_cases:
    result = two_sum_hash(nums, target)
    if result:
        i, j = result
        print(f"nums={nums}, target={target}")
        print(f"  → İndeksler: {result} ({nums[i]} + {nums[j]} = {target}) ✅")
    else:
        print(f"nums={nums}, target={target} → Bulunamadı ❌")
    print()

# Performans karşılaştırması
import time
import random

print("=" * 50)
print("⚡ PERFORMANS KARŞILAŞTIRMASI")
big_nums = list(range(5000))
random.shuffle(big_nums)
target = big_nums[2345] + big_nums[3456]

start = time.time()
two_sum_brute(big_nums, target)
brute_time = time.time() - start

start = time.time()
two_sum_hash(big_nums, target)
hash_time = time.time() - start

print(f"Brute Force (O(n²)): {brute_time*1000:.2f} ms")
print(f"Hash Table (O(n)): {hash_time*1000:.2f} ms")
print(f"Hash {brute_time/hash_time:.0f}x daha hızlı!")

# =========================================
# İKİ DİZİDE ORTAK ELEMANLAR
# =========================================

def ortak_bul_yavas(liste1, liste2):
    """
    Yöntem 1: Brute Force
    Zaman: O(n × m)
    """
    ortak = []
    for eleman in liste1:
        if eleman in liste2:  # O(m) arama!
            ortak.append(eleman)
    return ortak

def ortak_bul_hizli(liste1, liste2):
    """
    Yöntem 2: Hash Table (set)
    Zaman: O(n + m)
    """
    tablo = set(liste2)  # O(m) - hash table oluştur
    
    ortak = []
    for eleman in liste1:  # O(n)
        if eleman in tablo:  # O(1) arama!
            ortak.append(eleman)
    
    return ortak

def ortak_bul_pythonic(liste1, liste2):
    """
    Yöntem 3: Python set intersection
    En temiz yol!
    """
    return list(set(liste1) & set(liste2))

# Test
import time

liste1 = list(range(0, 10000, 2))  # Çift sayılar: 0, 2, 4, ...
liste2 = list(range(5000, 15000))   # 5000'den başlayan

print(f"Liste1: {len(liste1)} eleman")
print(f"Liste2: {len(liste2)} eleman")

# Yavaş yöntem
start = time.time()
ortak1 = ortak_bul_yavas(liste1, liste2)
yavas_sure = time.time() - start
print(f"\n❌ Yavaş (O(n×m)): {yavas_sure*1000:.2f} ms → {len(ortak1)} ortak")

# Hızlı yöntem
start = time.time()
ortak2 = ortak_bul_hizli(liste1, liste2)
hizli_sure = time.time() - start
print(f"✅ Hızlı (O(n+m)): {hizli_sure*1000:.2f} ms → {len(ortak2)} ortak")

# Pythonic
start = time.time()
ortak3 = ortak_bul_pythonic(liste1, liste2)
pythonic_sure = time.time() - start
print(f"🐍 Pythonic: {pythonic_sure*1000:.2f} ms → {len(ortak3)} ortak")

kat = yavas_sure / hizli_sure
print(f"\n⚡ Hash table {kat:.0f}x daha hızlı!")

print(f"\nİlk 10 ortak: {ortak2[:10]}")

# =========================================
# ANAGRAM GRUPLARI
# =========================================

from collections import defaultdict

def group_anagrams(words):
    """
    Anagramları grupla
    Zaman: O(n * k log k) - n kelime, k ortalama kelime uzunluğu
    Alan: O(n * k)
    """
    groups = defaultdict(list)
    
    for word in words:
        # Sıralanmış harfleri anahtar yap
        key = tuple(sorted(word))
        groups[key].append(word)
    
    return list(groups.values())

def group_anagrams_count(words):
    """
    Alternatif: Harf sayımı ile (sorting yok)
    Zaman: O(n * k) - daha iyi!
    """
    groups = defaultdict(list)
    
    for word in words:
        # Her harfin sayısını key yap
        count = [0] * 26  # a-z için
        for char in word:
            count[ord(char) - ord('a')] += 1
        
        key = tuple(count)
        groups[key].append(word)
    
    return list(groups.values())

# ============ TEST ============
print("🔤 ANAGRAM GRUPLARI")
print("=" * 50)

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(f"Input: {words}")

result = group_anagrams(words)
print(f"\n📦 Gruplar:")
for i, group in enumerate(result, 1):
    print(f"  Grup {i}: {group}")

# Nasıl çalışıyor?
print("\n🔍 Nasıl Çalışıyor?")
for word in words[:4]:
    key = tuple(sorted(word))
    print(f"  '{word}' → sorted: {key}")

# Türkçe örnek
print("\n" + "=" * 50)
print("🇹🇷 TÜRKÇE ÖRNEK")
turkce = ["arı", "rıa", "ıar", "kar", "rak", "ark"]
result_tr = group_anagrams(turkce)
print(f"Input: {turkce}")
for i, group in enumerate(result_tr, 1):
    print(f"  Grup {i}: {group}")

# =========================================
# BASİT CACHE SİSTEMİ
# =========================================

import time

class SimpleCache:
    """Hash table ile basit önbellek"""
    
    def __init__(self):
        self.cache = {}
        self.hit_count = 0
        self.miss_count = 0
    
    def get(self, key, hesaplama_func):
        """Cache'te varsa getir, yoksa hesapla"""
        if key in self.cache:
            self.hit_count += 1
            print(f"  ✅ Cache HIT: {key}")
            return self.cache[key]
        else:
            self.miss_count += 1
            print(f"  ❌ Cache MISS: {key} (hesaplanıyor...)")
            
            value = hesaplama_func(key)
            self.cache[key] = value
            return value
    
    def stats(self):
        """İstatistikler"""
        total = self.hit_count + self.miss_count
        if total == 0:
            return
        
        hit_rate = self.hit_count / total * 100
        print(f"\n📊 Cache İstatistikleri:")
        print(f"   Hit: {self.hit_count} (%{hit_rate:.1f})")
        print(f"   Miss: {self.miss_count}")

# Yavaş hesaplama simülasyonu
def faktoriyel_yavas(n):
    time.sleep(0.3)  # 300ms bekleme
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# Test
cache = SimpleCache()

print("🗄️ CACHE SİSTEMİ TESTİ")
print("=" * 50)

# İlk çağrılar (cache miss)
print("\n1. Çağrı:")
start = time.time()
result = cache.get(5, faktoriyel_yavas)
print(f"   5! = {result} ({(time.time()-start)*1000:.0f} ms)")

print("\n2. Çağrı:")
start = time.time()
result = cache.get(7, faktoriyel_yavas)
print(f"   7! = {result} ({(time.time()-start)*1000:.0f} ms)")

# Tekrar çağrılar (cache hit)
print("\n3. Çağrı (tekrar 5):")
start = time.time()
result = cache.get(5, faktoriyel_yavas)
print(f"   5! = {result} ({(time.time()-start)*1000:.0f} ms) ⚡ ANINDA!")

print("\n4. Çağrı (tekrar 7):")
start = time.time()
result = cache.get(7, faktoriyel_yavas)
print(f"   7! = {result} ({(time.time()-start)*1000:.0f} ms) ⚡ ANINDA!")

cache.stats()

# Python'ın hazır cache'i
print("\n" + "=" * 50)
print("🐍 PYTHON LRU_CACHE")
from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(f"fib(30) = {fib(30)}")
print(f"Cache bilgisi: {fib.cache_info()}")

# =========================================
# İLK TEKRAR ETMEYEN KARAKTER
# =========================================

from collections import Counter

def first_unique_char(s):
    """
    İlk tekrar etmeyen karakteri bul
    Zaman: O(n)
    Alan: O(1) - en fazla 26 harf
    """
    # Adım 1: Frekans say
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    # Adım 2: İlk unique'i bul
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i, char
    
    return -1, ""

def first_unique_counter(s):
    """Counter ile daha temiz"""
    freq = Counter(s)
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i, char
    return -1, ""

# ============ TEST ============
print("🔤 İLK TEKRAR ETMEYEN KARAKTER")
print("=" * 50)

test_cases = [
    "leetcode",
    "loveleetcode", 
    "aabb",
    "python",
    "abcabc"
]

for s in test_cases:
    idx, char = first_unique_char(s)
    if idx >= 0:
        print(f"'{s}' → indeks {idx}: '{char}' ✅")
    else:
        print(f"'{s}' → Tekrar etmeyen yok ❌")

# Frekans görselleştirme
print("\n" + "=" * 50)
print("📊 'loveleetcode' Frekans Analizi:")
s = "loveleetcode"
freq = Counter(s)
for char, count in sorted(freq.items(), key=lambda x: -x[1]):
    bar = '█' * count
    status = "✅ unique" if count == 1 else ""
    print(f"  '{char}': {bar} ({count}) {status}")

# =========================================
# CONTAINS DUPLICATE
# =========================================

def contains_duplicate_brute(nums):
    """O(n²) - her çifti kontrol et"""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

def contains_duplicate_sort(nums):
    """O(n log n) - sırala, ardışık kontrol"""
    sorted_nums = sorted(nums)
    for i in range(len(sorted_nums) - 1):
        if sorted_nums[i] == sorted_nums[i + 1]:
            return True
    return False

def contains_duplicate_hash(nums):
    """O(n) - hash set ile"""
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

def contains_duplicate_pythonic(nums):
    """Tek satır Python çözümü"""
    return len(nums) != len(set(nums))

# ============ TEST ============
print("🔍 CONTAINS DUPLICATE")
print("=" * 50)

test_cases = [
    [1, 2, 3, 1],
    [1, 2, 3, 4],
    [1, 1, 1, 3, 3, 4, 3, 2, 4, 2],
    [],
    [1]
]

for nums in test_cases:
    result = contains_duplicate_hash(nums)
    emoji = "✅ Tekrar VAR" if result else "❌ Tekrar YOK"
    print(f"{nums} → {emoji}")

# Performans karşılaştırması
import time
import random

print("\n" + "=" * 50)
print("⚡ PERFORMANS (10000 eleman)")

big_list = list(range(10000))
random.shuffle(big_list)
big_list.append(5000)  # Bir tekrar ekle

start = time.time()
contains_duplicate_brute(big_list[:1000])  # Sadece 1000 için brute
brute_time = time.time() - start

start = time.time()
contains_duplicate_hash(big_list)
hash_time = time.time() - start

print(f"Brute (1000 eleman): {brute_time*1000:.2f} ms")
print(f"Hash (10000 eleman): {hash_time*1000:.2f} ms")

# =========================================
# VALID ANAGRAM
# =========================================

from collections import Counter

def is_anagram_sort(s, t):
    """
    Yöntem 1: Sıralama
    Zaman: O(n log n)
    """
    return sorted(s) == sorted(t)

def is_anagram_hash(s, t):
    """
    Yöntem 2: Hash Table ile frekans sayma
    Zaman: O(n)
    """
    if len(s) != len(t):
        return False
    
    freq = {}
    
    # s'deki harfleri say (artır)
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    # t'deki harfleri say (azalt)
    for char in t:
        if char not in freq:
            return False
        freq[char] -= 1
        if freq[char] < 0:
            return False
    
    return True

def is_anagram_counter(s, t):
    """Yöntem 3: Counter - en temiz"""
    return Counter(s) == Counter(t)

# ============ TEST ============
print("🔤 VALID ANAGRAM")
print("=" * 50)

test_cases = [
    ("anagram", "nagaram"),
    ("rat", "car"),
    ("listen", "silent"),
    ("hello", "world"),
    ("aaa", "aaa"),
    ("ab", "a")
]

for s, t in test_cases:
    result = is_anagram_hash(s, t)
    emoji = "✅ Anagram" if result else "❌ Değil"
    print(f"'{s}' vs '{t}' → {emoji}")

# Detaylı analiz
print("\n" + "=" * 50)
print("📊 'listen' vs 'silent' Analizi:")
s, t = "listen", "silent"
freq_s = Counter(s)
freq_t = Counter(t)
print(f"  '{s}': {dict(freq_s)}")
print(f"  '{t}': {dict(freq_t)}")
print(f"  Eşit mi? {freq_s == freq_t}")

# =========================================
# LONGEST CONSECUTIVE SEQUENCE
# =========================================

def longest_consecutive_sort(nums):
    """
    Yöntem 1: Sıralama
    Zaman: O(n log n)
    """
    if not nums:
        return 0
    
    nums = sorted(set(nums))  # Duplicate'leri kaldır ve sırala
    
    longest = 1
    current = 1
    
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] + 1:
            current += 1
            longest = max(longest, current)
        else:
            current = 1
    
    return longest

def longest_consecutive_hash(nums):
    """
    Yöntem 2: Hash Set
    Zaman: O(n) - her eleman en fazla 2 kez ziyaret edilir
    """
    if not nums:
        return 0
    
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # Sadece dizi başlangıçlarından başla
        if num - 1 not in num_set:
            # Bu bir dizinin başlangıcı!
            current_num = num
            current_length = 1
            
            # Diziyi takip et
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
            
            longest = max(longest, current_length)
    
    return longest

# ============ TEST ============
print("🔢 LONGEST CONSECUTIVE SEQUENCE")
print("=" * 50)

test_cases = [
    [100, 4, 200, 1, 3, 2],
    [0, 3, 7, 2, 5, 8, 4, 6, 0, 1],
    [1, 2, 0, 1],
    [],
    [1]
]

for nums in test_cases:
    result = longest_consecutive_hash(nums)
    print(f"{nums}")
    print(f"  → En uzun ardışık dizi: {result} eleman")
    print()

# Detaylı analiz
print("=" * 50)
print("🔍 [100, 4, 200, 1, 3, 2] Analizi:")
nums = [100, 4, 200, 1, 3, 2]
num_set = set(nums)
print(f"Set: {num_set}")
print("\nDizi başlangıçları (num-1 set'te yok):")
for num in sorted(num_set):
    if num - 1 not in num_set:
        # Dizi uzunluğunu bul
        length = 1
        current = num
        while current + 1 in num_set:
            current += 1
            length += 1
        print(f"  {num} → dizi: {list(range(num, num + length))} (uzunluk: {length})")

# =========================================
# SUBARRAY SUM EQUALS K
# =========================================

def subarray_sum_brute(nums, k):
    """
    Yöntem 1: Brute Force
    Zaman: O(n²)
    """
    count = 0
    n = len(nums)
    
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total == k:
                count += 1
    
    return count

def subarray_sum_hash(nums, k):
    """
    Yöntem 2: Prefix Sum + Hash Table
    Zaman: O(n)
    
    prefix_sum[j] - prefix_sum[i] = k
    → prefix_sum[i] = prefix_sum[j] - k
    → Kaç tane i için bu doğru?
    """
    count = 0
    prefix_sum = 0
    
    # prefix_sum → kaç kez görüldü
    prefix_count = {0: 1}  # Boş prefix için 0
    
    for num in nums:
        prefix_sum += num
        
        # prefix_sum - k daha önce kaç kez görüldü?
        needed = prefix_sum - k
        if needed in prefix_count:
            count += prefix_count[needed]
        
        # Bu prefix_sum'ı kaydet
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

# ============ TEST ============
print("📊 SUBARRAY SUM EQUALS K")
print("=" * 50)

test_cases = [
    ([1, 1, 1], 2),
    ([1, 2, 3], 3),
    ([1, -1, 0], 0),
    ([3, 4, 7, 2, -3, 1, 4, 2], 7)
]

for nums, k in test_cases:
    result = subarray_sum_hash(nums, k)
    print(f"nums = {nums}, k = {k}")
    print(f"  → {result} alt dizi toplamı {k}'ya eşit")
    print()

# Detaylı analiz
print("=" * 50)
print("🔍 [1, 2, 3], k=3 Analizi:")
nums = [1, 2, 3]
k = 3
prefix = 0
prefix_count = {0: 1}
print("Adım | num | prefix | needed | count artışı")
print("-" * 50)

count = 0
for i, num in enumerate(nums):
    prefix += num
    needed = prefix - k
    increase = prefix_count.get(needed, 0)
    count += increase
    print(f"  {i+1}  |  {num}  |   {prefix}    |   {needed}    |    +{increase} (toplam: {count})")
    prefix_count[prefix] = prefix_count.get(prefix, 0) + 1

print(f"\n✅ Sonuç: {count} alt dizi")