Hash Maps & Data-Structure Design

Palantir engineers spend their days turning heterogeneous, half-clean data into something an analyst or a field operator can query in one keystroke. So it is no surprise that the coding rounds keep circling back to the same reflex: given a pile of records and a question about them, build the structure that answers the question fast. Sometimes that is a bare hash map keyed the right way. Sometimes it is a small system you assemble live. Think of an index over integrated records, a cache in front of an expensive join, a limiter guarding a downstream feed, or a store that can roll a bad write back. Either way the round is checking whether you can name the right structure and keep its invariant honest while an interviewer keeps changing the question.

These problems run in a real editor, and the code executes. A structure that looks right on the whiteboard but drops an eviction or double-counts a rollback fails a hidden case in front of you. What separates a strong showing from a passing one is rarely the trick. It is clean operations with tight names, edge cases handled before you are asked, and a base design that bends when the interviewer piles on a constraint two thirds of the way through. That last move is the Palantir tell, and every problem below is built to rehearse it.

How Palantir frames it

Two shapes recur. The first is a hash-map algorithm dressed in a data story: aggregate events into a per-key total, group records by a property, dedup accounts that net to zero. You have already seen that family in the arrays and hashing lesson, where the portfolio and transaction problems live. The second shape, small data-structure design, is the one this lesson owns. The prompt hands you an interface (get, put, allow, commit) and asks you to build the thing behind it. Every operation must be fast and correct, and the prompt extends once you have a working version.

The design prompts lean toward the operational flavor of the platforms. An index is what makes the Ontology feel instant when an analyst filters objects by property. A cache sits in front of a resolved-entity lookup that would otherwise re-run a heavy join on a deployment. A rate limiter fronts an API a Foundry pipeline exposes to a customer's own systems. A transactional store mirrors how datasets get written atomically, so a failed pipeline run leaves no half-applied garbage behind. You do not need to know the products to solve these. Still, the framing is not decoration. The interviewer's escalation usually pushes toward the messy reality those products live in.

The design toolkit

Almost every small design here is a hash map paired with one auxiliary structure that gives an operation its speed. Learn the four pairings below. Most prompts then resolve to picking one and keeping it in sync.

Asked at Palantir

Four problems, in the order they tend to escalate. Build each base version so it runs and passes your own quick asserts, then reveal the walkthrough and work the follow-up, because the follow-up is where these rounds are decided.

1

LRU Cache: O(1) Get and Put

MediumFrequently asked

Problem

Build a cache with a fixed capacity that evicts the least recently used entry when it is full.

- get(key) returns the value for key, or -1 if it is absent. A successful get counts as a use.
- put(key, value) inserts or updates the entry and counts as a use. If inserting a new key would exceed capacity, evict the least recently used entry first.

Both operations must run in O(1).

Input: cap = 2 put(1,1); put(2,2); get(1); put(3,3); get(2)

Output: get(1)=1, get(2)=-1

put(3,3) runs while the cache holds {1,2} and 1 was used more recently than 2, so 2 is evicted and get(2) misses.

How this uses the pattern

Hash map plus doubly-linked list. The map gives O(1) key lookup to a node. The list keeps nodes in recency order with sentinels at both ends, so moving a node to the front and evicting from the back are both O(1).

LRU Cache: O(1) Get and Put

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["LRUCache",[2]],["put",[1,1]],["put",[2,2]],["get",[1]],["put",[3,3]],["get",[2]],["get",[3]]]Expected: [null,null,null,1,null,-1,3]

Input: [["LRUCache",[2]],["put",[1,1]],["put",[2,2]],["put",[1,10]],["put",[3,3]],["get",[2]],["get",[1]],["get",[3]]]Expected: [null,null,null,null,null,-1,10,3]

Need a hint? (3 available)

The Palantir angle

On a live deployment, resolving an entity or a permission can mean re-running an expensive join. A small cache in front of that lookup is the difference between a snappy screen and a stalled one, and the least-recently-used policy is what keeps hot objects resident. Interviewers like this one for the O(1) constraint. It rules out scanning for the oldest entry and forces the map-plus-list design. Then the question is whether you keep two structures in lockstep without leaking a node.

