Feature #8: Verify User Session

Description

Netflix has received a user complaint about the Back button we implemented in the previous feature misbehaving. The complaint was that the viewing history was not shown in the sequence it was accessed. Being the lead developer of this functionality, you went through the logs and retrieved the sequence of push operations and the sequence of pop operations in separate lists. Each new entry that the user clicked went to the push operations list. Each time the user clicked the back button, the removed entry went to the pop operations list.

The user also had a session where they browsed for some titles or pressed the Back button several times. The user did not browse the same title more than once. At the end of the session, the Back button was disabled. Unfortunately, these logs are separate and there are no timestamps. We want to know if the stack handled the user session correctly or if there may be a bug in the stack implementation.

We’ll receive two lists of push and pop operations. These lists will contain the ID’s of the pages that were browsed. We want to verify whether our implementation of the max stack is behaving correctly or not. To do this, we can check if the sequence of push operations and the sequence of pop operations have been interleaved and performed on a valid stack that was initially empty.

Let’s say that the user browsed through the following title pages mapped to their respective IDs. The following does not depict the order in which these were viewed.