CP #31: Cakal Problemler Seckisi

1. Find The Missing Number

Problem surada.

Cozum
Benim ilk aklima gelen yontem verilen inputu bir set'e donusturmek, O(n). Sonra bir dongu ile 1'den n'e kadar olan sayilari sirayla bu setten cikarmak, O(n). Set'te olmayan bir sayi olacaktir, buna denk gelince bu sayiyi geri dondurmek.

def find_missing(input):

    cache = set(input)

    

    # O(n)

    for i in range(len(input)+1):

        if i in cache:

            cache.remove(i) # O(1)

        else:

            return i

Bu calisiyor evet. Sonra dusundum acaba bu cozumu iyilestirebilir miyiz diye? Dedim ki, O(n) iste daha nasil iyilesecek? Ama cakallik burada iste. Size tek bir sorum var:

1'den n'e kadar olan ardisik sayilarin toplami nedir? 1 + 2 + 3 + ... + n = n * (n+1) / 2

Iste bu kadar. Normalde inputta eksik olmasa idi, toplami bu olacakti. Peki simdi ne? sum(input). 

Simdi farkediyorum ki bu cozum de O(n) time compl.ye sahip :D ama olsun, daha az memory harciyor enazindan. Memory ihtiyacina bakarsak constant oldugunu goruyoruz: O(1).

2. Sum Two Values

Problem surada.

Cozum

Bu problemi single-pass ile cozmek onemli. Her bir elemana bakip, daha once bu eleman ile toplansa idi, targeti verecek olan bir eleman gecmismiydi? sorusuna cevap verebiliyor olursak bunu yapabiliriz. Her gordugumuz elemani bir set'e eklersek, diger adimdaki elemani targete tamamlayacak elemanin gecip gecmedigini O(1) ile kontrol edebiliriz. 

def find_sum_of_two(nums, target):

    cache = set()

    for n in nums:

        if target - n in cache:

            return True

        cache.add(n)

    return False

Toplamda lineer bir cozum. Memory gereksinimi de lineer. 

3. Level Order Traversal of Binary Tree

Problem surada.

Cozum

BFS kullanarak, ve de BFS'in her bir pass'inde, ziyaret edilen elemanlari toplayarak bunu yapabiliriz. 

from collections import deque

def level_order_traversal(root):

    q = deque([root])

    while q:

        lenq = len(q)

        

        level = []

        for _ in range(lenq):

            cur = q.pop()

            level.append(cur.val)

            

            if cur.left:

                q.append(cur.left)

            if cur.right:

                q.append(cur.right)

        print(level)

Tum tree node'larini ziyaret ettigimiz icin O(n) bir cozum. Memory icin de yine queue ve level kullanimindan dolayi lineer, O(n) diyebiliriz. 

4. String Segmentation

Problem surada.

Cozum

Ilk akla gelen cozum, verilen input string uzerine karakter katakter ilerleriz. Her adimda bu kismin sozlukte olup olmadiginina bakariz. Eger sozluk var ise, tam bu noktadan devam eden yeni bir arama baslatalim. Bir baska secenek de orada durmamak. Yani iki ihtimali de paralel olarak devam ettirabiliriz. 

def can_segment_string(word, dictionary):

    # recursive helper fonk

    def segment(start):

        nonlocal word, dictionary

        # eger start, kelimenin sonuna gelebildi ise

        # segmentasyon basarili demektir

        if start == len(word):

            return True

        # karakter karakter ilerleyelom

        # python range operatorunun bitis noktasi 

        # exclusive oldugu icin uzunluk+1 yapmamiz gerekiyor

        for i in range(len(word)+1):

            word_so_far = word[start:i]

            # eger sozlukte varsa iki secenegimiz var

            # burada durup, buradan baslayan yeni bir arama baslatmak

            # burada durmayarak, word_so_far'i genisletmeye devam etmek

            # ikisinden birisi cozume goturebilir

            # bu noktada bilmiyoruz

            if word_so_far in dictionary:

                # bu noktadan ayiracagimiz program dali 

                # basarili olur da kelimeyi parcalamayi bitirebilirsek

                # devam etmeye gerek yok

                if segment(i):

                    return True

        # bu noktaya gelebildi isek segmentasyon basarlili degil

        return False

    retrun segment(start=0)

Analiz
Recursive fonksyionda programi verilen bir start noktasindan 2 dala ayirip arama yapmaya devam ediyoruz. Bu da demek oluyor ki, verilen n karakterli bir kelime icin 2^n seklinde bir dallanma olacak (worst case). O acidan O(2^n) gibi exponential bir time compl. sozkonusu. Ama ekstra hafiza tuketmiyorz, hafiza gereksinimi O(1), constant. 

