Palantir Interview Questions

Given a collection of intervals, merge all overlapping ones. The standard approach sorts intervals by start time, then does a single linear pass, extending the current merged interval whenever the next one overlaps and starting a new one otherwise. It's a foundational interval problem that shows up across many companies because interval merging underlies a large family of harder scheduling and calendar-style questions.

A grid graph-traversal problem: count connected components of '1' cells using DFS, BFS, or Union-Find, being careful with boundary checks and marking visited cells so you don't recount. It's one of the most common entry points into grid-based graph problems and is often used as a warm-up before harder multi-source or Union-Find variants. The core signal is whether a candidate can translate a 2D grid into an implicit graph and correctly implement flood-fill without off-by-one or infinite-loop bugs.

A design problem requiring O(1) get and put operations with least-recently-used eviction, implemented by combining a hash map (for O(1) lookup) with a doubly linked list (for O(1) reordering and eviction from either end). This exact structure underlies real inference key-value caches — it's reportedly one of the most frequently asked design questions at companies building LLM inference systems, since eviction policy for a bounded cache maps directly onto managing GPU memory for attention KV caches. It's a strong test of whether a candidate can compose two data structures to get O(1) across every required operation, not just some of them.

Given prerequisite pairs, this problem asks whether all courses can be finished, which is equivalent to detecting a cycle in a directed graph. Candidates typically solve it with Kahn's algorithm (in-degree tracking and a queue) for topological sort, or with DFS using a three-color (unvisited/visiting/visited) scheme to catch back edges. It tests fundamental graph modeling skills — representing prerequisites as an adjacency list and correctly distinguishing cycle detection from simple reachability.

A classic topological-sort problem: given courses and prerequisite pairs, return a valid ordering (or detect that no valid ordering exists due to a cycle). It tests whether a candidate can build an adjacency list, track in-degrees, and run Kahn's BFS algorithm (or DFS with visited/in-progress marking) to order and cycle-detect simultaneously. Its broad company reach reflects how often real systems need this exact shape of problem — resolving build or package dependency order, or task scheduling graphs — making it a reliable signal for graph traversal fluency.

For every node in a directed acyclic graph, find all nodes that can reach it — solved either by running a DFS/BFS from each node and recording reachable descendants, or by iterating nodes in topological order and propagating ancestor sets forward. The DAG structure (no cycles) is what makes propagation-based approaches valid, and recognizing that is central to an efficient solution rather than repeated per-node traversals. It's a solid test of graph reachability reasoning at a data-heavy company like Palantir, where modeling entity relationships as graphs is a common real-world pattern.

Merging k sorted linked lists efficiently requires either a min-heap holding the current head of each list (repeatedly popping the smallest and pushing its successor) or a divide-and-conquer pairwise merge, both achieving O(N log k). It tests whether a candidate can extend the two-list merge pattern to k lists and reason about the resulting complexity rather than defaulting to an O(Nk) linear scan across lists. Correct pointer management across multiple linked lists under time pressure is the practical difficulty.

Given an elevation map, compute how much water it can trap after rain — the water trapped at each index equals the shorter of the tallest bars to its left and right, minus its own height. It's solvable with two pointers in O(1) extra space, with a monotonic stack, or with two precomputed max-prefix/max-suffix arrays, making it a great vehicle for comparing multiple valid techniques in one interview. Its breadth of companies asking it reflects that it's one of the most widely used checks of two-pointer/array reasoning in the entire interview circuit.

Implement regular expression matching supporting `.` (any single character) and `*` (zero or more of the preceding element) against a full string. The standard solution is a 2D dynamic program over (string index, pattern index), where the transition for `*` requires considering both 'match zero occurrences' and 'match one more occurrence' cases. It's widely regarded as one of the trickier string DP problems because the `*` transitions are easy to get subtly wrong, making it a good test of precise DP formulation under pressure.

A straightforward hash-map and string-parsing problem: given a list of 'count subdomain' pairs, split each domain into all of its subdomain suffixes (e.g., 'a.b.c' contributes to 'a.b.c', 'b.c', and 'c') and accumulate visit counts for each. The main trap is correctly parsing the count prefix and generating every valid suffix without off-by-one errors around the dot boundaries. It's a low-complexity but detail-sensitive problem, useful for checking careful string handling rather than algorithmic depth.

