Day 10 of 30 days of Data Structures and Algorithms and System Design Simplified — Divide and Conquer technique
Welcome back peeps. Hope all’s well. In this post we will cover Divide and Conquer technique as follows —
What and Why Divide and Conquer technique(in 2–3 sentences)?
How does Divide and Conquer technique work?
Important Patterns and Techniques in Divide and Conquer technique Questions
Most Important Questions with Solutions
Tips and Techniques to solve Divide and Conquer Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Divide and Conquer Technique
Importance : High
Note : New Divide and Conquer technique questions with solutions will be added everyday. So keep checking this post daily.
Let’s dive in!
What is Divide and Conquer technique?
Divide and Conquer is a technique in which we —
Divide — Divide the problem into two or smaller subproblems or instances
Conquer — Solve the subproblems recursively
Combine — Combine the solution to the subproblems into a global solution for the original problem.
Divide and Conquer makes very efficient use of memory caches and helps in developing an optimized algorithm to the difficult problems.
Examples of Divide and Conquer technique problems —
Merge Sort
Closest Pair of Point
Quick Sort
Partition Find
Skyline problem
Subset Sum
How does Divide and Conquer technique work?
Divide and conquer is a problem-solving technique that involves breaking a problem down into smaller subproblems, solving each subproblem individually, and then combining the solutions to the subproblems to solve the original problem. This technique is often used to solve problems that are too complex to be solved by a single, straightforward approach.
The divide and conquer technique typically involves recursively breaking down the problem into smaller subproblems, until the subproblems become simple enough to be solved directly. Once the subproblems have been solved, the solutions are combined to solve the original problem.
The main gist of Divide and Conquer is —
1.The divide and conquer technique splits N inputs into k subsets where 1<k≤ N which leads to k sub problems.
2. These subproblems are solved recursively and sub solutions are produced
3. Then the sub solutions are combined together to form one global solution to the original problem.
Important Patterns and Techniques in Divide and Conquer technique Questions
Important patterns and techniques in divide and conquer technique questions include identifying the subproblems, understanding how the subproblems relate to the original problem, and recognizing the appropriate time to use the divide and conquer technique.
Divide the larger problem into two or more smaller instances, solve the smaller instances recursively and then combine the sub solutions to get the final solution.
Patterns → Questions like below belong to Divide and Conquer technique technique( not limited to):
Merge Sort
Merge Lists
Closest Pair of Point
Quick Sort
Partition Find
Skyline problem
Subset Sum
Most Important Questions with Solutions
Note : New Divide and Conquer technique questions with solutions are added everyday. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Divide and Conquer technique questions.
Sort List
Question —
Given the head of a linked list, return the list after sorting it in ascending order.
Example :
Input: head = [4,2,1,3]
Output: [1,2,3,4]Solution :
Main Logic/Idea —
The main gist is — Using the two pointers ( slow and fast pointer) get to the mid of the list. Sort the left list and the right list recursively as the sub problems. Then merge the sub lists by comparing the list node values and simultaneously incrementing the tail.next pointer.
Implementation —
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
l = head
r = self.gmid(head)
t1 = r.next
r.next = None
r = t1
l = self.sortList(l)
r = self.sortList(r)
return self.merge(l,r)
def merge(self,list1,list2):
temp= ListNode()
tail = temp
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1= list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
if list2:
tail.next = list2
return temp.next
def gmid(self,head):
first,second = head, head.next
while second and second.next:
first = first.next
second = second.next.next
return firstQuestion Link
Similar Pattern —
Sort Linked List Already Sorted Using Absolute Values
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Merge k Sorted Lists
Question —
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example :
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]Solution :
Main Logic/Idea —
The main logic is — divide the lists ( alternate nodes), sort the list1 and the list2 recursively as the sub problems. Then merge the sub lists by comparing the list node values and simultaneously incrementing the tail.next pointer.
Implementation —
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
while len(lists) > 1:
finalList=[]
for i in range(0,len(lists),2):
list1 = lists[i]
list2 = lists[i+1] if (i+1) < len(lists) else None
finalList.append(self.subMerge(list1,list2))
lists = finalList
return lists[0]
def subMerge(self,list1,list2):
temp = ListNode()
tail = temp
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1 :
tail.next = list1
elif list2:
tail.next = list2
return temp.nextQuestion Link
Similar Pattern —
Smallest Subarrays With Maximum Bitwise OR
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Divide and Conquer technique questions with solutions will be added everyday. So keep checking this post daily.
Tips and Techniques to solve Divide and Conquer technique Questions Fast —
Remember the gist of Divide and Conquer technique is to break the problem into subproblems/instances of the same type and then solve the sub problems recursively and lastly combine all the sub solutions to get the final solution.
To solve the Divide and Conquer technique questions fast —
Know how to implement merge sort and quick sort ( this will help you understand Divide and conquer in depth)
Get a better hand on Recursion and Two pointer technique.
Learn how to combine the sub solutions efficiently.
That’s it for now. Day 11: Arrays coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