Bir iyilestirme memoization ile yapilabilir.  

5. Coin Changing Problem

Problem surada.

Cozum
Bu problemin cozumunu ben tam olarak anladim diyemem. Yine de bahsedeyim, belki anlariz ilerde :D 

Herhangi verilen bozuk para seti icin (S = {1,2,5} olsun ornek olarak), ve de verilen bir hedef icin (n=7 olsun), gidilebilecek yol sayisi

{m.inci coini icermeyen cozum sayisi} + {enazindan 1 coin iceren cozum sayisi}

seklinde hesaplaniyor. Koda dokersek soyle:

def count(s=[1,2,5], n = 7):

    # bu bizim base case

    # hic para yoksa ancak 1 sekilde odenir

    if n == 0:

        return 1

    # egere elde coin kalmadi ise cozum yok

    if n > 0 and len(s) == 0:

        return 0

 

    if n < 0:

        return 0

    return count(s[:-1], n) + count(s, n - s[-1])

6. Find Kth Permutation

Problem surada.

Cozum

7. Find All Subsets

Problem surada.

Cozum
Soyle dusunelim. Her bir subset'i bastan olusturuyoruz. Elimizde bir bos kume (bos array) var. Simdi, verilen elemanlardan ilki icin elimde iki secenek var. Bu elemani subset'e dahil edebiliriz ya da etmeyiz. Burada program iki dala ayriliyor. Sonra siradaki elemana geciyoruz. Bu eleman icin de ayni sey gecerli ya alacagiz ya da almayacagiz. Bu sekilde, verilen input array'deki tum elemanlari tukettikten sonra, her bir program dalinin sonucunda bir cozum olusuyor. Iste bu cozumler birer subset. 

def subsets(items = [1,2,3]):

    subsets = []    

    # her bir cozumu sifirdan baslayarak olusturacagiz

    def build_solution(arr, ind):

        nonlocal items, subsets

        # tum elemanlari denedik, 

        if ind == len(items):

            # burada arrayi kopyalamamiz gerekiyor

            subsets.append(arr[:])

            return

        # ind.inci elemani al

        arr.append(items[ind])

        build_solution(arr, ind+1)

        # ind.inci elemani alma

        arr.pop()

        build_solution(arr, ind+1)

    build_solution([], ind=0)

    return subsets

Analiz
Disarikadi dongude, yani build_solutions fonksyionu, 2^n kadar calisacaktir. Neder? Cunku her adimda 2 kere cagiriyoruz bu fonksiyonu. Zaten n elemanli bir kumenin altkume sayisi 2^n'dir. Her bir cozume ulastigimizda (2^n kere), array kopyalamasi yapiyoruz ki O(n) bir islemdir. Bu durumda toplamda
O(n 2^n) gib bir time compl. sahip oluyoruz. 

Her bir cozum icin wors case n elemanli array tutuyoruz ve bu cozumler 2^n adet var. Toplamda yine o zaman O(n 2^n) seklinde bir memory ihtiyaci var demektir. 

8. All Possible Braces

Problem surada.

Cozum
Sanirim bu problemin daha bilimsel bir cozum var ama ben burada cakal bir cozumden bahsedecegim. Oncelikle n=1 ve n=2 icin cozum nasil bir bakalim.

n=1 icin tek bir cozum var ()

n=2 icin iki cozum var ()() veya (()) 

n=3 icin bes cozum var ()()(), (())(), ()(()), (()()), ((()))

Burada bir patern var. Mesela, n=1 olan cozumu, alip n=1 icin olan yine cozum uzerinde sirayla 0'dan sona kadar insert edersek, n=2 icin olan cozumu buluyoruz. 

() -> sifira inset et ()()

() -> bire insert et (())

Dikkatli bakarsak n=3 icin olan cozum de yine n=2 olan cozum uzerine n=1 icin olan cozumun sirayla her bir karakter indeksi noktasina insert edilmesiyle ortaya cikiyor. (Dunyanin en kotu anlatimi oldu).

def braces(n):

    if n == 1:

        return ["()"]

    # sonuclari sette topluyoruz cunku 

    # farkli program dallari ayni sonucu uretebiliyor

    ret = set()

    rest = braces(n-1)
    for r in rest:

        for i in range(len(r)):

            solution = r[:i] + "()" + r[i:]

            ret.append(solution)

    return solution