Among n people, a "celebrity" is someone everyone else knows but who knows no one else; you're only given a knows(a, b) API and must identify the celebrity (or determine none exists) using as few calls as possible. The efficient solution does a single elimination pass to find one candidate (if a knows b, a can't be the celebrity, so move on; otherwise b can't be), then verifies that candidate against everyone else in a second pass, achieving O(n) calls instead of the naive O(n^2). It's a strong signal for recognizing an elimination-based linear-time approach over a brute-force pairwise check.

Given a sequence of integers representing bytes, determine whether they form a valid UTF-8 encoding by checking the leading-bit pattern of each byte against UTF-8's rules for 1-to-4-byte characters (continuation bytes must start with '10', and the leading byte's high bits declare how many continuation bytes follow). It's fundamentally a bit-manipulation and state-tracking problem, testing whether a candidate can translate a real encoding specification into precise bitwise checks rather than hardcoding special cases sloppily. This kind of low-level protocol/format validation fits naturally into an infrastructure-leaning interview loop like Palantir's.

Given an array of heights, find two lines that, together with the x-axis, form the container holding the most water. The optimal solution uses two pointers starting from both ends, always moving the pointer at the shorter line inward (since moving the taller one can never increase the area), tracking the best area seen. It tests two-pointer greedy reasoning and, more importantly, whether a candidate can articulate why the greedy move is provably safe rather than just applying it by rote.

A grid flood-fill problem: for each unvisited land cell, run DFS or BFS to measure the connected island's size and track the maximum across all islands. It's a direct, well-known application of grid traversal with visited-tracking, generally used as an accessible warm-up to confirm a candidate can implement flood fill cleanly (including edge and boundary handling) before moving to a harder graph or DP follow-up.

Convert a non-negative integer into its English words representation (e.g. 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"). The approach breaks the number into groups of three digits, converts each group using lookup tables for ones/teens/tens and hundreds, then appends the appropriate scale word (thousand, million, billion) per group. It's not algorithmically deep, but it's implementation-heavy with many easy-to-miss edge cases (zero, teens, trailing zero groups), making it a good test of careful, methodical coding under a large but mechanical spec.

Given a list of time points in HH:MM format, find the minimum difference in minutes between any two of them, accounting for the wraparound from 23:59 back to 00:00. The efficient approach converts each time to minutes-since-midnight, sorts them, checks adjacent differences, and separately checks the wraparound gap between the largest and smallest value. It's a compact test of whether a candidate spots the sort-then-scan-adjacent pattern and remembers the circular edge case, rather than comparing every pair.

A foundational grid-traversal problem: starting from a given cell, recolor every connected cell of the same original color using DFS or BFS, analogous to the paint-bucket tool in image editors. It's usually a warm-up used to confirm a candidate can correctly implement grid traversal with visited-state tracking and boundary checks before moving on to harder graph or matrix problems in the same interview.

A shortest-path problem with an added constraint on the number of edges (stops) used: the standard approaches are a bounded Bellman-Ford (relax all edges K+1 times) or a modified Dijkstra/BFS that tracks both cost and stop count as part of the search state. It tests whether a candidate understands why plain Dijkstra can fail here (it doesn't account for the stop limit) and can adapt a shortest-path algorithm to a secondary constraint — a pattern that generalizes to real routing and logistics problems.

Word Ladder models words as nodes in an implicit graph, connecting two words if they differ by exactly one letter, and asks for the shortest transformation sequence from a start word to an end word via BFS. Because the graph isn't given explicitly, candidates must generate neighboring words on the fly (e.g., by trying all 26 letter substitutions at each position) and use a word dictionary/set for O(1) membership checks and visited tracking. Its practical relevance in interviews often ties to NLP transformations — reasoning about minimal edit-style paths between text tokens — which is one reason it recurs in ML-adjacent interview loops.

This asks for the maximum profit from a single buy and sell of one share, given a sequence of daily prices. The optimal solution is a single pass that tracks the minimum price seen so far and the best profit achievable by selling at the current price. Despite being an easy problem, it's a useful check for whether a candidate defaults to an unnecessary O(n^2) pairwise comparison or immediately sees the one-pass greedy/DP formulation.