Feature #8: Overlapping Topics

Implement the "Overlapping Topics" feature for our "Facebook" project.

Description

Alice and Bob have created some posts on their walls. Each of the posts contain one or more “topics.” We want to mine their sequence of posts to find any overlap in the topics. Specifically, we want to find the shortest sequence of posts by Alice that have mentioned all the topics that Bob has also posted about.

In this problem, we have two lists. List A contains all of the topics that Alice posted about, namely: ["corona", "petrol", "climate", "cricket", "climate", "corona", "soccer", "music", "submarine", "elections"]. List B contains all of the topics that Bob posted about, namely: ["corona","climate"]. Now, we want to take a snapshot of the smallest contiguous portion of Alice’s wall in which she has mentioned all the topics that Bob talked about in his posts. To solve this problem, we need to find the smallest sequence of topics mentioned by User Y (including duplicates), which overlaps with the topics mentioned by User X. In our case, the smallest sequence is ["climate","corona"].

Note: The topics are case sensitive, and the order of the topics does not matter.

Let’s take a look at an illustration to better understand this:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.