Longest Uploaded Prefix

Longest Uploaded Prefix

What is this problem about?

The Longest Uploaded Prefix problem requires you to design a system that simulates a video uploading process. You receive chunks of a video out of order (e.g., chunk 3, then chunk 1, then chunk 2). You must implement an upload(video_stream_id) method and a longest() method. The longest() method should return the length of the longest contiguous uploaded prefix starting directly from chunk 1.

Why is this asked in interviews?

System design and state management questions like this are incredibly popular because they mirror real-world networking scenarios, such as handling TCP packets arriving out of sequence. It tests a candidate's ability to design a class that handles constant insertions and queries efficiently. Interviewers look for solutions that avoid $O(N)$ rescans on every query.

Algorithmic pattern used

This problem is best solved using an Array/Hash Set combined with a Monotonic Pointer. You maintain a boolean array or a Hash Set to mark which chunks have been uploaded. You also maintain a single integer pointer, max_prefix, initialized to 0. When chunks are uploaded, you simply mark them as true. When longest() is called (or inside upload()), you incrementally advance max_prefix as long as max_prefix + 1 exists in your set/array.

Example explanation

We initialize the system with total video size n = 4. max_prefix = 0.

• upload(3): Set has {3}. Is max_prefix + 1 (1) in set? No.
• longest(): Returns max_prefix which is 0.
• upload(1): Set has {1, 3}. We check max_prefix + 1 (1). It's in the set! max_prefix becomes 1. Next is 2. Is 2 in the set? No.
• longest(): Returns 1.
• upload(2): Set has {1, 2, 3}. We check max_prefix + 1 (2). Yes! max_prefix=2. Check 3. Yes! max_prefix=3. Check 4. No.
• longest(): Returns 3. The pointer naturally stops where the continuous chain breaks.

Common mistakes candidates make

A very common mistake is iterating from 1 to N inside the longest() function every single time it's called. If longest() is called repeatedly, this creates an $O(N)$ time complexity per query, leading to Time Limit Exceeded. The max_prefix variable must be persistent across method calls so it only ever moves forward, making the amortized time complexity of longest() $O(1)$.

Interview preparation tip

When tackling the Longest Uploaded Prefix interview pattern, recognize that a sliding pointer that never moves backward is a massive optimization tool. If a prefix is contiguous up to k, it will never "un-upload". Therefore, your checking logic only needs to evaluate k + 1 going forward, guaranteeing that you evaluate each chunk exactly once throughout the entire lifespan of the object.