DEV Community: João Filippe Rossi Rodrigues

A técnica dos dois ponteiros

João Filippe Rossi Rodrigues — Wed, 15 Jan 2025 14:12:30 +0000

Maximização da Área do Contêiner com Dois Ponteiros em Go

Ao resolver problemas que envolvem arrays ou listas, a técnica dos dois ponteiros é uma estratégia poderosa e eficiente. Neste artigo, vamos explorar como usar essa técnica para resolver o problema "Container With Most Water", que envolve encontrar a área máxima entre duas linhas verticais em um gráfico.

Enunciado do Problema

Dado um array de inteiros não negativos onde cada inteiro representa a altura de uma linha vertical em um gráfico, encontre duas linhas que, junto com o eixo x, formem um contêiner que contenha a maior quantidade de água.

Exemplo

Vamos considerar o array height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. O objetivo é encontrar as duas linhas que formam o contêiner com a área máxima.

Técnica dos Dois Ponteiros

A técnica dos dois ponteiros envolve inicializar dois ponteiros no início e no final do array e movê-los em direção um ao outro para encontrar a solução ideal.

Explicação Passo a Passo

Inicialização:
- maxArea é inicializado como 0 para armazenar a maior área encontrada.
- Dois ponteiros, l (esquerda) e r (direita), são inicializados no início e no final do array, respectivamente.
Iteração:
- Enquanto l for menor que r, o loop continua.
- A área entre as linhas nos índices l e r é calculada como min(height[l], height[r]) * (r - l).
- maxArea é atualizado se a área calculada for maior que o valor atual de maxArea.
Movimento dos Ponteiros:
- Para potencialmente encontrar uma área maior, o ponteiro que aponta para a linha mais curta é movido:
  - Se height[l] for menor que height[r], incremente l.
  - Caso contrário, decremente r.
Retorno:
- Quando os ponteiros se encontram, o loop termina, e maxArea é retornado como a maior área encontrada.

Exemplo Passo a Passo

Vamos percorrer o exemplo height = [1, 8, 6, 2, 5, 4, 8, 3, 7] passo a passo:

Inicialização:
- maxArea = 0
- Ponteiros: l = 0 (altura 1) e r = 8 (altura 7)
Primeira Iteração:
- Área: min(1, 7) * (8 - 0) = 1 * 8 = 8
- Atualiza maxArea: maxArea = max(0, 8) = 8
- Move l (já que height[l] < height[r]): l = 1
Segunda Iteração:
- Ponteiros: l = 1 (altura 8) e r = 8 (altura 7)
- Área: min(8, 7) * (8 - 1) = 7 * 7 = 49
- Atualiza maxArea: maxArea = max(8, 49) = 49
- Move r: r = 7
Terceira Iteração:
- Ponteiros: l = 1 (altura 8) e r = 7 (altura 3)
- Área: min(8, 3) * (7 - 1) = 3 * 6 = 18
- maxArea permanece 49
- Move r: r = 6
Quarta Iteração:
- Ponteiros: l = 1 (altura 8) e r = 6 (altura 8)
- Área: min(8, 8) * (6 - 1) = 8 * 5 = 40
- maxArea permanece 49
- Move r: r = 5
Quinta Iteração:
- Ponteiros: l = 1 (altura 8) e r = 5 (altura 4)
- Área: min(8, 4) * (5 - 1) = 4 * 4 = 16
- maxArea permanece 49
- Move r: r = 4
Sexta Iteração:
- Ponteiros: l = 1 (altura 8) e r = 4 (altura 5)
- Área: min(8, 5) * (4 - 1) = 5 * 3 = 15
- maxArea permanece 49
- Move r: r = 3
Sétima Iteração:
- Ponteiros: l = 1 (altura 8) e r = 3 (altura 2)
- Área: min(8, 2) * (3 - 1) = 2 * 2 = 4
- maxArea permanece 49
- Move r: r = 2
Oitava Iteração:
- Ponteiros: l = 1 (altura 8) e r = 2 (altura 6)
- Área: min(8, 6) * (2 - 1) = 6 * 1 = 6
- maxArea permanece 49
- Move r: r = 1
Fim do Loop:
- Os ponteiros se encontram (l = r), então o loop termina.

