Checkpoint — Collections framework

Q: What is the time complexity of get, add and contains on ArrayList, HashSet and TreeMap?

ArrayList: get O(1), add at the end O(1) amortised, contains O(n). HashSet: add and contains O(1) on average. TreeMap: get, put and containsKey O(log n).

Q: Why use ArrayDeque instead of Stack for a stack in Java?

Stack extends Vector: every method is synchronised, which is slow, and it inherits index methods that break the stack abstraction. ArrayDeque gives O(1) push, pop and peek without either problem.

26 min · +25 XP · 3 exercises · 15 questions

Exercises0/3

Quiz · 70% to clear15 q

This checkpoint covers the framework's structure and complexities, lists, sets, maps and HashMap internals, queues and PriorityQueue, sorting and comparators, iteration and fail-fast behaviour, and immutable collections and utilities.

How it works. Fifteen questions and two programs; 70% on the questions and both programs accepted clears the module.

Before you start, make sure you can answer:

The complexity of get, add and contains on ArrayList, HashSet and TreeMap.
How HashMap.put finds a bucket and what happens on collision and resize.
Which class to use for a stack, and why not Stack.
Whether iterating a PriorityQueue gives sorted order.
The four safe ways to remove while iterating.
The difference between List.of, Arrays.asList and Collections.unmodifiableList.

The programs are a word-frequency report using the modern map API and comparators, and a small task scheduler built on a priority queue and a deque.

Common questions

What is the time complexity of get, add and contains on ArrayList, HashSet and TreeMap?

ArrayList: get O(1), add at the end O(1) amortised, contains O(n). HashSet: add and contains O(1) on average. TreeMap: get, put and containsKey O(log n).

Does iterating a PriorityQueue give sorted order?

No. Only the head is guaranteed to be the smallest element; iteration and toString show the heap's internal order. Poll the elements one by one, or copy and sort them, to get them in order.

Why use ArrayDeque instead of Stack for a stack in Java?

Stack extends Vector: every method is synchronised, which is slow, and it inherits index methods that break the stack abstraction. ArrayDeque gives O(1) push, pop and peek without either problem.

Java Collections Quiz: Lists, Sets, Maps and Queues Test

Practise the Java collections framework with 15 questions and two programs on lists, sets, HashMap internals, PriorityQueue, comparators and fail-fast loops.

Course: Java study plan
Module: Collections framework
Kind: Checkpoint — cleared at 70%
Reading time: 26 min
Runtime: OpenJDK 18

Checkpoint — Collections framework is the checkpoint that closes the Collections framework module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

How it works. Fifteen questions and two programs; 70% on the questions and both programs accepted clears the module.

Before you start, make sure you can answer:

The complexity of get, add and contains on ArrayList, HashSet and TreeMap.
How HashMap.put finds a bucket and what happens on collision and resize.
Which class to use for a stack, and why not Stack.
Whether iterating a PriorityQueue gives sorted order.
The four safe ways to remove while iterating.
The difference between List.of, Arrays.asList and Collections.unmodifiableList.

The programs are a word-frequency report using the modern map API and comparators, and a small task scheduler built on a priority queue and a deque.

Common questions

What is the time complexity of get, add and contains on ArrayList, HashSet and TreeMap?

ArrayList: get O(1), add at the end O(1) amortised, contains O(n). HashSet: add and contains O(1) on average. TreeMap: get, put and containsKey O(log n).

Does iterating a PriorityQueue give sorted order?

No. Only the head is guaranteed to be the smallest element; iteration and toString show the heap's internal order. Poll the elements one by one, or copy and sort them, to get them in order.

Why use ArrayDeque instead of Stack for a stack in Java?

Exercises

Word frequency report

Read all of standard input as text. Split into words on non-letters ([^a-zA-Z]+), lower-case them, ignore empties. Count with a HashMap and merge. Print the top 3 words as <word> <count> per line, ordered by count descending then word ascending (sort the entry set with Map.Entry.comparingByValue().reversed() and a tie-breaker — or a hand-written comparator), then distinct=<number of distinct words>, then longest=<the longest word; ties by natural order>.

Example input the cat and the hat. The end →

the 3
and 1
cat 1
distinct=5
longest=and

A tiny scheduler

Tasks have a name and a priority (lower number = more urgent). Read an integer n and n commands: add <name> <priority> (into a PriorityQueue ordered by priority, ties by name); run (poll the most urgent and print run <name>, or idle if empty); defer (poll the most urgent and push it onto an ArrayDeque stack of deferred tasks, printing deferred <name>, or idle); resume (pop the last deferred task back into the queue, printing resumed <name>, or none). After all commands print pending=<queue size> deferred=<stack size>.

Example: 5 then add b 2, add a 1, defer, run, resume →

deferred a
run b
resumed a
pending=1 deferred=0

Meeting rooms

Read n meetings <start> <end> (integers, end exclusive). Compute the minimum number of rooms so that no two overlapping meetings share a room: sort by start, keep a PriorityQueue<Integer> of end times of meetings in progress, free a room when the earliest end is <= the next start. Print rooms=<k>, then assign rooms greedily in that order — each meeting takes the lowest-numbered free room (a TreeSet<Integer> of free rooms) — printing <start>-<end> room <r> in start order.

Example: 3 then 0 30, 5 10, 15 20 →

rooms=2
0-30 room 1
5-10 room 2
15-20 room 2

In this module: Collections framework

← Immutable collections and the utility toolkit · Streams — pipelines over data →