Analiz
Bizim recursive fonksyion n'den basyalarak sirayla 1'e kadar gidecek. 1'de return gorup tum solution'lari olustura olustura gelecek. Demek ki distaki dongu lineer. Yani O(n). Iceride, bir onceki adimda olusturulan cozumler uzerinde cozum uzunlugu kadar iterasyon yapiyoruz. Burayi hesaplamak zor ama ust limite bakacar olursak, ayni sonucu da uretseler, program dali sayisi n*2^n.  

9. Clone A Directed Graph

Problem surada.

Cozum

Bir node'u kopyalamak gercekten kolay bir islem. Buradaki cakallik, orjinali ile kopyasi arasinda bir iliski kurabilmek. Bunu yapabilmek icin bir hashtable kullanacagiz.

def copy_graph(root):

    # orjinal : kopya

    # iliskisini tutacak hashtable

    cache = {}

    

    # verilen node'u kopyalan recursive

    # fonsksiyonumuz

    def copy_node(node):

        # eger bu node daha once kopyalanmissa 

        # direk dondur

        if node in cache:

            return cache[node]

        

        # kopyala

        copied_node = Node(node.data)

        cache[node] = copied_node

        

        # komsulari kopyala

        copied_node.neighbors = [copy_node(x) for x in node.neighbors]

        return copied_node

    return copy_node(root)

Analiz
Burada BFS ile aslinda graph uzerinde geziyoruz bir nevi, bu acidan dis dongu O(n). Iceride ise pek bisey yapmiyoruz, node kopyalamak zaten constant. Demek ki toplamda O(n) time compl. sahibiz. 

Hafiza gereksinimi de, tum node'larin kopyasini sakladigimiz icin O(n) seklinde olacaktir. 

10. Find Low/High Index

Problem surada.

Cozum

Verilen arrayi lineer olarak traverse edip de degisim noktalarini bulmak cazip gozukse de, arrayin milyonlarca elemandan olusabilecegi hinti verilmis. Bu da bize gosteriyor ki O(n)'den daha iyi bir cozume ihtiyacimiz var. 

Ilk akla gelen binary search. O(log n) ile istedigimiz key'i array uzerinde bulabiliriz. Ama bize verilen key'in en alt ve en ust indexleri soruluyor. Bu durumda binary search'i biraz modifiye etmek gerekecek. Alt siniri ve ust siniri bulan ayri ayri iki farkli binary search metodu gelistirecegiz ki sonucta yine de cozum O(log n)'e tekabu ediyor olacak. 

def find_high_low_index(arr, key):

    def find_low(start, end):

        nonlocal arr

        

        # hemen orta noktayi hesaplayalim

        mid = start + (end - start) // 2

        # eger orta nokta bizim aradigimiz key ise guzel

        # aramayi daha da daraltacagiz

        if arr[mid] == key:

            # burada alt siniri ariyoruz.

            # yani ya bu eleman sifirinci eleman olacak daha alti olmayacak

            # ya da bir solundaki eleman kendisinden kucuk olacak

            # (verilen arrayin sorted oldugunu unutmayalim)

            if mid == 0 or (mid > 0 and arr[mid-1] < key):

                return mid

            else:

                # bulundugumuz yerden baslangic noktasi arasindaki

                # orta noktayi alarak yeni bir pivot olusturup

                # sola dogru aramayi devam ettiriyoruz

                # alt sinira gelene kadar

                return find_low(start, start + (mid - start)//2)

        elif arr[mid] < key:

            return find_low(mid+1, end)

        elif arr[mid] > key:

            return find_low(start, mid)

    # ust limiti bulan binary search fonk.

    def find_high(start, end):

        mid = start + (end - start)//2

        

        if arr[mid] == key:

            # eger en sagdaysak ya da bu elemanin sagindaki eleman

            # kendisinden buyuk ise ust siniri bulduk demektir

            if mid == len(arr)-1 or (mid > len(arr)-1 and arr[mid+1] > key):

                return mid

            else:

                # saga dogru aramaya devam et

                return find_high(mid+1, mid + (end-mid)//2)

        elif arr[mid] < key:

            return find_high(mid+1, end)

        elif arr[mid] > key:

            return find_high(start, mid)

    # alt ve ust indexleri dondurelim

    return (find_low(start, len(arr)), find_high(start, len(arr)))

Analiz

Tipik bir binary search oldugundan her adimda arama uzayini 2ye boluyoruz. Bu da O(logn) gibi bir time compl. tekabul ediyor. 

Herhangi bir ekstra hafiza kullanmadik, O(1) de space compl. elde etmis olduk.