Core Java · Chapter 47 of 48

Interview: collections

By the end of this chapter you can build a hash map from buckets, explain how it grows, build an LRU cache, and predict the classic ways people break the real collections. Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.

  • Part: The interview
  • 6 tasks
  • Java
  • In the all labs plan

The first 2 chapters of Core Java are free. This one comes with the all labs plan.

Why you need this

Round two. Every Tapri till uses HashMap thousands of times a shift: prices by item, stock by station, tickets by seat. Last month a refund screen could not find a booking that was still in the map, and a set of sold tickets counted one seat twice. Dev wants developers who know why.

So far HashMap has been a black box. That holds until a key changes, a class overrides equals alone, or a loop removes items as it goes: then it misbehaves in ways your tests do not catch, unless you know what happens inside.

What you build: 6 tasks

Each task has tests. You write the code in the lab's editor and press Check.

  1. Task 1 · interview question

    Interview: ChaiHashMap.java, build put and get for a hash map with buckets

    In ChaiHashMap.java, make put(key, value) and get(key) work on the array of buckets. put stores the value under the key and returns the value it replaced, or null when the key is new; putting a key that is already there replaces its value and does not change size(). get returns the value stored under the key, or null when there is none. Two keys are the same key when equals says so: different keys can land in the same bucket and must still be told apart. A null key is allowed. size() counts the keys.

    For example, put("Masala chai", 40) returns null, put("Masala chai", 45) then returns 40, get("Masala chai") gives 45 and size() stays 2 with Cutting chai also stored. get("Filter coffee") gives null, put(null, 0) returns null and get(null) gives 0. Three keys whose hash codes are all 42 are each found under their own value.

  2. Task 2 · interview question

    Interview: ChaiHashMap.java, grow the hash map when it gets too full

    In ChaiHashMap.java, make put double the number of buckets when a new key would make size() greater than 0.75 times capacity(). Do it before adding the key, and move every node to the bucket indexFor gives it for the new length, so every key, colliding keys included, can still be found. Replacing the value of a key that is already there never grows the map.

    For example, the map starts with 8 buckets; 6 keys keep it at 8 (exactly 0.75), the 7th key makes it 16, and the 13th makes it 32, with all 13 keys still found. Ten keys whose hash codes are all 42 end in 16 buckets, each still found.

  3. Task 3 · interview question

    Interview: LruCache.java, build an LRU cache on LinkedHashMap

    In LruCache.java, make the cache keep its keys in order of use, the one used longest ago first: a get and a put of a key both count as using it. When a put adds a key that makes the cache hold more than maxEntries, drop the entry used longest ago, so it never holds more than maxEntries.

    For example, with 3: put SBC-NDLS 2400, SBC-CSMT 1100 and NDLS-CSMT 1900, get SBC-NDLS, then put SBC-MAS 600, and the keys are [NDLS-CSMT, SBC-NDLS, SBC-MAS]. Then put NDLS-CSMT 2000 and CSMT-PUNE 300, and the keys are [SBC-MAS, NDLS-CSMT, CSMT-PUNE].

  4. Task 4 · interview question

    Interview: CollectionsQuiz.java, predict what removing inside a for-each loop does

    In CollectionsQuiz.java, make failFast() return the lines the code in its comment prints, one string per line, in order, written exactly as Java prints them (a list prints in square brackets, like [a, b]).

    The check runs the same code and compares your list with what Java really printed.

  5. Task 5 · interview question

    Interview: CollectionsQuiz.java, predict what happens to a key changed inside a HashMap

    In CollectionsQuiz.java, make mutableKey() return the lines the code in its comment prints, one string per line, in order, written exactly as Java prints them (null, true and false in lower case, a collection in square brackets).

    The check runs the same code and compares your list with what Java really printed.

  6. Task 6 · interview question

    Interview: Ticket.java, fix a class that overrides equals but not hashCode

    In Ticket.java, add a hashCode() method that overrides the one from Object, so that two equal tickets (the same station and the same seat) always have the same hash code. Build it from the same two fields equals uses. Then hash sets and maps treat equal tickets as one.

    For example, new Ticket("SBC", 7) and another new Ticket("SBC", 7) have the same hash code; a HashSet given NDLS 7 twice has size 1, contains NDLS 7 and does not contain NDLS 8; a HashMap with CSMT 3 mapped to Anjali finds Anjali for a new Ticket("CSMT", 3).

What you will learn

  • Buckets and collisions: the hash code picks a bucket, equals picks the key.
  • Load factor and resizing: why the buckets double, and why keys move.
  • LinkedHashMap in access order: the base of an LRU cache.
  • Fail-fast iterators, changed keys and hashCode: three classic ways to break a collection.

More in The interview

Build "Interview: collections" yourself

Tapri runs chai counters at railway stations, and every counter runs a Java program you write. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.

The first 2 chapters of Core Java are free. This one comes with the all labs plan.