Browser History with Delete Range

Design a browser history data structure. Implement BrowserHistory(homepage) and the following methods: - visit(url): Visit url. Forward history is cleared. - back(steps): Move back at most steps in history. Return current URL. - forward(steps): Move forward at most steps. Return current URL. Optimal: Use a doubly linked list for O(1) visit and O(steps) back/forward. This enables an additional deleteRange(startNode, count) in O(k) where k is the range size — unlike arrays which require O(n) shifting. DE Shaw Tier 1 — asked verbally Dec 2024. Talk-track: 'I use a doubly linked list so visiting truncates forward history in O(1), and range deletion is O(range size) — same trade-off as why browsers keep a DLL internally.'