Feature #3: Find Story ID
Explore how to efficiently locate story IDs in a rotated array of Facebook stories using a modified binary search algorithm. Understand how to leverage sorted halves of the array to perform O(log n) searches with constant space. This lesson helps you implement solutions for rewatching Instagram stories uploaded via Facebook.
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 ...