Problem overview
You write the class BrowserHistory. A tab starts on a homepage. Visit(url) goes to a new page and erases every page ahead of the current one. Back(steps) goes back that many pages, or as far as the homepage if fewer are behind, and returns the url it ends on. Forward(steps) does the same in the other direction and stops at the last page that is still reachable.
Here is a tab in use. It starts on home.com, then visits news.com, shop.com and mail.com. The calls return:
Back(2) news.com
Visit("maps.com")
Forward(5) maps.com
Visit("chat.com")
Back(9) home.com
The tab was on mail.com, so Back(2) went to news.com. The visit of maps.com erased shop.com and mail.com, the pages that were ahead, so the history became home.com, news.com, maps.com. Then Forward(5) had nowhere to go and stayed on maps.com. After the visit of chat.com, Back(9) could only go back as far as the homepage.
Approach: one list and two indexes
The natural design uses two stacks: pages behind and pages ahead. Back(steps) moves one page at a time from one stack to the other, so it costs O(steps), and steps can be as large as 100,000.
A list with indexes does the same in O(1). Keep all the pages in one List<string> in visiting order, plus two integers:
current: the index of the page the tab is on.last: the index of the last pageForwardcan reach.
Back and Forward only change current, by any number of steps in one subtraction or addition, kept between 0 and last.
The trick is Visit. Erasing the forward pages from a list would cost time, so it does not erase anything. It moves current one ahead, writes the new url at that index (or appends it if the list ends there), and sets last to current. Old pages may still sit in the list after last, but Forward never goes past last, and later visits overwrite them.
The history list, current and last in the example above, step by step (this is the class's internal state, printed from a copy that exposes it):
start home.com, news.com, shop.com, mail.com | current=3 last=3
after Back(2) home.com, news.com, shop.com, mail.com | current=1 last=3
after Visit home.com, news.com, maps.com, mail.com | current=2 last=2
after Forward(5) home.com, news.com, maps.com, mail.com | current=2 last=2
after Visit home.com, news.com, maps.com, chat.com | current=3 last=3
after Back(9) home.com, news.com, maps.com, chat.com | current=0 last=3
After the first visit, mail.com is still in the list at index 3, but last is 2, so Forward cannot reach it. The next visit writes over it with chat.com. Going back and forward is only a change of current.
Step by step
- Declare
history, aList<string>set tonew List<string>(). - Declare
currentandlastasintfields, both 0. The tab starts on the homepage, which is also the last reachable page. - The constructor adds
homepagetohistory, at index 0. Visitmovescurrentahead with++.- If
current < history.Count, an erased page sits at that index: overwrite it withurl. Otherwise the list ends at the previous page, so addurl. - Set
lasttocurrent. This one line erases the forward history. BacksetscurrenttoMath.Max(0, current - steps)and returnshistory[current].ForwardsetscurrenttoMath.Min(last, current + steps)and returnshistory[current].
The solution in C#
class BrowserHistory {
List<string> history = new List<string>();
int current = 0;
int last = 0;
public BrowserHistory(string homepage) {
history.Add(homepage);
}
public void Visit(string url) {
current++;
if (current < history.Count) {
history[current] = url;
} else {
history.Add(url);
}
last = current;
}
public string Back(int steps) {
current = Math.Max(0, current - steps);
return history[current];
}
public string Forward(int steps) {
current = Math.Min(last, current + steps);
return history[current];
}
}
C# details: Math.Max and Math.Min are in the System namespace. The constructor shares the class's name and has no return type; it is the only place the homepage enters the list. The list indexer history[current] = url replaces an existing element and throws if the index is past the end, which is why the else branch uses Add instead.
Complexity
- Time: every method is O(1), whatever
stepsis. The list'sAddis amortized O(1). - Space: O(n) for the pages in the list, where n is the longest the history ever got.
Testing
The second example starts on home.com. The calls Back(1), then two visits (a.com, b.com), then Back(5), Forward(1) and Forward(9) return:
home.com
home.com
a.com
b.com
Nothing is behind the homepage, so the first Back stays. From b.com two pages are behind, so Back(5) goes to home.com. Forward(9) goes as far as b.com.
The third example: from home.com visit a.com, b.com and c.com, then Back(2), Visit("d.com"), Forward(1), Back(1), Forward(2). The four results are:
a.com
d.com
a.com
d.com
Edge cases and common mistakes
- Capping
Forwardat the end of the list. The cap islast. Pages after it were erased by a visit but may still be in the list. - Going below index 0.
Backmust not pass the homepage, so useMath.Max(0, ...); otherwisehistory[current]throws for a negative index. - Forgetting to set
lastinVisit. The forward history would then survive the visit. - Always calling
AddinVisit. The new page would land after the erased pages, and the indexes would no longer match. - Walking page by page. It is correct but takes O(steps) per call.
