What are Online Algorithms?
Learn what online algorithms are, competitive analysis, LRU caching, and how to answer this algorithms interview question well.
Expected Interview Answer
An online algorithm processes its input piece by piece in the order it arrives, committing to each decision immediately without knowledge of future input, in contrast to an offline algorithm that sees the entire input up front before deciding anything.
Because an online algorithm cannot see the future, it is evaluated using competitive analysis: comparing its performance on any input sequence to the performance of an optimal offline algorithm that had full knowledge in advance, expressed as a competitive ratio. Classic examples include the LRU and LFU cache eviction policies, which must decide what to evict without knowing future access patterns, and the ski-rental problem, which balances renting versus buying without knowing how many days remain. Online algorithms trade optimality for practicality — they must work in real time as data streams in, such as scheduling jobs on a server as requests arrive or routing network packets hop by hop. A good online algorithm minimizes its worst-case competitive ratio against any adversarial input ordering.
- Handles data as it arrives without needing the full input upfront
- Enables real-time decisions in caching, scheduling, and streaming
- Analyzed rigorously via competitive ratio against optimal offline solutions
- Practical for systems where future input is genuinely unknown
AI Mentor Explanation
An online algorithm is like a captain who must decide each bowling change in real time as the innings unfolds, without knowing how the rest of the match will play out. An offline strategist reviewing the full scorecard after the match could pick the objectively best bowling order in hindsight, but the captain in the moment only has the balls bowled so far. A good in-match captain aims to never be too far behind that hindsight-optimal plan, which is exactly what a competitive ratio measures. This is why bowling changes are judged by how close they come to the best possible plan given what was knowable at the time, not by a plan only visible after the match ends.
Step-by-Step Explanation
Step 1
Define the input stream
Identify what arrives incrementally (requests, cache accesses, jobs) and what decision must be made on arrival.
Step 2
Commit without lookahead
Make each decision using only past and present information, since future input is unknown.
Step 3
Compare to the offline optimum
Define OPT as the best achievable cost if the entire input were known in advance.
Step 4
Compute the competitive ratio
Bound the online algorithm's worst-case cost as a multiple of OPT across all possible input sequences.
What Interviewer Expects
- Define online vs offline algorithms clearly with the lookahead distinction
- Explain competitive analysis and the competitive ratio
- Give concrete examples: LRU cache eviction, ski-rental problem, online scheduling
- Acknowledge online algorithms generally cannot match offline-optimal performance
Common Mistakes
- Confusing online algorithms with algorithms that just run “online” or on a server
- Forgetting the competitive ratio is a worst-case bound over all input sequences
- Assuming online algorithms are always inferior rather than provably near-optimal in bounded ratio
- Not being able to name a concrete online algorithm example like LRU or ski-rental
Best Answer (HR Friendly)
“An online algorithm has to make decisions as data comes in, one piece at a time, without knowing what is coming next — like a cache deciding what to evict without knowing future requests. I would explain we measure how good it is with a competitive ratio, comparing it to a hypothetical algorithm that could see the whole future in advance.”
Code Example
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict least recently usedFollow-up Questions
- How would you prove LRU has a bounded competitive ratio against OPT?
- What is the ski-rental problem and its optimal deterministic strategy?
- How does randomization improve the competitive ratio of some online algorithms?
- How does online scheduling differ from offline job-scheduling problems?
MCQ Practice
1. What fundamentally distinguishes an online algorithm from an offline algorithm?
The defining trait is lack of lookahead: an online algorithm commits to decisions as input arrives, while an offline algorithm has the complete input before deciding anything.
2. What does the competitive ratio measure?
The competitive ratio bounds how much worse the online algorithm can perform, in the worst case, relative to an all-knowing offline optimal solution.
3. Which is a classic online algorithm problem?
The ski-rental problem is a canonical online decision problem: choose to rent or buy each day without knowing how many days of skiing remain.
Flash Cards
What defines an online algorithm? — It processes input incrementally, committing to decisions without knowledge of future input.
How are online algorithms evaluated? — Via competitive analysis, comparing worst-case cost to an optimal offline algorithm using a competitive ratio.
Name a real-world online algorithm. — LRU cache eviction, which decides evictions without knowing future accesses.
What problem models renting vs buying under uncertainty? — The ski-rental problem.