Kodlama Kalıpları: Kodlama Mülakatı Hazırlığına Daha Akıllı Bir Yaklaşım

Kodlama röportajlarına hazırlanmak, geliştiricilerin genellikle yeni materyalleri incelemek ve öğrenmek için birkaç hafta harcaması nedeniyle gerçek bir zorluk olabilir.

Gerçek şu ki çoğu geliştirici kodlama görüşmelerine hiçbir zaman tam olarak hazır hissetmez. Geliştiricilerin LeetCode'da sorunları çözmek için haftalar harcamasına rağmen kendilerini hazırlıksız hissetmeleri alışılmadık bir durum değil. Açıkçası, bu yaklaşımla ilgili sorunlar var.

Geleneksel kodlama görüşmesi hazırlığıyla ilgili bazı sorunlara daha yakından bakalım.

Geleneksel Mülakat Hazırlığının Tuzakları

Geleneksel mülakat hazırlığında en sık karşılaşılan tuzaklardan biri "eziyet" uygulamasıdır. Bu yaklaşım, net bir plan veya strateji olmadan mümkün olduğu kadar çok LeetCode sorununu çözmeyi içerir. Bu verimli bir strateji gibi görünse de birçok dezavantajı var.

Sorunları yapılandırılmış bir yaklaşım olmadan çözdüğünüzde, zayıf yönlerinizi fark edemeyebilirsiniz. Çalışmanız için kasıtlı bir plan yok; amaç mümkün olduğu kadar çok sorunu çözmektir. Sonuç olarak, çok şey öğrendiğinizi hissedebilirsiniz ancak bilginizde önemli boşluklar olabilir.

Dahası, bununla ilgili sorun, esasen çok sayıda sorunun çözümlerini ezberlemek etrafında dönmesidir. Yüzlerce farklı kodlama probleminin çözümlerini hatırlamaya çalışmak, görüşmeyi yapan kişinin daha önce karşılaştığınızdan biraz bile farklı sorular sorması durumunda etkisiz kalır. Bu, sorundaki değişikliklerle başa çıkma konusunda kendinizi hazırlıksız hissetmenize neden olabilir.

Bu stratejiyle ilgili son sorunum, uzun vadede daha fazla stres ve baş ağrısı yaratmasıdır. Her iş değiştirmek istediğinizde aynı birkaç haftalık çalışma seansına katlanmak zorunda kalırsanız, her seferinde mücadele edeceksiniz. Bir şeyleri yeniden öğrenmek ve daha önce olduğu gibi aynı sorunları çözmek için haftalar harcayacaksınız.

Bu zorluklar göz önüne alındığında, daha iyi bir yol olmalı.

Daha İyi Bir Yol: Kodlama Modellerini Benimsetmek

Peki röportaj hazırlığını kodlamak için daha etkili ve sürdürülebilir bir yaklaşım var mı? Cevap, kodlama kalıplarını anlamak ve kullanmakta yatmaktadır.

Kodlama görüşmelerine hazırlanırken sorunların altında yatan kalıpları kavramaya öncelik veririm. İki İşaretçi , Kayan Pencere , Değiştirilmiş İkili Arama , Topolojik Sıralama ve çok daha fazlası gibi teknikleri içeren bu modeller, çok çeşitli kodlama sorunlarının üstesinden gelmek için çok yönlü ve güçlü bir çerçeve sağlar. Vurgu, çözümleri ezberlemekten kanıtlanmış problem çözme tekniklerine doğru kayıyor.

Kodlama kalıplarına odaklanarak görüşme hazırlığınızı önemli ölçüde kolaylaştırabilir ve daha verimli hale getirebilirsiniz.

Unutmayın, daha akıllıca hazırlanın, daha zor değil.

Ne bekleyebileceğinizi?

Bu yazıda derledim En İyi 15 Kodlama Modeli Herhangi bir kodlama sorusunu yanıtlamak için bilmeniz gerekenler. Her bir modelin ne olduğunu ve nasıl çalıştığını anlatacağım. Modeli tanımlamanıza yardımcı olacak temel göstergeleri paylaşın ve son olarak anlayışınızı sağlamlaştırmanıza yardımcı olacak şablon koduyla birlikte ayrıntılı grafikler sunun.

Bu makalede pek çok konuyu ele alsam da, daha derinlemesine eğitim, açıklamalar ve kodlama pratiği istiyorsanız Techinterviews.io adresindeki Kapsamlı Kodlama Mülakat Hazırlık Kursumuza göz atabilirsiniz . Ayrıca veri yapıları , davranışsal görüşmeler ve hatta maaş pazarlığı gibi önemli konuları da ele alıyoruz.

Şimdi bu kodlama kalıplarına dalalım.

1. Bağlantılı Listeyi Tersine Çevirme

Bağlantılı Listeyi Ters Çevirme, öğelerin sırasını tersine çevirmek için bağlantılı bir listedeki işaretçilerin yönünü değiştirmeyi içerir. Bu, veri yapılarında temel bir işlemdir ve genellikle düğüm referanslarının dikkatli bir şekilde değiştirilmesini gerektirir.