O valor final de maxArea é 49, que é a maior área possível entre duas linhas no array height.

Solução em Go

Aqui está o código completo em Go implementando a técnica dos dois ponteiros:

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        maxArea = max(maxArea, min(height[l], height[r])*(r-l))
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }

    return maxArea
}

Conclusão

A técnica dos dois ponteiros é uma ferramenta poderosa para resolver problemas que envolvem arrays ou listas. Movendo os ponteiros de forma inteligente, podemos encontrar a solução ideal de maneira eficiente.

No problema "Container With Most Water", essa técnica nos permite encontrar a área máxima entre duas linhas em tempo linear

Golang e DSA

João Filippe Rossi Rodrigues — Tue, 14 Jan 2025 15:59:40 +0000

No vasto cenário das linguagens de programação, escolher a certa para aprender Estruturas de Dados e Algoritmos (DSA) pode ter um grande impacto na sua curva de aprendizado e eficácia. Aqui está por que Golang, ou Go, se destaca como uma excelente escolha para essa jornada educacional:

1 - Simplicidade e Legibilidade

Golang foi projetado com simplicidade em mente. Sua sintaxe é limpa e concisa, tornando mais fácil para iniciantes entenderem conceitos complexos sem se perderem em açúcar sintático ou código excessivamente verboso. Quando você está aprendendo DSA, a última coisa que você quer é que a linguagem seja uma barreira. A sintaxe direta do Go permite que você se concentre na lógica das estruturas de dados e algoritmos, e não na sintaxe da linguagem.

// Exemplo de um nó de lista encadeada simples em Go
type Node struct {
    Value int
    Next  *Node
}

2 - Suporte a Concorrência

Entender como as estruturas de dados e algoritmos funcionam sob concorrência é crucial na computação moderna. Go oferece suporte integrado para concorrência através de goroutines e canais, que são leves e fáceis de usar. Esse recurso permite explorar a programação concorrente junto com DSA, preparando você para aplicações do mundo real onde o desempenho em multi-threading é fundamental.

// Exemplo de uso de goroutines para trabalhar com um slice
func main() {
    data := []int{1, 2, 3, 4, 5}
    for _, value := range data {
        go func(v int) {
            // Faça algo com v
            fmt.Println(v)
        }(value)
    }
    time.Sleep(time.Second) // Espera as goroutines terminarem
}

3 - Coleta de Lixo

A gestão de memória pode ser uma grande distração ao aprender DSA. O coletor de lixo do Golang cuida dos vazamentos de memória, permitindo que você se concentre nos algoritmos em si, em vez de se preocupar com a alocação e desalocação manual de memória. Isso é particularmente benéfico ao lidar com estruturas de dados complexas como árvores ou grafos.

4 - Tipagem Estática

A tipagem estática do Go ajuda a capturar erros em tempo de compilação e não em tempo de execução. Isso significa que você pode depurar suas implementações de DSA de maneira mais eficiente, pois incompatibilidades de tipo ou outros erros lógicos serão identificados antes que o programa seja executado, proporcionando um ambiente de aprendizado mais estável.

5 - Compilação Rápida

Go compila rapidamente, o que significa que você gasta menos tempo esperando seu código compilar e mais tempo iterando sobre seus conceitos de DSA. Esse ciclo de feedback rápido é inestimável quando você está experimentando diferentes abordagens para resolver problemas algorítmicos.

6 - Facilidade de Testabilidade

Um dos pontos fortes do Go para aprender DSA é a facilidade de testabilidade. Go possui suporte integrado para escrever testes ao lado do seu código. Com o pacote testing, você pode facilmente escrever, executar e gerenciar testes unitários para suas estruturas de dados e algoritmos. Isso incentiva boas práticas de codificação desde o início, permitindo que você verifique a correção das suas implementações rapidamente. Aqui está um exemplo breve:

// Exemplo de teste para uma função simples
func TestAdd(t *testing.T) {
    result := Add(2, 3)
    if result != 5 {
        t.Errorf("Add(2, 3) = %d; want 5", result)
    }
}

func Add(a, b int) int {
    return a + b
}

