GoPkg — A Golang Tech Blog

Practical guides on Go, backend engineering, and cloud technologies.

Golang Backend Engineer Brainstorming — Session 01

Three problems. One session. Build your Go backend skills from the basics.

Session overview · Easy

  • DSA: Two Sum — Arrays & Maps · Complement lookup.
  • LLD: Key-value store — Storage · Encapsulation & Go methods.
  • HLD: URL shortener — APIs & Databases · Durable lookups.

Think first. Try it. Then reveal the solution.

Choose 01, 02, or 03 to jump into a topic. Open a panel when you are ready; multiple panels can stay open.

01

DSA Warm-up

EASY

Two Sum

Category: Arrays & Maps · Pattern: Complement lookup · Difficulty: Easy

Given an integer slice and a target, return the indices of two distinct elements that add up to the target. Assume exactly one solution exists, as in LeetCode #1: Two Sum, a problem in the Top Interview 150 study plan.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Reason: nums[0] + nums[1] = 2 + 7 = 9
Brainstorm first
  • Could we check every pair? What would that cost?
  • For the current value, can we calculate the other value we need?
  • How can we remember values we have already visited?
  • How do we avoid using the same element twice?
Reveal solution: From brute force to a pattern

Checking each pair takes O(n²) time and O(1) extra space. For a value x, the required partner is target - x. Instead of searching the slice again, maintain a map from previously visited values to their indices.

For each element, look for its complement. If found, return the stored index and the current index. Otherwise, remember the current value.

Copy & run: Use the code block’s Copy button, paste the complete program into main.go, then run go run main.go. Run each example in its own folder.

package main

import "fmt"

func TwoSum(nums []int, target int) []int {
	seen := make(map[int]int, len(nums))
	for i, value := range nums {
		if previous, ok := seen[target-value]; ok {
			return []int{previous, i}
		}
		seen[value] = i
	}
	return nil
}

func main() {
	nums := []int{2, 7, 11, 15}
	target := 9
	fmt.Println(TwoSum(nums, target)) // [0 1]
}
Walk through the example
  1. At index 0, the value is 2. We need 7. The map is empty, so store 2 → 0.
  2. At index 1, the value is 7. We need 2. The map contains 2 at index 0.
  3. Return [0, 1].
Why check before inserting?

For [3, 3] with target 6, the first 3 is stored and the second 3 finds it. Inserting before checking could match the current element with itself. The order of these two operations preserves the “two distinct indices” requirement.

Go basics hidden in this small solution
  • []int is a slice. range returns its index and value.
  • make(map[int]int, len(nums)) creates a writable map with a capacity hint; that hint is not a limit.
  • value, ok := m[key] distinguishes an absent key from a stored zero value. Index 0 is valid, so checking only the returned integer would be incorrect.
  • The final nil is a defensive fallback when no pair exists. A broader API could return an explicit boolean or error.

Complexity: Expected O(n) time and O(n) additional space. We assume integer arithmetic fits in int, consistent with the problem’s constraints.

Related patterns: Two pointers for sorted input, frequency maps when counts matter, and prefix sums with maps for subarray-sum questions. Sorting this input would require extra care because we must return original indices.

02

LLD Implementation

EASY

In-memory key-value store

Category: Storage & Data Structures · Patterns: Encapsulation, constructor, explicit lookup result · Difficulty: Easy

Now use a map as the core of a small component. Design a store supporting Set, Get, and Delete.

Brainstorm first
  • Should callers access the map directly, or use methods?
  • How do we distinguish an empty value from a missing key?
  • What does deleting an absent key return?
  • Will data survive a restart?
  • Can multiple goroutines call this component safely?
Contract & Go implementation

Keys and values are strings, including empty strings. Setting an existing key overwrites its value. Get returns a value and an existence flag. Delete reports whether the key existed. Callers construct the store through NewStore.

This first version is intentionally single-threaded, has no expiration or capacity limit, and loses all data when the process exits. Those boundaries make it clear what the implementation promises.

Copy & run: Use the code block’s Copy button, paste the complete program into main.go, then run go run main.go. Run each example in its own folder.

package main

import "fmt"

// Store is an in-memory string store. It is not safe for concurrent use.
// Construct it with NewStore; an empty string is a valid key or value.
type Store struct {
	items map[string]string
}

func NewStore() *Store {
	return &Store{items: make(map[string]string)}
}

