Feature #3: Find Story ID
Explore how to implement a modified binary search to find story IDs in Facebook's story array, where watched stories rotate to the end. Understand the time and space complexity and learn techniques to optimize search in a rotated sorted array for interview coding problems.
We'll cover the following...
Description
This feature will allow us to watch or re-watch stories on Instagram that are uploaded through Facebook. Every story uploaded by a user on Facebook gets assigned a unique incrementing id. On Instagram, a user can only watch one story at a time. These stories will be accessed from Facebook in ascending id order. When a story is watched, the story array rotates to accommodate unwatched stories at the start and watched stories at the end. Since stories are fetched from Facebook, so whenever a user wants to rewatch a story on Instagram, our system has to search for its id in the Facebook story list.
Observe this behavior in the illustration below:
We’ll have an array containing the story id’s. Some of the stories will be watched and will be at the end of the array, and some will be unwatched and will be at the start of the array. If a user clicks a story, we need to search for its ...