Java OOP & Design Problems

This is the session where interviews stop asking "do you know an algorithm?" and start asking "can you build a data structure in idiomatic Java?" It splits cleanly in two. First, the OOP fundamentals interviewers actually probe: abstract class versus interface, single versus multiple inheritance and the diamond problem it dodges, and how generics quietly change your design decisions. Then the practical half — implementing Stack and Queue from scratch, twice each: once over a linked list, once over a fixed-capacity array. The array version drags in the circular-buffer full-vs-empty puzzle and the amortized-resize follow-up, both of which are where candidates either sound senior or get filtered.

List, ArrayList, LinkedList: Interface vs Implementation

Start where the notes start, because it frames everything after. List is an interface — a contract that says "ordered collection with indexed access," nothing about how. ArrayList and LinkedList are two implementations of that same contract with opposite performance profiles: ArrayList is a resizable array (O(1) random access by index, O(1) amortized append, but O(n) to insert or delete in the middle because everything shifts), while LinkedList is a chain of nodes (O(1) to add/remove at either end, but O(n) to reach index i). We unpacked those exact tradeoffs in Session 4; here they justify a design choice — a linked list is the natural spine for a stack or queue precisely because all the action is at the ends.

That split — one contract, many implementations — is the whole point of the OOP half of this session. The next two sections are just the two Java tools for expressing it.

Abstract Class vs Interface

The single most common Java-fundamentals question, and the notes give the full comparison. An abstract class is a half-finished parent in an is-a hierarchy: it can hold fields (final and non-final, static and non-static), define constructors, and mix abstract methods (no body, subclass must fill them in) with concrete ones. An interface is a pure capability contract: historically only abstract method signatures and static final constants, and — the detail interviewers love to check you know — since Java 8 it can also carry default and static methods, which is how the language added methods to existing interfaces without breaking every implementer.

The decision rule to say out loud: reach for an abstract class when subtypes share state or default behavior and form a genuine is-a family (every Shape is a shape); reach for an interface when you're describing a capability that unrelated types can opt into (anything Comparable, Iterable, or Drawable, regardless of its class hierarchy). And there's an asymmetry worth naming: an abstract class can implement an interface, but an interface can never implement an abstract class — the contract sits above the partial implementation, never below it.

Single vs Multiple Inheritance (and the Diamond Problem)

Why can a Java class implement any number of interfaces but extend only one class? The notes nail the answer in one line, and it's the crux: implementing an interface forces you to write the method body yourself, so multiple inheritance is never ambiguous. If two interfaces both declare foo(), the implementing class still provides exactly one foo() — there is only ever one implementation to run.

Extending classes is different. If class C extends A, B were legal and both A and B shipped their own concrete foo(), then a call to c.foo() is genuinely undecidable — which parent's implementation do you inherit? This is the classic diamond problem (A at the top, B and C inheriting, D at the bottom inheriting both). Java's design decision is simply to forbid the situation: at most one superclass, so there is never a competing inherited body to disambiguate. Interfaces sidestep it by construction, because before default methods they carried no bodies at all.

Generics: Why <T> Changes the Design

Every structure in this session is generic — MyStack<T>, MyQueue<T>, backed by a generic Node<T>. Generics buy you type safety (the compiler stops you pushing a String onto an Integer stack) and eliminate casts on the way out. But they change one design decision that trips people up: you can no longer use null as an "empty" sentinel. A method like pop() that returns null when empty is ambiguous the moment T can itself be null — a caller who legitimately pushed a null value gets the same signal as a caller hitting an empty stack. The two clean fixes, both used below: keep an explicit size field and check it, or throw (NoSuchElementException / EmptyStackException) rather than overloading null.

One runtime wrinkle the array-backed versions expose: you cannot write new T[capacity]. Generics are erased at runtime, so the array has no real element type to instantiate; the idiom is (T[]) new Object[capacity] with a suppressed unchecked warning. Knowing why — type erasure — is the point, not the incantation.

Design a Stack (FILO) with a Linked List

The reflex answer in production is Deque<Integer> stack = new ArrayDeque<>(); — and that's genuinely the right call in real code. But it is not what the interviewer wants; the question is "build the structure," not "name the library class." A stack is last-in-first-out, and a singly linked list makes it trivial: keep one head pointer and do everything there. Push links a new node above the old top; pop unlinks the top. Both are O(1), and there's no capacity ceiling.

public class MyStack<T> {
    private static class Node<T> {   // singly-linked node
        T val;
        Node<T> next;
        Node(T val) { this.val = val; }
    }

    private Node<T> head;               // top of the stack

    public boolean push(T x) {
        Node<T> node = new Node<>(x);
        node.next = head;                // link the new node above the old top
        head = node;                     // it becomes the new top
        return true;
    }

    public T pop() {
        if (head == null) return null;  // caveat: null is ambiguous when T can be null
        Node<T> node = head;
        head = head.next;
        node.next = null;                // good habit: disconnect the removed node
        return node.val;
    }

    public T peek() {
        return head == null ? null : head.val;
    }
}

Notice node.next = null before returning — deliberately severing the removed node's link. It costs nothing and prevents a stale reference from keeping a chain of objects alive; the notes flag this as a "good habit," and it reads as one in an interview. The lingering weakness is that pop()/peek() return null on empty — fine for a demo, but state the generic-null caveat aloud and offer the size-field or exception alternative.

Design a Queue (FIFO) with a Linked List

A queue is first-in-first-out, so a single head pointer isn't enough — you enqueue at one end and dequeue from the other. The fix is two references: a head to poll from and a tail to offer at, so both operations stay O(1) (a singly linked list with a tail pointer suffices; a doubly linked list — "in from the right, out from the left" — makes the wiring symmetric and is what the notes sketch). The two cases that must be handled precisely are the empty queue on offer (the first node is simultaneously head and tail) and the last element on poll (draining to empty must reset both pointers to null, or a stale tail will haunt the next offer).

