LeetCode Solutions Blog

Design Video Sharing Platform

Number: 2396

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Design a video sharing platform where users can upload, delete, watch, like, and dislike videos. Each video is represented as a string of digits, where each digit corresponds to the content at that minute. The platform assigns the smallest available videoId (starting from 0) upon upload, and when videos are removed, their videoIds become available for reuse. The system also tracks the number of views, likes, and dislikes per video.

Key Insights

Use a min-heap (or priority queue) to efficiently track and assign the smallest available videoId when uploading a video.
Store video information (video string, views, likes, dislikes) in a hash map (or dictionary) keyed by the videoId.
Update the view count on each watch call and ensure proper substring extraction based on provided indices.
Ignore operations (like, dislike, watch, removal) for invalid or non-existing videoIds by returning error indicators as specified.

Space and Time Complexity

Time Complexity:

upload: O(log n) due to the heap operation for available videoIds (or O(1) if heap is empty).
remove: O(log n) due to adding an id back into the heap.
watch, like, dislike, getLikesAndDislikes, getViews: O(1) (plus O(k) for substring extraction where k is the substring length, but k summed over calls is limited). Space Complexity:
O(V + L) where V is the number of active videos (storing video strings and counts) and L is the space needed for the min-heap of available videoIds.

Solution

We maintain a counter to assign new videoIds and use a min-heap to store freed videoIds when videos are removed. The active videos are stored in a hash map where each entry holds the video content string along with its view count, like count, and dislike count. For each operation:

upload: Check the min-heap; if any id is available, reuse it. Otherwise, assign the next new id.
remove: Delete the video from the hash map and add its id to the min-heap.
watch: Validate the videoId; if exists, increment its view count, extract the required substring, and return it.
like/dislike: Increment the corresponding counter for the video if it exists.
getLikesAndDislikes/getViews: Return the stored counters if the video exists; otherwise, return an error indicator.

This design ensures constant time access for most operations while keeping track of reusable ids efficiently.

Code Solutions

import heapq

class VideoSharingPlatform:
    def __init__(self):
        # Dictionary to store video info with videoId as key.
        # Each value is a dictionary containing the video string, 
        # view count, like count, and dislike count.
        self.video_info = {}
        # Min-heap to store freed videoIds.
        self.available_ids = []
        # The next new videoId to be assigned.
        self.next_id = 0

    def upload(self, video: str) -> int:
        # If there are available freed videoIds, reuse the smallest one.
        if self.available_ids:
            video_id = heapq.heappop(self.available_ids)
        else:
            # Otherwise, use the next new video id.
            video_id = self.next_id
            self.next_id += 1
        # Initialize the video's information.
        self.video_info[video_id] = {
            "video": video,
            "views": 0,
            "likes": 0,
            "dislikes": 0
        }
        return video_id

    def remove(self, videoId: int) -> None:
        # Remove video if it exists.
        if videoId in self.video_info:
            del self.video_info[videoId]
            # Add the videoId back into the available ids heap.
            heapq.heappush(self.available_ids, videoId)

    def watch(self, videoId: int, startMinute: int, endMinute: int) -> str:
        # If the video does not exist, return "-1".
        if videoId not in self.video_info:
            return "-1"
        video_data = self.video_info[videoId]
        video_str = video_data["video"]
        # Increase view count by 1.
        video_data["views"] += 1
        # end index should be the minimum of requested endMinute and last index of video.
        actual_end = min(endMinute, len(video_str) - 1)
        # Return the substring from startMinute to actual_end (inclusive).
        return video_str[startMinute:actual_end+1]

    def like(self, videoId: int) -> None:
        # Increase like count if the video exists.
        if videoId in self.video_info:
            self.video_info[videoId]["likes"] += 1

    def dislike(self, videoId: int) -> None:
        # Increase dislike count if the video exists.
        if videoId in self.video_info:
            self.video_info[videoId]["dislikes"] += 1

    def getLikesAndDislikes(self, videoId: int) -> list:
        # If video exists, return [likes, dislikes] otherwise [-1].
        if videoId in self.video_info:
            data = self.video_info[videoId]
            return [data["likes"], data["dislikes"]]
        return [-1]

    def getViews(self, videoId: int) -> int:
        # Return view count if video exists, otherwise -1.
        if videoId in self.video_info:
            return self.video_info[videoId]["views"]
        return -1

# Example usage:
# platform = VideoSharingPlatform()
# print(platform.upload("123"))          # Output: 0
# print(platform.upload("456"))          # Output: 1
# platform.remove(4)                     # No video with id 4, do nothing.
# platform.remove(0)                     # Removes video with id 0.
# print(platform.upload("789"))          # Reuses id 0, Output: 0
# print(platform.watch(1, 0, 5))           # Output: "456"
# print(platform.watch(1, 0, 1))           # Output: "45"
# platform.like(1)
# platform.dislike(1)
# platform.dislike(1)
# print(platform.getLikesAndDislikes(1))   # Output: [1, 2]
# print(platform.getViews(1))              # Output: 2