Take it further

A common Palantir twist is staleness. Cached data can go out of date, so entries carry an expiry, and an expired entry reads as a miss even before it is evicted. That threads a time argument through get and lazily drops stale nodes, worked through below.

Show solution & walkthrough

2

In-Memory Store: Nested Transactions

MediumCommonly asked

Problem

Build an in-memory key-value store with transactions.

- set(key, value) and get(key) (returns the value or None) and delete(key).
- begin() opens a transaction; transactions can nest.
- rollback() discards every change made since the most recent begin(), restoring the exact prior state.
- commit() finalizes the most recent transaction. If it is nested inside another, its changes become part of the enclosing transaction (so an outer rollback still undoes them); if it is the outermost, they become permanent.

Input: set("a",1); begin(); set("a",2); get("a"); rollback(); get("a")

Output: 2 then 1

Inside the transaction a reads as 2; rollback restores the value a held when begin() ran, so it reads 1 again.

Input: begin(); set("b",5); begin(); set("b",9); rollback(); get("b")

Output: 5

The inner rollback undoes only set("b",9), leaving the value 5 set in the outer transaction.

How this uses the pattern

Base map plus a stack of undo logs. Writes apply to the live map at once; each open transaction records the pre-write value of any key it touches, so rollback restores those values and commit folds them into the parent log.

In-Memory Store: Nested Transactions

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["KVStore",[]],["set",["a",1]],["begin",[]],["set",["a",2]],["get",["a"]],["rollback",[]],["get",["a"]]]Expected: [null,null,null,null,2,null,1]

Input: [["KVStore",[]],["begin",[]],["set",["b",5]],["begin",[]],["set",["b",9]],["rollback",[]],["get",["b"]],["commit",[]],["get",["b"]]]Expected: [null,null,null,null,null,null,5,null,5]

Input: [["KVStore",[]],["set",["a",1]],["delete",["a"]],["get",["a"]]]Expected: [null,null,null,null]

Need a hint? (3 available)

The Palantir angle

Foundry writes datasets transactionally, so a pipeline run that fails partway leaves no half-applied state behind. This problem shrinks that idea to a key-value store, and nested transactions are the test. Snapshotting the whole map on begin works but costs O(n) per begin. An undo log per transaction is O(1) per begin and O(changes) per rollback. Interviewers escalate straight into nesting to see whether your commit correctly hands changes up to the enclosing transaction instead of making them permanent too early.

Take it further

A frequent extension asks for count(value), the number of keys currently mapped to a given value, in O(1). That needs a reverse index maintained on every write, including the writes a rollback performs, which is a clean lesson in routing all mutations through one place. Worked below.

Show solution & walkthrough

3

Entity Index: Inverted Hash Map

MediumSometimes asked

Problem

You are integrating records from several source systems into one searchable set of entities. Each entity has a string id and a set of properties, given as a map of field to value (for example {"dept": "eng", "site": "denver"}).

Build an EntityIndex that supports:

- add(entity_id, props) registers an entity and its properties.
- find(field, value) returns the ids of every entity whose field equals value, sorted, or an empty list if none match.

A plain scan of all entities per query is too slow once the set is large, so build the lookup structure up front.

Input: add("emp_1", {"dept": "eng", "site": "denver"}) add("emp_2", {"dept": "eng", "site": "nyc"}) add("emp_3", {"dept": "ops", "site": "denver"}) find("dept", "eng")

Output: ["emp_1", "emp_2"]

Both emp_1 and emp_2 sit in the eng department, so the field-to-value index returns them in sorted order.

Input: find("dept", "legal")

Output: []

No entity carries dept=legal, so the lookup misses cleanly and returns an empty list.

How this uses the pattern

Nested map. Keep a map from field to (a map from value to a set of entity ids). add() drops the id into each field-value bucket. find() is one set lookup, sorted.

