Test-Drive a Set in Java Without java.util Using Strict Red-Green-Refactor

In a 60-minute collaborative pairing interview you test-drive a set in Java with JUnit, without using anything from `java.util`. The interviewer shares an IDE and does all the typing; you dictate every test and every change precisely enough to be typed line by line (for example, "in `add`, add `size++`"). Every candidate gets the same exercise with the behaviours in the same fixed order, and the round is judged on collaboration and reasoning, not on finishing a complete implementation. Work in strict red, green, refactor cycles. For each behaviour, first write a test and watch it fail; then write the minimal production code that makes it pass, even if that code does not yet look anything like a real set; then refactor. "Minimal" is meant literally: if a hard-coded value passes the tests, hard-code it and let the next test break it. Elements are of type `Object` and are compared with `equals`. After every green step, expect to be asked what else should be tested or refactored. ### Clarifying Questions - Must the set accept `null` as an element, and if so, how should comparisons avoid calling `equals` on `null`? - Is a fixed capacity acceptable for now, and what should happen when the backing storage is full? - Should `add` and `remove` return whether the set changed, or nothing? What should removing an element that is not in the set do? - Does a compilation failure count as red, or should each new test compile and fail on an assertion first? ### Part 1 — An empty set, then a non-empty one Start with a test that a newly created set is empty, and give it the minimal implementation. Then test that the set is no longer empty after one `add`, and make that pass. The interviewer then asks how you could make the second test pass without a `size` field. ```hint Only what the tests can see List what the two tests so far actually need to tell apart, and ask whether telling it apart requires counting anything. ``` #### What This Part Should Cover - A test that is seen failing before any production code makes it pass - The smallest implementation for each test, and the smallest piece of state the second test forces - The point at which that minimal state stops being enough ### Part 2 — Size and duplicates Add tests for `size` after adding one element and after adding two. Also write the test that adding the same element twice leaves the size at 1; when the interviewer asks to skip it for now and come back to it later, park it. ```hint Why it has to wait Ask what the set would need to be able to do before it could notice that an element is already present. ``` #### What This Part Should Cover - Hard-coded answers that the next size test breaks, and the state that replaces them - The refactor of the earlier `isEmpty` code once that state exists - How the duplicates test is parked so that it stays visible without blocking progress ### Part 3 — Contains Drive `contains` with tests: an empty set contains nothing; after an `add`, the set contains that element; after two different elements are added, it contains both. Then return to the parked duplicates test. ```hint Let each test break one shortcut For each new test, find the cheapest code that passes it, then ask which later test that code would fail. ``` #### What This Part Should Cover - The progression from a constant answer, to one stored element, to storage for many elements - Element comparison with `equals` rather than reference identity, and a test that would notice the difference - Re-enabling the duplicates test and making it pass ### Part 4 — Remove without leaving a hole Drive `remove`. A first implementation that finds the element, sets its slot to `null` and decrements `size` leaves a hole in the backing array. Moving every later element one position to the left closes the hole but costs O(n) moves. Can you close the hole without moving all the other elements? ```hint What a set does not promise Ask whether anything about the set depends on the order in which its elements are stored, and what that frees you to put into the emptied slot. ``` #### What This Part Should Cover - A test, written against the public methods only, that fails because of the hole - The ways to close the hole and the cost of each - Edge cases: removing the only element, the last stored element, an absent element, and removing from an empty set ### What a Strong Answer Covers - Red before green on every cycle, including the very first one - Implementations that are truly minimal, with each hard-coded value removed by a later test rather than in advance - Dictation precise enough to type: the file, the method and the exact line - Ready answers to "what else should we test or refactor?" after each green step - No `java.util` anywhere, including the helpers that are easy to reach for by habit - Collaboration: thinking aloud, following the interviewer's order and taking course corrections well ### Follow-up Questions - The backing array has a fixed capacity. Which test would drive growth, and how would you grow the array without `java.util`? - How would you make `contains` and `remove` faster than a linear scan without `java.util`, and what must `hashCode` then guarantee? - If `null` must be a legal element, which tests do you add and which lines change?