7 - Biblioteca Padrão

A biblioteca padrão do Go é abrangente, mas minimalista, oferecendo ferramentas poderosas para implementar estruturas de dados e algoritmos sem a necessidade de bibliotecas externas. Desde algoritmos de ordenação até contêineres, a biblioteca padrão fornece tudo o que você precisa para começar a implementar e testar seu conhecimento em DSA.

Conclusão

Escolher Golang para aprender Estruturas de Dados e Algoritmos não só simplifica o processo de aprendizado, mas também equipa você com habilidades relevantes para o desenvolvimento de software moderno.

Sua simplicidade, combinada com recursos poderosos de concorrência, bibliotecas padrão robustas e, especialmente, a facilidade de testabilidade, fazem do Go uma linguagem ideal para mergulhar profundamente no mundo dos algoritmos e estruturas de dados.

Seja você um iniciante ou buscando solidificar seu conhecimento, Go pode ser seu aliado nesta jornada educacional.

Golang and DSA

João Filippe Rossi Rodrigues — Tue, 14 Jan 2025 15:55:12 +0000

In the vast landscape of programming languages, choosing the right one for learning Data Structures and Algorithms (DSA) can significantly impact your learning curve and effectiveness. Here's why Golang, or Go, stands out as an excellent choice for this educational journey:

1 - Simplicity and Readability

Golang was designed with simplicity in mind. Its syntax is clean and concise, making it easier for beginners to understand complex concepts without getting bogged down by syntactic sugar or overly verbose code. When you're learning DSA, the last thing you want is for the language to be a barrier. Go's straightforward syntax allows you to focus on the logic of data structures and algorithms rather than the syntax of the language.

// Example of a simple linked list node in Go
type Node struct {
    Value int
    Next  *Node
}

2 - Concurrency Support

Understanding how data structures and algorithms perform under concurrency is crucial in modern computing. Go provides built-in support for concurrency through goroutines and channels, which are lightweight and easy to use. This feature allows you to explore concurrent programming alongside DSA, preparing you for real-world applications where performance under multi-threading is key.

// Example of using goroutines to work with a slice
func main() {
    data := []int{1, 2, 3, 4, 5}
    for _, value := range data {
        go func(v int) {
            // Do something with v
            fmt.Println(v)
        }(value)
    }
    time.Sleep(time.Second) // Wait for goroutines to finish
}

3 - Garbage Collection

Memory management can be a significant distraction when learning DSA. Golang's garbage collector takes care of memory leaks, allowing you to concentrate on the algorithms themselves rather than worrying about manual memory allocation and deallocation. This is particularly beneficial when dealing with complex data structures like trees or graphs.

4 - Static Typing

Go's static typing helps catch errors at compile time rather than runtime. This means you can debug your DSA implementations more efficiently, as type mismatches or other logical errors will be identified before the program runs, providing a more stable learning environment.

5 - Fast Compilation

Go compiles quickly, which means you spend less time waiting for your code to compile and more time iterating over your DSA concepts. This rapid feedback loop is invaluable when you're experimenting with different approaches to solve algorithmic problems.

6 - Standard Library

Go's standard library is comprehensive but minimalistic, offering powerful tools for implementing data structures and algorithms without the need for external libraries. From sorting algorithms to containers, the standard library provides everything you need to start implementing and testing your DSA knowledge.

7 - Ease of Testability

One of the standout features of Go for learning DSA is its ease of testability. Go has built-in support for writing tests alongside your code. With the testing package, you can easily write, run, and manage unit tests for your data structures and algorithms. This encourages good coding practices from the start, allowing you to verify the correctness of your implementations quickly. Here's a brief example:

// Example test for a simple function
func TestAdd(t *testing.T) {
    result := Add(2, 3)
    if result != 5 {
        t.Errorf("Add(2, 3) = %d; want 5", result)
    }
}

func Add(a, b int) int {
    return a + b
}

Conclusion

Choosing Golang for learning Data Structures and Algorithms not only simplifies the learning process but also equips you with skills relevant to modern software development. Its simplicity, coupled with powerful concurrency features and robust standard libraries, makes it an ideal language to delve deep into the world of algorithms and data structures. Whether you're just starting or looking to solidify your knowledge, Go can be your companion in this educational journey.

