Problem overview
A browser tab starts on a homepage. The class BrowserHistory has to support three moves. visit(url) goes to a new page and erases every page that was ahead of the current one, as a real browser does. back(steps) goes back that many pages, or as far as the homepage if fewer pages are behind. forward(steps) goes forward that many pages, or as far as it can. Both back and forward return the url of the page the tab ends on.
Take the third example: the homepage is home.com, then the tab visits a.com, b.com and c.com. back(2) returns a.com, with b.com and c.com ahead. visit("d.com") erases both, so the history is home.com, a.com, d.com. Then forward(1) returns d.com (nothing is ahead), back(1) returns a.com, and forward(2) returns d.com, because only one page is ahead. The outputs are a.com d.com a.com d.com.
The statement asks for O(1) time per call, whatever the value of steps, which can reach 100,000.
Approach: one list, two indexes
The natural first design is two stacks: pages behind the current one and pages ahead. back(steps) pops from one stack and pushes onto the other, one page at a time, so it costs O(steps).
The faster design keeps all the pages in one list, in the order they were visited, and remembers where the tab is. Moving back or forward then changes a single number. Two indexes are enough:
current, the position in the list of the page the tab is on;last, the position of the last page thatforwardmay reach.
back(steps) sets current to current - steps, but not below 0, the homepage. forward(steps) sets it to current + steps, but not above last. Each is one arithmetic operation and one list lookup.
The only subtle move is visit. Erasing the forward pages from a vector would cost time proportional to how many there are. Instead, visit writes the new url at the next position (over an old page if one is there), and sets last to that position. Pages after last may still sit in the list, but nothing can reach them: forward never goes past last, and later visits overwrite them.
The third example shows it. After the four visits and back(2) the list is home.com a.com b.com c.com with current at 1. After visit("d.com") the list is:
list: home.com a.com d.com c.com
current = 2, last = 2The old c.com is still in the vector, but last is 2, so forward stops at d.com.
Step by step
- Declare
historyas avector<string>. It holds the pages in visit order. - Declare
current, starting at 0. The tab begins on the homepage, at index 0. - Declare
last, starting at 0. For now the homepage is also the last pageforwardcan reach. - In the constructor,
push_backthe homepage so that it sits at index 0. - In
visit, increasecurrent. The new page belongs right after the current one. - If that index is already inside the vector, overwrite it. An erased page sits there, and writing over it is
O(1). - Otherwise
push_backthe url. The list grows only when the history reaches further than it ever did. - Set
lasttocurrent. This one line erases the forward history. - In
back, setcurrentto the larger of 0 andcurrent - stepswithmax. - Return
history[current]. - In
forward, setcurrentto the smaller oflastandcurrent + stepswithmin. The cap islast, not the end of the vector, because pages afterlastwere erased. - Return
history[current].
The solution in C++
class BrowserHistory {
public:
vector<string> history;
int current = 0;
int last = 0;
BrowserHistory(string homepage) {
history.push_back(homepage);
}
void visit(string url) {
current++;
if (current < history.size()) {
history[current] = url;
} else {
history.push_back(url);
}
last = current;
}
string back(int steps) {
current = max(0, current - steps);
return history[current];
}
string forward(int steps) {
current = min(last, current + steps);
return history[current];
}
};
The C++ details worth a closer look:
- Member initializers.
int current = 0;inside the class gives the field its value every time an object is created, so the constructor only has to store the homepage. maxandminwith twoints. Both arguments must have the same type.current - stepsis anintand so is0, somax(0, current - steps)compiles. If one side were asize_t, the call would not compile, and a subtraction likehistory.size() - 1on an empty vector would wrap to 18446744073709551615.- Signed against unsigned.
current < history.size()compares anintwith an unsigned value. It is safe here becausecurrentwas just increased and is never negative. - Strings are copied. The parameters are
stringvalues, so each call copies its argument, and so does the returned page. With urls of at most 20 characters that is a constant cost. - Overwriting through
[].history[current] = urlis legal only for an index inside the vector, which theifguarantees. Writing athistory.size()would be undefined behaviour, which is why the other branch usespush_back.
Running the third example gives a.com for back(2) and then d.com a.com d.com for the last three calls. Running the second example (homepage home.com, then back(1), visit("a.com"), visit("b.com"), back(5), forward(1), forward(9)) gives home.com home.com a.com b.com.
Complexity
Time: O(1) per call. back and forward do one subtraction or addition, one comparison and one lookup, whatever steps is. visit writes one element or appends one; appending is amortized O(1), as the vector now and then reallocates. The cost of a url is its length, at most 20 characters.
Space: O(n) for n visits. The list can hold erased pages that are waiting to be overwritten, but it never holds more entries than the longest history the tab has had.
Edge cases and common mistakes
- Going back from the homepage.
back(1)on a new tab stays on the homepage, and a hugestepsis clamped:back(100000)returns the homepage too. Withoutmax(0, ...)the index would go negative. - Going forward with nothing ahead.
forward(9)on the last page stays put. Capping at the end of the vector instead of atlastis the classic mistake: in the third example it would letforwardreach the erasedc.com. - Forgetting to update
lastinvisit. The visit would overwrite one page, but the tab could still walk forward onto pages that should be gone. - Overwriting versus appending. After
back, the next index is inside the vector and must be overwritten. At the end of the vector it must be appended. Doing the first withpush_backwould insert the new page after the erased ones. - Erasing the forward pages. Calling
history.eraseworks, but it costs time proportional to the pages erased. Movinglastachieves the same effect in constant time. - Moving
currentonbackbut returning the old page. Update first, then read.
Testing
- Homepage
home.com, visita.com,b.com,c.com, thenback(2),visit("d.com"),forward(1),back(1),forward(2)givesa.com d.com a.com d.com. - Homepage
home.com, thenback(1), visita.comandb.com, thenback(5),forward(1),forward(9)giveshome.com home.com a.com b.com. - Homepage
x.com, thenback(100000)andforward(100000)givesx.com x.com.
