Browser Session History Navigation

Implement a BrowserSession class to manage the navigation history for a single-tab browser. The session should start at a specified homepage.

APIs:

• BrowserSession(string homepage): Initializes the browser session. The homepage is the first page visited, and the current page starts at homepage.
• void visit(string url): Navigates to the given url from the current page. This action clears any existing forward history.
• string back(int steps): Moves the current page pointer up to steps pages backward in the history. If fewer than steps pages are available in the backward history, move as far back as possible. Returns the URL of the page after the move.
• string forward(int steps): Moves the current page pointer up to steps pages forward in the history. If fewer than steps pages are available in the forward history, move as far forward as possible. Returns the URL of the page after the move.

Bonus:

• bool haveVisited(string url): Returns true if the session has ever visited the given url at least once since its construction, regardless of whether it is currently in the back or forward history. Returns false otherwise.

Requirements:

• Target O(1) amortized time complexity for each operation.
• Target O(N) space complexity for N total visits.
• Clearly define and justify how to handle edge cases (e.g., steps <= 0, visiting the same URL consecutively, an empty forward history).
• Describe and justify your chosen data structure(s) (e.g., two stacks, doubly linked list with a cursor, dynamic array with an index) and discuss their trade-offs in terms of time and space complexity.