skip to content

What navigation methods does NavigableMap add, and what does each of floorKey, ceilingKey, lowerEntry, and higherEntry return?

level: middleimportance: must knowfreq 68%

answer

  1. floor ≤ k, ceiling ≥ k (inclusive)
  2. lower < k, higher > k (strict)
  3. *Key returns key, *Entry returns Map.Entry
  4. null when no such key exists
  5. All O(log n) on the red-black tree

basics

~20 s

NavigableMap adds nearest-key lookups. For a key k: floorKey returns the largest key ≤ k, ceilingKey the smallest key ≥ k, lowerKey the largest key strictly < k, higherKey the smallest key strictly > k. The *Entry versions return the whole entry, or null if none exists.

solid answer

~40 s

NavigableMap (implemented by TreeMap) adds nearest-neighbour and endpoint navigation on the sorted keys. The four relative lookups, given a key k, are: floor = greatest key ≤ k (inclusive below), ceiling = least key ≥ k (inclusive above), lower = greatest key strictly < k (exclusive below), higher = least key strictly > k (exclusive above). Each comes in a *Key form returning just the key and a *Entry form returning the Map.Entry; both return null when no such key exists. It also adds firstEntry/lastEntry, pollFirstEntry/pollLastEntry (read-and-remove), descendingMap/descendingKeySet (reverse views), and the inclusive-bound range views headMap/tailMap/subMap with a boolean to include or exclude the endpoint. All run in O(log n) since they descend the red-black tree. The mnemonic: floor/ceiling are inclusive (≤ / ≥), lower/higher are strict (< / >).

go deeper

for a junior

Knows TreeMap can find the nearest key and that there are floor/ceiling-style methods.

for a middle

Correctly states inclusive vs strict semantics for all four lookups and the Key vs Entry/null behaviour.

for a senior

Adds poll/descending/endpoint methods, the firstKey-throws-vs-firstEntry-returns-null gotcha, and concrete use cases like as-of queries.

for a principal

Designs APIs/algorithms on these primitives (interval trees, scheduling, versioned lookups) and reasons about view semantics and concurrency.

## Why NavigableMap exists Because TreeMap keeps keys **sorted**, it can answer questions an unordered map cannot: 'what is the nearest key at or below 50?' or 'give me every entry between 10 and 20'. These live on the **NavigableMap** interface (which extends SortedMap), and TreeMap implements them all in **O(log n)** by descending its balanced tree. ## The four relative lookups Given a query key `k`, picture the sorted keys on a number line: - **floorKey(k)** → the **greatest key ≤ k** ('floor' = round down, *inclusive*). For keys {10,20,30}, floorKey(25)=20, floorKey(20)=20. - **ceilingKey(k)** → the **least key ≥ k** ('ceiling' = round up, *inclusive*). ceilingKey(25)=30, ceilingKey(20)=20. - **lowerKey(k)** → the **greatest key strictly < k** (*exclusive*). lowerKey(20)=10. - **higherKey(k)** → the **least key strictly > k** (*exclusive*). higherKey(20)=30. The distinction is inclusivity: **floor/ceiling include k itself; lower/higher exclude it.** ## Key form vs Entry form Each lookup has two variants: - `floorKey(k)` returns the **key** (or null). - `floorEntry(k)` returns the whole **Map.Entry** (key + value) (or null). Use the Entry form when you also need the value; the Key form when you only need the key. **Both return null when no matching key exists** — e.g. lowerKey(10) on {10,20,30} is null because nothing is strictly below 10. ## Endpoint and poll methods - `firstEntry()` / `lastEntry()` — smallest / largest entry (null if empty). - `firstKey()` / `lastKey()` (from SortedMap) — but these **throw NoSuchElementException** when empty, unlike firstEntry/lastEntry which return null. (A common gotcha.) - `pollFirstEntry()` / `pollLastEntry()` — return **and remove** the smallest/largest entry; great for priority-queue-like draining. ## Reverse views - `descendingMap()` — a view of the same map with reversed ordering. - `descendingKeySet()` / `navigableKeySet()` — navigable key-set views. These are **views**, not copies: changes write through to the backing map. ## Range views (covered more in subMap/headMap/tailMap) `headMap(k, inclusive)`, `tailMap(k, inclusive)`, `subMap(from, fromIncl, to, toIncl)` return sorted sub-views with explicit endpoint inclusivity. ## Mental model Think of the keys as a ruler. floor/ceiling snap **to-or-toward** k inclusively; lower/higher step **past** k exclusively. All of these are why people reach for TreeMap: time-series 'value as of timestamp T' (floorEntry), autocomplete ranges (subMap), nearest-match lookups.

  • On a TreeMap with keys {10,20,30}, what do floorKey(20) and lowerKey(20) return?
    floorKey(20)=20 (inclusive, ≤), lowerKey(20)=10 (strict, <).
  • What is a real use case for floorEntry?
    Time-series 'as-of' lookups: a TreeMap keyed by timestamp, floorEntry(t) gives the most recent record at or before time t.

saying these in an interview costs you the question

  • Swapping inclusive (floor/ceiling) with strict (lower/higher)
  • Thinking floorKey throws when absent (it returns null)
  • Confusing floorEntry returning null with firstKey throwing NoSuchElementException
  • Assuming these methods are O(n)

context

resolving links…