Design Browser History - Leetcode 1472 - Python

[@Disusede]

For this one I was able to easily come up with a doubly linked list solution but time complexity wasn't great. The array solution eluded me so it was nice to see it here.

[@maxlievikoff2162]

I wanna get a song “Hey everyone welcome back and let’s write some more needcode today”. That became an everyday motto. Thank you man for all work you are doing.

[@BenjaminCBaritone]

In a real world app I don’t think you’d ever want to use an array, as this would cause memory use to increase in an unbounded fashion over time. Whereas with a stack-based solution, every time you pop the memory can be freed/garbage collected. And in practice, O(n) traversal is perfectly fine since n would never be above a few hundred for a human user. You really don’t want a memory leak in your web browser. I know in a DSA interview the focus is usually on time complexity, but this tradeoff might be something good to discuss with an interviewer.

[@oana8608]

Using an array instead of a doubly linked list for the browser history could finally explain why Chrome tabs use so much memory.

[@kartikgadagalli1008]

True. For those that don't understand the above comment: In the video (array) solution we are soft deleting the URLs ahead of the current page when visiting another URL. So potentially if a user visits 20 pages and goes back 10 steps and visits another URL. We will still store 20 elements in the array even if we only need 11 or 15. This becomes a problem when 20 becomes a bigger number. In other solutions, you remove the URLs ahead of the current page when you visit another URL.

[@CodingResoures]

@@kartikgadagalli1008 so linked list is the optimal method to implement

[@SharmaTushar1-yt]

Yes. You can use this solution. Idea is similar just use stack. class BrowserHistory: def __init__(self, homepage: str): # make a stack for history pages. The current ones that are in the current stack. self.history = [homepage] # make one for the pages that you visited earlier # so the ones that have been removed from the current stack # will be used when I press forward self.visitedPages = [] def visit(self, url: str) -> None: self.history.append(url) # clear the visited pages self.visitedPages = [] def back(self, steps: int) -> str: if len(self.history) 1: lastPage = self.history.pop() self.visitedPages.append(lastPage) steps -= 1 print(self.history) return self.history[-1] def forward(self, steps: int) -> str: if len(self.visitedPages)

[@stylisgames]

The array solution is quite clever! I just want to point out that in JavaScript you don't need the if/else statement in the visit method, since in JS there's no issue with setting the value of an out of bounds index. I coded it up with just `this.history[this.i + 1] = url;` and it works fine.

[@Simon-lk6ky]

lol I got this on an amazon phone screen a few months ago. totally bombed it

[@shadyabhi]

Did they allow to just solve via LinkedIn list, or was the follow-up to do array version as well? Just curious.

[@geghamayvazyan5637]

i think it's worth to mention in the interviews that from practical point of view soft delete with array introduces a memory leak

[@paulw7647]

Depends on the garbage collection algo

[@tomiwaadedokun6638]

Hey Neetcode, just want to let you know that you're GOATED fr! Best in quality explanation and code implementation 👏👏👏

[@andytai9401]

for the browser history question, when you are using arrays, there doesn't seem to be the code that helps with truncating the browser history from the array, after you've visiting a new website. Shouldn't we ensure that all URLS beyond the current page are removed after visiting a new website? This is asked in the question "Visits url from the current page. It clears up all the forward history."

[@andytai9401]

For example using something more simple and robust Unconditional Truncation and Append like: def visit(self, url): # Truncate any forward history beyond the current page before appending new URL self.history = self.history[:self.i + 1] self.history.append(url) self.i += 1 self.len = len(self.history)

[@basma-ba]

I was waiting you to make the challenge of the day. But mine was different from you: "1519. Number of Nodes in the Sub-Tree With the Same Label" But thank you for this video and for the great explanation

[@nipunshah1373]

Amazing explanation !!

[@akash5653]

Great as always!

[@AparnaBushan]

That's amazing!

[@blutoo1363]

Bro, did you get a different daily question than others?

[@RiazKhan-b6e]

Nice

[@JohnSmith-uu5gp]

Awesome!!!!!