Senior LevelData Structures & Algorithms
What is the difference between Online and Offline algorithms?
❓ Interview Prompt: Distinguish Online (process input as it arrives) vs Offline (all input available) algorithms, competitive ratios, and examples.
Online Algorithm:
Must process each input piece as it arrives, without knowledge of future inputs.
•
Example: Reservoir Sampling, LRU eviction, ski rental problem.
•
Competitive Ratio: $\frac{\text{Online cost}}{\text{Optimal offline cost}}$. A $c$-competitive algorithm is at most $c$ times worse than optimal.
Offline Algorithm:
Has access to the entire input before processing. Can sort, preprocess, and query in any order.
•
Example: Merge Sort, Mo's Algorithm, Floyd-Warshall.
Trade-offs:
| | Online | Offline |
|---|---|---|
| Input knowledge | Incremental | Full |
| Optimal possible | Sometimes impossible | Often achievable |
| Real-world fit | Streaming/real-time | Batch processing |
Code Implementation Example
typescript
// Online: LRU cache eviction (must decide without knowing future requests)
// Competitive ratio: O(log N) vs optimal offline (Optimal Page Replacement)
// Offline: Sort requests by next access time (Bélády's Algorithm)
// Optimal — evict the page accessed farthest in the future
// But requires knowing all future accesses → offline only!
// Ski Rental Problem (classic online problem):
// Rent skis for R per day vs buy for B. Optimal online strategy:
// Rent until day B/R, then buy. Competitive ratio = 2 - R/B ≈ 2.
function skiRentalOnline(rentCost: number, buyCost: number, days: number): number {
// Optimal online strategy: rent until break-even day
const breakEvenDay = Math.ceil(buyCost / rentCost);
if (days <= breakEvenDay) return days * rentCost; // rented entire time
return breakEvenDay * rentCost + buyCost; // switch to buying
}💡Ski rental: classic 2-competitive online algorithm vs optimal offline.
🎯 Interview Key Takeaway
Online algorithms process streaming data with competitive ratio analysis. Mo's Algorithm is a classic offline-only O(√N) approach that cannot be made online.
#DSA#Online Algorithms#Offline Algorithms#Competitive Ratio#Senior
Back to all Data Structures & Algorithms Questions→