Feel free to customize this text further for your Medium post, adding personal insights or additional examples that resonate with your experience.

Encapulating the Server

João Filippe Rossi Rodrigues — Mon, 13 Jan 2025 21:59:52 +0000

In my personal project, I recently decided to encapsulate the Echo server in a struct to improve the organization, maintainability, and extensibility of my code. In this article, I’ll explain the benefits of this approach and provide a practical example.

Why Encapsulate the Echo Server?

Encapsulating the Echo server in a struct offers several advantages:

Organization and Modularity: Grouping all server-related operations in a single struct makes the code easier to read and maintain. Ease of Configuration: Centralizing server configuration allows for easy application of global settings, such as middlewares and ports.
Extensibility: Adding new functionalities becomes straightforward. You can add methods for configuring middlewares, routes, and other server-specific features without modifying the main code. Testability: Creating unit and integration tests becomes easier. You can instantiate the server with different configurations and test its functionalities in isolation.
Dependency Injection: Encapsulating the server allows for organized dependency injection, making it easier to pass configurations, services, and other components needed for the server’s operation.
Framework Agnosticism: By encapsulating the server logic, you can easily switch to another framework if you find a better one, without incurring high maintenance costs. This abstraction layer decouples your application logic from the specific server implementation.

Practical Example

Here is an example of how I encapsulated the Echo server in my project:

package api

import (
    "github.com/labstack/echo/v4"
    "github.com/labstack/echo/v4/middleware"
)

type Server struct {
    server *echo.Echo
}

func NewServer() *Server {
    e := echo.New()
    e.Use(middleware.Logger())
    e.Use(middleware.Recover())

    s := &Server{
        server: e,
    }

    s.buildRoutes()

    return s
}

func (s *Server) Start(address string) error {
    return s.server.Start(address)
}

func (s *Server) buildRoutes() {
    s.server.GET("/", func(c echo.Context) error {
        return c.String(200, "Hello, World!")
    })
    // Add other routes here
}

Using the Server in main

To use the encapsulated server in your main function, you can simply create a new instance of the server and call its Start method.

Notice that the main function has no idea which framework is being used to run the server. This highlights the framework agnosticism of the approach.

The server configuration, including middleware setup and route definitions, is centralized within the Server struct, making it easy to manage and modify.

By encapsulating the server logic in a struct, the main function remains clean and focused on high-level application flow:

package main

import (
    "discount-club/infra/api"
    "log"
)

func main() {
    server := api.NewServer()
    if err := server.Start(":8000"); err != nil {
        log.Fatalf("Failed to start server: %v", err)
    }
}

Example Tests

Creating unit and integration tests for the encapsulated server is straightforward and highlights the benefits of encapsulation. Encapsulating the server logic makes it easier to create isolated tests for different components and functionalities. Grouping related tests in a suite improves the organization and readability of the test code. Here are two example test cases for the encapsulated server:

package api_test

import (
    "net/http"
    "net/http/httptest"
    "testing"

    "github.com/joaofilippe/discount-club/infra/api"
    "github.com/stretchr/testify/assert"
    "github.com/stretchr/testify/suite"
)

type ServerTestSuite struct {
    suite.Suite
    server *api.Server
}

func (s *ServerTestSuite) SetupTest() {
    s.server = api.NewServer()
}

func (s *ServerTestSuite) TestNewServer() {
    assert.NotNil(s.T(), s.server)
    assert.NotNil(s.T(), s.server.Start)
}

func (s *ServerTestSuite) TestSingletonServer() {
    server1 := api.NewServer()
    server2 := api.NewServer()

    assert.Equal(s.T(), server1, server2)
}

func TestServerTestSuite(t *testing.T) {
    suite.Run(t, new(ServerTestSuite))
}

Conclusion

Encapsulating the Echo server in a struct brings several benefits in terms of organization, maintainability, extensibility, testability, and dependency injection. This approach helps create cleaner, more modular, and easier-to-maintain code. I applied this technique in my personal project, and it has significantly improved the structure and readability of my code.