lombak şehidi

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