func (s *Store) Set(key, value string) {
	s.items[key] = value
}

func (s *Store) Get(key string) (string, bool) {
	value, ok := s.items[key]
	return value, ok
}

func (s *Store) Delete(key string) bool {
	if _, ok := s.items[key]; !ok {
		return false
	}
	delete(s.items, key)
	return true
}

func main() {
	s := NewStore()
	s.Set("language", "Go")
	value, ok := s.Get("language")
	fmt.Println(value, ok) // Go true

	s.Set("language", "Golang")
	value, ok = s.Get("language")
	fmt.Println(value, ok) // Golang true

	fmt.Println(s.Delete("language")) // true
	_, ok = s.Get("language")
	fmt.Println(ok) // false
}
Why wrap a map in a struct?

The unexported items field keeps storage details inside the package. Callers use the methods, so we can later add validation, locking, or expiration without exposing the underlying map.

NewStore allocates the map. A nil map permits reads and deletion, but assigning into it panics. This implementation therefore requires construction through NewStore; its zero value does not support writes.

Pointer receivers make the shared component identity explicit and avoid copying the struct. Go maps already reference shared backing state, so pointer receivers are not what makes map entries mutable.

Do we need an interface immediately?

No. A concrete type is enough for this component. Introduce a small interface at the consuming code when it needs interchangeable storage or a test substitute. Start from actual usage rather than adding abstractions in advance.

Complexity: Expected O(1) for each operation, treating key length as bounded. Space grows with the number of entries and the bytes stored. There is no memory budget yet.

Tests: verify the contract

Keep the two examples in separate folders, each with its own main.go. Save the Two Sum tests as main_test.go beside the Two Sum program, and the store tests as main_test.go beside the store program.

Two Sum tests

package main

import "testing"

func TestTwoSum(t *testing.T) {
	cases := []struct {
		name string
		nums []int
		target int
	}{
		{"basic", []int{2, 7, 11, 15}, 9},
		{"duplicates", []int{3, 3}, 6},
		{"negative", []int{-3, 4, 3, 90}, 0},
		{"zeros", []int{0, 4, 3, 0}, 0},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			got := TwoSum(tc.nums, tc.target)
			if len(got) != 2 {
				t.Fatalf("expected two indices, got %v", got)
			}
			i, j := got[0], got[1]
			if i < 0 || j < 0 || i >= len(tc.nums) || j >= len(tc.nums) {
				t.Fatalf("indices out of bounds: %v", got)
			}
			if i == j || tc.nums[i]+tc.nums[j] != tc.target {
				t.Fatalf("invalid pair: %v", got)
			}
		})
	}
}

Key-value store tests

package main

import "testing"

func TestStore(t *testing.T) {
	s := NewStore()
	if _, ok := s.Get("missing"); ok {
		t.Fatal("missing key should not exist")
	}
	s.Set("language", "Go")
	s.Set("language", "Golang")
	if value, ok := s.Get("language"); !ok || value != "Golang" {
		t.Fatalf("update failed: value=%q, exists=%v", value, ok)
	}
	s.Set("", "")
	if value, ok := s.Get(""); !ok || value != "" {
		t.Fatal("an empty value must be distinguishable from a missing key")
	}
	if !s.Delete("language") || s.Delete("language") {
		t.Fatal("delete should report whether a key existed")
	}
	if _, ok := s.Get("language"); ok {
		t.Fatal("deleted key should not exist")
	}
}

In a new example directory, initialize a module once and run the tests:

go mod init example.com/session01
go test ./...
What changes in an HTTP server?

Handlers can run concurrently. Sharing this store across handlers without synchronization is unsafe. A later session will protect operations with a mutex and add concurrent tests. Running the race detector is useful then, but passing a single-threaded test under it would not prove concurrent safety.

Related patterns: Thread-safe storage, TTL expiration, LRU eviction, and durable repositories. Each adds a separate requirement; a basic map is the foundation, not the complete cache design.

03

HLD Concepts

EASY

URL shortener

Category: API & Database Design · Patterns: Key-based lookup, durable storage · Difficulty: Easy

Design a service that converts a long URL into a short link and redirects visitors to its destination. The connection to our earlier sections is lookup: a short code becomes the key used to retrieve a stored value.

Brainstorm first
  • What are the two essential user actions?
  • What information must we store?
  • How do we ensure short codes are unique?
  • What happens for a code that does not exist?
  • Why is an in-memory map insufficient as our only storage?
