A Widespread Laborious Interview Drawback seen at prime corporations
Implement the BrowserHistory class: BrowserHistory(string homepage) Initializes the item with the homepage of the browser. void go to(string url) Visits url from the present web page. It clears up all of the ahead historical past. string again(int steps) Transfer steps again in historical past. Should you can solely return x steps within the historical past and steps > x, you’ll return solely x steps. Return the present url after transferring again in historical past at most steps. string ahead(int steps) Transfer steps ahead in historical past. Should you can solely ahead x steps within the historical past and steps > x, you’ll ahead solely x steps. Return the present url after forwarding in historical past at most steps. Leetcode
Enter:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
his downside describes a category referred to as “BrowserHistory” that simulates an online browser’s historical past characteristic. The category has three strategies:
BrowserHistory(string homepage): This methodology is the constructor of the category and initializes the item with the homepage of the browser. It units the present URL to the homepage and initializes two lists, one for the historical past of URLs visited (again historical past) and one other for the URLs which have been navigated away from (ahead historical past).void go to(string url): This methodology known as when the person visits a brand new URL. It clears the ahead historical past and provides the brand new URL to the again historical past. The present URL is about to the brand new URL.string again(int steps): This methodology known as when the person desires to maneuver again within the historical past. The variety of steps to maneuver again is handed as an argument. If the person desires to maneuver again extra steps than can be found within the historical past, the tactic will transfer again the utmost variety of steps potential. The present URL is up to date to the URL that’s reached after transferring again in historical past.string ahead(int steps): This methodology known as when the person desires to maneuver ahead within the historical past. The variety of steps to maneuver ahead is handed as an argument. If the person desires to maneuver ahead extra steps than can be found within the historical past, the tactic will transfer ahead the utmost variety of steps potential. The present URL is up to date to the URL that’s reached after transferring ahead in historical past.
This class ought to have the ability to maintain observe of the URLs which have been visited, permit the person to maneuver ahead and backward by means of the historical past, and return the present URL at any cut-off date.
Let’s go over the answer step-by-step utilizing Object Oriented Programming.
Constructor
In a browser, we’re ready to return and ahead. To perform this, we have to observe our again historical past and our ahead historical past.
/**
* @param string homepage
*/
var BrowserHistory = operate(homepage)
this.historical past = [homepage]
this.forwardHistory = []
;
Go to URL
After we go to a brand new url, the browser erases all of our ahead historical past. Should you had beforehand gone again 5 occasions after which visited an entire new url, you may not go ahead to the urls that you simply beforehand went again from.
Suppose you visited “Google”, “Apple”, after which “Medium” in that order, now your again historical past would have [“Google”, “Apple”, “Medium”]. Say now you clicked again 2 occasions — so you’d now be at “Google” and your ahead historical past would now have [“Apple”, “Medium”] and your again historical past would have [“Google”]. Should you now go to a brand new url “YouTube”, you may not go ahead since this it’s a new path and also you haven’t gone again from it but. So now, your ahead historical past can be empty and your again historical past can be [“Google”, “YouTube”].
You may attempt the above instance in your personal browser!
/**
* @param string url
* @return void
*/
BrowserHistory.prototype.go to = operate(url)
this.historical past.push(url)
if (this.forwardHistory.size > 0)
this.forwardHistory = []
;
Go Again plenty of steps
Every time we return, we add the url we’re going again from to our ahead historical past as we take away it from our again historical past. The difficult half right here can be if somebody clicked again extra occasions than there are url’s saved in our again historical past. Suppose we have now [“Google”, “Apple”] is our again historical past however somebody clicks again 5 occasions. We are able to solely return twice, so we should always take them to “Google” with a ahead historical past of [“Apple”].
Assessment the code and feedback beneath to grasp the sting circumstances:
/**
* @param quantity steps
* @return string
*/
BrowserHistory.prototype.again = operate(steps)
// Initializing this variable is necessary as a result of we're altering
// the size of the array within the loop and it'll have an effect on
// our i < worth verify at every iteration
const l = this.historical past.size - 1
// Taking the min of steps or l will deal with our edge case
// for steps > objects in historical past
for (let i = 0; i < Math.min(steps, l); i++)
let b = this.historical past.pop()
this.forwardHistory.push(b)
// Make certain to not use the above initialized variable "l" right here
// as a result of the size is now totally different
return this.historical past[this.history.length - 1]
;
One other fast notice right here: In case of steps > objects, we wish to solely pop size — 1 objects from the historical past array so we’re in a position to present the final merchandise within the historical past. They method we have now arrange our object permits historical past’s final merchandise to be the present web page that the person is on.
Go Ahead plenty of steps
When going ahead, the person can solely click on ahead as many occasions because the ahead Historical past’s size. If there are 2 objects within the ahead historical past, we are able to solely permit steps ≤ 2. We’ll once more use the minimal of steps and the size to make sure this edge case. One other factor to note right here is that within the steps > size case for ahead historical past, we’re in a position to pop each single merchandise from the ahead historical past and add it to the again historical past. It’s because the person’s present web page is on the finish of the again historical past array in our arrange.
/**
* @param quantity steps
* @return string
*/
BrowserHistory.prototype.ahead = operate(steps)
const l = this.forwardHistory.size
if (l > 0)
for (let i = 0; i < Math.min(steps, l); i++)
let b = this.forwardHistory.pop()
this.historical past.push(b)
return this.historical past[this.history.length - 1]
;
Typically, to raised perceive my code, I add logs to every step to see how every of our variable values are up to date all through the operate calls. I like to recommend the beneath logs to see your code in motion:
/**
* @param string homepage
*/
var BrowserHistory = operate(homepage)
this.historical past = [homepage]
this.forwardHistory = []
;/**
* @param string url
* @return void
*/
BrowserHistory.prototype.go to = operate(url)
// console.log(`go to "$url"`)
this.historical past.push(url)
if (this.forwardHistory.size > 0)
this.forwardHistory = []
// console.log(`historical past: "$this.historical past"`)
// console.log(`ahead: "$this.forwardHistory"`)
;
/**
* @param quantity steps
* @return string
*/
BrowserHistory.prototype.again = operate(steps)
// console.log(`again $steps steps`)
// console.log(this.historical past.size - 1, Math.min(steps, this.historical past.size - 1))
const l = this.historical past.size - 1
for (let i = 0; i < Math.min(steps, l); i++)
let b = this.historical past.pop()
// console.log(`Popped $b from historical past`)
this.forwardHistory.push(b)
// console.log(`historical past: "$this.historical past"`)
// console.log(`ahead: "$this.forwardHistory"`)
// console.log(`return: "$this.historical past[this.history.length - 1]"`)
return this.historical past[this.history.length - 1]
;
/**
* @param quantity steps
* @return string
*/
BrowserHistory.prototype.ahead = operate(steps)
// console.log(`ahead $steps steps`)
const l = this.forwardHistory.size
if (l > 0)
for (let i = 0; i < Math.min(steps, l); i++)
let b = this.forwardHistory.pop()
this.historical past.push(b)
// console.log(`historical past: "$this.historical past"`)
// console.log(`ahead: "$this.forwardHistory"`)
// console.log(`return: "$this.historical past[this.history.length - 1]"`)
return this.historical past[this.history.length - 1]
;
/**
* Your BrowserHistory object shall be instantiated and referred to as as such:
* var obj = new BrowserHistory(homepage)
* obj.go to(url)
* var param_2 = obj.again(steps)
* var param_3 = obj.ahead(steps)
*/
