The latest articles on Forem by Gabriel Pereira (@painkiller54). https://forem.com/painkiller54 https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F1291476%2Fa485693e-ba66-4ee2-9c03-36f589087229.png https://forem.com/painkiller54 en Gabriel Pereira Thu, 22 Feb 2024 01:50:22 +0000 https://forem.com/painkiller54/leetcode-1472-design-browser-history-5cdh https://forem.com/painkiller54/leetcode-1472-design-browser-history-5cdh <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fcroy8mpess9eyylcrir5.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fcroy8mpess9eyylcrir5.png" alt="Image description" width="800" height="286"></a></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fyc0rnf5qgjn9obrrqbqw.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fyc0rnf5qgjn9obrrqbqw.png" alt="Image description" width="563" height="349"></a></p> <p>O desafio envolve "implementar" um historico de navegacao onde temos 3 operacoes: visit, back e forward, sendo bem simples e direto, as operacoes back e forward avancam/retornam no historico, a operacao visit deve acessar uma nova pagina a partir da posicao atual, limpando o historico de acesso posterior.</p> <p>Ex:</p> <p><strong>1 - input inicial, instanciando a classe com uma url:</strong><br> <code>BrowserHistory("www.google.com")</code></p> <p><strong>2 - visit</strong><br> <code>BrowserHistory.visit("www.facebook.com")</code></p> <p><strong>3 - visit</strong><br> <code>BrowserHistory.visit("www.linkedin.com")</code></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fw77ol2my511ojzkoz2jq.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fw77ol2my511ojzkoz2jq.png" alt="Image description" width="800" height="192"></a></p> <p><strong>4 - back 2 steps</strong><br> <code>BrowserHistory.back(2)</code></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Foweory8otnbi0ok53zr9.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Foweory8otnbi0ok53zr9.png" alt="Image description" width="800" height="198"></a></p> <p><strong>5 - forward 1 step</strong><br> <code>BrowserHistory.forward(1)</code></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fd3isjgbfs59ncc5jg245.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fd3isjgbfs59ncc5jg245.png" alt="Image description" width="800" height="222"></a></p> <p><strong>6 - visit <a href="http://www.youtube.com">www.youtube.com</a></strong><br> <code>BrowserHistory.visit("www.youtube.com")</code></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fz52lwxgqq95jlww11g7s.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fz52lwxgqq95jlww11g7s.png" alt="Image description" width="800" height="385"></a></p> <p><strong>Approach 1 - Usando doubly singled list (menos performático)</strong></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fj3ajwvnfm8skpmuzlav3.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fj3ajwvnfm8skpmuzlav3.png" alt="Image description" width="800" height="204"></a></p> <p>usando essa estrutura, cada no da lista ligada armazena o endereco do proximo/anterior</p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F2o8l8ahc7n6rqhfpl6nt.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F2o8l8ahc7n6rqhfpl6nt.png" alt="Image description" width="526" height="629"></a></p> <p>Sendo mais custoso por ter que percorrer um loop toda vez que usar as operacoes back/forward, complexidade de tempo e espaco O(n) onde n é o número de steps</p> <p><strong>Approach 2 - usando um array e um pointer para salvar as posicoes (mais performatico)</strong></p> <p><a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fuzr8tifokbzbodiqnkuf.png" class="article-body-image-wrapper"><img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fuzr8tifokbzbodiqnkuf.png" alt="Image description" width="798" height="428"></a></p> <p>Como nao é necessário percorrer o array nas operações de back/forward, a complexidade de tempo é O(1) e a complexidade de espaço é O(n) onde n é o numero de urls visitadas usando o método visit()</p> leetcode python