Bu, bağlantılı bir listeyle uğraşırken kullanışlıdır ve kısıtlama onu yerinde tersine çevirmektir.

Bağlı bir listeyi yerinde tersine çevirme süreci aşağıdaki gibidir:

1. Üç değişkeni tanımlayarak başlayın: geçerli , önceki ve sonraki . Geçerliyi bağlantılı listenin başı olarak ayarlayın ve önceki ve sonrakini Yok olarak başlatın.

2. Geçerli değişken Yok olmasa da aşağıdaki şekilde ilerleyin:

   1. Sonraki düğümü geçici bir değişkende saklayın.
   2. Geçerli düğümün işaretçisini önceki düğümü işaret edecek şekilde ters çevirin.
   3. Geçerli düğüm olmak için öncekini güncelleyin ve sonraki düğüm olacak şekilde güncelleyin.

3. Son olarak, ters çevrilmiş listenin başlığını , önceki değişkende saklanan, ulaşılan son düğüme ayarlayın.

Temel Göstergeler:

• Bağlantılı listedeki öğelerin sırasını tersine çevirmeniz gerekir.
• Sorunlar bağlantılı listelerde palindromların kontrol edilmesini içerir.
• Liste içindeki belirli bir alt listedeki öğelerin sırasını tersine çevirmek istiyorsunuz.

Şablon Kodu:

Python

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

Java

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. Değiştirilmiş İkili Arama

Değiştirilmiş İkili Arama, çeşitli sorunları çözmek için klasik ikili arama algoritmasını uyarlar. Varyasyonlar arasında bir öğenin ilk/son oluşumunu bulma veya döndürülmüş dizilerde arama yer alır. Orta noktaların ve koşulların dikkatli bir şekilde ele alınmasını gerektirir.

Eğer size sıralanmış bir dizi, bağlantılı liste veya matris verildiyse, değiştirilmiş bir ikili arama kullanmayı düşünün.

Bu modelin sıralanmış bir veri yapısına nasıl uygulanacağının bir dökümü burada verilmiştir:

1. Başlangıç ve bitiş konumları arasındaki orta noktayı tanımlayarak başlayın. Potansiyel tamsayı taşmasını önlemek için ortayı şu şekilde hesaplamak daha güvenlidir: middle = start + (end - start) / 2 .
2. Anahtarın orta dizindeki öğeyle eşleşip eşleşmediğini kontrol edin. Eğer öyleyse, sonuç olarak ortadaki dizini döndürün.
3. Anahtar orta dizindeki öğeyle eşleşmiyorsa sonraki adımlara geçin.
4. Anahtarın indeks ortadaki elemandan küçük olup olmadığını değerlendirin. Öyleyse, uçtan ortaya doğru güncelleyerek arama aralığınızı daraltın - 1 .
5. Tersine, eğer anahtar orta indeksteki elemandan büyükse, start'ı orta + 1 olarak güncelleyerek arama aralığınızı ayarlayın.

Temel Göstergeler:

• Sıralanmış bir veri yapısıyla çalışıyorsunuz.
• Belirli öğeleri, sınırları veya pivot noktalarını verimli bir şekilde bulmanız gerekir.
• Sorunlar döndürülmüş sıralanmış dizilerde arama yapmayı içerir.

Şablon Kodu:

Python

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

Java

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. İki İşaretçi

İki İşaretçi tekniği, genellikle çiftleri veya alt dizileri içeren problemlerde kullanılan, genellikle diziler veya bağlantılı listeler olmak üzere bir veri yapısından geçen iki işaretçinin korunmasını içerir. Farklı konumlardaki öğeler arasında karşılaştırma gerektiren sorunları optimize eder.

Bu tekniğin avantajı, özellikle başlangıçta yalnızca bir işaretçi kullanabileceğiniz diziler veya dizeler gibi doğrusal veri yapılarıyla uğraşırken basitliği ve verimliliğinde yatmaktadır. İki işaretçi kullanarak, gereksiz işlemleri atlatabilir ve çalışma zamanı verimliliğini önemli ölçüde artırabilir, potansiyel olarak O(n^2) 'den O(n)' ye düşürebilirsiniz.

"İki İşaretçi" modeli, her biri belirli senaryolara göre uyarlanmış çeşitli varyasyonları kapsar. Bu varyasyonlar aynı yönü , zıt yönü ve "hızlı ve yavaş" olarak bilinen, genellikle "kaplumbağa ve tavşan" tekniği olarak adlandırılan, bir veri yapısı boyunca farklı hızlarda hareket eden iki işaretçiyi içeren ve özellikle algılama için yararlı olan benzersiz bir yöntemi içerir. döngüler.

Bir veri yapısında geçiş yapmak için birden fazla işaretçi kullanıyorsanız yaklaşımınızı "İki İşaretçi" modelini takip ederek kategorize edebilirsiniz.

Temel Göstergeler:

• Farklı konumlardaki elemanları karşılaştırmanız veya bunlar üzerinde işlem yapmanız gerekir.
• Sorunlar, sıralanmış bir dizideki öğe çiftlerinin aranmasını gerektirir.
• Sıralanmış bir dizideki kopyaları verimli bir şekilde kaldırmak istiyorsunuz.
• Doğrusal veri yapılarıyla (diziler, dizeler veya bağlantılı listeler) uğraşırken ve ikinci dereceden zaman karmaşıklığıyla ( O(n^2) kaba kuvvet çözümü) karşı karşıya kalırken, İki İşaretçi kullanmayı düşünün.

Şablon Kodu:

“Ters yön” varyasyonu için şablon

Python

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

Java

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. Sürgülü Pencere

Kayan Pencere tekniği, diziler, dizeler veya bağlantılı listeler gibi doğrusal bir veri yapısı üzerinde dinamik bir pencerenin korunmasını içerir. Pencerenin boyutu, spesifik uygulamaya bağlı olarak değişebilir ve aynı zamanda sabit bir değer olarak da ayarlanabilir. Bu pencerenin birincil amacı, belirli kriterleri karşılayan verileri sürekli olarak izlemek ve yakalamaktır; bu da onu özellikle alt dizi veya alt dizi problemlerini verimli bir şekilde çözmek için değerli kılar.

Bu model genellikle pencere içindeki bireysel verilerin takibini kolaylaştırmak için bir karma haritası kullanır. Ancak bu yaklaşımın O(n) kadar uzay-zaman karmaşıklığına yol açabileceğini unutmamak önemlidir.

Temel Göstergeler:

• Bitişik veya bitişik olmayan alt dizileri veya alt dizileri analiz etmeniz gerekir.
• Sorunlar, daha büyük bir veri kümesi içindeki değişken uzunluklu dizilerin izlenmesini içerir.
• Sabit uzunluktaki maksimum toplam alt diziyi bulmak istiyorsunuz.
• Sorun girişi; dizi, bağlantılı liste veya dize gibi doğrusal bir veri yapısıdır.

Şablon Kodu:

Python

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

Java

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. En İyi K Öğeleri

Bu model, genellikle yığınlar veya öncelik kuyrukları gibi veri yapıları kullanılarak uygulanan bir koleksiyondaki en büyük veya en küçük K öğesinin bulunmasını içerir. Değerlerine veya sıklıklarına göre bir öğe alt kümesi seçmek için kullanışlıdır.

Belirli bir veri kümesindeki en sık görülen, en küçük veya en üstteki 'K' öğelerini bulmamız istendiğinde bu modeli kullanmayı düşünebiliriz.

Çalışma şekli basittir:

1. 'K' elemanlarını minimum veya maksimum yığınımıza ekliyoruz (Bu, uygulamaya bağlıdır).
2. Yığınımıza her ekleme yaptığımızda, her zaman sık/en küçük/en üstteki 'K' elemanlarının korunmasını sağlayacak şekilde ayarlama yapmalıyız.

Bu yaklaşımın güzelliği verimliliğinde yatmaktadır; Yığın kendisi doğal olarak sizin için gerekli düzeni sağladığından herhangi bir sıralama algoritmasına başvurmanıza gerek yoktur.

Temel Göstergeler:

• Bir koleksiyondaki en büyük veya en küçük K öğesini tanımlamanız gerekir.
• Problemler belirli kriterlere göre sıralama elemanlarını gerektirir.
• Bir veri kümesindeki en sık görülen K öğelerini bulmak istiyorsunuz.

Şablon Kodu:

Python

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

Java

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. İki Yığın

İki Yığın, bir veri kümesindeki medyan değerleri bulmak gibi belirli sorunları optimize etmek için iki yığından (bir maksimum yığın ve bir minimum yığın) yararlanır. Bu model özellikle dengeli bir yapıyı korumak için kullanışlıdır.

İşte nasıl çalışıyor:

1. İki yığın kullanın: En büyük öğeyi tanımlamak için Maksimum Yığın ve en küçüğünü bulmak için Min Yığın.
2. Max Heap'i sayıların ilk yarısıyla doldurun ve aralarından en büyüğünü bulmayı hedefleyin.
3. Bu kısımdaki en küçüğü belirlemek için Min Heap'i sayıların ikinci yarısıyla doldurun.
4. Mevcut sayı kümesinin medyanı her iki yığının üst elemanları incelenerek herhangi bir zamanda hesaplanabilir.

Temel Göstergeler:

• Verimli medyan bulma için dengeli bir yapıyı korumanız gerekir.
• Problemler, dinamik medyanlarla kayan pencere problemlerinin ele alınmasını içerir.
• Bir koleksiyondaki öğelere değerlerine göre öncelik vermek istiyorsunuz.

Şablon Kodu:

Python

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

Java

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. Monoton Yığın

Monotonik - (bir fonksiyon veya niceliğin) ya hiç azalmayacak ya da hiç artmayacak şekilde değişen.

