The Foundations Nobody Wants to Build: DSA Baseline, Constraints, Arrays, and Strings

By FreePare Team · Mon Aug 10 2026 · 11 min read

Lab 1 of the 75-problem placement system

This is the first of four labs, and the prerequisite graph in section 2 is what orders them. This one builds arrays, hashing and honest cost analysis; Lab 2 spends them on windows, two pointers and linked lists; Lab 3 on stacks, queues, backtracking and trees; and Lab 4 on binary-search-tree invariants, heaps and graphs.

Advanced techniques are useful only after you can recognize when they are unnecessary. A candidate who reaches for Dijkstra on an unweighted graph, dynamic programming for a single pass, or a hash map for a bounded frequency table is not short of algorithms. The missing skill is diagnosis.

This lab measures that skill before assigning a study path. It then builds the three foundations that unlock the rest of the series: constraint reading, array transformations, and honest cost analysis.

Outcome

By the end, you will have:

• a scored baseline across arrays, hashing, recursion, trees, graphs, debugging, and complexity;
• a four-, eight-, or twelve-week route chosen from available hours;
• a prerequisite map that tells you why a later topic is blocked;
• 13 versioned foundation problems with target times and retry rules;
• an exit score of at least 80% on a new mixed set.

Java 25 is the primary implementation language. The algorithmic ideas are language-independent, but string representation, integer overflow, recursion depth, and library behavior are not. Java arrays are objects with checked indexing (JLS Chapter 10); Java integer arithmetic and conversions follow the language rules in JLS Chapters 4, 5, and 15.

Algorithm names and operation terminology should be checked against a standard reference such as the NIST Dictionary of Algorithms and Data Structures rather than inferred from platform tags.

1. Take the baseline before choosing a roadmap

Set a 45-minute timer. Do not use hints, search, old code, or an IDE completion tool.

Classify every miss by cause, not topic:

• Representation: misunderstood index, integer, string, node, or edge storage.
• Invariant: could code a pattern but could not state what stays true.
• Selection: chose an algorithm that did not match weights, order, or constraints.
• Proof: produced code but could not explain correctness.
• Testing: missed empty, duplicate, extreme, skewed, or malformed input.
• Tooling: could not isolate or reproduce the failure.

Use the score only to choose workload:

These are capacity routes, not promises of placement. Move to a slower route if two weekly exit tests fall below 80%.

2. Read the prerequisite graph

The graph explains remediation. If heap problems fail because loop invariants are weak, solving 20 more heap problems treats the symptom.

Progression rule: advance only when you can solve a new problem, state its invariant, pass edge tests, and explain why a tempting alternative fails.

3. Interpret constraints like an engineer

Before coding, fill this card:

Input variables:
Maximum values:
Operations per item:
Memory limit:
Structure or graph density:
Ordering/duplicate rules:
Numeric range:
Output size:
Candidate approaches rejected:
Reason each was rejected:

Reject by growth, not folklore

For n = 100,000, a nested all-pairs comparison performs roughly n(n - 1)/2, about five billion comparisons. That arithmetic is evidence that the approach deserves rejection under ordinary assessment limits. It is not permission to publish a universal "one second equals X operations" table. Counterexample: one integer comparison and one remote service call are both "one operation" in a loose table, yet their costs differ by orders of magnitude. Hardware, language, runtime, cache behavior, and operation cost differ.

Write the counted operation. A pointer chase, hash computation, integer comparison, database call, and string comparison are not interchangeable units.

Graph density changes the representation

For V vertices:

• an undirected simple graph has at most V(V - 1)/2 edges;
• an adjacency matrix uses Theta(V^2) space and offers constant-time edge lookup;
• an adjacency list uses Theta(V + E) space and scans neighbors in Theta(degree(v)) time.

At V = 100,000, a full matrix is implausible for ordinary memory limits. If V = 500 and the graph is dense, a matrix may be entirely reasonable. Constraints choose the representation.

Numeric range is part of correctness

If up to 100,000 values can each be 1,000,000,000, their sum can reach 10^14. Java int cannot represent that. Use long for the prefix sums even when each individual input fits in int.

4. Arrays: make the invariant visible

Traversal

static long sum(int[] values) {
    long total = 0;
    for (int value : values) {
        total += value;
    }
    return total;
}

Precondition: values is non-null. Invariant: before each iteration, total equals the sum of processed elements. Postcondition: every element has been processed exactly once.

Prefix sums

Use a length n + 1 prefix array so the empty prefix is explicit:

static long[] prefixSums(int[] values) {
    long[] prefix = new long[values.length + 1];
    for (int i = 0; i < values.length; i++) {
        prefix[i + 1] = prefix[i] + values[i];
    }
    return prefix;
}

static long rangeSum(long[] prefix, int left, int rightExclusive) {
    return prefix[rightExclusive] - prefix[left];
}

The half-open interval [left, rightExclusive) removes the usual left - 1 special case.

Trace it once

An invariant is easier to believe after one pass over real numbers. Take five section marks, values = [5, 3, 8, 2, 7], and build the prefix array a step at a time.

The finished array is [0, 5, 8, 16, 18, 25]. It is one longer than the input, and that extra prefix[0] = 0 is the empty prefix the next line depends on. Now ask for the sum of values[1] through values[3]:

rangeSum(prefix, 1, 4) = prefix[4] - prefix[1] = 18 - 5 = 13

Check it by hand rather than believing the code: 3 + 8 + 2 = 13. Two array reads and one subtraction answered a question that the obvious loop answers in three additions — and would answer the same question over 100,000 elements in the same two reads. That is the whole of the transformation, and it is worth tracing on paper once before trusting it under a timer.

Frequency counting

Choose representation from the value domain:

• small known range: primitive frequency array;
• large or sparse range: map;
• membership only: set;
• order-sensitive counts: ordered map or sort-and-scan.

static int[] frequencies(int[] values, int maximum) {
    int[] frequency = new int[maximum + 1];
    for (int value : values) {
        if (value < 0 || value > maximum) {
            throw new IllegalArgumentException("out of range: " + value);
        }
        frequency[value]++;
    }
    return frequency;
}

The range validation is not noise. It protects the representation assumption.

In-place updates

static void reverse(int[] values) {
    for (int left = 0, right = values.length - 1; left < right; left++, right--) {
        int temporary = values[left];
        values[left] = values[right];
        values[right] = temporary;
    }
}

Invariant: positions outside [left, right] already contain their final reversed values. The algorithm uses constant auxiliary space but mutates the caller's array. That side effect belongs in the contract.

Sorting as preprocessing

Sorting can turn pair search into a monotonic scan and grouping into a linear pass. It can also destroy original indices or order. Before sorting, ask:

1. May the input be mutated?

2. Must original positions be returned?

3. Does equal-item order matter?

4. Is the library sort stable for this type and call?

5. Is O(n log n) acceptable under the constraints?

5. Strings: count the right unit

A Java String is not an array of user-perceived characters. It is represented using UTF-16 semantics, and charAt returns a code unit. A supplementary code point can occupy two code units.

String text = "A😀";
System.out.println(text.length());                  // 3 UTF-16 code units
System.out.println(text.codePointCount(0, text.length())); // 2 code points

Even code points are not always grapheme clusters: "e\u0301" contains two code points that may display as one grapheme. State whether the problem measures bytes, code units, code points, or user-visible graphemes.

Other cost boundaries:

• repeated immutable concatenation can copy growing prefixes;
• StringBuilder makes incremental construction explicit;
• substring creates a result whose cost depends on result length and implementation, so do not assume a permanent shared backing array;
• lexicographic comparison may inspect a common prefix, so "one comparison" is not always constant work.

Foundation problem batch: F01-F13

Record clean only when solved without hints and with tests, invariant, complexity, and one rejected alternative.

Retry hint-assisted or failed problems after 2 days, 7 days, and 21 days. Do not view prior code before the retry.

Tracker row

ID | first date | result | hint level | invariant | time | auxiliary space |
edge tests | clean-solve date | retry 1 | retry 2 | next action

Result values: clean, hint-assisted, partial, or failed. An accepted submission with no proof or tests is partial, not clean.

Exit test

In 50 minutes, complete three unseen tasks:

1. one prefix/frequency transformation;

2. one constraint-based approach rejection;

3. one string problem containing supplementary and combining characters.

Score each task out of 10:

1. Approach selection (2)
2. Invariant/proof (2)
3. Correct code (2)
4. Edge tests (2)
5. Time and space with assumptions (2). 

Pass at 24/30, with no task below 7. Otherwise repeat only the weakest prerequisite block and retest after 72 hours.

Next in this series: The Patterns That Betray You, which assumes the arrays, hashing and cost analysis built here. If the complexity questions in the baseline were the ones that cost points, read Time Complexity for Beginners before starting it.

Tags: prerequisite-mapping, coding-fundamentals, computer-science-fundamentals, problem-solving-framework, technical-interview-preparation, exam-preparation-tips, freshers-placement-guide, study-tips-for-students