OOP for DSA & Design Rounds: guided lesson

the story

Classes, objects & encapsulation

Every tool here exists because something was too slow or broke without it. Here is what.

1962–1967 · Ole-Johan Dahl and Kristen Nygaard

Dahl and Nygaard, at the Norwegian Computing Center, wanted to describe and simulate real systems. Simula I, a simulation language, and Simula 67, a general-purpose language built on ALGOL 60, introduced classes, objects and inheritance. In 2001 they received the ACM Turing Award "for ideas fundamental to the emergence of object oriented programming". Java's class, new and extends are those same three ideas.

the problem it solved

Keep each piece of state together with the only code allowed to change it, and create as many independent copies (objects) as the program needs.

why it matters: without it

State and the code that guards it drift apart: any line could set a count to −1, and design answers become bags of global variables.

sources: ACM A.M. Turing Award 2001: Kristen Nygaard ↗ · ACM A.M. Turing Award 2001: Ole-Johan Dahl ↗

also in this chapter: Static nested vs inner classes · The equals/hashCode contract · Records · Generics · Enums

the idea

The idea in 30 seconds

A class is a blueprint; new builds an object from it on the heap. Every linked list and tree you write is objects pointing at objects.

Design questions ("Design a HashSet", "Design a Parking System") test one habit: keep the state in private fields, and make each operation a small method that checks, updates and returns.

HashMap, HashSet and sorting trust your class's equals, hashCode and compareTo. Keep those contracts and the library does the heavy lifting.

picture this

A Google Form: the form (class) defines the questions once, and every submission (object) holds its own answers. A setting printed on the form itself, like the closing date, is shared by every submission: that is a static field.

watch it

Design Linked List: Node objects and next references

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Design Linked List: Node objects and next references

The MyLinkedList object holds size and an arrow to a dummy node; each Node holds a value and a next arrow. An insert is two arrow changes, in the right order.

loading simulation…

javajava.util.*

1// On LeetCode, name this class MyLinkedList.2class MyLinkedListSingly {3    private static class Node {4        int val;5        Node next;6 7        Node(int val) {8            this.val = val;9        }10    }11 12    private final Node dummy = new Node(0);          // sentinel before the real head13    private int size = 0;14 15    private Node before(int index) {                 // the node just BEFORE position index16        Node prev = dummy;17        for (int i = 0; i < index; i++) prev = prev.next;18        return prev;19    }20 21    public int get(int index) {22        if (index < 0 || index >= size) return -1;23        return before(index).next.val;24    }25 26    public void addAtHead(int val) {27        addAtIndex(0, val);28    }29 30    public void addAtTail(int val) {31        addAtIndex(size, val);32    }33 34    public void addAtIndex(int index, int val) {35        if (index < 0 || index > size) return;       // index == size means append36        Node prev = before(index);37        Node node = new Node(val);38        node.next = prev.next;                       // link forward first...39        prev.next = node;                            // ...then hook it in40        size++;41    }42 43    public void deleteAtIndex(int index) {44        if (index < 0 || index >= size) return;45        Node prev = before(index);46        prev.next = prev.next.next;                  // the skipped node becomes garbage47        size--;48    }49}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Design HashSet: hashCode picks the bucket, equality confirms

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Design HashSet: hashCode picks the bucket, equality confirms

Each call searches one bucket only. With 5 buckets, keys 1, 6, 11 and 16 all land in bucket 1: a collision chain.

loading simulation…

javajava.util.*

1class MyHashSet {2    private static class Node {                      // one link in a bucket's chain3        final int key;4        Node next;5 6        Node(int key, Node next) {7            this.key = key;8            this.next = next;9        }10    }11 12    private final Node[] buckets;13 14    public MyHashSet() {15        this(10_007);                                // a prime above the 10^4 calls: short chains16    }17 18    MyHashSet(int bucketCount) {                     // the 3D sim uses only a few buckets19        buckets = new Node[bucketCount];20    }21 22    private int indexOf(int key) {23        return Math.floorMod(Integer.hashCode(key), buckets.length);   // hashCode picks the bucket24    }25 26    public void add(int key) {27        if (contains(key)) return;                   // a set keeps one copy28        int i = indexOf(key);29        buckets[i] = new Node(key, buckets[i]);      // the new node becomes the chain's head30    }31 32    public void remove(int key) {33        int i = indexOf(key);34        Node dummy = new Node(-1, buckets[i]);       // a dummy head: removing the first node is not special35        for (Node prev = dummy; prev.next != null; prev = prev.next) {36            if (prev.next.key == key) {              // the equality check (for int keys, ==)37                prev.next = prev.next.next;38                break;39            }40        }41        buckets[i] = dummy.next;42    }43 44    public boolean contains(int key) {45        for (Node n = buckets[indexOf(key)]; n != null; n = n.next) {  // walk one short chain46            if (n.key == key) return true;47        }48        return false;49    }50}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 10