Monotonik Yığın, genellikle bir dizideki en yakın daha küçük/daha büyük öğeleri bulmak için kullanılan, öğelerin artan veya azalmayan bir yığınını tutar. Belirli sorunları optimize etmek için güçlü bir araçtır.

Sıra katıdır; ne zaman yığının en üstünde bulunandan daha küçük (veya daha büyük) bir öğeyle karşılaşırsak, eklemek istediğimiz öğe en küçük (veya en büyük) olana kadar monoton yığından çıkmalıyız. onlara.

Temel Göstergeler:

• Öğeleri artmayan veya azalmayan sırada tutmanız gerekir.
• Problemler en yakın daha küçük veya daha büyük elemanı bulmayı içerir.
• Sırayı korurken yığın tabanlı işlemleri optimize etmek istiyorsunuz.

Şablon Kodu:

Python

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

Java

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. Derinlik-İlk Arama

DFS veya Derinlik Öncelikli Arama , geri izlemeden önce bir dal boyunca mümkün olduğunca derinlemesine araştırma yaptığınız bir geçiş yöntemidir; ağaçlar ve grafikler içeren problemlerde, özellikle geçiş ve arama operasyonlarında yaygın olarak uygulanır.

Bir ağaçta DFS gerçekleştirmek için kökten başlamanız gerekir. Daha sonra aşağıdaki adımları izleyin:

1. Geçerli düğümü, alt düğümlerini (genellikle soldan sağa) ziyaret ederek keşfedin.
2. Ağacın derinliklerine inerek DFS işlemini her alt düğüme yinelemeli olarak uygulayın .
3. Tüm alt düğümler ziyaret edildikten sonra ana düğüme geri dönülür .
4. Ağaçtaki tüm düğümler ziyaret edilene kadar geçerli düğümün ziyaret edilmeyen her alt öğesi için 1-3 arasındaki adımları tekrarlayın .

Grafikte DFS ile Fark: Ağaç DFS ile grafik DFS arasındaki temel fark, döngülerin varlığında yatmaktadır. Bir ağaçta tanımı gereği döngü yoktur, bu nedenle ağaç DFS her düğümün tam olarak bir kez ziyaret edilmesini sağlar ve ağacın tamamı geçildiğinde doğal olarak sona erer. Buna karşılık, grafik DFS'nin bir grafik içindeki döngüsel yapıları işlemek için ek önlemler içermesi gerekir. Bir döngüdeki düğümlerin süresiz olarak yeniden ziyaret edilmesini önlemek için, grafik DFS, ziyaret edilen düğümlerin işaretlenmesi ve geri izlemenin uygun şekilde işlenmesi gibi mekanizmalar gerektirir. Bu ayrım, döngülerin varlığında sonsuz döngü potansiyeli nedeniyle grafik DFS'yi ağaç DFS'den daha karmaşık hale getirir.

Temel Göstergeler:

• Ağaç yapılarıyla uğraşıyorsunuz ve belirli geçiş sıralarını keşfetmeniz gerekiyor.
• Sorunlar yolları bulmayı, derinliği hesaplamayı veya ön sipariş/sıralı/sonraki geçişi gerçekleştirmeyi içerir.
• İki düğüm arasında bir yol olup olmadığını kontrol etmek istiyorsunuz.

Şablon Kodu:

Python

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

Java

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. Genişlik-Önce Arama

BFS, bir sonraki seviyeye geçmeden önce mevcut derinlikteki tüm düğümleri araştıran ağaçlar ve grafikler için bir geçiş tekniğidir.

Bir ağaçta BFS gerçekleştirmek için kökten başlamanız gerekir. Daha sonra aşağıdaki adımları izleyin:

1. Ziyaret edilecek düğümleri takip etmek için boş bir kuyruk veri yapısını başlatın.

2. Kök düğümü kuyruğa alın .

3. Kuyruk boşalana kadar bir döngü girin:

   1. Kuyruğun önündeki düğümü kuyruktan çıkarın.
   2. Sıradan çıkarılan düğümü işleyin (örneğin ziyaret edin veya üzerinde bazı işlemler gerçekleştirin).
   3. Düğümün tüm alt öğelerini (varsa) kuyruğa alın.

4. Sıra boşalana kadar 3a-3c adımlarını tekrarlayın .

5. BFS geçişi, ağaçtaki tüm düğümler soldan sağa seviyeli bir şekilde ziyaret edildiğinde tamamlanır.

Temelde, bir ağaçtaki BFS, kökten başlayıp bir sonraki seviyeye geçmeden önce çocuklara doğru ilerleyerek düğümleri seviye seviye araştırır. Bu, bir sonraki seviyeye geçmeden önce her seviyedeki düğümlerin ziyaret edilmesini sağlar, bu da onu özellikle ağırlıklandırılmamış bir ağaçta en kısa yolu bulmak veya bir ağacı seviye seviye keşfetmek gibi görevler için yararlı kılar.

Grafikte BFS ile Fark: DFS'ye benzer şekilde, Grafik BFS, düğümler arasındaki döngülerin ve çoklu yolların varlığına uyum sağlar. Grafikler içindeki karmaşık ilişkiler ağında verimli bir şekilde gezinmek için ziyaret edilen düğümleri işaretleme ve özel sonlandırma koşulları gibi mekanizmalar kullanır.

