Algorithm Design Techniques
Definition of Divide and Conquer:
Divide and Conquer is a powerful algorithm design technique used to solve complex problems by breaking them into
smaller, simpler sub-problems, solving each sub-problem recursively, and then combining their results to get the final
solution.
Real-Life Divide and Conquer Examples
Client: "Our e-commerce platform has over 10 million customer names. We want to display them alphabetically in the
user dashboard instantly, even when the server load is high."
Solution: Use Merge Sort — a stable, efficient sorting method used in large systems like Amazon backend.
2. Client: "I have a massive, already sorted list of 1 million transaction IDs. I need a function that can instantly
verify whether a specific transaction ID (e.g., 872345) exists."
Solution: Use Binary Search — a classic divide and conquer technique, implemented in databases and search
engines like Google’s index searching.
3. Client: "We have thousands of GPS coordinates from delivery vehicles across the country. We need to identify
the two vehicles that are geographically closest to each other."
Solution: Use Closest Pair of Points algorithm — used in logistics software like FedEx or Uber backend to
optimize routes.
4. Client: "Our news app stores massive text documents from different sources. We want to check whether two
documents are completely identical in content, quickly."
Solution: Use Divide and Conquer file comparison — break files into blocks, compare block-wise
recursively. Used in tools like WinMerge and file sync software.
5. Client: "I want to implement a spell checker that can check thousands of typed words against a dictionary in
real-time."
Solution: Use Binary Search (if dictionary is sorted) or Trie with divide logic — used in Microsoft Word
and Google Docs spell checkers.
6. Client: "We collect thousands of product reviews daily. Our site needs to sort all of them based on rating and
time to show most relevant ones first."
Solution: Use Quick Sort — fast sorting using pivot technique. Used in YouTube comment sorting and
Flipkart review systems.
7. Client: "My organization has 10 regional servers, each maintaining its own timestamped logs. I need to merge
all of them into a single time-ordered log for analysis."
Solution: Use Merge k Sorted Lists — divide log files and recursively merge. Used in distributed systems
and server monitoring tools like Datadog.
Key Signs You Should Think “Divide and Conquer”:
• The input is large or massive.
• You can break it down into smaller tasks.
• Combining results from smaller tasks makes the full answer.
• Speed is critical (client needs performance).
• Tasks are independent (no need to remember past results).
Algorithm Design Techniques Explained with Real-Life Client Problems
2. Dynamic Programming (DP)
Definition:
Dynamic Programming is used to solve problems with overlapping sub-problems (same sub-questions asked again
and again) and optimal substructure (small solutions help build the big solution), where results of sub-problems are
stored to avoid precomputation.
Key Steps:
• Break into sub-problems.
• Store solutions (memorization/tabulation) (saving answers in memory or table).
• Build final solution using stored values.
Real-Life Client Problems & Solutions:
1. Client: "What is the least number of coins needed to make Rs. 31 using coins of Rs. 1, 5, 10?"
Solution: Use Coin Change Problem (DP).
2. Client: "Find the longest path in this job dependency graph."
Solution: Use Longest Path DP (used when one task depends on others).
3. Client: "What's the cheapest way to travel from city A to B through connected flights?"
Solution: Use Shortest Path (Bellman-Ford, DP version).
4. Client: "Count the number of unique ways to reach step 10 by jumping 1, 2, or 3 steps."
Solution: Use Staircase Problem (DP).
5. Client: "Calculate the nth Fibonacci number fast."
Solution: Use Fibonacci DP with memorization (Fibonacci means adding last two numbers: 0, 1, 1, 2, 3...
etc.).
Key Signs You Should Think "Dynamic Programming":
• Sub-problems repeat multiple times.
• Need to store previous results.
• There is a clear dependency between steps.
• Optimal solution needs to be built from past choices.
3. Greedy Algorithm
Definition:
Greedy algorithms make the locally best choice at each step, with the hope of finding a global optimum (best overall
result).
Key Steps:
• Sort or prioritize elements.
• Pick the best available choice.
• Repeat until goal is achieved.
Real-Life Client Problems & Solutions:
1. Client: "We need to schedule maximum non-overlapping meetings in one day."
Solution: Use Activity Selection (Greedy) (pick meetings that finish earliest).
2. Client: "Select minimum number of coins to give Rs. 87 using Rs. 1, 2, 5, 10."
Solution: Use Greedy Coin Change (only works with standard coin sets).
3. Client: "Choose tasks to maximize profit given deadlines."
Solution: Use Job Scheduling (Greedy).
4. Client: "We have limited bandwidth. Choose the most valuable files to upload."
Solution: Use Fractional Knapsack (Greedy) (fill bag with highest value per weight).
5. Client: "Connect all cities with minimum cable cost."
Solution: Use Prim’s or Kruskal’s (Greedy MST) (used in internet cable and electrical networks).
Key Signs You Should Think "Greedy Algorithm":
• You can always pick the best local option.
• No need to look back or undo decisions.
• Problem has the greedy-choice property.
• Sorting or priority can guide the solution.
4. Backtracking
Definition:
Backtracking is a trial-and-error method used to solve problems where multiple solutions are possible. It explores all
options and backtracks (goes back) when a choice fails.
Key Steps:
• Choose an option.
• Explore further.
• Backtrack if it fails (go back and try another option).
Real-Life Client Problems & Solutions:
1. Client: "Find all possible combinations of a lock code (4 digits)."
Solution: Use Backtracking.
2. Client: "Can you solve this Sudoku board automatically?"
Solution: Use Sudoku Solver (Backtracking) (Sudoku is a number puzzle game).
3. Client: "Find all valid ways to arrange 8 queens on a chessboard."
Solution: Use N-Queens Problem (Backtracking) (chess problem where no queen attacks the other).
4. Client: "Print all valid passwords with specific conditions (e.g., one digit, one capital)."
Solution: Use Password Generator with constraints.
5. Client: "Build all valid file paths given folder rules."
Solution: Use Recursive backtracking on folder trees.
Key Signs You Should Think "Backtracking":
• The problem has multiple possible answers.
• You need to explore all combinations.
• Constraints must be checked at every step.
• You can discard partial solutions early (pruning).
Algorithm Design Techniques Explained with Real-Life Client Problems
Comparative Table of Algorithm Techniques
Technique Simple Meaning When to Use (Signs) Real-Life Examples
Divide and Divide problem, Problem can be broken into smaller Sorting big list, searching sorted
Conquer solve parts, then join same-type problems data, GPS location matching
Dynamic Store and reuse Sub-problems repeat, need to save Minimum coins, flight cost,
Programming solutions previous answers staircase ways, Fibonacci
Greedy Best choice at each Always pick local best option, don’t Meeting scheduling, coin change,
Algorithm step (quick decision) need to go back file upload, cable cost
Try all options, back Multiple answers possible, explore Sudoku, lock codes, password
Backtracking
if wrong combinations, follow rules/constraints making, chess queen arrangement
3. Greedy Algorithm – Meeting Scheduler
Problem:
The client says: “I want to schedule as many meetings as possible in one day without any overlaps.”
Data:
Start times = [1, 3, 0, 5, 8, 5]
End times = [2, 4, 6, 7, 9, 9]
Real-life Example:
You have 6 meetings. You want to schedule as many of them as possible in one hall, but only one meeting can be held
at a time.
Greedy Approach:
• First, sort all meetings based on their end times.
• Select the first meeting that finishes the earliest.
• Then, choose the next meeting that starts after the last selected meeting ends.
Meetings Selected:
(1,2), (3,4), (5,7), (8,9)
Total = 4 meetings
Greedy Logic:
At every step, choose the best local option (the meeting that ends the earliest) and keep moving forward.
4. Backtracking – 4-Digit Lock Code (No Same Digit Twice in a Row)
Problem:
The client says: “I need a 4-digit lock code where no digit appears twice in a row. Each digit can be 0, 1, or 2.”
Real-life Example:
You're building a password generator with the following rules:
• The password must be exactly 4 digits long.
• Each digit must be from 0 to 2 (only these three values).
• No digit should repeat immediately (like 00, 11, 22 — these are not allowed).
Backtracking Approach:
• For the first digit, try all options: 0, 1, 2.
• For the second digit, again try 0, 1, 2 — but skip it if it's the same as the previous one.
• Do the same for the next digits.
• If at any step a rule breaks, go back (backtrack) and try another option.
• When all 4 digits are complete and valid, print/save the result.
Example Valid Codes:
• 0120 • 1021 • 1201
Invalid Example:
• 1120 → Not allowed because 11 is a repeat.
