TreeMap as a leaderboard and time series
A real leaderboard must handle ties (two players with 820); key by score then name, or map each score to a list of names.
LinkedHashMap is a HashMap that also remembers order (insertion or, optionally, access order), which makes a five-line LRU cache. TreeMap keeps keys sorted in a red-black tree and answers range and nearest-key questions in O(log n).
Change the code and press Run (Ctrl+Enter). Try to predict the output first, then break it on purpose and read the error. Your edits are saved and match the lesson page.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Use a LinkedHashMap<String, Integer> to count words in "the cat and the hat and the bat" and print the counts in the order each word first appeared.
Build a booking checker with a TreeMap<Integer, Integer> mapping start time to end time. Add bookings 900-1000 and 1100-1200, then check whether 930-1030, 1000-1100 and 1150-1300 can be booked (no overlap), using floorEntry and ceilingEntry. Print each result.
Write a FIFO cache of capacity 2 (evicts the oldest inserted key, not the least recently used) using LinkedHashMap and removeEldestEntry. Put a, b, read a, put c, then print the keys.
Explain it without notes
How does LinkedHashMap maintain order, and what's the difference between insertion and access order?
Implement an LRU cache in Java and explain the time complexity of each operation.
When would you choose TreeMap over HashMap? Give two concrete use cases.
What are floorKey, ceilingKey, headMap and subMap, and are the range methods copies?
Expected output
top: 910=meera
leaderboard: {910=meera, 820=asha, 700=kabir, 640=ravi}
first score above 700: 820=asha
700 and up: {700=kabir, 820=asha, 910=meera}
between 650 and 850: {700=kabir, 820=asha}
price at 10:42: 102.0
price at 08:00: null
after dropping old history: {1015=102.0, 1100=99.8}
pollFirstEntry: 640=ravi, left [700, 820, 910]