Temel Göstergeler:

• Bir ağacı seviye seviye geçmeniz gerekiyor.
• Problemler ağırlıklandırılmamış grafiklerde en kısa yolu bulmayı içerir.
• Bir ağacı veya grafiği kapsamlı bir şekilde keşfetmek istiyorsunuz.

Şablon Kodu:

Python

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

Java

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. Birleşim Bulucu (Ayrık Küme Birleşimi)

Ayrık Küme Birliği (DSU) olarak da bilinen Birlik Bul veri yapısı, ayrık kümeleri veya bağlı bileşenleri içeren sorunları verimli bir şekilde yönetmek ve çözmek için kullanılır. Kümeleri birleştirme (birleştirme) ve bir elemanın ait olduğu kümeyi belirleme (bulma) işlemlerini sağlar. Union-Find, Kruskal'ın Minimum Yayılan Ağacı gibi algoritmalarda ve grafiklerde döngü tespitinde yaygın olarak kullanılır.

Union Find şu şekilde uygulanır:

1. Başlatma: Her biri ayrı bir ayrık küme olarak kabul edilen bir öğeler koleksiyonuyla başlayın. Her kümeye benzersiz bir temsilci (genellikle öğenin kendisi) atayın.
2. Birleştirme İşlemi: İki kümeyi birleştirmek için birleştirme işlemini gerçekleştirin. Bir kümenin temsilcisini seçin (genellikle sıralama veya boyut gibi bazı kriterlere göre) ve onu diğer kümenin temsilcisinin ebeveyni yapın. Bu, iki seti etkili bir şekilde birbirine bağlar.
3. Bulma İşlemi: Bir elemanın ait olduğu kümeyi belirlemeniz gerektiğinde bulma işlemini kullanın. Söz konusu öğeden başlayarak, kümesinin kök düğümünü (temsilcisini) bulmak için ağacı yukarı doğru hareket ettirin. Yol sıkıştırma tekniği, yol boyunca bulunan öğelerin doğrudan köke işaret etmesini sağlayarak gelecekteki bulma işlemlerini optimize etmek için burada uygulanabilir.
4. Döngü Algılama: Union-Find genellikle grafiklerdeki döngüleri algılamak için kullanılır. Birleştirme işlemi yapılırken her iki elemanın da aynı kümeye ait olması (yani aynı temsilciye sahip olması), düğümler arasına bir kenar eklenmesinin grafikte bir döngü yaratacağını gösterir.
5. Optimizasyon: Birleştirme Bul işlemlerinin verimliliğini artırmak için sıralamaya göre birleştirme ve yol sıkıştırma gibi çeşitli optimizasyon teknikleri uygulanabilir.

Şablon Kodu:

Python

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

Java

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. Topolojik Sıralama

Yönlendirilmiş bir döngüsel olmayan grafik (DAG), yönlendirilmiş döngüleri olmayan yönlendirilmiş bir grafiktir.

Topolojik Sıralama, yönlendirilmiş asiklik bir grafiğin ( DAG ) düğümlerini, her düğümün ardıllarından önce göründüğü doğrusal bir düzende düzenlemek için kullanılan bir algoritmadır. Bağımlılıkları planlamak, kodu derlemek ve çeşitli uygulamalardaki görevlerin önceliklerini analiz etmek gibi görevler için çok önemlidir.

Topolojik Sıralamanın adım adım dökümü aşağıda verilmiştir:

1. Başlatma: Bağımlılıkları olan görevleri veya düğümleri temsil eden yönlendirilmiş bir döngüsel olmayan grafik ( DAG ) ile başlayın. Sıralanan düğümleri tutmak için bir kuyruk başlatın.

2. Dereceli Hesaplama: Grafikteki her düğüm için dereceyi (gelen kenarların sayısını) hesaplayın. Derecesi 0 olan düğümlerin hiçbir bağımlılığı yoktur ve topolojik sıralamanın başlangıç noktası olmaya uygundur.

3. İlk Kuyruk Doldurma: Derecesi 0 olan tüm düğümleri kuyruğa alın. Bu düğümler ilk önce işlenebilir.

4. Topolojik Sıralama Döngüsü: Kuyruk boş değilken aşağıdaki adımları uygulayın:

   1. Kuyruğun ön kısmından bir düğümü kuyruktan çıkarın.
   2. Düğümü işleyin (örneğin sıralanmış listeye ekleyin).
   3. Düğümün komşularının her biri için (işaret ettiği düğümler), derecelerini 1 azaltın.
   4. Azalma sonucunda bir komşunun derecesi 0 olursa, onu kuyruğa alın.

5. Tamamlanma: Topolojik sıralama döngüsü tamamlandığında kuyruk boş olacak ve sıralanan liste, geçerli bir topolojik sıraya göre tüm düğümleri içerecektir.

