lombak şehidi

 Problem surada . Cozum Cok enteresan bir problem ile karsi karsiyayiz. Elimizde 2 inversion tipi var: global ve local.  Local inversion: yan yana olup da, kendisinden sonra gelenden buyuk olan bir eleman var ise bu local inversion oluyor.  Global inversion: yanyana olmasina gerek olmadan, kendisinden sonra gelen elemanlar icinde, kendisinden buyuk bir eleman var ise, bu global inversion oluyor.  Ben cok dusunmeden direk hesaplamaya giristim. Siz yapmayin diye burada tekrar yapalim ama sonra dusunme asamasina geri donecegiz.  O zaman oncelikle local inversionlari hesaplayalim: def isIdealPermutation(self, nums: List[int]) -> bool:      # local inversion sayisi kolay,     # her bir pair'i kontrol ediyoruz     loc = 0      for i in range(len(nums)-1):          if nums[i+1] < nums[i]:               loc += 1     glob = 0     # global icin ise 2 loop gerekli cunku her bir eleman icin     # kendisinden sonra gelen ve kendisinden kucuk kac eleman     # oldugunu bulmamiz gerek     fo

 Problem surada . Cozum Bu problemi O(n) space ile cozmek trivial o yuzden direk olarak follow-up ile baslayalim ve O(1) space ve O(n) time ile nasil cozeriz bunu dusunelim. Eger ileri ve geri olarak lined list uzerinde gezinebilse idik, ortasindan baslyarak yanlara dogru gider ve esitlik bozuluyorsa palindrome olmadigina karar verebilirdik. Peki geriye dogru gidemiyor ise, linkedlistin ilk yarisini ters cervirsek ve karsilastirmayi birincisi sifirdan ikincisi de linkedlistin tam ortasindan baslayacak sekilde iki pointer ile yapsak? Su sekilde: 1, 2, 2, 1 seklinde giden linked listi inceleyeim. Ilk yarisini ters cevirir isek, sonuca 2,1,2,1 seklinde bir hale gelir. Bu sekilde iken, i ve j olmak uzere iki pointer ile karsilastirma yapmak mumkun. Birincisi sifirdan ikincisi de ll'nin ortasindan baslayacak ve her adimda ikisini de 1 artiracagiz. Esitlik bozulursa False dondurecegiz.  O zaman ilk etapta linkedlistin uzunlugunu bulmamiz gerekiyor ki, ortsina kadar olan node'lari ter

 Problem surada . Cozum Naive implementasyon ile baslar isek, verilen arrayi sol taraf 1 elemanli olacak sekilde ayirmaya baslayabiliriz. Her adimda, sol arrayi bir eleman daha fazla genisletmeye calisiriz. Buradaki kriter su, sol arraydaki en buyuk eleman dahi, sag taraftaki elemanlarint tamamindan daha kucuk olacak. Bu kriteri sagladigimiz anda sol taraf eleman sayisini dondurecegiz.  def partitionDisjoint(self, A: List[int]) -> int:     # verilen left ve right arraylari icin bunun valid bir partition olup olmadigini      # kontrol eden fonksiyonumuz      # max hesaplayip, sagdaki tum elemanlarla karsilastirdigimizdan     # toplamda O(n) bir maliyete sahip     def is_valid_partition(left, right):          max_left = max(left)  # O(n)          for n in right:               if n > max_left:                    return False          return True     # sol taraf tek elemanli olacak sekilde baslayabiliriz     for i in range(1, len(A)):          left = A[:i]     # array kopyalama yapti

Problem: bit.ly gibi bir url shortening servisi tasarlayiniz. Requirements Ilk etapta requirements konusu cok detayli olarka aciga kavusturmamiz gerekiyor ki tasarimi yapabilelim. Diyelim ki su minvalde bir cozum isteniyor: Functional Requirements - Verilen bir URL'i kisaltip, calisan, unique bir kisa url olustur. - Bir kullanici bizim olusturdugumu kisa linki yizaret ettiginde, orjinal adrese yonlendir. - [Opsiyonel] Kullanici sisteme custom bir kisaltma onerebilmelidir  - Olusturulan link icin expiration zamani atanabilmeli Non-functional Requirements: - Sistem highly-available olmali - Rest API ile url olusturulabilmeli Back-of-the-envelope Hesabi On kabullerle birlestirerek asagi yukari ne kadar kaynaga ihtiyacimiz olacak bir bakalim. - Read-heavy bir sistem olacagi asikar. 100:1 (read/write orani kabul edecegiz) - Ayda 500 milyon url shortening requesti gelecek (demek ki aylik 50 milyar okuma olacak) - Ayda 500 milyon write (36 * 24 * 3600 saniye) => 200 Url / saniye yazma

Sorting onemli bir mevzumuzdur.  Sorting Nedir? https://en.wikipedia.org/wiki/Sorting_algorithm Bilgisayar bilimlerinde belirli bir dizi icerisinde yer alan elemanlaribelirli bir siraya sokan algoritmalara `sorting algorithm` adi verilir. En fazla kullanim alani su iki kategoride bulunmaktadir: 1. sayilari siralamak (numeric sorting) 2. alfabetik siralama (lexicographic sorting) Hangisi? Sorting algoritmalarinin elbette ki dandik olanlari vardir, guzel olanlari vardir. Her duruma gore secilebilecek sorting algoritmasi da biraz farklilik gosterebilir.  Algoritmalari kiyaslayabilmek icin birkac kritere bakmamiz gerekiyor.  1. Runtime complexity     a. Best     b. Average     c. Worst 2. Memory complexity (hafiza tuketimi) 3. Stabil mi? (relative order'i koruyor mu? gotu basi oynuyor mu?) 4. Online sorting algoritmalari: Tum arrayi gormesi gerekmeyen algoritmalardir. Ozellikle streamlari sort etmede fayda saglar. Elemanlar en bastan itibaren birer birer verilir ve algoritma arrayi sor

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 bakars