Start with a small scope

Support creating a link and resolving it. Links are immutable in this version. We will defer custom aliases, expiration, user accounts, and analytics. Assume one deployment region and modest initial traffic; exact traffic and retention requirements should be clarified before sizing infrastructure.

Define the APIs
POST /v1/links
Content-Type: application/json

{
  "url": "https://example.com/articles/go-maps"
}

After the database write succeeds, return 201 Created:

{
  "short_code": "aB91x",
  "short_url": "https://sho.rt/aB91x"
}

The domain and code above are illustrative. Resolving the link:

GET /aB91x

HTTP/1.1 302 Found
Location: https://example.com/articles/go-maps

Use 400 Bad Request for invalid input and 404 Not Found for an unknown code. A 302 redirect is a reasonable starting choice because it avoids declaring the mapping permanent to clients. Redirect caching should be an explicit decision.

Architecture: begin with three components
ClientGo HTTP ServicePostgreSQL
Figure 1. Requests reach one Go service; PostgreSQL stores the authoritative link mapping.

The service validates input, generates codes, writes mappings, and returns redirects. PostgreSQL provides persistence, an indexed lookup, and uniqueness enforcement. We do not need a separate cache or message broker to explain the initial system.

Model the data
CREATE TABLE links (
    short_code TEXT PRIMARY KEY,
    original_url TEXT NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

The primary key enforces unique short codes and creates an index for lookup. Store the destination in full; we are assigning a shorter identifier, not compressing the URL.

Generate a short code

One approach is a random Base62 code using letters and digits. Generate it with a cryptographically secure random source, attempt the insert, and retry with a new code if the database reports a short-code conflict. Choose a length based on expected volume; the five-character example above is not a capacity recommendation.

Do not rely only on “check whether the code exists, then insert.” Concurrent requests can both pass that check. The unique constraint must make the final decision. Bound collision retries, and distinguish a collision from a database outage.

A second approach is Base62 encoding of a unique numeric ID. It simplifies uniqueness when ID allocation is correct, but makes codes predictable. Base62 is an encoding, not encryption, and a short code is not an authorization secret.

Explain both request flows

Create
Client → validate URL → generate code → insert mapping → return short URL

Resolve
Client → read code → indexed database lookup → return 302 + Location
Unknown code → return 404

Figure 2. Creation writes a durable mapping; resolution reads the mapping before redirecting.
SELECT original_url
FROM links
WHERE short_code = $1;

Use a parameterized query. At creation, parse the destination and require an HTTP or HTTPS scheme plus a valid host. Returning a redirect does not require our server to fetch the destination. If we later add URL previews, fetching introduces additional security requirements.

Why not use our in-memory store as the database?

Its contents vanish on restart. Separate service instances would also have separate maps. A public short link should keep working across deployments, so durable storage is part of the basic design.

Where do database, scaling, and reliability fit?

They belong in HLD, introduced when the requirements justify them:

  • Database: Start with the schema, primary key, and query. Later investigate query plans, connection limits, replicas, and partitioning.
  • Scaling: Keep the service stateless so multiple instances can sit behind a load balancer and share storage.
  • Caching: If repeated reads become expensive, add cache-aside lookup: read the cache, fall back to the database on a miss, and populate the cache.
  • Reliability: Use database deadlines and a bounded connection pool. A storage failure should produce a controlled server error, not an incorrect 404.
  • Observability: Track request latency, error rate, and database latency. Avoid logging full destination URLs by default; they can contain private tokens.

These are growth directions, not extra components we must deploy in Session 01. Measure the bottleneck before selecting a scaling mechanism.

Connect the patterns

Two Sum uses a map to answer “Have I seen this complement?” The key-value store wraps lookup behavior in a small API. The URL shortener turns lookup into a durable service with an HTTP contract. The storage technology changes, but identifying the key and defining missing-value behavior remain useful throughout.

Before moving to Session 02

  1. Implement Two Sum without looking at the solution. Explain why lookup happens before insertion.
  2. Build the store and run the tests. Explain missing keys versus empty values.
  3. Draw the URL shortener and walk through one creation request and one redirect.
  4. Explain what breaks if two goroutines share our current store.
  5. Explain why a unique database constraint is necessary even when codes are random.

Next, we can build on these foundations with another DSA pattern, synchronized access to the store, and the first caching decisions in the URL shortener.

Further reading

Comments

Post a Comment