Divide-and-Conquer and Greedy
Concepts covered: Dynamic Programming
You do not need to implement sorting algorithms or solve textbook puzzles to benefit from algorithmic thinking. The core patterns behind famous algorithms show up constantly in data engineering, just wearing different clothes. Once you recognize the pattern, you can reason about performance, predict bottlenecks, and choose the right tool for the job.
Pattern 1: Divide and Conquer
The idea is simple: break a big problem into smaller pieces, solve each piece independently, then combine the results. This is exactly what MapReduce does. The "map" phase divides your data across workers, each worker processes its piece independently, and the "reduce" phase combines the results. Spark, Hadoop, and every distributed data framework follow this pattern.
Why is this pattern so powerful? Because the pieces can be processed in parallel. If you split 1 billion rows across 100 machines, each machine only handles 10 million rows. The total work is still O(n), but the wall-clock time drops by a factor of 100. This is the fundamental promise of distributed computing: divide the problem, conquer each piece on a separate machine.
# Divide-and-conquer thinking applied to data processing
def process_chunk(chunk):
"""Process one chunk: filter and aggregate."""
total = sum(row["amount"] for row in chunk if row["status"] == "completed")
count = sum(1 for row in chunk if row["status"] == "completed")
return {"total": total, "count": count}
def combine_results(results):
"""Combine chunk results into final answer."""
grand_total = sum(r["total"] for r in results)
grand_count = sum(r["count"] for r in results)
return grand_total, grand_count
# Simulate splitting data across 4 "workers"
all_orders = [
{"id": i, "amount": i * 10, "status": "completed" if i % 3 != 0 else "pending"}
for i in range(1, 101)
]
# Divide into 4 chunks
chunk_size = len(all_orders) // 4
chunks = [all_orders[i:i+chunk_size] for i in range(0, len(all_orders), chunk_size)]
# Each "worker" processes independently
chunk_results = [process_chunk(c) for c in chunks]
# Combine
total, count = combine_results(chunk_results)
print(f"Processed {len(all_orders)} orders across {len(chunks)} chunks")
print(f"Completed orders: {count}")
print(f"Total revenue: ${total:,}")
print(f"Average order: ${total / count:,.0f}")Output:
Processed 100 orders across 4 chunks Completed orders: 66 Total revenue: $34,320 Average order: $520
Pattern 2: Greedy Algorithms
A greedy algorithm makes the best available choice at each step without looking ahead. It does not consider every possible combination. It simply picks what looks best right now and moves on. This is exactly how database query optimizers work.
When your database runs a query that joins five tables, it needs to decide the order of the joins. The number of possible join orders grows factorially: 5 tables have 120 possible orderings, 10 tables have over 3.6 million. Testing every ordering would be far too slow. So the optimizer uses a greedy approach: at each step, it picks the join that produces the smallest intermediate result. This does not always find the absolute best ordering, but it finds a good ordering very quickly.
Why it matters: the number of valid join orderings for N tables is N factorial. At five tables there are 120 orderings to evaluate. At eight tables there are over forty thousand. This is why query optimizers use heuristics above a certain table count rather than testing every permutation.
# Greedy thinking: always pick the best next step
def greedy_task_scheduler(tasks):
"""Schedule tasks to minimize total waiting time.
Greedy approach: always run the shortest task next.
This is provably optimal for this problem!"""
tasks_sorted = sorted(tasks, key=lambda t: t["duration"])
time_elapsed = 0
total_wait = 0
schedule = []
for task in tasks_sorted:
time_elapsed += task["duration"]
total_wait += time_elapsed
schedule.append(task["name"])
return schedule, total_wait
# ETL pipeline tasks with different durations
pipeline_tasks = [
{"name": "validate_schema", "duration": 2},
{"name": "load_dim_tables", "duration": 15},
{"name": "clean_nulls", "duration": 5},
{"name": "deduplicate", "duration": 8},
{"name": "write_to_warehouse", "duration": 20},
]
order, total = greedy_task_scheduler(pipeline_tasks)
print("Optimal schedule (shortest first):")
for i, name in enumerate(order, 1):
print(f" {i}. {name}")
print(f"\nTotal waiting time: {total} minutes")
# Compare: worst order (longest first)
worst_order, worst_total = greedy_task_scheduler(
sorted(pipeline_tasks, key=lambda t: -t["duration"])
)
print(f"Worst order waiting: {worst_total} minutes")
print(f"Greedy saves {worst_total - total} minutes of waiting.")Output:
Optimal schedule (shortest first): 1. validate_schema 2. clean_nulls 3. deduplicate 4. load_dim_tables 5. write_to_warehouse Total waiting time: 112 minutes Worst order waiting: 168 minutes Greedy saves 56 minutes of waiting.
Pattern 3: Dynamic Programming (Caching Previous Work)
Dynamic programming sounds intimidating, but the core idea is straightforward: if you have already computed something, do not compute it again. Save the result and reuse it. This is the exact same idea behind incremental ETL. Instead of reprocessing your entire dataset every time your pipeline runs, you process only the new or changed records and reuse the results from previous runs.
# Dynamic programming thinking applied to ETL
class IncrementalAggregator:
"""Maintains running aggregates without reprocessing.
This is DP thinking: reuse previous results."""
def __init__(self):
self.total = 0
self.count = 0
self.records_processed = 0
def process_batch(self, new_records):
"""Process only new records. O(batch_size), not O(total)."""
for record in new_records:
self.total += record["amount"]
self.count += 1
self.records_processed += len(new_records)
def get_average(self):
return self.total / self.count if self.count else 0
# Simulate daily incremental loads
agg = IncrementalAggregator()
day1 = [{"amount": 100}, {"amount": 250}, {"amount": 75}]
agg.process_batch(day1)
print(f"Day 1: processed {len(day1)} records")
print(f" Running avg: ${agg.get_average():.2f}")
day2 = [{"amount": 300}, {"amount": 50}]
agg.process_batch(day2)
print(f"Day 2: processed {len(day2)} new records (not all {agg.count})")
print(f" Running avg: ${agg.get_average():.2f}")
day3 = [{"amount": 500}, {"amount": 125}, {"amount": 200}, {"amount": 80}]
agg.process_batch(day3)
print(f"Day 3: processed {len(day3)} new records (not all {agg.count})")
print(f" Running avg: ${agg.get_average():.2f}")
print(f"\nTotal records in system: {agg.count}")
print(f"Records actually processed today: {len(day3)}")
print(f"Full refresh would reprocess all {agg.count} every time.")Output:
Day 1: processed 3 records Running avg: $141.67 Day 2: processed 2 new records (not all 5) Running avg: $155.00 Day 3: processed 4 new records (not all 9) Running avg: $186.67 Total records in system: 9 Records actually processed today: 4 Full refresh would reprocess all 9 every time.
Recognizing Patterns in the Wild
- Textbook Name
- Divide and conquer
- Greedy algorithm
- Dynamic programming
- Memoization / caching
- Data Engineering Name
- MapReduce / Spark partitioning
- Query optimizer join ordering
- Incremental ETL / CDC pipelines
- Materialized views / result caching
You do not need to memorize algorithm names to be a great data engineer. But recognizing these patterns helps you understand why certain tools are fast, why certain approaches scale, and why certain designs are fundamentally better than others. When someone says "our pipeline does a full refresh every hour," you can immediately think: "That is recomputing from scratch instead of reusing previous results. Could we apply the dynamic programming pattern and go incremental?"
About this lesson
This section is part of the Complexity: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.