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 Bu yaklaşım, net bir plan veya strateji olmadan mümkün olduğu kadar çok sorununu çözmeyi içerir. Bu verimli bir strateji gibi görünse de birçok dezavantajı var. "eziyet" uygulamasıdır. LeetCode 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. , , , 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. İki İşaretçi Kayan Pencere Değiştirilmiş İkili Arama Topolojik Sıralama 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 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. En İyi 15 Kodlama Modeli Bu makalede pek çok konuyu ele alsam da, daha derinlemesine eğitim, açıklamalar ve kodlama pratiği istiyorsanız Techinterviews.io adresindeki göz atabilirsiniz Ayrıca , ve hatta gibi önemli konuları da ele alıyoruz. Kapsamlı Kodlama Mülakat Hazırlık Kursumuza . veri yapıları davranışsal görüşmeler maaş pazarlığı Ş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: Üç değişkeni tanımlayarak başlayın: , ve . Geçerliyi bağlantılı listenin başı olarak ayarlayın ve önceki ve sonrakini Yok olarak başlatın. geçerli önceki sonraki Geçerli değişken olmasa da aşağıdaki şekilde ilerleyin: Yok düğümü geçici bir değişkende saklayın. Sonraki düğümün işaretçisini düğümü işaret edecek şekilde ters çevirin. Geçerli önceki Geçerli düğüm olmak için güncelleyin ve düğüm olacak güncelleyin. öncekini sonraki şekilde Son olarak, ters çevrilmiş listenin , değişkende saklanan, ulaşılan son düğüme ayarlayın. başlığını önceki 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 ç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. Değiştirilmiş İkili Arama, Eğer size sıralanmış bir dizi, bağlantılı liste veya matris verildiyse, kullanmayı düşünün. değiştirilmiş bir ikili arama Bu modelin sıralanmış bir veri yapısına nasıl uygulanacağının bir dökümü burada verilmiştir: ve 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: . Başlangıç bitiş middle = start + (end - start) / 2 Anahtarın dizindeki öğeyle eşleşip eşleşmediğini kontrol edin. Eğer öyleyse, sonuç olarak dizini döndürün. orta ortadaki Anahtar dizindeki öğeyle eşleşmiyorsa sonraki adımlara geçin. orta Anahtarın indeks elemandan küçük olup olmadığını değerlendirin. Öyleyse, uçtan doğru güncelleyerek arama aralığınızı daraltın . ortadaki ortaya - 1 Tersine, eğer anahtar indeksteki elemandan büyükse, olarak güncelleyerek arama aralığınızı ayarlayın. orta start'ı orta + 1 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 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. İki İşaretçi tekniği, 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 'den ye düşürebilirsiniz. O(n^2) O(n)' modeli, her biri belirli senaryolara göre uyarlanmış çeşitli varyasyonları kapsar. Bu varyasyonlar , ve olarak bilinen, genellikle 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. "İki İşaretçi" aynı yönü zıt yönü "hızlı ve yavaş" "kaplumbağa ve tavşan" Bir veri yapısında geçiş yapmak için birden fazla işaretçi kullanıyorsanız yaklaşımınızı modelini takip ederek kategorize edebilirsiniz. "İki İşaretçi" 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 ( kaba kuvvet çözümü) karşı karşıya kalırken, İki İşaretçi kullanmayı düşünün. O(n^2) Şablon Kodu: varyasyonu için şablon “Ters yön” 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 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. Kayan Pencere tekniği, Bu model genellikle pencere içindeki bireysel verilerin takibini kolaylaştırmak için bir karma haritası kullanır. Ancak bu yaklaşımın kadar uzay-zaman karmaşıklığına yol açabileceğini unutmamak önemlidir. O(n) 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 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: 'K' elemanlarını minimum veya maksimum yığınımıza ekliyoruz (Bu, uygulamaya bağlıdır). 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 topKElements(int[] arr, int k) { PriorityQueue 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 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: En büyük öğeyi tanımlamak için Maksimum Yığın ve en küçüğünü bulmak için Min Yığın. İki yığın kullanın: Max Heap'i sayıların ilk yarısıyla doldurun ve aralarından en büyüğünü bulmayı hedefleyin. Bu kısımdaki en küçüğü belirlemek için Min Heap'i sayıların ikinci yarısıyla doldurun. 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 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.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 minHeap; // Right heap to store larger half private PriorityQueue 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 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] 0 && stack[stack.length - 1] 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 veya , 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. DFS Derinlik Öncelikli Arama Bir ağaçta DFS gerçekleştirmek için kökten başlamanız gerekir. Daha sonra aşağıdaki adımları izleyin: Geçerli düğümü, alt düğümlerini (genellikle ziyaret ederek keşfedin. soldan sağa) Ağacın derinliklerine inerek . DFS işlemini her alt düğüme yinelemeli olarak uygulayın Tüm alt düğümler ziyaret edildikten sonra ana düğüme . geri dönülür 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 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, ve 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. Grafikte DFS ile Fark: ziyaret edilen düğümlerin işaretlenmesi geri izlemenin uygun şekilde işlenmesi 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: Ziyaret edilecek düğümleri takip etmek için boş bir kuyruk veri yapısını başlatın. Kök düğümü kuyruğa . alın Kuyruk boşalana kadar bir döngü girin: Kuyruğun önündeki düğümü kuyruktan çıkarın. Sıradan çıkarılan düğümü işleyin (örneğin ziyaret edin veya üzerinde bazı işlemler gerçekleştirin). Düğümün tüm alt öğelerini (varsa) kuyruğa alın. Sıra boşalana kadar . 3a-3c adımlarını tekrarlayın 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 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. seviye seviye 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. Grafikte BFS ile Fark: 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 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 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. Küme Birliği (DSU) Union Find şu şekilde uygulanır: 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. Başlatma: İ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. Birleştirme İş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. Bulma İşlemi: 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. Döngü Algılama: 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. Optimizasyon: Birleştirme Ş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 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. yönlendirilmiş asiklik bir grafiğin ( ) 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ıralama, DAG Topolojik Sıralamanın adım adım dökümü aşağıda verilmiştir: Bağımlılıkları olan görevleri veya düğümleri temsil eden yönlendirilmiş bir döngüsel olmayan grafik ( ) ile başlayın. Sıralanan düğümleri tutmak için bir kuyruk başlatın. Başlatma: DAG 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. Dereceli Hesaplama: Derecesi 0 olan tüm düğümleri kuyruğa alın. Bu düğümler ilk önce işlenebilir. İlk Kuyruk Doldurma: Kuyruk boş değilken aşağıdaki adımları uygulayın: Topolojik Sıralama Döngüsü: Kuyruğun ön kısmından bir düğümü kuyruktan çıkarın. Düğümü işleyin (örneğin sıralanmış listeye ekleyin). Düğümün komşularının her biri için (işaret ettiği düğümler), derecelerini 1 azaltın. Azalma sonucunda bir komşunun derecesi 0 olursa, onu kuyruğa alın. 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. Tamamlanma: 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. Döngü Tespiti: 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 findIndegree(Map > graph) { Map 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 topologicalSort(Map > graph) { List result = new ArrayList<>(); Queue queue = new LinkedList<>(); Map 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ç) , 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. Trie Bir Trie'nin nasıl uygulanacağı aşağıda açıklanmıştır: Genellikle ilişkili karakteri olmayan bir kök düğümden oluşan boş bir Trie ile başlayın. Başlatma: 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: Ekleme: Geçerli düğümün altında bu karaktere sahip bir alt düğümün olup olmadığını kontrol edin. Varsa alt düğüme geçin. Değilse, karakterle yeni bir alt düğüm oluşturun ve ona gidin. 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. Kelime Tamamlama: 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. Önek Arama: 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. Silme: 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 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 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. Dinamik Programlama, İş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: 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. Alt Sorunları Tanımlayın: 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. Özyinelemeli Çözüm: Çakışan alt problemleri çözmek için iki yaygın teknik arasından seçim yapabilirsiniz: Not Alma veya Tablolama: 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 yaklaşım olarak da bilinir. Notlandırma: yukarıdan aşağıya Alt problemlerin çözümlerini 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. Tablolama: aşağıdan yukarıya 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. Optimal Çözüm: 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. Aşağıdan Yukarıya Yaklaşım, Yukarıdan Aşağıya, Notlandırma, Tablolama Önemli Kavramlar: 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 memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map 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üş , 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 izleme Geri izlemenin nasıl çalıştığına dair ayrıntılı bir bakış: 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. Sorun Alanı Keşfi: 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. Özyinelemeli Yapı: 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. Karar Noktaları: 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. Çözümün Doğrulanması: izleme, iki koşuldan biri karşılanıncaya kadar devam eder: Fesih Koşulları: Geriye doğru 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. 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. Budama: 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: Aralıklar tipik olarak ve noktası çiftleri olarak temsil edilir (örneğin, ). Aralık Gösterimi: başlangıç bitiş [start, end] 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. Sıralama: Birleştirilen aralıkları tutmak için boş bir liste başlatın. Ardından, sıralanan aralıkları birer birer yineleyin: Birleştirme İşlemi: 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. Tüm aralıklar işlendikten sonra, birleştirilmiş aralıkların listesi örtüşmeyen ve birleştirilmiş aralıklar içerecektir. Tamamlama: 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 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 göz atın! Sizi bir sonraki kodlama röportajınıza hazırlamak için , , ve hatta 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. techinterviews.io'ya veri yapıları algoritmalar davranışsal röportajlar maaş pazarlığı Kodlama görüşmesi hazırlığınızı bugün promosyon kodumuzla 30 $ indirimle güçlendirin! TECH30 @Limarc'ın öne çıkan görseli "kod yazan bir geliştirici" ile yapılan grafikler Okso.app