6. Döngü Tespiti: Topolojik sıralama işlemi sırasında herhangi bir noktada kuyrukta derecesi 0 olan hiçbir düğüm kalmazsa, bu durum grafikte döngülerin varlığını gösterir ve topolojik sıralamayı imkansız hale getirir.

Topolojik Sıralamanın sonucu, düğümlerin bağımlılıklarına saygı duyan doğrusal bir sıralamasıdır, bu da onu çeşitli uygulamalardaki görevlerin planlanması veya yürütme sırasını analiz etmek için uygun hale getirir.

Temel Göstergeler:

• Sorun, bağımlılıkları olan görevlerin zamanlanmasını veya sıralanmasını içerir.
• Yönlendirilmiş bir döngüsel olmayan grafik (DAG) ile çalışıyorsunuz.
• Görevlerin bağımlılıklarına bağlı kalarak belirli bir sırayla yürütülmesi gerekir.

Şablon Kodu:

Python

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

Java

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. Denemeler (Önek-Ağaç)

Trie , verimli dize eşleştirme ve sözcüklerin depolanması için kullanılan ağaç benzeri bir veri yapısıdır. Ortak öneklere sahip dizeleri saklamanız ve aramanız gereken problemlerde mükemmeldir.

Bir Trie'nin nasıl uygulanacağı aşağıda açıklanmıştır:

1. Başlatma: Genellikle ilişkili karakteri olmayan bir kök düğümden oluşan boş bir Trie ile başlayın.

2. Ekleme: Trie'ye bir kelime eklemek için kök düğümden başlayın ve her seferinde bir karakter olacak şekilde ağaçta aşağı doğru ilerleyin. Kelimedeki her karakter için:

   1. Geçerli düğümün altında bu karaktere sahip bir alt düğümün olup olmadığını kontrol edin.
   2. Varsa alt düğüme geçin.
   3. Değilse, karakterle yeni bir alt düğüm oluşturun ve ona gidin.

3. Kelime Tamamlama: Trie'de bir kelimenin bulunup bulunmadığını kontrol etmek için, eklemeye benzer bir şekilde onu çaprazlayın. Kelimedeki her karakterin geçerli düğümün bir alt düğümüne karşılık geldiğinden emin olun. Geçiş kelimenin sonuna ulaşırsa ve son karakter düğümünde geçerli bir bitiş işareti (örneğin bir boole bayrağı) varsa, kelime Trie'de mevcuttur.

4. Önek Arama: Trie, önek aramada üstündür. Belirli bir öneke sahip tüm kelimeleri bulmak için, kök düğümden geçişe başlayın ve önekin karakterlerini takip ederek ağaçta aşağı doğru ilerleyin. Ön ekin son karakterine ulaştığınızda, aynı öneki paylaşan tüm kelimeleri bulmak için o düğümden derinlik öncelikli arama (DFS) gerçekleştirebilirsiniz.

5. Silme: Trie'den bir kelimeyi silmek için kelimeyi arayın. Kelimenin sonuna ulaştığınızda, bitiş işaretini (varsa) kaldırın. Düğümün başka alt öğesi yoksa, Trie'nin sözcüğü temsil eden dalının tamamını güvenli bir şekilde kaldırabilirsiniz.

Denemeler, özellikle geniş kelime dağarcığı söz konusu olduğunda hafıza açısından yoğun olabilir. Belleği optimize etmek için, sıkıştırma (örneğin, her düğümde bir karakter dizisi yerine bir harita kullanmak) ve budama (dönüşleri olmayan düğümlerin kaldırılması) gibi teknikler uygulanabilir.

Denemeler özellikle verimli dize eşleştirme, otomatik tamamlama önerileri, yazım denetleyicileri ve ortak öneklere sahip sözcüklerin dizine eklenmesi için kullanışlıdır. Ağaç benzeri bir yapıda paylaşılan öneklere sahip kelimeleri veya dizeleri depolamak ve aramak için hızlı ve yerden tasarruf sağlayan bir yol sağlarlar.

Temel Göstergeler:

• Dizelerle uğraşıyorsunuz ve verimli dize eşleştirmeye ihtiyacınız var.
• Sorunlar arasında otomatik tamamlama önerileri, yazım denetleyicileri veya ortak öneklere sahip sözcüklerin aranması yer alır.
• Kelimeleri verimli bir şekilde depolamak ve aramak istiyorsunuz.

Şablon Kodu:

Python

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

Java

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. Dinamik Programlama

Dinamik Programlama, bilgisayar bilimleri ve matematikte çok çeşitli karmaşık problemleri verimli bir şekilde çözmek için kullanılan güçlü bir problem çözme tekniğidir. Bir problemin daha basit alt problemlere bölünebilmesi ve bu alt problemlerin çözümlerinin genel problemi çözmek için birleştirilebilmesi özellikle değerlidir.

İşte temel özellikleri ve nasıl çalıştığı:

Optimum Altyapı:

