1. The task: implement a Set class, test-first (Java in the real interview; JavaScript or Python here).
The full question
The task: implement a Set class, test-first (Java in the real interview; JavaScript or Python here). Support isEmpty(), add(x), contains(x), remove(x) and size(). For each operation, write the tests first, one at a time, then the simplest code that makes each one pass. Finish by explaining how you'd expand the set (more operations, scale, threads).
---
Test-driven pair programming: build a set class in Java (JUnit). You think and talk; the interviewer types. For each operation you name the unit tests it needs, they write them, and you direct the smallest change that makes the failing test pass. The rule is "do the simplest thing that works": runtime and memory don't matter, but you'll be pushed on whether your code is really the simplest that passes (while only isEmpty() is tested, one boolean is enough). It's assessed on how clearly you state tests and steps, and how you debug together. There isn't time for every operation, so cover the core ones. It ends with a spoken discussion of how you'd expand the set.
Assume: a minimal API, isEmpty(), add(x), contains(x), remove(x) and size() (confirm it). Only behavior that appears in a test counts.
Worth clarifying: whether add and remove return a boolean like java.util.Set; String or a generic element type; whether null is allowed; whether you may delegate to ArrayList; and equals vs identity.
Part 1: tests first. Pick the order of operations, starting with the one that needs the least state. For each, list small, independent, well-named tests: positive, negative and interactions. Include the edge cases: duplicates, removing an absent element, emptiness after removal, and distinct but equal objects.
Part 2: the simplest implementation. Starting from an empty class, dictate each change that turns the current test green. Say why it's the simplest, which test forces each new piece of state, and when to refactor while everything is green.
Part 3: expanding the set (verbal). More operations and the tests that drive them; storage that scales and why the tests make that change safe; generics, iteration, and the equality and hashing contract.
Follow-ups:
- Is a boolean
isEmpty()still right onceremoveexists, and which test proves it? - Which tests change if you switch to a hash table?
- How do you test
equalsrather than reference equality? - What happens to
containswhen an element is mutated after it was added?
Model answer
How to run this round (about 45-60 min) Talk first, then dictate. Before every test run, say what you expect ("this should be red: isEmpty doesn't exist yet"). Aim to have isEmpty, add, contains, size and remove green by about minute 35, and keep the last 10 minutes for the expansion discussion.
0. Clarify (2-3 min), then propose defaults
- API: "I'll use
isEmpty(),add,contains,remove,size. I'd likeaddandremoveto return a boolean, true when the set changed, likejava.util.Set. OK?" - Element type: "I'll start with
Stringto keep the first tests simple, and make it generic at the end if we have time." (Or generic from the start if they prefer; it costs nothing.) null: "I'll reject it withIllegalArgumentException, but only once a test asks for it."- Storage: "May I delegate to
ArrayListwhen a test forces real storage?" Most interviewers say yes. - Equality: "Elements are the same when they're
equals, not only when they're the same object." - Refactoring: "When a test forces a bigger change, I'll refactor first while everything is green, then add the behavior."
1. The test order (state grows one step at a time) In the interview these are JUnit tests in Java. Here they're JavaScript, so you can run them in the app; the names and the order are the same.
newSetIsEmpty:assert(new MySet().isEmpty())setWithOneElementIsNotEmpty: add "a",assert(!s.isEmpty())newSetContainsNothing:assert(!s.contains("a"))setContainsAnElementAfterItIsAdded: add "a",assert(s.contains("a"))setDoesNotContainAnElementThatWasNotAdded: add "a",assert(!s.contains("b"))setContainsEveryAddedElement: add "a" and "b", assert bothnewSetHasSizeZero, thensizeCountsDistinctElements(add "a", "b": size 2)addingADuplicateDoesNotChangeTheSize(add "a" twice: size 1) andaddReturnsFalseForADuplicateremovedElementIsNoLongerContainedremovingTheOnlyElementLeavesTheSetEmpty(the test that catches the boolean shortcut)removingAnAbsentElementReturnsFalseAndChangesNothingsizeShrinksAfterRemovecontainsComparesByEqualityNotIdentity: addnew Point(1, 2),assert(s.contains(new Point(1, 2)))- If agreed:
addingNullThrows
Each name reads as a sentence, so a failure explains itself. One idea per test, and no test depends on another.
2. The simplest implementation, step by step
| Failing test | Smallest change you dictate |
|---|---|
newSetIsEmpty | isEmpty() { return true; }: hard-coded is the simplest thing that passes |
setWithOneElementIsNotEmpty | a field #empty = true; add sets it to false; isEmpty returns it. Still no storage: nothing needs it |
newSetContainsNothing | contains() { return false; } |
setContainsAnElementAfterItIsAdded | contains returns !this.#empty: fake it until a test says otherwise |
setDoesNotContainAnElementThatWasNotAdded | breaks the fake: keep one element, #only, and compare with it |
setContainsEveryAddedElement | breaks the single field. Refactor while green first: replace #only with an array #items, and contains uses #items.some(...). Then #empty is redundant: isEmpty becomes #items.length === 0 |
newSetHasSizeZero, sizeCountsDistinctElements | size() returns #items.length |
addingADuplicateDoesNotChangeTheSize, addReturnsFalseForADuplicate | add checks contains first and returns whether it added |
removedElementIsNoLongerContained | remove finds the index and splices it out, returning whether it did |
removingTheOnlyElementLeavesTheSetEmpty | nothing: green, because emptiness now comes from the array. With the old boolean it would be red. Say so before you run it |
removingAnAbsentElementReturnsFalseAndChangesNothing, sizeShrinksAfterRemove | already green: say why |
containsComparesByEqualityNotIdentity | compare with equals() for objects, not === (Java's ArrayList.contains already uses equals) |
addingNullThrows | a null guard at the top of add |
Say the change, where it goes and the exact line to the typist: "In MySet, replace the body of contains with return this.#items.some(item => same(item, x));." If a test is unexpectedly red, read the failure out loud, find which state is stale, and fix the source of truth instead of patching around it.
The finished code (runs in the app) Paste this into the JavaScript editor and press Run: it prints a check for each test and 16/16 tests passed.
// Elements are the same when they're equal by value: strings and numbers
// compare with ===, objects through their own equals() (like Java's equals).
const same = (a, b) => a === b || (a != null && typeof a.equals === "function" && a.equals(b));
class MySet {
#items = [];
isEmpty() {
return this.#items.length === 0;
}
add(x) {
if (x === null || x === undefined) throw new TypeError("null is not allowed");
if (this.contains(x)) return false;
this.#items.push(x);
return true;
}
contains(x) {
return this.#items.some((item) => same(item, x));
}
remove(x) {
const i = this.#items.findIndex((item) => same(item, x));
if (i === -1) return false;
this.#items.splice(i, 1);
return true;
}
size() {
return this.#items.length;
}
}
// A value object for the "equal but not the same object" test.
class Point {
constructor(x, y) { this.x = x; this.y = y; }
equals(o) { return o instanceof Point && o.x === this.x && o.y === this.y; }
}
// ── Tests, in the order you dictate them ──────────────────────────────────
const assertEquals = (expected, actual) =>
assert(expected === actual, `expected ${expected}, got ${actual}`);
const assertThrows = (fn) => {
try { fn(); } catch { return; }
throw new Error("expected an error");
};
const tests = {
newSetIsEmpty() {
assert(new MySet().isEmpty());
},
setWithOneElementIsNotEmpty() {
const s = new MySet(); s.add("a");
assert(!s.isEmpty());
},
newSetContainsNothing() {
assert(!new MySet().contains("a"));
},
setContainsAnElementAfterItIsAdded() {
const s = new MySet(); s.add("a");
assert(s.contains("a"));
},
setDoesNotContainAnElementThatWasNotAdded() {
const s = new MySet(); s.add("a");
assert(!s.contains("b"));
},
setContainsEveryAddedElement() {
const s = new MySet(); s.add("a"); s.add("b");
assert(s.contains("a") && s.contains("b"));
},
newSetHasSizeZero() {
assertEquals(0, new MySet().size());
},
sizeCountsDistinctElements() {
const s = new MySet(); s.add("a"); s.add("b");
assertEquals(2, s.size());
},
addingADuplicateDoesNotChangeTheSize() {
const s = new MySet(); s.add("a"); s.add("a");
assertEquals(1, s.size());
},
addReturnsFalseForADuplicate() {
const s = new MySet();
assert(s.add("a") === true);
assert(s.add("a") === false);
},
removedElementIsNoLongerContained() {
const s = new MySet(); s.add("a");
assert(s.remove("a") === true);
assert(!s.contains("a"));
},
removingTheOnlyElementLeavesTheSetEmpty() {
const s = new MySet(); s.add("a"); s.remove("a");
assert(s.isEmpty());
},
removingAnAbsentElementReturnsFalseAndChangesNothing() {
const s = new MySet(); s.add("a");
assert(s.remove("b") === false);
assertEquals(1, s.size());
},
sizeShrinksAfterRemove() {
const s = new MySet(); s.add("a"); s.add("b"); s.remove("a");
assertEquals(1, s.size());
},
containsComparesByEqualityNotIdentity() {
const s = new MySet(); s.add(new Point(1, 2));
assert(s.contains(new Point(1, 2)));
},
addingNullThrows() {
assertThrows(() => new MySet().add(null));
},
};
let passed = 0;
for (const [name, test] of Object.entries(tests)) {
try {
test();
passed++;
console.log(`✓ ${name}`);
} catch (e) {
console.log(`✗ ${name}: ${e.message}`);
}
}
console.log(`${passed}/${Object.keys(tests).length} tests passed`);
3. Expanding the set (verbal)
- First ask: "More operations, more elements, or both?"
- More operations, each driven by tests:
clear,addAll/ union,retainAll/ intersection,iterator(so it'sIterable<T>),equals/hashCodebetween sets,toString. Don't assert iteration order unless the API promises one. - Generics:
MySet<T>; possibly extendAbstractSet<T>to get thejava.util.Setcontract and its tests. - Scale: when complexity matters, swap the list for a hash table (array of buckets, resize at a load factor) for O(1) average operations. The behavior tests should not change at all: they test the public API, not the storage. That is the point of the safety net. Only a test that relied on ordering or reached into internals would have to change, which is why you don't write those.
- Contracts: elements must implement
equalsandhashCodeconsistently, and must not change in a way that affects equality while in the set. - If they push on scale or threads ("open it to a multi-threaded system, or memory limits"):
- Write the failing test first. Many threads
adddistinct elements at once, using anExecutorServiceand aCountDownLatchstart gate, then assertsize()equals the count.add-if-absent is check-then-act, so it races: two threads both see "absent" and both add. - The simplest fix is to make the methods
synchronized, or guard them with one lock. It's correct and easy to reason about. Mention aReadWriteLockif reads dominate. - At scale, delegate to
ConcurrentHashMap.newKeySet(), or stripe locks per bucket. Use atomic check-and-insert, nevercontainsfollowed byadd. - Iteration under concurrent change needs a choice: a snapshot (copy-on-write, good when reads dominate), or a fail-fast iterator that throws
ConcurrentModificationException. State which one, and test it. - Memory limits:
- a bounded capacity that rejects or evicts at the limit (decide the policy with a test)
- resize growth and load factor
- primitive specializations to avoid boxing
- off-heap storage, or a Bloom filter in front when "probably contains" is acceptable
- The behavior tests from the session stay unchanged throughout: only new tests for the new requirements are added.
Follow-up answers
- Is a boolean
isEmpty()still correct onceremoveexists? No.removingTheOnlyElementLeavesTheSetEmptyexposes it. Make sure it gets written by listing "emptiness after removal" when you plan theremovetests, before you start implementing. - Switching to a hash table: which tests change? None of the behavior tests. If one has to change, it was testing the implementation.
- Testing
equalsvs reference: two distinct but equal objects,new String("a")twice (or a small value class with its ownequals), add one,containsthe other. - An element is mutated after being added: by contract the behavior is undefined (as with
java.util.HashSet). The list implementation scans withequals, socontainsreflects the element's current state. A hash table would look in the wrong bucket and return false, and the element could become unreachable. Document that elements must be effectively immutable while in the set; you could test for the documented behavior, not "fix" it.
What a strong answer does
- Never adds behavior without a failing test that demands it
- Keeps state minimal, and names the exact test that forces each new piece of state
- Notices when a shortcut has become wrong, and refactors while green
- Predicts every run, dictates precisely, and debugs together calmly
- Covers the core operations first, and leaves time for the discussion
Common mistakes
- Reaching for
HashSetor a list at test one - Writing several tests before making one pass
- Vague dictation ("make contains work")
- Testing internals or iteration order
- Running out of time before
remove