Entity Index: Inverted Hash Map

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["EntityIndex",[]],["add",["emp_1",{"dept":"eng","site":"denver"}]],["add",["emp_2",{"dept":"eng","site":"nyc"}]],["add",["emp_3",{"dept":"ops","site":"denver"}]],["find",["dept","eng"]]]Expected: [null,null,null,null,["emp_1","emp_2"]]

Input: [["EntityIndex",[]],["add",["emp_1",{"dept":"eng","site":"denver"}]],["add",["emp_2",{"dept":"eng","site":"nyc"}]],["add",["emp_3",{"dept":"ops","site":"denver"}]],["find",["site","denver"]]]Expected: [null,null,null,null,["emp_1","emp_3"]]

Input: [["EntityIndex",[]],["add",["emp_1",{"dept":"eng","site":"denver"}]],["add",["emp_2",{"dept":"eng","site":"nyc"}]],["add",["emp_3",{"dept":"ops","site":"denver"}]],["find",["dept","legal"]]]Expected: [null,null,null,null,[]]

Need a hint? (3 available)

The Palantir angle

This is the shape behind an Ontology filter feeling instant: an analyst narrows objects by a property and expects the matches immediately, not after a full table scan. The signal is whether you build the index on write so reads are cheap, rather than scanning on every query. Interviewers here care about the empty-match case and about a deterministic sorted result, since flaky output order is exactly the kind of thing a reviewer would flag on a real deployment.

Take it further

The near-universal extension is a multi-field query: return the ids that match every field-value pair at once, an AND across predicates. It falls out of the same index if you intersect the matching sets, and intersecting the smallest set first keeps it fast. That is worked through in full below.

Show solution & walkthrough

4

Rate Limiter: Sliding Window

MediumSometimes asked

Problem

Build a per-client rate limiter. Configure it with max_requests and a window_seconds length. Then:

- allow(client_id, timestamp) returns True if this client may make a request at timestamp, and False otherwise. Timestamps for a given client arrive in non-decreasing order.

A request is allowed only if the client has made fewer than max_requests in the trailing window, meaning the interval covering the most recent window_seconds up to and including timestamp. An allowed request counts against the window.

Input: max=3, window=10 allow(c,1); allow(c,2); allow(c,3); allow(c,4)

Output: True, True, True, False

The first three requests fit; at t=4 the window [−6,4] still holds all three, so a fourth is denied.

Input: allow(c,11)

Output: True

At t=11 the window is (1,11], so the request at t=1 has aged out; only 2 and 3 remain, leaving room.

How this uses the pattern

Hash map plus per-client queue. Keep a deque of allowed timestamps per client. On each call, pop timestamps that have aged out of the front, then allow only if the remaining count is below the max.

Rate Limiter: Sliding Window

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["RateLimiter",[3,10]],["allow",["c",1]],["allow",["c",2]],["allow",["c",3]],["allow",["c",4]],["allow",["c",11]]]Expected: [null,true,true,true,false,true]

Input: [["RateLimiter",[3,10]],["allow",["c",1]],["allow",["c",2]],["allow",["c",3]],["allow",["c",4]],["allow",["d",5]]]Expected: [null,true,true,true,false,true]

Need a hint? (3 available)

The Palantir angle

A Foundry pipeline often exposes an endpoint that a customer's own systems call, and that endpoint fronts data that must not be hammered. A rate limiter is the guard, and the per-client sliding window is the honest version of it, since a fixed calendar window lets a client fire a double burst across the boundary. The thing interviewers watch for is the window boundary: whether a request exactly window_seconds old is in or out, and whether you drop aged entries before you count rather than after.

Take it further

The sliding-window log is correct but stores a timestamp per request, which is heavy for a chatty client. The token-bucket variant holds O(1) state per client (a token count and a last-refill time) while still smoothing bursts, and it is the design worth reaching for at scale. Worked below.

Show solution & walkthrough

Before you move on

The four structures share a spine: a hash map for O(1) lookup, plus one companion that gives an operation its guarantee, kept in sync by hand. Name the invariant. Do the bookkeeping on write. Then the escalation the interviewer is holding usually reduces to threading one more field through the same operations. That is the muscle these rounds test, and it is the same one an FDE uses to stand up a working tool over a customer's data on day one.