RandomStringChooser / RandomLetterChooser: 2016 FRQ 1

Picking random items from a shrinking pool, without ever repeating one, is the core challenge behind this AP Computer Science A free-response question — and it asks you to build that behavior into a class completely from scratch before extending it with a subclass.

What This FRQ Tests

• AP CSA units: Unit 5 (Writing Classes) and Unit 9 (Inheritance)
• Core skill: designing a class's private state and every one of its methods from a plain-English description, with no skeleton provided
• Secondary skill: extending that class with extends and calling its constructor through super(...)
• Official category: Classes — this question asks you to write an entire class in part (a), then extend it in part (b). It's printed as FRQ 1 in the 2016 booklet; under the modern fixed ordering (adopted starting with the 2019–2020 course redesign), Classes is always FRQ 2, so this year's order doesn't match the current pattern.

The Setup

• A RandomStringChooser object is constructed from an array of non-null String values. When it's first built, every string is considered "available."
• getNext() returns a randomly chosen string from whatever's still available, and that string is never returned again by a later call. Once nothing is left, getNext() returns "NONE".
• Neither the constructor nor any method may alter the array passed into the constructor — copying its contents into your own storage is explicitly allowed (and is the way to satisfy that rule).
• RandomLetterChooser is given as a subclass of RandomStringChooser. It comes with a static helper, getSingleLetters(String str), already implemented (not shown) — it returns an array of one-letter strings, one per character of str (e.g., getSingleLetters("cat") returns { "c", "a", "t" }).
• You're asked to write two things: the entire RandomStringChooser class (part a), and the constructor for RandomLetterChooser (part b).

Part (a): Writing the RandomStringChooser Class

The Rule, Broken Down

1. Store the given strings somewhere private, without ever exposing or altering the original array.
2. Each call to getNext() must return a string that hasn't been returned before.
3. Once a string is returned, it can never be chosen again.
4. If nothing is left to choose from, return "NONE" instead of crashing or returning null.

Step-by-Step Approach

1. Declare one private field: an ArrayList<String> to hold whatever strings are still available.
2. In the constructor, create that ArrayList and copy every element of the given array into it, one at a time. Copying (rather than storing a reference to the array itself) is what keeps the original array untouched no matter what getNext() later does.
3. In getNext(), check first whether anything is left. If the list is empty, return "NONE" immediately.
4. Otherwise, generate a random valid index into the list.
5. Remove the string at that index and return it in the same step — removing it is exactly what makes it unavailable for next time.

The Code

public class RandomStringChooser
{
    private ArrayList<String> available;

    public RandomStringChooser(String[] wordArray)
    {
        available = new ArrayList<String>();

        for (int i = 0; i < wordArray.length; i++)
        {
            available.add(wordArray[i]);
        }
    }

    public String getNext()
    {
        if (available.size() == 0)
        {
            return "NONE";
        }

        int index = (int) (Math.random() * available.size());
        return available.remove(index);
    }
}

Why Each Piece Matters

• Copying into a new ArrayList in the constructor — if available instead pointed directly at wordArray (or wrapped it without copying), removing an item from available could end up changing the caller's original array, which the problem explicitly forbids.
• Checking available.size() == 0 before generating a random index — Math.random() * available.size() would just evaluate to 0 on an empty list, but then calling .remove(0) on an empty ArrayList throws an exception. Checking first avoids that entirely.
• (int) (Math.random() * available.size()) — Math.random() returns a double from 0.0 up to (but never reaching) 1.0. Multiplying by the current size and truncating with (int) scales that into a valid index from 0 to size() - 1 — and it has to be recomputed against the current size every call, since the pool shrinks after each removal.
• available.remove(index) — ArrayList's remove(int index) conveniently does two jobs in one call: it takes the string out of the list (so it's no longer available) and returns the value that was removed, which is exactly the string getNext() needs to hand back.

Tracing the Example

Using the question's own example — wordArray = {"wheels", "on", "the", "bus"}, then six calls to getNext():

