AlgoDaily

Data Structures and Algorithms

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Why DSA Now

From using collections to choosing strategies

In Intermediate Java, you built a practical mental model for List, Set, Map, ownership, and implementation tradeoffs.

Now we move one level deeper: Data Structures and Algorithms asks:

  • What work does this operation actually do?
  • How does performance change as input grows?
  • Which structure makes the algorithm simple, safe, and fast?

For interviews, DSA is the shared language of problem solving. For engineering, it is how you avoid accidental slowdowns in APIs, data pipelines, and services.

One sentence to carry through this lesson: data structures organize access; algorithms organize decisions.

Why DSA Now

Measure The Growth

Big-O is about scale, not stopwatch time

When engineers discuss complexity, we usually care about growth rate.

If input size doubles:

  • O(1) stays about the same
  • O(log n) grows slowly
  • O(n) roughly doubles
  • O(n log n) grows faster than linear
  • O(n²) can become painful quickly

In Java, implementation constants matter too: allocation, hashing, cache locality, object overhead, and JVM warmup. But Big-O helps you choose the right family of solution before tuning details.

Below, both searches are correct. The difference is how their work grows.

```java
import java.util.*;

public class Main {
    static int linearSearch(int[] a, int target) {
        int checks = 0;
        for (int x : a) {
            checks++;
            if (x == target) break;
        }
        return checks;
    }

    static int binarySearchChecks(int[] a, int target) {
        int lo = 0, hi = a.length - 1, checks = 0;
        while (lo <= hi) {
            checks++;
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == target) return checks;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return checks;
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) data[i] = i;

        int target = 999_999;
        System.out.println("Linear checks: " + linearSearch(data, target));
        System.out.println("Binary checks: " + binarySearchChecks(data, target));
    }
}
```

Complexity Check

You have a sorted array of n integers. You repeatedly cut the remaining search range in half until you find the target or prove it is absent.

What is the time complexity?

Pick Access Shape

Start with the access pattern

Since you already practiced Java collection tradeoffs in Intermediate Java, we will not re-teach ArrayList, HashSet, or HashMap here. Instead, ask what kind of access your algorithm needs.

Need Common structure Why it helps Fast index lookup Array / ArrayList Direct position access Fast membership HashSet Avoid repeated scans Key-to-value association HashMap Store derived facts Process newest first Stack / Deque Backtracking, parsing Process oldest first Queue / Deque BFS, scheduling Ordered min/max access Heap / priority queue Repeated best-next choice Relationships Graph Dependencies, networks, flows

A strong DSA solution often starts as a sentence: I need to repeatedly access X, so I will store Y.

Pick Access Shape

Hash For Memory

Trading memory for fewer repeated decisions

A common interview and production pattern is: store what you have learned so you do not recompute it.

For example, frequency counting is useful in logs, events, deduplication, stream summaries, and many coding problems.

Here we use a HashMap<String, Integer> as an algorithmic tool: not just a container, but a compact memory of facts discovered during a scan.

Time: O(n) average-case scan.
Space: O(k) where k is the number of distinct words.

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> events = Arrays.asList(
            "login", "purchase", "login", "logout", "login", "purchase"
        );

        Map<String, Integer> counts = new HashMap<>();
        for (String event : events) {
            counts.put(event, counts.getOrDefault(event, 0) + 1);
        }

        System.out.println("Event counts: " + counts);
        System.out.println("login count: " + counts.get("login"));
    }
}
```

HashMap Guarantee

True or false: If a solution uses a HashMap, every operation is guaranteed to be O(1) in all cases.

Patterns Beat Memorization

Most DSA problems are variations

You do not need to memorize thousands of solutions. You need to recognize the shape of the problem.

Useful patterns:

  • Two pointers: move through a sequence from one or both ends
  • Sliding window: maintain a valid range while expanding and shrinking
  • Prefix sums: convert repeated range totals into fast lookups
  • Hash memory: remember seen values, counts, or positions
  • BFS / DFS: explore connected states or relationships
  • Heap: repeatedly choose the smallest, largest, or highest priority item
  • Dynamic programming: reuse answers to overlapping subproblems

For a Java engineer, the key is translating the pattern into clean state: indexes, queues, maps, sets, and invariants.

Patterns Beat Memorization

Traversal Tool

In breadth-first search, we usually process nodes in first-in, first-out order using a ______.

Graph Traversal

Graphs model relationships

Graphs show up whenever entities connect:

  • services calling services
  • tasks depending on tasks
  • users connected to users
  • tables connected by references
  • states connected by valid moves

BFS is a good first traversal when you want shortest distance in an unweighted graph, level-by-level exploration, or dependency-style reachability.

The code below builds a tiny graph and prints each node's distance from A.

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D"));
        graph.put("C", Arrays.asList("D", "E"));
        graph.put("D", Arrays.asList("F"));
        graph.put("E", Arrays.asList());
        graph.put("F", Arrays.asList());

        Map<String, Integer> distance = new HashMap<>();
        Queue<String> queue = new ArrayDeque<>();

        distance.put("A", 0);
        queue.add("A");

        while (!queue.isEmpty()) {
            String node = queue.remove();
            for (String next : graph.getOrDefault(node, List.of())) {
                if (!distance.containsKey(next)) {
                    distance.put(next, distance.get(node) + 1);
                    queue.add(next);
                }
            }
        }

        System.out.println("Distances from A: " + distance);
    }
}
```

Practice Like Engineer

A repeatable DSA workflow

When solving a problem, use this loop:

  1. Restate the task in your own words.
  2. Name the input size: n, m, number of nodes, number of edges, etc.
  3. Start brute force to clarify correctness.
  4. Find repeated work or expensive access.
  5. Choose a structure that removes that pain.
  6. State complexity before coding.
  7. Code small, test edges: empty input, one item, duplicates, extremes.

This is also how you communicate in interviews: not by instantly producing magic code, but by showing structured reasoning.

Next, Database Design will shift from in-memory structures to durable data models; the same habit of choosing structures based on access patterns will carry forward.

Practice Like Engineer

Open interactive view →