• Bu özellik, daha büyük bir problemin optimal çözümünün, onun daha küçük alt problemlerinin optimal çözümlerinden oluşturulabilmesi özelliğini ifade eder.
• Başka bir deyişle, DP problemleri özyinelemeli bir yapı sergiler; burada bir problem için en uygun çözüm, alt problemlerin en iyi çözümlerine dayanır.
• Örneğin bir grafikte iki nokta arasındaki en kısa yolu bulurken herhangi iki ara nokta arasındaki en kısa yolun da optimal olması gerekir.

Örtüşen Alt Problemler:

• Çakışan alt problemler, aynı alt problemlerin hesaplama sırasında birden çok kez çözülmesi durumunda ortaya çıkar ve bu da gereksiz çalışmaya yol açar.
• Dinamik Programlama, alt problemlerin çözümlerini yeniden hesaplamayı önlemek için bir veri yapısında (genellikle bir tablo veya not dizisi) depolayarak bu sorunu çözmeyi amaçlar.
• Alt problem çözümlerinin bu şekilde saklanması ve yeniden kullanılması, algoritmanın zaman karmaşıklığını önemli ölçüde azaltır.

Dinamik Programlama Nasıl Çalışır:

1. Alt Sorunları Tanımlayın: DP kullanarak bir sorunu çözmenin ilk adımı alt sorunları tanımlamaktır. Sorunu, çözüldüğünde ana sorunun çözümüne katkıda bulunacak daha küçük, yönetilebilir alt problemlere ayırın.
2. Özyinelemeli Çözüm: Daha küçük alt problemlerin çözümleri açısından daha büyük bir problemin çözümünü ifade eden yinelemeli bir çözüm geliştirin. Bu özyinelemeli formülasyon en uygun altyapıyı yakalar.
3. Not Alma veya Tablolama: Çakışan alt problemleri çözmek için iki yaygın teknik arasından seçim yapabilirsiniz:
   • Notlandırma: Alt problemlerin sonuçlarını, hesaplandıkları sırada bir veri yapısında (genellikle bir dizi veya karma tablo) saklayın. Bir alt problemle tekrar karşılaşıldığında, çözümü yeniden hesaplamak yerine depodan alın. Bu aynı zamanda yukarıdan aşağıya yaklaşım olarak da bilinir.
   • Tablolama: Alt problemlerin çözümlerini aşağıdan yukarıya doğru depolamak için bir tablo (genellikle 2 boyutlu bir dizi) oluşturun. En küçük alt problemleri çözerek başlayın ve giderek ana probleme doğru ilerleyin.
4. Optimal Çözüm: Tüm alt problemler çözüldükten sonra, alt problemlerin çözümlerinin problemin yinelemeli yapısına göre birleştirilmesiyle ana problemin çözümü elde edilebilir.

Dinamik Programlama, grafiklerde en kısa yolları bulma, kaynak tahsisini optimize etme, kombinasyonları sayma, sırt çantası problemlerini çözme ve çok daha fazlasını içeren çok çeşitli problemlere uygulanır. Karmaşık sorunları daha basit parçalara bölerek ve gereksiz hesaplamalardan kaçınarak çözümleri optimize etme yeteneği, onu algoritma tasarımı ve optimizasyonunda temel bir teknik haline getirir.

Önemli Kavramlar: Aşağıdan Yukarıya Yaklaşım, Yukarıdan Aşağıya, Notlandırma, Tablolama

Temel Göstergeler:

• Problem daha küçük, örtüşen alt problemlere bölünebilir.
• Alt problemlere yönelik çözümleri depolayarak ve yeniden kullanarak optimizasyona ihtiyaç vardır.
• Optimizasyon veya saymayla ilgili problemleri çözmek istiyorsunuz.

Şablon Kodu:

Yukarıdan aşağıya notlandırma şablonu, dinamik programlamayı uygulamanın birçok yolundan biridir.

Python

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

Java

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. Geriye Dönüş

Geri izleme , farklı olasılıkları deneyerek sorunları aşamalı olarak çözmek ve bir çözüme götürmezlerse bunları geri almak için kullanılan genel bir algoritmik tekniktir. Kapsamlı bir arama gerektiğinde kullanılır.

Geri izlemenin nasıl çalıştığına dair ayrıntılı bir bakış:

1. Sorun Alanı Keşfi: Geriye doğru izleme, her seferinde tek parça bir çözümü aşamalı olarak oluşturarak sorun alanını araştırır. Her adımda bir karar verir ve ilerler.
2. Özyinelemeli Yapı: Geri izleme genellikle özyinelemeyi içerir. Başlangıçta kısmi bir çözümle başlar ve onu genişletmenin tüm olası yollarını araştırır. Bu süreç, tam bir çözüm bulunana veya geçerli bir çözümün bulunmadığı ortaya çıkana kadar yinelemeli olarak devam eder.
3. Karar Noktaları: Her adımda algoritmanın mevcut seçenekler arasından seçim yapması gereken karar noktaları vardır. Bu seçimler keşif sürecinde dallanmaya yol açmaktadır.
4. Çözümün Doğrulanması: Bir seçim yapıldıktan sonra algoritma mevcut kısmi çözümün geçerli olup olmadığını kontrol eder. Geçerliyse algoritma bir sonraki adıma geçer. Değilse, önceki seçimi geri alarak diğer seçenekleri keşfederek geri adım atar.
5. Fesih Koşulları: Geriye doğru izleme, iki koşuldan biri karşılanıncaya kadar devam eder:
   • Geçerli bir çözüm bulunur, bu durumda algoritma durur ve çözümü döndürür.
   • Geçerli bir çözümün bulunmadığı belirlenir ve bu noktada algoritma önceki bir karar noktasına geri döner ve farklı seçenekleri araştırır.
