The Hot Potato Problem, also known as the Josephus Problem, is a mathematical game that involves a group of people and a hot potato. Participants stand in a circle and pass the hot potato around. When the music stops, the person holding the potato is eliminated. This continues until only one person remains. The goal is to determine the optimal strategy for winning the game, which varies depending on the number of participants.
You have a browser of one tab where you start on the homepage and you can visit another URL, get back in the history number of steps or move forward in the history number of steps. The task is to design a data structure and implement the functionality of visiting a URL starting from the homepage and moving back and forward in the history. The following functionalities should be covered:
visit(page)
forward(step)
back(step)
Note: The starting page of the tab will always be the homepage.
Examples:
Input:
homepage = “geeksforgeeks.org”
visit(“amazon.com”);
back(2);
Output: geeksforgeeks.org
Explanation: We need to move 2 steps back but since only 1 step is available we would land up at the homepage, i.e., geeksforgeeks.org
Input:
homepage = “gfg.org”
visit(“google.com”);
visit(“facebook.com”);
visit(“youtube.com”);
back(1);
back(1);
forward(1);
visit(“linkedin.com”);
forward(2);
back(2);
back(7);
Output:
facebook.com
google.com
facebook.com
linkedin.com
google.com
gfg.org
Explanation:
visit(“google.com”) : We are at google.com
visit(“facebook.com”): Now, we are at facebook.com
visit(“youtube.com”): We are at youtube.com
back(1): We would land up at facebook.com, if we move one step back.
back(1): Moving one step back, takes us to google.com
forward(1): Moving a step forward we would be at facebook.com
visit(“linkedin.com”): We are at linkedin.com
forward(2): We are still at linkedin. since visiting clear the forward history . When we are the current URL, there is no URL to move forward to.
back(2): Moving two steps back, takes us to google.com
back(7): We need to move 7 steps back, but only 1 url is available. Therefore we would return gfg.org.
Link: https://www.geeksforgeeks.org/design-custom-browser-history-based-on-given-operations/
In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.
We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, and false otherwise. How can we solve the problem?
Given a total of N tasks that you have to pick, labelled from 0 to N-1. Some tasks may have prerequisite tasks, for example, to pick task 0 you have to first finish task 1, which is expressed as a pair: [0, 1] Given the total number of tasks and a list of prerequisite pairs, return the ordering of tasks you should pick to finish all tasks. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all tasks, return an empty array.