Since Math.random() is different every run, the exact strings returned aren't fixed — but the question shows one possible output, bus the wheels on NONE NONE, and this table reproduces it with one valid sequence of random picks:

That reproduces bus the wheels on NONE NONE exactly — and no matter which indices happen to be chosen on a given run, the list only ever shrinks, so the code is guaranteed to eventually run out and start returning "NONE".

Common Mistakes to Avoid

• Storing the constructor parameter directly (available = wordArray; as an array, or wrapping it without copying). Any later removal risks corrupting data the caller still owns — the problem is explicit that this isn't allowed.
• Generating the random index before checking whether the list is empty. available.size() being 0 doesn't crash the random-number math, but the very next line — remove(index) — will, since there's nothing at any index of an empty list.
• Forgetting to re-read available.size() on every call. Caching the original array length and reusing it would eventually generate an index that no longer exists once strings have been removed.
• Using an int[] of "used" flags alongside the original array instead of actually removing anything. It can be made to work, but it's more bookkeeping than necessary — removing the chosen string is simpler and automatically keeps available.size() accurate.

Part (b): Writing the RandomLetterChooser Constructor

The Rule, Broken Down

1. RandomLetterChooser extends RandomStringChooser — it inherits getNext() for free, and never needs to override it.
2. The only thing left to write is its constructor, which builds a chooser out of the individual letters of a given string, not the whole string itself.
3. getSingleLetters(str) already does the work of splitting str into single-letter strings — the instructions are explicit that you must use it to get full credit, not reimplement it.

Step-by-Step Approach

1. Recognize that RandomStringChooser's constructor already does exactly what's needed — it takes a String[] and marks every element available — so RandomLetterChooser just needs to hand it the right array.
2. Call getSingleLetters(str) to turn str into an array of one-letter strings.
3. Pass that array straight into the parent constructor with super(...).

The Code

public RandomLetterChooser(String str)
{
    super(getSingleLetters(str));
}

Why Each Piece Matters

• super(...) must be the very first statement in the constructor. Java requires this for any explicit superclass constructor call, and here it's also the only way to initialize the private available field declared inside RandomStringChooser — a subclass can never touch a superclass's private fields directly, no matter what.
• Calling getSingleLetters(str) instead of writing a manual letter-splitting loop — the method is static and already fully implemented, so calling it both satisfies the "you must use getSingleLetters appropriately" requirement and avoids duplicating logic that already exists.
• No new fields or methods are needed at all. Once the parent class is constructed with the right starting array, getNext() — inherited unchanged from RandomStringChooser — already behaves correctly for letters instead of whole words.

Tracing the Example

Using the question's own example — new RandomLetterChooser("cat"), then four calls to getNext() printed back-to-back with no separator:

1. getSingleLetters("cat") returns { "c", "a", "t" } (given).
2. super({ "c", "a", "t" }) runs RandomStringChooser's constructor, so available starts as [c, a, t].

One valid sequence of random picks that reproduces the question's own sample output, actNONE:

Concatenated with no spaces (since the loop prints letterChooser.getNext() alone), that's "a" + "c" + "t" + "NONE" — exactly actNONE, matching the question's example.

Common Mistakes to Avoid

• Putting any code before super(...). Even a harmless-looking line above it fails to compile — the superclass constructor call has to come first, unconditionally.
• Reimplementing letter-splitting by hand (e.g., looping over str.length() and building single-character strings) instead of calling getSingleLetters. It might produce the same array, but the rubric specifically requires using the given method.
• Trying to call getSingleLetters as if it needed an object (like this.getSingleLetters(str) in a context where this isn't valid yet). It's static, so it's called directly by name, which also happens to be necessary since this isn't usable until after super(...) has run.

Key Takeaways

• When a subclass needs to initialize private state it inherits but can't touch directly, super(...) is the only path in — and it always has to be the first line of the constructor.
• Designing a class's fields from scratch starts with asking what needs to persist between method calls — here, exactly one ArrayList of "what's still available" is enough to support the entire class.
• A method that both removes an item from a collection and returns that item (like ArrayList.remove(int index)) is a natural fit anywhere "pick one and take it out of the pool" shows up.