public class MyQueue<T> {
    private static class Node<T> {   // doubly-linked node
        T val;
        Node<T> next, prev;
        Node(T val) { this.val = val; }
    }

    private Node<T> head;    // dequeue end
    private Node<T> tail;    // enqueue end

    public void offer(T val) {          // enqueue at the tail
        Node<T> node = new Node<>(val);
        if (head == null) {           // empty queue: node is both ends
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    public T poll() {                  // dequeue from the head
        if (head == null) return null;
        Node<T> node = head;
        if (head == tail) {          // single element: reset BOTH ends
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
            node.next = null;         // disconnect the removed node
        }
        return node.val;
    }

    public T peek() {
        if (head == null) throw new NoSuchElementException();
        return head.val;
    }
}

Two things to say aloud here. The head == tail branch in poll is the whole correctness story — forget to null out tail and the next offer appends onto a detached node. And peek now throws instead of returning null: that's the deliberate answer to the generic-null trap from earlier. Returning an exception (or gating on a size field) is how you keep "empty" and "stored a null" from collapsing into the same value.

Design a Queue with a Fixed-Capacity Array (Circular Buffer)

Now the array version, where the interesting problems live. Model the live region as the half-open interval [head, tail): head indexes the front element, tail is the next write slot. Offer writes then advances tail; poll reads then advances head. The catch is the array end — a naive tail++ runs off the edge while there's free space at the front. The fix is a circular array: every advance wraps with % arr.length, so the buffer reuses the vacated front slots.

That wrap creates the classic ambiguity: after enough operations, head == tail means the queue is either completely empty or completely full — the pointers can't tell you which. Two standard resolutions: waste one slot (never let tail catch head), or — cleaner and what we use — keep an explicit size counter and compare it against capacity. size == 0 is empty, size == arr.length is full, no guessing.

public class ArrayQueue<T> {
    private T[] arr;
    private int head;    // index of the front element
    private int tail;    // next write position — the live region is [head, tail)
    private int size;

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        arr = (T[]) new Object[capacity];   // can't do new T[] — generics are erased at runtime
        head = tail = size = 0;
    }

    public boolean offer(T val) {
        if (size == arr.length) return false;   // full
        arr[tail] = val;                          // assign first...
        tail = (tail + 1) % arr.length;         // ...then advance, wrapping around
        size++;
        return true;
    }

    public T poll() {
        if (size == 0) return null;             // empty
        T val = arr[head];                        // read first...
        arr[head] = null;                        // release the reference for GC
        head = (head + 1) % arr.length;         // ...then advance
        size--;
        return val;
    }

    public T peek() {
        if (size == 0) throw new NoSuchElementException();
        return arr[head];
    }
}

The mechanical detail worth verbalizing: offer assigns then increments, poll reads then increments. Keep that order straight and the half-open [head, tail) invariant holds through every wrap. The size field does double duty — it disambiguates full/empty and makes offer/poll/peek all trivially O(1).

Design a Stack with a Fixed-Size Array

The array-backed stack is the easy sibling — no wraparound, because a stack only ever grows and shrinks at one end. Model the live region as [0, head), where head is both the element count and the next write index. Push assigns at head then increments; pop decrements then reads; peek looks at arr[head - 1]. Everything is O(1) and there's a single boundary variable to reason about.

public class ArrayStack<T> {
    private final T[] arr;
    private int head;    // element count; the valid range is [0, head)

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {   // note: constructor named for its own class, not ArrayQueue
        arr = (T[]) new Object[capacity];
        head = 0;
    }

    public boolean push(T val) {
        if (head == arr.length) return false;   // full
        arr[head++] = val;                        // assign, then advance the top
        return true;
    }

    public T pop() {
        if (head == 0) throw new EmptyStackException();
        T val = arr[--head];                      // step back, then read
        arr[head] = null;                        // release the reference
        return val;
    }

    public T peek() {
        if (head == 0) throw new EmptyStackException();
        return arr[head - 1];
    }
}

The pre- versus post-increment is the entire trick: arr[head++] pushes into the current top slot and moves the marker up, while arr[--head] steps the marker down first and then reads the element now exposed. (The notes threw a raw NullPointerException on empty; the idiomatic signal is EmptyStackException — what java.util.Stack itself raises — so an empty-stack bug reads as an empty-stack bug.)

Follow-up: Resizing & Amortized Cost

The obvious pushback on any fixed-capacity structure: "what happens when it fills?" The answer is to grow the backing array — typically double it — allocate a bigger array, copy the elements over, and swap it in. For the circular queue there's one subtlety: you can't Arrays.copyOf blindly, because the live elements may wrap past the end; you unroll them from head into a fresh, non-wrapped array and reset head = 0, tail = size.

@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
    T[] bigger = (T[]) new Object[newCapacity];
    for (int i = 0; i < size; i++)
        bigger[i] = arr[(head + i) % arr.length];   // unroll the wrap into a clean layout
    arr = bigger;
    head = 0;
    tail = size;                                     // [0, size) again — no wraparound
}

A single resize is genuinely expensive — O(n) to copy everything, and if you were doing this in a hash table it's the same "rehashing is expensive" cost. But — the line worth landing — the amortized cost is not much. Because you double rather than grow by one, a copy of size n only happens after n cheap O(1) operations, so the copy work spread across those operations averages out to O(1) per operation. This is exactly the argument behind ArrayList's append and HashMap's resize from Session 6 — say "expensive once, O(1) amortized" and you've answered the follow-up the way the interviewer is fishing for.

Design Checklist