6. Budama: Aramayı optimize etmek için geri izleme genellikle budama stratejilerini içerir. Budama, geçersiz çözümlere yol açması garanti edilen yolların araştırılmasından kaçınmayı içerir ve arama alanını önemli ölçüde azaltır.

Geri İzleme Uygulamaları:

Geri izleme, aşağıdakiler de dahil olmak üzere çeşitli sorun alanlarında kullanılır:

• Sudoku ve N-Queens gibi bulmacaları çözmek.
• Permütasyon ve kombinasyon oluşturma.
• Grafiklerde ve ağaçlarda yollar aramak.
• Kısıt tatmini sorunları (örneğin, gezici satıcı sorunu).
• Oyun oynama algoritmaları (örneğin satranç yapay zekası).

Temel Göstergeler:

• Sorun, birden fazla olasılığın aşamalı olarak araştırılmasını içerir.
• Farklı seçenekleri denemeyi gerektiren karar noktaları veya kısıtlamalar vardır.
• Kapsamlı bir arama yoluyla tüm olası çözümleri bulmanız veya belirli koşulları karşılamanız gerekir.

Şablon Kodu:

Python

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

Java

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. Aralıkları Birleştir

Aralıkların birleştirilmesi, üst üste binen veya bitişik aralıkların birleştirilmiş bir küme halinde birleştirilmesini içerir ve sıklıkla zaman aralıkları veya çizelgelemeyle ilgili problemlerde kullanılır. Aralık bazlı işlemleri basitleştirir.

Aralıkları birleştirmenin nasıl çalıştığına daha yakından bakalım:

1. Aralık Gösterimi: Aralıklar tipik olarak başlangıç ve bitiş noktası çiftleri olarak temsil edilir (örneğin, [start, end] ).
2. Sıralama: Aralıkları verimli bir şekilde birleştirmek için bunları başlangıç noktalarına göre sıralayarak başlayın. Bu, sıralanan listede örtüşen veya bitişik aralıkların bitişik olmasını sağlar.
3. Birleştirme İşlemi: Birleştirilen aralıkları tutmak için boş bir liste başlatın. Ardından, sıralanan aralıkları birer birer yineleyin:
   • Geçerli aralık öncekiyle örtüşmüyorsa bunu birleştirilmiş aralıklar listesine ekleyin.
   • Bir çakışma varsa önceki birleştirilmiş aralığın uç noktasını, hem mevcut hem de önceki aralıkları kapsayacak şekilde güncelleyin ve bunları etkili bir şekilde birleştirin.
4. Tamamlama: Tüm aralıklar işlendikten sonra, birleştirilmiş aralıkların listesi örtüşmeyen ve birleştirilmiş aralıklar içerecektir.

Birleştirme Aralıklarının Uygulamaları:

Birleştirme aralıkları yaygın olarak şu durumlarda kullanılır:

• Planlama ve zaman yönetimi uygulamaları.
• Takvim sistemlerinde çakışan olay tespiti.
• Veritabanı sorgularında olduğu gibi aralık bazlı veri analizi.
• Kaynak tahsisi ve toplantı planlamasıyla ilgili sorunları çözme.

Bu teknik, örtüşen aralıkları birleştirerek aralık bazlı işlemleri basitleştirir ve çeşitli uygulamalarda verimliliği artırır.

Temel Göstergeler:

• Aralıklarla veya zamana dayalı verilerle uğraşıyorsunuz.
• Sorunlar örtüşen veya bitişik aralıkların birleştirilmesini içerir.
• Aralık bazlı işlemleri basitleştirmek veya etkinlik zamanlamasını optimize etmek istiyorsunuz.

Şablon Kodu:

Python

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

Java

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

Daha fazla öğrenmek ister misiniz?

Bu kalıplar hakkında daha fazla bilgi edinmek ve bir sonraki kodlama görüşmenizde bunları nasıl daha etkili bir şekilde uygulayabileceğinizi öğrenmek istiyorsanız bugün techinterviews.io'ya göz atın! Sizi bir sonraki kodlama röportajınıza hazırlamak için veri yapıları , algoritmalar , davranışsal röportajlar ve hatta maaş pazarlığı gibi konuları kapsayan kapsamlı bir müfredat sunuyoruz. Hatta pratik yapmanız için yerleşik bir kodlama çalışma alanımız bile var.

Kodlama görüşmesi hazırlığınızı bugün TECH30 promosyon kodumuzla 30 $ indirimle güçlendirin!