These are the notes for Low-Level Design (LLD) episode 4. Every design in a machine-coding round stores many objects: orders, users, dishes, bookings. This episode builds the tools for that, each invented as the fix for a bug in a food-delivery app: the Collections Framework (List, Set, Map, Queue, Deque), the classes behind them (ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, LinkedHashMap, ArrayDeque, PriorityQueue), how Java decides two objects are equal (equals, hashCode and the equals-hashCode contract), how it puts objects in order (Comparable and Comparator), and Big-O notation for choosing the right collection. Every program was run with javac Main.java && java -cp . Main (Java 21), the same way the SyntaxPilot compiler runs it; outputs and error messages are real.
1. Why arrays are not enough
A restaurant keeps order slips on a board with 3 hooks. On a busy day order number 4 arrives and there is no hook left. An array is that board: a box of numbered slots whose size is fixed when you create it.
public class Main {
public static void main(String[] args) {
String[] orders = new String[3];
orders[0] = "Biryani";
orders[1] = "Dosa";
orders[2] = "Paneer Roll";
System.out.println("3 orders saved");
orders[3] = "Masala Chai";
System.out.println("4 orders saved");
}
}
3 orders saved
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
at Main.main(Main.java:8)
Slots are numbered from 0, so a length-3 array has slots 0, 1 and 2. Writing to slot 3 crashes. An exception is Java's way of stopping the program and reporting a problem (episode 5 covers them in depth). Real apps never know how many orders will come, so a fixed size is always wrong.
2. The Collections Framework
The Collections Framework is Java's ready-made set of containers in the package java.util. It has four families, each an interface (a promise of methods) with several implementations (classes that keep the promise):
| Family | Promise | Real-life picture | Main classes |
|---|---|---|---|
List |
ordered, grows, allows repeats, access by position | a roll of order paper | ArrayList, LinkedList |
Set |
no duplicates | students present today | HashSet, LinkedHashSet, TreeSet |
Map |
key -> value pairs, unique keys | a menu card: dish -> price | HashMap, LinkedHashMap, TreeMap |
Queue / Deque |
take from the ends | kitchen ticket rail, stack of plates | ArrayDeque, PriorityQueue, LinkedList |
A collection is simply an object that holds a group of other objects (its elements). Collections hold objects, not primitives: you write List<Integer>, not List<int>; Java converts int to Integer automatically (this is called autoboxing).
List and ArrayList
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> orders = new ArrayList<>();
orders.add("Biryani");
orders.add("Dosa");
orders.add("Paneer Roll");
orders.add("Masala Chai");
System.out.println(orders + " size " + orders.size());
System.out.println("First: " + orders.get(0));
orders.remove("Dosa");
System.out.println(orders);
System.out.println(orders.contains("Biryani"));
}
}
[Biryani, Dosa, Paneer Roll, Masala Chai] size 4
First: Biryani
[Biryani, Paneer Roll, Masala Chai]
true
import java.util.*;imports every class of the package (the*is a wildcard import).add(x)appends,get(i)reads positioni(the index, from 0),remove(x)removes the first match,contains(x)checks membership,size()counts.- An
ArrayListkeeps an array inside. When it fills up, it creates a bigger array (about 1.5 times larger) and copies the items over, so it seems to grow by itself. - Declare the interface, create the class:
List<String> orders = new ArrayList<>();. The rest of the code depends only onList, so swapping the class later changes one line. This is programming to an interface (OOP 2 goes deeper).
Other useful List methods: add(i, x) inserts at a position, set(i, x) replaces, indexOf(x), isEmpty(), clear(), List.of(...) (a fixed, unmodifiable list).
ArrayList vs LinkedList
- ArrayList = a cinema row with numbered seats: you walk straight to seat 7 (fast
get(i)), but if someone must sit in seat 1, everybody shifts (slow insert at the front). - LinkedList = a human chain holding hands: each item, a node, holds a link to the next (and previous) one. Joining at the front is easy, but finding person 7 means counting from the start.
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> a = new ArrayList<>(List.of("Dosa", "Idli"));
List<String> l = new LinkedList<>(List.of("Dosa", "Idli"));
a.add(0, "Vada");
l.add(0, "Vada");
System.out.println(a + " " + a.getClass().getSimpleName());
System.out.println(l + " " + l.getClass().getSimpleName());
System.out.println(a.equals(l));
}
}
[Vada, Dosa, Idli] ArrayList
[Vada, Dosa, Idli] LinkedList
true
Two Lists are equals when they hold equal items in the same order, whatever their class. The only difference is speed.
3. Big-O notation
Big-O notation describes how the number of steps an operation needs grows as the number of items n grows, ignoring constant details. It lets you compare speed without a stopwatch.
| Big-O | Name | Steps for n = 1,000,000 | Example |
|---|---|---|---|
| O(1) | constant | 1 | ArrayList.get(i), HashMap.get(k) |
| O(log n) | logarithmic | about 20 (halve each time, like a dictionary) | TreeMap.get(k) |
| O(n) | linear | up to 1,000,000 | ArrayList.contains(x) |
| O(n log n) | linearithmic | about 20,000,000 | sorting a list |
"Average" O(1) for hash collections means most operations take one step, but it gets slower if many items land in the same bucket (see section 5).
| Operation | ArrayList | LinkedList |
|---|---|---|
get(i) |
O(1) | O(n) |
| add at the end | O(1) amortised (on average, counting the occasional copy) | O(1) |
| add / remove at the front | O(n) (shifting) | O(1) |
contains(x) |
O(n) | O(n) |
Default choice: ArrayList. Its items sit next to each other in memory, which modern processors read very fast. If you need a fast front, use ArrayDeque (section 6), which usually beats LinkedList too.
4. Set: no duplicates
The problem: a coupon applied twice
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> coupons = new ArrayList<>();
coupons.add("WELCOME50");
coupons.add("FREEDEL");
coupons.add("WELCOME50");
int discount = 0;
for (String c : coupons)
discount += c.equals("WELCOME50") ? 50 : 30;
System.out.println(coupons);
System.out.println("Discount: Rs " + discount);
}
}
[WELCOME50, FREEDEL, WELCOME50]
Discount: Rs 130
A List keeps repeats, so the welcome coupon counted twice: a real money bug.
The fix: a Set
Change one line: Set<String> coupons = new HashSet<>();
[FREEDEL, WELCOME50]
Discount: Rs 80
A Set is a collection with no duplicates, like the set of students present today: nobody can be present twice. Adding an item that is already there does nothing, and add returns false.
HashSet vs TreeSet
- HashSet = railway station lockers: your token number tells you exactly which locker is yours. A HashSet turns each item into a number, its hash code, and that number picks a slot called a bucket. That is why
addandcontainsare O(1) on average, and also why the order looks random. - TreeSet = a library shelf kept in A to Z order. It stores items in a balanced tree (a red-black tree), always sorted; operations are O(log n).
- LinkedHashSet = a HashSet that also remembers insertion order.
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> tags = List.of("veg", "spicy", "south",
"jain", "chinese", "spicy");
Set<String> hash = new HashSet<>(tags);
Set<String> tree = new TreeSet<>(tags);
System.out.println("HashSet: " + hash);
System.out.println("TreeSet: " + tree);
System.out.println(hash.add("veg"));
}
}
HashSet: [chinese, south, veg, spicy, jain]
TreeSet: [chinese, jain, south, spicy, veg]
false
Never rely on a HashSet's order: it can change between Java versions or as the set grows.
5. Map: look-up by key
The problem: two parallel lists
import java.util.*;
public class Main {
static List<String> names = List.of("Dosa", "Idli", "Biryani");
static List<Integer> prices = List.of(80, 50, 250);
static int price(String dish) {
for (int i = 0; i < names.size(); i++)
if (names.get(i).equals(dish)) return prices.get(i);
return -1;
}
public static void main(String[] args) {
System.out.println("Biryani: Rs " + price("Biryani"));
System.out.println("Pizza: Rs " + price("Pizza"));
}
}
Biryani: Rs 250
Pizza: Rs -1
It works, but it is fragile (add a name without its price and every later price shifts) and every look-up is O(n).
The fix: a Map
A Map stores key-value pairs, like a menu card: the key is what you look up by (the dish name), the value is what you get back (the price). Keys are unique; putting the same key again replaces the value.
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, Integer> menu = new HashMap<>();
menu.put("Dosa", 80);
menu.put("Idli", 50);
menu.put("Biryani", 250);
menu.put("Dosa", 90);
System.out.println("Biryani: Rs " + menu.get("Biryani"));
System.out.println("Pizza: " + menu.get("Pizza"));
System.out.println(menu.getOrDefault("Pizza", 0));
System.out.println(menu.containsKey("Idli") + " " + menu.size());
for (Map.Entry<String, Integer> e : menu.entrySet())
System.out.println(e.getKey() + " -> " + e.getValue());
}
}
Biryani: Rs 250
Pizza: null
0
true 3
Dosa -> 90
Biryani -> 250
Idli -> 50
put(k, v)adds or replaces,get(k)returns the value ornull(no object at all) for a missing key,getOrDefault(k, d)returnsdinstead,containsKey(k),remove(k),size().entrySet()gives every pair as aMap.EntrywithgetKey()andgetValue(). AlsokeySet()andvalues().- Storing
menu.get("Pizza")in anintthrows aNullPointerException, becausenullcannot become a number. UsegetOrDefaultorcontainsKey. - Counting idiom:
count.merge(dish, 1, Integer::sum);orcount.put(dish, count.getOrDefault(dish, 0) + 1);.
HashMap vs LinkedHashMap vs TreeMap
import java.util.*;
public class Main {
static void fill(Map<String, Integer> m) {
m.put("Masala Chai", 20); m.put("Dosa", 80);
m.put("Vada", 40); m.put("Biryani", 250);
}
public static void main(String[] args) {
Map<String, Integer> hash = new HashMap<>();
Map<String, Integer> linked = new LinkedHashMap<>();
Map<String, Integer> tree = new TreeMap<>();
fill(hash); fill(linked); fill(tree);
System.out.println("HashMap: " + hash);
System.out.println("LinkedHashMap: " + linked);
System.out.println("TreeMap: " + tree);
}
}
HashMap: {Vada=40, Masala Chai=20, Dosa=80, Biryani=250}
LinkedHashMap: {Masala Chai=20, Dosa=80, Vada=40, Biryani=250}
TreeMap: {Biryani=250, Dosa=80, Masala Chai=20, Vada=40}
| Map | Order | Speed | Use when |
|---|---|---|---|
HashMap |
none promised | O(1) average | order doesn't matter (most look-ups) |
LinkedHashMap |
insertion order | O(1) average | print in the order things were added; LRU caches |
TreeMap |
sorted by key | O(log n) | sorted keys, ranges (firstKey, floorKey, headMap) |
6. equals and hashCode
The problem: two Dosas in a Set
import java.util.*;
class Dish {
final String name; final int price;
Dish(String name, int price) { this.name = name; this.price = price; }
}
public class Main {
public static void main(String[] args) {
Set<Dish> cart = new HashSet<>();
cart.add(new Dish("Dosa", 80));
cart.add(new Dish("Dosa", 80));
System.out.println("Items: " + cart.size());
System.out.println(cart.contains(new Dish("Dosa", 80)));
}
}
Items: 2
false
Every class inherits equals and hashCode from the class Object. The default equals means identity: "is this the very same object in memory?" (the same as ==). Two new Dish(...) are two different objects, so they are not equal. For a value-like class we want equality by content: same name and price = same dish.
Overriding equals only (still broken)
@Override public boolean equals(Object o) {
if (!(o instanceof Dish d)) return false;
return name.equals(d.name) && price == d.price;
}
@Override asks the compiler to check that we really are replacing an inherited method. o instanceof Dish d checks the type and, if it matches, gives us o as a Dish named d (pattern matching). Adding to main:
Dish a = new Dish("Dosa", 80), b = new Dish("Dosa", 80);
System.out.println(a.equals(b) + " " + (a.hashCode() == b.hashCode()));
Items: 2
true false
false
equals is now true, but the hash codes differ. A HashSet first uses hashCode to pick the bucket (the locker), and only then calls equals on the items in that bucket. Different hash codes mean different lockers, so equals is never even called.
The fix: override both
@Override public int hashCode() { return Objects.hash(name, price); }
Items: 1
true true
true
Objects.hash(...) combines the hash codes of the given fields into one number.
The equals-hashCode contract
- If
a.equals(b)is true, thena.hashCode() == b.hashCode()must be true. - The reverse is not required: unequal objects may share a hash code (a collision: two bags in one locker);
equalstells them apart. Too many collisions make hash collections slow. equalsmust be reflexive (a.equals(a)), symmetric (a.equals(b)⇔b.equals(a)), transitive (a = b and b = c ⇒ a = c), consistent (same answer while the objects don't change), anda.equals(null)isfalse.- Use the same fields in both and keep them
final. If a key's fields change after it is inside a HashSet or HashMap, it sits in the wrong bucket and can no longer be found.
Shortcut: a record (episode 3) generates a correct equals, hashCode and toString from its components. For value objects, use a record.
7. Queue and Deque
- A Queue is first in, first out (FIFO): kitchen tickets on a rail.
offer(x)adds at the back,poll()removes from the front (or returnsnullif empty),peek()looks at the front without removing. - A stack is last in, first out (LIFO): a stack of plates. Perfect for undo.
push(x),pop(),peek(). - A Deque (said "deck") is a double-ended queue: add or remove at both ends, like a train with doors at both ends.
ArrayDequeis the fast, standard implementation; use it instead of the oldStackclass.
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<String> kitchen = new ArrayDeque<>();
kitchen.offer("#101 Biryani");
kitchen.offer("#102 Dosa");
kitchen.offer("#103 Chai");
System.out.println("Waiting: " + kitchen);
System.out.println("Next up: " + kitchen.peek());
while (!kitchen.isEmpty())
System.out.println("Cooking " + kitchen.poll());
System.out.println("Empty poll: " + kitchen.poll());
}
}
Waiting: [#101 Biryani, #102 Dosa, #103 Chai]
Next up: #101 Biryani
Cooking #101 Biryani
Cooking #102 Dosa
Cooking #103 Chai
Empty poll: null
import java.util.*;
public class Main {
public static void main(String[] args) {
Deque<String> undo = new ArrayDeque<>();
undo.push("added Dosa");
undo.push("added Chai");
undo.push("removed Idli");
System.out.println("History: " + undo);
System.out.println("Undo: " + undo.pop());
System.out.println("Undo: " + undo.pop());
undo.addLast("oldest action");
System.out.println(undo.peekFirst() + " | " + undo.peekLast());
}
}
History: [removed Idli, added Chai, added Dosa]
Undo: removed Idli
Undo: added Chai
added Dosa | oldest action
| Action | Throws an exception if it fails | Returns a special value |
|---|---|---|
| add at back | add(x) |
offer(x) (returns false) |
| remove front | remove() |
poll() (returns null) |
| look at front | element() |
peek() (returns null) |
8. Ordering: PriorityQueue, Comparable and Comparator
The problem: Java can't order an Order
A PriorityQueue always hands out the smallest (highest-priority) item first, not the oldest. We want the quickest orders cooked first.
import java.util.*;
class Order {
final int id; final int mins;
Order(int id, int mins) { this.id = id; this.mins = mins; }
public String toString() { return "#" + id + "(" + mins + "m)"; }
}
public class Main {
public static void main(String[] args) {
Queue<Order> pq = new PriorityQueue<>();
pq.add(new Order(101, 25));
pq.add(new Order(102, 5));
pq.add(new Order(103, 12));
while (!pq.isEmpty()) System.out.println(pq.poll());
}
}
Exception in thread "main" java.lang.ClassCastException: class Order cannot be cast to class java.lang.Comparable (Order is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:643)
at java.base/java.util.PriorityQueue.siftUp(PriorityQueue.java:639)
at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:330)
at java.base/java.util.PriorityQueue.add(PriorityQueue.java:311)
at Main.main(Main.java:11)
It fails on the very first add: the queue must be able to compare orders, and Order has no order.
Comparable: the natural order
Comparable gives a class its one natural order, like roll numbers in a class. Implement Comparable<Order> and write compareTo(other), which returns a negative number if this comes first, 0 for a tie, positive if this comes after.
class Order implements Comparable<Order> {
final int id; final int mins;
Order(int id, int mins) { this.id = id; this.mins = mins; }
public String toString() { return "#" + id + "(" + mins + "m)"; }
public int compareTo(Order o) {
return Integer.compare(mins, o.mins);
}
}
#102(5m)
#103(12m)
#101(25m)
- PriorityQueue
offer/pollare O(log n),peekis O(1). It is stored as a binary heap (a tree kept in an array where each parent is smaller than its children). Printing the whole queue does not show sorted order; onlypolldoes. - Use
Integer.compare(a, b), nota - b: subtraction can overflow (go past the largestint, 2,147,483,647, and wrap around to a negative number), giving the wrong sign. String,Integer,LocalDateand enums are alreadyComparable.
Comparator: any order, from outside
A Comparator is a separate object that compares two things, like a sports-day judge who lines students up by height or by marks. One class can have many Comparators.
import java.util.*;
record Dish(String name, int price, double rating) { }
public class Main {
public static void main(String[] args) {
List<Dish> menu = new ArrayList<>(List.of(
new Dish("Dosa", 80, 4.5), new Dish("Biryani", 250, 4.8),
new Dish("Idli", 50, 4.5), new Dish("Thali", 180, 4.2)));
menu.sort(Comparator.comparing(Dish::price));
System.out.println("Cheapest first:");
menu.forEach(d -> System.out.println(" " + d));
menu.sort(Comparator.comparing(Dish::rating).reversed()
.thenComparing(Dish::name));
System.out.println("Best rated first:");
menu.forEach(d -> System.out.println(" " + d));
}
}
Cheapest first:
Dish[name=Idli, price=50, rating=4.5]
Dish[name=Dosa, price=80, rating=4.5]
Dish[name=Thali, price=180, rating=4.2]
Dish[name=Biryani, price=250, rating=4.8]
Best rated first:
Dish[name=Biryani, price=250, rating=4.8]
Dish[name=Dosa, price=80, rating=4.5]
Dish[name=Idli, price=50, rating=4.5]
Dish[name=Thali, price=180, rating=4.2]
Comparator.comparing(Dish::price)builds a comparator from a "key extractor".Dish::priceis a method reference: "callprice()on each dish".d -> ...is a lambda, a small unnamed function. Both are covered in episode 5..reversed()flips the order;.thenComparing(...)breaks ties.list.sort(c)andCollections.sort(list)use a stable merge sort (TimSort): O(n log n), and equal items keep their relative order.- You can pass a Comparator to
new TreeSet<>(c),new TreeMap<>(c)andnew PriorityQueue<>(c).
| Comparable | Comparator | |
|---|---|---|
| Where | inside the class: implements Comparable<T> |
outside: a separate object |
| Method | compareTo(T other) |
compare(T a, T b) |
| How many | one natural order | as many as you like |
| Example | an order by id | dishes by price, by rating |
9. Choosing the right collection
Ask what the code needs, then pick the class.
| You need | Use |
|---|---|
| order kept, repeats allowed, access by position | ArrayList |
| no duplicates | HashSet |
| no duplicates, sorted | TreeSet |
| no duplicates, insertion order | LinkedHashSet |
| look-up by key | HashMap |
| keys in insertion order | LinkedHashMap |
| keys sorted, ranges | TreeMap |
| first in, first out | ArrayDeque as a Queue |
| last in, first out (undo, back button) | ArrayDeque with push/pop |
| smallest / most urgent first | PriorityQueue |
| keys that are enum constants | EnumMap (episode 3) |
Big-O cheat sheet
| Collection | add | remove | contains / get | Notes |
|---|---|---|---|---|
| ArrayList | O(1) at end, O(n) at front | O(n) | get(i) O(1), contains O(n) | default list |
| LinkedList | O(1) at ends | O(1) at ends | O(n) | rarely the best choice |
| HashSet / HashMap | O(1) avg | O(1) avg | O(1) avg | needs equals + hashCode |
| TreeSet / TreeMap | O(log n) | O(log n) | O(log n) | needs an order |
| ArrayDeque | O(1) at ends | O(1) at ends | O(n) | queue and stack |
| PriorityQueue | O(log n) | poll O(log n) | peek O(1) | needs an order |
The class diagram
«interface» Collection<E> «interface» Map<K, V>
+ add(e) + contains(e) + size() + put(k, v) + get(k)
^ ^ ^ ^ (implements)
«interface» «interface» «interface» HashMap, LinkedHashMap,
List<E> Set<E> Queue<E> TreeMap
ArrayList, HashSet, ArrayDeque,
LinkedList TreeSet PriorityQueue
Map is not a Collection: it stores pairs, not single elements.
Common mistakes
| Mistake | Exact message / symptom | Why | Fix |
|---|---|---|---|
| Writing past an array's end | ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3 |
Arrays have a fixed size | Use an ArrayList |
list.get(5) on a 3-item list |
IndexOutOfBoundsException: Index 5 out of bounds for length 3 |
No such position | Check size() first |
Override equals but not hashCode |
No error: a HashSet keeps both (Items: 2) |
Equal objects land in different buckets | Override both, or use a record |
| Changing a field of an object inside a HashSet/HashMap key | contains returns false for it |
It is in the wrong bucket now | Make key fields final |
| PriorityQueue/TreeSet of a class with no order | ClassCastException: class Order cannot be cast to class java.lang.Comparable |
Java can't compare them | implements Comparable, or pass a Comparator |
Doing maths with map.get(k) for a missing key |
NullPointerException |
get returned null |
getOrDefault(k, 0) or containsKey |
Adding to List.of(...) |
UnsupportedOperationException |
List.of is unmodifiable |
new ArrayList<>(List.of(...)) |
compareTo with a - b |
wrong order for huge or negative values | integer overflow | Integer.compare(a, b) |
| Removing from a list inside a for-each loop | ConcurrentModificationException |
The list changed under the loop | list.removeIf(...) or an Iterator |
| Relying on HashSet/HashMap print order | order changes | no order is promised | LinkedHashMap/TreeMap |
Mini project
Build an order book for the app: count orders per dish, list unique customer cities in A to Z order, cook orders quickest first, and show the menu by price.
Solution
import java.util.*;
record Order(int id, String dish, String city, int mins) implements Comparable<Order> {
public int compareTo(Order o) { return Integer.compare(id, o.id); }
}
public class Main {
public static void main(String[] args) {
List<Order> orders = List.of(
new Order(103, "Dosa", "Pune", 10), new Order(101, "Biryani", "Delhi", 25),
new Order(102, "Dosa", "Bengaluru", 12), new Order(104, "Chai", "Pune", 5));
Map<String, Integer> perDish = new TreeMap<>();
for (Order o : orders) perDish.merge(o.dish(), 1, Integer::sum);
System.out.println("Per dish: " + perDish);
Set<String> cities = new TreeSet<>();
for (Order o : orders) cities.add(o.city());
System.out.println("Cities: " + cities);
List<Order> byId = new ArrayList<>(orders);
Collections.sort(byId);
System.out.println("By id: " + byId.get(0).id() + " ... " + byId.get(3).id());
Queue<Order> kitchen = new PriorityQueue<>(Comparator.comparing(Order::mins));
kitchen.addAll(orders);
while (!kitchen.isEmpty()) System.out.print(kitchen.poll().id() + " ");
System.out.println();
}
}
Per dish: {Biryani=1, Chai=1, Dosa=2}
Cities: [Bengaluru, Delhi, Pune]
By id: 101 ... 104
104 103 102 101
merge(key, 1, Integer::sum) puts 1 for a new key, or adds 1 to the existing value. The record's natural order is by id; the kitchen uses a Comparator by minutes.
Practice
- Which collection: (a) a user's search history, newest first, with an undo; (b) all usernames, checked for "is this taken?"; (c) a leaderboard sorted by score?
Solution
(a) ArrayDeque used as a stack (push/pop). (b) HashSet<String>: O(1) contains. (c) TreeMap<Integer, ...> or a List sorted with a Comparator (or a PriorityQueue if you only need the top).
- Why is
list.contains(x)slow on a million-itemArrayList, and what would you use?
Solution
It checks items one by one: O(n). Keep a HashSet for membership checks: O(1) on average.
- Two
Dishobjects areequalsbut have different hash codes. Which rule is broken, and what happens in aHashMap<Dish, Integer>?
Solution
The equals-hashCode contract (equal objects must have equal hash codes). map.get(sameDish) looks in the wrong bucket and returns null; put adds a second entry instead of replacing.
- Write a Comparator that sorts orders by city A to Z, and by minutes (smallest first) within a city.
Solution
Comparator<Order> c = Comparator.comparing(Order::city).thenComparing(Order::mins);
Quick quiz
A Seat class overrides equals (same seat number = equal) but not hashCode. We add new Seat(7) twice to a HashSet. What does size() print?
- 1
- 2
- 0
- Compile error
Answer
2. The two seats are equal, but their default hash codes differ, so they land in different buckets and equals is never called. The set keeps both.
Interview questions
- ArrayList vs LinkedList? ArrayList: array inside, O(1)
get(i), O(n) insert at front, cache-friendly; the default. LinkedList: nodes, O(1) at the ends, O(n)get(i). - HashMap vs TreeMap vs LinkedHashMap? No order and O(1) average / sorted keys and O(log n) / insertion order and O(1) average.
- How does a HashMap find a key? It computes
hashCode(), picks a bucket from it, then compares keys in that bucket withequals(). (Since Java 8, a crowded bucket turns into a small tree.) - What is the equals-hashCode contract? Equal objects must have equal hash codes; equals must be reflexive, symmetric, transitive, consistent, and false for null.
- Comparable vs Comparator? Comparable: the class's one natural order (
compareTo). Comparator: any external order (compare), as many as needed. - Why should HashMap keys be immutable? If a key's fields change, its hash code changes and the entry can't be found.
- Which collection for an LRU cache?
LinkedHashMapwith access order (new LinkedHashMap<>(16, 0.75f, true)andremoveEldestEntry).
Glossary
| Term | Meaning, with an example |
|---|---|
| Array | A fixed-size box of numbered slots. new String[3] |
| Index | An item's position, starting at 0. orders.get(0) |
| Exception | Java stopping the program to report a problem. ArrayIndexOutOfBoundsException |
| Collection | An object holding a group of other objects (its elements) |
| Collections Framework | Java's ready-made containers in java.util: List, Set, Map, Queue |
| Interface vs implementation | The promise (List) vs the class that keeps it (ArrayList) |
| Programming to an interface | Declaring variables with the interface type: List<String> x = new ArrayList<>() |
| Wildcard import | import java.util.*; imports every class of the package |
| Autoboxing | Java turning int into Integer automatically so it fits in a collection |
| List | Ordered, growing, allows repeats |
| ArrayList | A List backed by a growing array; fast get(i) |
| LinkedList | A List of linked nodes; fast at the ends |
| Node | One item in a linked structure, holding a link to the next |
| Set | A collection with no duplicates |
| HashSet | A Set using hash codes and buckets; O(1) average, no order |
| TreeSet | A Set kept sorted in a tree; O(log n) |
| LinkedHashSet | A HashSet that remembers insertion order |
| Map | Key-value pairs with unique keys. menu.put("Dosa", 80) |
| Key / value | What you look up by / what you get back |
| HashMap | A Map using hashing; O(1) average, no order |
| TreeMap | A Map with sorted keys; O(log n) |
| LinkedHashMap | A HashMap that keeps insertion order |
null |
No object at all; map.get returns it for a missing key |
| NullPointerException | Using null as if it were an object or a number |
getOrDefault |
A map's value, or a default if the key is missing |
entrySet / Map.Entry |
All pairs of a map / one pair with getKey() and getValue() |
| Hash code | A number computed from an object, used to pick a bucket. hashCode() |
| Bucket | A slot in a hash table, chosen by the hash code |
| Hashing | Turning an item into a number that decides where it is stored |
| Collision | Two different objects with the same bucket |
equals |
The method that decides if two objects are equal |
| Identity vs equality | Same object in memory (==) vs same content (equals) |
@Override |
Asks the compiler to check you are replacing an inherited method |
Objects.hash |
Combines fields' hash codes into one |
| equals-hashCode contract | Equal objects must have equal hash codes (+ reflexive, symmetric, transitive, consistent, not equal to null) |
| Reflexive / symmetric / transitive | a = a / a = b ⇒ b = a / a = b and b = c ⇒ a = c |
| Queue | First in, first out (FIFO). offer, poll, peek |
| FIFO / LIFO | First in first out (a queue) / last in first out (a stack) |
| Stack | Last in, first out: a stack of plates. push, pop |
| Deque | Double-ended queue (said "deck"): add/remove at both ends |
| ArrayDeque | Java's fast Deque, used as a queue or a stack |
| PriorityQueue | A queue that always gives the smallest / highest-priority item |
| Binary heap | A tree stored in an array, parent smaller than children; inside PriorityQueue |
| Natural order | The one obvious order of a class (numbers, A to Z, roll numbers) |
| Comparable | Interface giving a class its natural order via compareTo |
compareTo / compare |
Return negative (before), 0 (tie), positive (after) |
| Comparator | A separate object defining any order. Comparator.comparing(Dish::price) |
thenComparing / reversed |
Break ties / flip the order |
| Method reference | Dish::price: "call price() on each" (episode 5) |
| Lambda | A small unnamed function. d -> d.price() (episode 5) |
| Overflow | A number going past the largest int and wrapping around |
| Big-O notation | How steps grow with the number of items n |
| O(1), O(log n), O(n), O(n log n) | Constant, logarithmic, linear, linearithmic (sorting) |
| Amortised | Averaged over many operations (ArrayList's occasional copy) |
| Unmodifiable | Cannot be changed: List.of(...) throws on add |
Summary
- Arrays are fixed; the Collections Framework gives growing containers: List (order, repeats), Set (no duplicates), Map (key -> value), Queue/Deque (ends).
- ArrayList is the default list; HashSet/HashMap are O(1) average and unordered; Tree versions are sorted, O(log n); Linked versions keep insertion order.
- Hash collections need
equalsandhashCodetogether (the contract); records do it for you. - ArrayDeque is the queue and the stack; PriorityQueue serves the smallest first.
- Comparable = one natural order (
compareTo); Comparator = any order (comparing,thenComparing,reversed). - Choose with Big-O and by asking what the code needs.
Next episode: Java for LLD 4: exceptions, Optional, lambdas and streams.