Problem overview
A browser tab starts on a homepage. From the page it is on, it can visit a new page, go back some number of pages, or go forward again. Visiting a new page erases the pages you could have gone forward to, as in a real browser. The class BrowserHistory has a constructor BrowserHistory(String homepage) and three methods:
visit(String url)goes tourland erases every page ahead of the current one.back(int steps)goes backstepspages, or as far as the homepage if fewer pages are behind, and returns the url of the page it ends on.forward(int steps)goes forwardstepspages, or as far as it can, and returns the url it ends on.
Here is a session. After back(2) from the page c.com the tab is on a.com, with b.com and c.com ahead. Visiting d.com erases both.
BrowserHistory bh = new BrowserHistory("home.com");
bh.visit("a.com");
bh.visit("b.com");
bh.visit("c.com");
System.out.println(bh.back(2));
bh.visit("d.com");
System.out.println(bh.forward(1));
System.out.println(bh.back(1));
System.out.println(bh.forward(2));
a.com
d.com
a.com
d.com
The history is now home.com, a.com, d.com, so forward(1) cannot move beyond d.com, and from a.com the call forward(2) can only reach d.com.
Approach: indexes instead of walking
The natural design uses two stacks: one for the pages behind the current one and one for the pages ahead. back pops from the first and pushes onto the second, one page at a time, and forward does the reverse. A visit clears the second stack. It works, but moving one page at a time makes back(steps) and forward(steps) cost O(steps), and steps can be as large as 100,000.
The lesson keeps all pages in one list, history, in the order they were visited, and two indexes into it:
currentis the index of the page the tab is on.lastis the index of the last page thatforwardcan reach.
Now back and forward only change current, by any number of steps at once: back subtracts and stops at 0, forward adds and stops at last. That is one arithmetic operation, whatever steps is.
The clever part is how a visit erases the forward pages. It does not delete them from the list, which could be slow. It writes the new url at the next index, or appends it if the list ends there, and sets last to current. Pages after last may still sit in the list, but forward never goes past last, and later visits overwrite them one by one. The erased pages are unreachable, which is the same as erased.
After the visit of d.com above, the list, current and last are as follows. This reads the fields directly, which is only for looking inside:
System.out.println(bh.history + " current=" + bh.current + " last=" + bh.last);
[home.com, a.com, d.com, c.com] current=2 last=2
The page c.com is still in the list at index 3, but no call can reach it, since last is 2.
Step by step
- Declare
history, aList<String>that starts as an emptyArrayList<>. - Declare an
intfieldcurrentset to 0. The tab starts on the homepage, at index 0. - Declare an
intfieldlastset to 0. For now the homepage is also the last page that can be reached. - In the constructor, add
homepagetohistory. visit: movecurrentone page ahead with++. The new page goes right after the current one.- If
current < history.size(), an erased page sits at that index. Replace it withhistory.set(current, url), which takesO(1). - Otherwise the list ends at the current page, so add
urltohistory. The list grows only when the history reaches further than it ever did. - Set
last = current. This one line erases the forward history. back: setcurrenttoMath.max(0, current - steps). Index 0 is the homepage, so it cannot go lower.- Return
history.get(current). forward: setcurrenttoMath.min(last, current + steps). The cap islast, not the end of the list, because the pages afterlastwere erased.- Return
history.get(current), as inback.
The solution in Java
class BrowserHistory {
List<String> history = new ArrayList<>();
int current = 0;
int last = 0;
public BrowserHistory(String homepage) {
history.add(homepage);
}
public void visit(String url) {
current++;
if (current < history.size()) {
history.set(current, url);
} else {
history.add(url);
}
last = current;
}
public String back(int steps) {
current = Math.max(0, current - steps);
return history.get(current);
}
public String forward(int steps) {
current = Math.min(last, current + steps);
return history.get(current);
}
}
A few details about the Java code:
setversusadd.history.set(i, x)replaces the element at indexiand keeps the size.history.add(x)appends and grows the list.setthrowsIndexOutOfBoundsExceptionifiis not belowsize(), which is why the code checkscurrent < history.size()first.Math.maxandMath.minas clamps.Math.max(0, current - steps)keeps the result from going below 0, andMath.min(last, current + steps)keeps it from going abovelast. Withstepsup to 100,000 and indexes in the same range, no overflow is possible.- Field defaults. The fields
currentandlastare initialised in their declaration, and the constructor only adds the homepage. - Strings. The list holds
Stringobjects, and the methods return the stored reference. No comparison of strings is needed anywhere.
Seeing it work
When too many steps are asked for, the tab stops at the end of the history. On a fresh tab nothing is behind the homepage, so back(1) stays on it. After two visits, back(5) goes back two pages and forward(9) goes forward as far as it can.
BrowserHistory b2 = new BrowserHistory("home.com");
System.out.println(b2.back(1));
b2.visit("a.com");
b2.visit("b.com");
System.out.println(b2.back(5));
System.out.println(b2.forward(1));
System.out.println(b2.forward(9));
home.com
home.com
a.com
b.com
A longer session shows the erasing. The tab visits four pages, goes back twice, forward once, and then visits a new page:
BrowserHistory b3 = new BrowserHistory("start.org");
b3.visit("one.org");
b3.visit("two.org");
b3.visit("three.org");
System.out.println(b3.back(1) + " " + b3.back(1) + " " + b3.forward(1));
b3.visit("four.org");
System.out.println(b3.forward(2) + " " + b3.back(2) + " " + b3.back(7));
two.org one.org two.org
four.org one.org start.org
The visit of four.org from two.org erased three.org, so forward(2) stays on four.org. Then back(2) goes to one.org, and back(7) can only go one more page, to start.org.
Complexity
Time: O(1) for each call. visit does one set or add (appending is amortized O(1) for an ArrayList). back and forward do one arithmetic operation and one get, whatever steps is. The two-stack design takes O(steps) for back and forward.
Space: O(n), where n is the largest number of pages the history ever held. Erased pages are overwritten by later visits, so the list never grows beyond the longest history reached.
Edge cases and common mistakes
- Going back past the homepage. Without the clamp at 0,
history.get(-1)throws an exception. The tab must stop on the homepage. - Going forward past
last. Capping athistory.size() - 1instead oflastwould letforwardreach erased pages, such asc.comabove. - Forgetting
last = currentinvisit. The forward pages would survive a visit. - Always appending in
visit. After aback, appending puts the new page at the end of the list, not right after the current page, so the order breaks. - Removing the erased pages from the list. It works but costs time proportional to the number of pages removed. Overwriting them on later visits is cheaper.
- Visiting the same url again. It is a new entry in the history like any other.
