Real Interview Questions for the Software Engineer at Apple
NewInterview Q&A
Q&A-1Design and implement an LRU cache with O(1) get and put operations?
Reported in Apple Software Engineer interview: timing, circuits, and coding ...
The 90-second answer
Two structures, one invariant. A hash map from key to node gives O(1) lookup; a doubly linked list threaded through those same nodes holds recency order, most-recently-used at the head. get finds the node, splices it to the head, returns its value. put either updates an existing node (splice to head) or inserts a new node at the head and, when the map is already at capacity, unlinks the node just before the tail sentinel and drops its map entry. Every operation touches a constant number of pointers, so both are O(1) worst case, not amortised.
Sentinels are worth the two extra nodes: a dummy head and tail mean insert and remove never branch on nil, which is where most of the bugs in this question live.
swift // Swift 5.9 final class LRUCache { private final class Node { let key: Int var value: Int var prev: Node? var next: Node? init(key: Int, value: Int) { self.key = key; self.value = value } }
private let capacity: Int
private var map: [Int: Node] = [:]
private let head = Node(key: 0, value: 0) // MRU side
private let tail = Node(key: 0, value: 0) // LRU side
init(capacity: Int) {
self.capacity = capacity
head.next = tail
tail.prev = head
}
func get(_ key: Int) -> Int {
guard let node = map[key] else { return -1 }
moveToFront(node)
return node.value
}
func put(_ key: Int, _ value: Int) {
if let node = map[key] { // update: no eviction
node.value = value
moveToFront(node)
return
}
guard capacity > 0 else { return }
if map.count == capacity, let lru = tail.prev, lru !== head {
remove(lru)
map[lru.key] = nil
}
let node = Node(key: key, value: value)
map[key] = node
insertAtFront(node)
}
private func insertAtFront(_ n: Node) {
n.next = head.next
n.prev = head
head.next?.prev = n
head.next = n
}
private func remove(_ n: Node) {
n.prev?.next = n.next
n.next?.prev = n.prev
}
private func moveToFront(_ n: Node) { remove(n); insertAtFront(n) }
}
Trace, capacity 2
| Call | Map keys after | List, MRU → LRU | Returns |
|---|---|---|---|
put(1,1) | 1 | 1 | — |
put(2,2) | 1,2 | 2,1 | — |
get(1) | 1,2 | 1,2 | 1 |
put(3,3) | 1,3 | 3,1 | — (evicts 2) |
get(2) | 1,3 | 1,3 | -1 |
put(1,10) | 1,3 | 1,3 | — (update, no evict) |
get(1) | 1,3 | 1,3 | 10 |
What the interviewer will push on
getmust refresh recency. The classic bug is agetthat returns the value without splicing the node forward; the cache then evicts a key that was just read. The trace above fails at row 4 if you skip it.- Updating an existing key must not evict. Check the map before the capacity check, as above.
- Capacity 0 and 1. With capacity 0,
putis a no-op andgetalways misses; thelru !== headguard keeps a one-element cache from unlinking a sentinel. - Thread safety. A single
os_unfair_lockorNSLockaround both methods is correct but serialises every read. If reads dominate, shard byhash(key) % Ninto N independent LRUs: you lose global LRU order but keep O(1) and cut contention N-fold. Apple'sNSCacheis thread-safe and evicts under memory pressure, but it does not promise LRU order, so it is not an answer to this question. - Language shortcuts. Java's
LinkedHashMapwithaccessOrder=trueplus aremoveEldestEntryoverride, and Python'sOrderedDictwithmove_to_end(k)/popitem(last=False), are both O(1) and worth naming, then say you'd write the list yourself if the interviewer wants to see the pointer work. - If they ask for a cheaper read path, CLOCK/second-chance approximates LRU with a reference bit and no list mutation on
get; it's what real buffer caches use when the lock is the bottleneck. Say what you give up: exact LRU ordering. In production code,getshould returnInt?rather than the-1sentinel the LeetCode contract forces.
Curated: · Written: · Reviewed:
Q&A-2Implement string compression.
Reported in Apple Software Engineer interview: timing, circuits, and coding ...
The 90-second answer
Pin down three things first, because each one changes the code: what unit I'm counting (Swift Character, Unicode scalar, or UTF-8 byte), whether the function must return the compressed form even when it's longer, and whether I get to allocate a new string or must edit a buffer in place. I'll assume run-length encoding over Characters, return the original when compression doesn't shrink it, and allocate.
swift // Swift 5.9 func compress(_ s: String) -> String { guard let first = s.first else { return s } var out = "" out.reserveCapacity(s.count) var outCount = 0 // String.count is O(n); don't recount per append var runChar = first var runLen = 0 for c in s { if c == runChar { runLen += 1 } else { let piece = "(runChar)(runLen)" out += piece; outCount += piece.count runChar = c; runLen = 1 } } let piece = "(runChar)(runLen)" out += piece; outCount += piece.count return outCount < s.count ? out : s }
for c in s walks grapheme clusters once, O(n), and reserveCapacity keeps the appends amortised O(1). Total O(n) time, O(n) space for the output.
| input | compressed | lengths | returned |
|---|---|---|---|
aabcccccaaa | a2b1c5a3 | 10 < 11 | a2b1c5a3 |
abc | a1b1c1 | 6 > 3 | abc |
11 × a | a11 | 3 < 11 | a11 |
"" | — | — | "" |
Worst case is 2n for a string with no repeats, which is why the length check is part of the contract, not an optimisation.
What the interviewer will push on
Don't build what you throw away. The version above allocates up to 2n characters before deciding to return the original. A two-pass version counts the compressed length first (same O(n) walk, no allocation) and returns s immediately if the count is ≥ s.count. On a 100 MB input that's the difference between ~200 MB of transient allocation and none.
Unicode. Character is a grapheme cluster, so "🇺🇸🇺🇸" is two characters and compresses to "🇺🇸2", while "e\u{301}e\u{301}" is also two characters (each two scalars) and compresses to "é2": 2 characters, not smaller, so the original comes back. Iterating unicodeScalars or utf8 instead gives different and sometimes invalid output: splitting a ZWJ family emoji or a combining sequence mid-cluster produces bytes that no longer render. Decide the unit and say so; for a wire format I'd compress UTF-8 bytes and document that the result is bytes, not text.
In place. If the signature is a mutable buffer (C, NSMutableData, UnsafeMutableBufferPointer<UInt8>), the two-pointer trick (read index, write index) only works after you've verified the compressed length fits. Otherwise the write pointer overtakes the read pointer and corrupts input you haven't read yet. Verify first, then write.
Failure modes I'd name. Peak memory doubling on large inputs (stream in 64 KB chunks to an OutputStream instead); run counts past one digit, which "\(runLen)" handles but a fixed two-bytes-per-run format would not; and callers who need the compressed form unconditionally: that's a separate function or a flag, because silently returning the input breaks a decoder that expects RLE.
Curated: · Written: · Reviewed:
Q&A-3Design the backend for iMessage, focusing on end-to-end encryption and multi-device synchronization.
Reported in Apple Software Engineer Interview Questions - JobMentis
The 90-second answer
Assume one Apple ID owns N devices, conversations are 1:1 and small groups, and the server must never hold plaintext or a key that decrypts it. That last constraint decides the whole architecture: encryption is per device, not per account, and the server is a store-and-forward queue of opaque blobs.
Each device generates its own long-term identity key (Curve25519) plus signed prekeys at setup and registers the public halves with a key directory. To send, Alice fetches Bob's current device list, runs an X3DH-style handshake against each device, and then a Double Ratchet per device for forward secrecy and post-compromise recovery. She encrypts the plaintext once per recipient device and once per own other device, so her Mac shows the sent message. The server routes ciphertext, pushes a wake-up through APNs, and stores undelivered blobs until the device reconnects.
| Component | Holds | Never holds |
|---|---|---|
| Key directory (IDS) | Apple ID → device identity keys, signed prekeys | private keys |
| Transparency log | append-only Merkle log of key-directory entries | — |
| Message queue | ciphertext per destination device, TTL | plaintext, session keys |
| APNs | device token, opaque queue id | message content |
| Client | ratchet state, plaintext | other devices' private keys |
Trace: Alice (2 devices) → Bob (3 devices)
- Alice's iPhone queries the directory, gets three device entries for Bob, each signed and chained to his account key, plus an inclusion proof from the transparency log.
- It derives a root key per device via X3DH, then encrypts: 3 ciphertexts for Bob's devices, 1 for Alice's Mac. Five blobs, one plaintext.
- Each blob is enqueued under the destination device's queue and an APNs push fires with only a queue id: no content in the payload, since push payloads traverse Apple infrastructure that shouldn't see message bodies.
- Bob's iPad is offline. The blob sits in its queue; on reconnect it fetches over TLS with device credentials and the ratchet's skipped-key window (bounded, say 1000 stored keys) handles out-of-order arrival.
- Bob replies from his iPhone. Alice's Mac decrypts because it had its own session all along.
Where the design actually gets hard
Fan-out cost. Per-device encryption is O(devices) per message. A 32-person group with 2 devices each is 64 encryptions per message: untenable. Use sender keys: each member distributes one symmetric sender key to every other device once (31 handshakes), then encrypts each message once and broadcasts. The trade-off is that sender keys give weaker post-compromise security: a leaked sender key exposes all future messages from that sender until rotation, so rotate on membership change and on a schedule.
New device. It has no ratchet history, so it cannot read old messages. Either accept "your history starts here" or back up the ratchet/keys encrypted under an iCloud Keychain-derived key. The backup widens the attack surface, a compromised account plus backup password yields history, so it's a product decision, not an engineering one, and it must be opt-in.
Malicious directory. The server could silently add a device to Bob's account and read everything. That's what the transparency log is for: devices check inclusion proofs, gossip signed tree heads, and Contact Key Verification lets two people compare a short code out of band. Without it, E2EE only protects against everyone except the operator.
Failure modes and detection
- Ratchet desync or replay: monotonic counters per session; reject reused counters; cap skipped-key storage so a forged high counter can't exhaust memory.
- Key change mid-conversation: re-handshake and surface a visible warning rather than silently continuing. A silent key swap is exactly the attack the log exists to catch.
- Server drops or delays: it can't read, but it can censor. Delivery receipts plus sequence gaps let the client show "not delivered" instead of pretending success.
- Undelivered backlog: bound the queue TTL (Apple's stated behaviour is roughly 30 days for undelivered messages) and expire blobs, or storage grows without limit for abandoned devices.
Curated: · Written: · Reviewed:
Q&A-4Design an iCloud Photo storage system to handle billions of high-resolution images with low latency for global users.
Reported in Apple Software Engineer Interview Questions - JobMentis
Clarify first. I'd confirm the shape: ~1B libraries, ~5k assets each, 2–3 MB HEIC originals, read:write around 1000:1, and thumbnails outnumbering full-res fetches roughly 50:1. Those ratios decide the design more than the word "billions" does.
The split. Two planes with different physics. Metadata is small, mutable, needs transactions and read-your-writes. Blobs are large, immutable, and want to be content-addressed and pushed to the edge. Image bytes never sit behind the metadata service.
| Plane | Holds | Store | Access path |
|---|---|---|---|
| Metadata | asset rows, albums, versions, change log | sharded on library_id, 3× replicated per region | app servers, strong per-library |
| Blob | originals + derivatives, immutable | object store, erasure-coded, 2+ regions | signed URL, client → store direct |
| Edge | 256 px thumbs, 1024 px previews | CDN, hash-named immutable URLs | 95%+ hit rate |
Upload. The client hashes the asset locally and calls POST /v1/libraries/{id}/assets with {sha256, bytes, captured_at}. If that hash is already in the library manifest, the server returns the existing asset_id and zero bytes move: re-imports, device restores and shared-album copies are free. Otherwise it returns a multipart session with 8 MiB parts presigned to the nearest PoP, and the client runs 4–6 parts in parallel. On completion the server verifies the hash, writes the metadata row and the change-log record in one transaction, then enqueues derivative generation.
Read. Grid scroll is one metadata call returning 200 rows with thumb_hash; the client pulls thumbnails straight from the edge. Full-screen gets a 5-minute signed URL to the regional blob store, so image bytes never traverse the app tier.
Hot-path arithmetic: 1B devices × 5 sessions/day × 20 thumbnails = 1e11 requests/day ≈ 1.2M/s average, 6M/s at 5× peak. At 30 KB per thumb that's ~180 GB/s: only a CDN makes that affordable. Edge hit is 15–30 ms p50; a miss costs 60–90 ms from the regional store. A 3 MB original on a 20 Mbps link is ~1.2 s, which is bandwidth, not architecture, so the win is making sure the first screen is thumbnails.
Sync. Each library is a single-writer log. Devices hold a change token and call GET /changes?since=<token>; the server returns ordered deltas. That's the CloudKit CKRecordZone change-token model, and it's what makes a photo appear on the iPad two seconds after the iPhone without polling the whole library.
Failure modes I'd plan for. A shared album with 10k members is a hot key: thumbnails are absorbed by the CDN, metadata reads go to replicas, writes are rate-limited per device. Abandoned multipart uploads get a 7-day abort lifecycle rule, and the client resumes by listing parts. Silent corruption is caught by per-part CRC32C on read plus a background scrubber. A regional outage fails metadata over in 30–60 s; blobs are already in a second region.
One thing I'd refuse. Cross-user dedup on plaintext hashes. It turns the upload endpoint into a confirmation-of-a-file oracle: send a hash, learn whether anyone in iCloud holds that photo. Dedup stays inside a library, or across users only on ciphertext under per-user keys.
Curated: · Written: · Reviewed:
Q&A-5Design a distributed rate limiter using a token bucket.
Reported in Two Phone Screens Then a Four-Round Onsite | Apple ...
The 90-second answer
Pin down three things before designing: the key (per Apple ID, per device, per IP, per endpoint), the budget (burst B and sustained rate r), and what the limiter does when its own backing store is unreachable. I'll assume per apple_id + endpoint, enforced at the edge, B = 100, r = 10/s, and that a false 429 on sign-in is worse than a brief overshoot, while on password-reset and 2FA-code endpoints the reverse is true.
A token bucket is two numbers per key: tokens and ts (last refill). Capacity B bounds the burst; rate r bounds the sustained rate. On each request: refill by (now - ts) * r, cap at B, take one token if tokens >= 1, else reject with Retry-After = (1 - tokens) / r.
The distributed part is not the algorithm, it's the atomicity. Bucket state lives in Redis and the read-modify-write runs as one Lua script, so two edge nodes can't both read tokens = 1 and both spend it. Use Redis's own clock inside the script: client clocks across PoPs skew by hundreds of milliseconds and that skew becomes free tokens.
lua -- KEYS[1] = rl:{apple_id}:{endpoint} ARGV = capacity, refill_per_sec, cost local t = redis.call('TIME') local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000) local cap = tonumber(ARGV[1]) local rate = tonumber(ARGV[2]) / 1000 -- tokens per ms local cost = tonumber(ARGV[3])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts') local tokens = tonumber(s[1]) or cap local ts = tonumber(s[2]) or now
tokens = math.min(cap, tokens + (now - ts) * rate) local allowed = 0 if tokens >= cost then tokens = tokens - cost allowed = 1 end redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now) redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate) + 1000) return {allowed, math.floor(tokens)}
Worked trace. B = 100, r = 10/s = 0.01 tokens/ms. A client syncs and fires 100 requests at t = 0: each takes a token, tokens goes 100 → 0, all allowed. At t = 200 ms five more arrive; refill is 200 × 0.01 = 2, so two are allowed and three get 429 with Retry-After: 100 ms. At t = 1 s the bucket holds 10 again. A fixed-window counter with the same budget would have allowed 100 at t = 999 ms and another 100 at t = 1001 ms: 200 in 2 ms. That boundary doubling is why token bucket, not fixed window.
Failure modes, and how you'd see them.
- Redis unreachable or over the 5 ms timeout. Fail-open with a local in-process bucket at 2× the global rate, so an outage degrades to per-node limiting instead of an outage. Fail-closed on credential endpoints. Detect via limiter error rate and the ratio of allowed-to-total on the local fallback.
- Hot key. One Apple ID at 50k rps pins a single Redis Cluster shard. Shard the bucket into 8 sub-buckets (
rl:{id}:0..7, each B/8, r/8), but that multiplies the achievable burst by 8, so apply it only to keys flagged hot, or lease tokens locally (below). - Retry storm. 429s without jitter resynchronise every client. Put the jitter in the SDK, not the server.
- Enumeration leak. Return the same 429 body for unknown Apple IDs as for real ones, or the limiter becomes an account-existence oracle.
At Apple's edge scale, the cross-region round trip (60–100 ms) is the real cost, not the arithmetic. Each edge node keeps a local bucket and leases a chunk, say 50 tokens every 200 ms, from Redis. Limiter latency drops to ~0; the price is up to 50 tokens of overshoot per node per window, which you size against the abuse budget rather than the happy path.
Curated: · Written: · Reviewed:
Q&A-6Implement a Hit Counter that records the time of each hit and returns how many hits occurred in the last 300 seconds.
Reported in Two Phone Screens Then a Four-Round Onsite | Apple ...
The 90-second answer
Two decisions drive this: exactness versus bounded memory, and which clock you read. For a server-side counter I default to a 300-slot ring buffer of per-second counts (O(1) memory, O(1) query, at most one second of error at each window edge) and I read a monotonic clock, not wall time, so an NTP step can't corrupt the window. If the interviewer needs exact answers and hit volume is modest, a deque of timestamps is the simpler correct thing.
python import threading, time
class HitCounter: WINDOW = 300
def __init__(self):
self._counts = [0] * self.WINDOW
self._stamps = [0] * self.WINDOW # which second each slot holds
self._lock = threading.Lock()
def hit(self, now=None):
t = int(now if now is not None else time.monotonic())
i = t % self.WINDOW
with self._lock:
if self._stamps[i] != t: # slot is stale, recycle it
self._stamps[i] = t
self._counts[i] = 0
self._counts[i] += 1
def query(self, now=None):
t = int(now if now is not None else time.monotonic())
lo = t - self.WINDOW + 1
with self._lock:
return sum(c for s, c in zip(self._stamps, self._counts) if lo <= s <= t)
Checked against Python 3.12. The _stamps array is what makes the ring safe: a slot is only valid if it still holds the second it was written for, so a bucket from 300 seconds ago is never mistaken for the current one. Query scans 300 slots: constant work, ~300 additions, nothing.
Trace. Hits at t=1000 (twice) and t=1050, then queries:
| t | action | slot | stamps[slot] | counts[slot] | query result |
|---|---|---|---|---|---|
| 1000 | hit | 100 | 1000 | 1 | — |
| 1000 | hit | 100 | 1000 | 2 | — |
| 1050 | hit | 150 | 1050 | 1 | — |
| 1050 | query | — | — | — | 3 (lo=751) |
| 1301 | query | — | — | — | 1 (lo=1002; slot 100 at 1000 is out) |
At t=1301 the two hits from 1000 are 301 s old and drop out; the hit at 1050 is 251 s old and stays. That's the whole mechanism.
Alternatives.
| Approach | hit | query | memory | exactness |
|---|---|---|---|---|
| deque of timestamps | O(1) amortized | O(k) evict | O(hits in window) | exact |
| 300-slot ring buffer | O(1) | O(300) | O(300) | ±1 s at edges |
| Redis sorted set | O(log n) | O(log n + m) | O(hits in window) | exact, shared |
| Redis per-second keys | O(1) | O(300) | O(300) | ±1 s, shared |
The deque is exact and dead simple: append the timestamp, and on query pop from the left while front < now - 300. It loses when traffic is bursty: 100k hits in 300 s is 100k timestamps, roughly 800 KB per counter, and you feel it at query time. The ring buffer caps memory at 300 ints regardless of rate.
Failure modes.
Clock. time.time() can jump backwards on an NTP correction; a hit stamped at 1000 then a query at 990 sees a negative window and returns garbage. time.monotonic() is per-process and never steps, which is why it's the default here. The cost: monotonic values aren't comparable across processes or machines, so the moment you shard the counter you need a shared time source.
Multiple processes. An in-memory counter behind a load balancer with 8 instances each reports 1/8 of the truth. Move to Redis: ZADD hits <ts> <id>, ZREMRANGEBYSCORE hits -inf <ts-300>, ZCARD hits. Exact and shared, but O(hits) memory. At high rate switch to INCR hits:<second> with a 300 s TTL and sum the 300 keys in a Lua script.
Lock contention. One mutex on every hit serializes all writers. At a few hundred k QPS that mutex is the bottleneck; stripe it (N counters each with its own lock, summed on query) or use per-thread counters flushed periodically.
Boundary precision. Second granularity means a hit at 1000.9 and a query at 1300.1 are treated as 1000 and 1300, so the answer can be off by one second's worth of hits at each edge. If the contract needs exact, use the deque or store millisecond timestamps.
Curated: · Written: · Reviewed:
Q&A-7Explain setup and hold timing in digital circuits.
Reported in Apple Software Engineer interview: timing, circuits, and coding ...
The 90-second answer
Both numbers describe the same flop, from opposite sides of the clock edge. Setup time is how long data must be stable before the capturing edge; hold time is how long it must stay stable after it. Violate setup and the flop may not have resolved its input in time. Violate hold and the flop captures the next value, because the input moved while the flop was still deciding.
For a launch flop A and a capture flop B one clock period apart:
- Setup:
T_clk + t_skew >= t_cq + t_comb_max + t_su - Hold:
t_cq + t_comb_min >= t_h + t_skew
where t_skew is capture clock arrival minus launch clock arrival. Setup is a max-delay check across one full cycle; hold is a min-delay check at the same edge.
Numbers
1 GHz clock (T = 1000 ps), 5 nm library, t_cq = 60 ps, t_su = 40 ps, t_h = 30 ps, skew +50 ps (capture clock arrives later):
| Path | t_comb (max/min) | Setup slack | Hold slack |
|---|---|---|---|
| typical | 700 / 120 ps | 1000+50-60-700-40 = +250 ps | 60+120-30-50 = +100 ps |
| long logic | 980 / 120 ps | -30 ps, violation | +100 ps |
| short logic | 700 / 0 ps | +250 ps | 60+0-30-50 = -20 ps, violation |
The asymmetry interviewers listen for: a hold violation does not care how fast the clock is. Drop to 100 MHz and the long path's setup slack becomes 10000+50-60-980-40 = +8970 ps, comfortably fine, while the short path still sits at -20 ps. Hold is fixed in the netlist (delay buffers on the short path, or less skew) never by slowing the clock. Setup is fixed by shortening the max path: retiming, pipelining, logic restructuring, upsizing, or deliberately skewing the capture clock later.
What a violation actually does
Setup violation leaves the input still moving at the edge; the output may settle to either value or go metastable and resolve after a probabilistic delay. Synchronizer MTBF scales as e^(t_res/tau) / (T_w * f_clk * f_data), which is why two flops buy orders of magnitude and a single flop is never acceptable across a clock domain. Hold violation is worse in one specific way: the flop deterministically captures the wrong value, so it can pass simulation and fail only on silicon at a fast corner.
Corners
Setup is worst at slow-slow, low voltage, high temperature: slow cells, long delays. Hold is worst at fast-fast, high voltage, low temperature: fast cells, short delays. Static timing analysis signs off both across the PVT matrix with on-chip variation derates; a design that closes setup at typical can still fail hold at fast.
Why this matters to a software engineer at Apple
Firmware reading a status register over a bus, or a driver touching a peripheral in another clock domain, sits on the other side of this. Two habits follow. Read a status register twice and compare, because one read can catch a multi-bit value mid-update. And never assume a register write is visible to another agent without the barrier or handshake the TRM specifies. Same physics, different layer.
Curated: · Written: · Reviewed:
Q&A-8Given a sorted array, where the distance between two numbers is defined as d = |a - b|, how do you find the Top K pairs with the smallest distance?
Reported in Two Phone Screens Then a Four-Round Onsite | Apple ...
The 90-second answer
Two clarifications before coding: the array is sorted ascending, and "pair" means any i < j, not just neighbours. That distinction decides the algorithm. If only adjacent pairs counted, you'd sort the n−1 gaps and take K, but for K > n−1 the true answer includes non-adjacent pairs. In [1,2,3] the three smallest pairs are (1,2)=1, (2,3)=1, (1,3)=2, and (1,3) is not adjacent.
The structure that makes it fast: fix the left index i. Because the array is sorted, a[i+1]-a[i] ≤ a[i+2]-a[i] ≤ …, so the pairs starting at i form a sorted list. There are n−1 such lists, and the K smallest pairs overall are the K smallest of their merge: a k-way merge with a heap of size n−1.
python import heapq
def top_k_pairs(a, k): n = len(a) if k <= 0 or n < 2: return [] heap = [(a[i+1] - a[i], i, i+1) for i in range(n - 1)] heapq.heapify(heap) # O(n) out = [] while heap and len(out) < k: d, i, j = heapq.heappop(heap) out.append((a[i], a[j], d)) if j + 1 < n: # advance this list only heapq.heappush(heap, (a[j+1] - a[i], i, j + 1)) return out
Trace on the reported input [1,2,4,7,11,16], K=5. Initial heap: (1,0,1), (2,1,2), (3,2,3), (4,3,4), (5,4,5).
| pop d | pair | push next in that list |
|---|---|---|
| 1 | (1,2) | 4−1 = 3 → (0,2) |
| 2 | (2,4) | 7−2 = 5 → (1,3) |
| 3 | (1,4) | 7−1 = 6 → (0,3) |
| 3 | (4,7) | 11−4 = 7 → (2,4) |
| 4 | (7,11) | 16−7 = 9 → (3,5) |
Result: (1,2,1), (2,4,2), (1,4,3), (4,7,3), (7,11,4). Ties break on (i,j) so the output is deterministic.
Cost: heapify O(n), then K pops and pushes at O(log n) each → O(n + K log n) time, O(n) space. For n = 10⁵ and K = 100 that is ~10⁵ + 1.7×10³ operations, against 5×10⁹ pairs if you enumerate.
Alternatives, and when to reach for them
Binary search on the distance D: count pairs with a[j]-a[i] ≤ D in O(n) with two pointers (advance i while the gap exceeds D, add j-i), binary search D over the value range, then collect. O(n log(max−min)): better when K is a large fraction of n², or when the real question is "all pairs within D". The heap wins for small K, which is the usual framing.
If the interviewer does mean adjacent pairs only, it collapses to sorted(gaps)[:K] in O(n log n), or a size-K heap in O(n log K).
Failure modes
- Assuming adjacency. This is the mistake the question is built to catch; state the assumption out loud before you code.
- K > n(n−1)/2. Clamp it or the loop drains the heap and silently returns fewer pairs: decide with the interviewer whether that is an error or a short return.
- Materialising all pairs first: 10⁵ elements is 5×10⁹ tuples, instant OOM.
- Duplicates give distance 0 and the heap handles them, but confirm tie order if the caller diffs output.
- In Swift or Java,
a[j] - a[i]on 32-bit ints overflows when values span the full range; widen to Int64.
Curated: · Written: · Reviewed:
Q&A-9Can you copy a linked list where each node has a next pointer and a random pointer that may point to any node in the list or to null, then get the extra space down to O(1)?
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
The 90-second answer
Two passes with a hash table is the version I'd write first: pass one creates a copy of every node keyed by the original, pass two wires next and random by lookup. That's O(n) time, O(n) space. The O(1) version drops the map by temporarily interleaving each copy directly after its original, so the original node itself is the lookup: orig.next is its copy, and orig.random.next is the copy's random.
java class Node { int val; Node next, random; Node(int v){val=v;} }
// O(n) space Node copyMap(Node head) { if (head == null) return null; Map<Node,Node> m = new HashMap<>(); for (Node c = head; c != null; c = c.next) m.put(c, new Node(c.val)); for (Node c = head; c != null; c = c.next) { m.get(c).next = m.get(c.next); // get(null) -> null m.get(c).random = m.get(c.random); } return m.get(head); }
// O(1) extra space Node copyWeave(Node c) { if (c == null) return null; for (Node p = c; p != null; p = p.next.next) { // 1: A -> A' -> B -> B' Node copy = new Node(p.val); copy.next = p.next; p.next = copy; } for (Node p = c; p != null; p = p.next.next) // 2: random pointers if (p.random != null) p.next.random = p.random.next;
Node head = c.next; // 3: unweave, restore input
for (Node p = c; p != null; p = p.next) {
Node copy = p.next;
p.next = copy.next;
copy.next = (copy.next != null) ? copy.next.next : null;
}
return head;
}
Trace on A(7) → B(13) → C(11) with A.random=C, B.random=A, C.random=C:
| After | List shape | Random wiring |
|---|---|---|
| pass 1 | A A' B B' C C' | none yet |
| pass 2 | unchanged | A'.random = A.random.next = C'; B'.random = A'; C'.random = C' |
| pass 3 | A B C and A' B' C' | A'.next=B', B'.next=C', C'.next=null |
Three linear passes, O(1) auxiliary space: the copies are the output, not overhead.
What the interviewer will push on
- The null check in pass 2 is not optional.
randomcan be null, andnull.nextthrows. Same for the last copy in pass 3:copy.next.nextdereferences null unless guarded. - The weave mutates the input. If the caller still holds the list, or another thread reads it, you've corrupted it for the duration. Pass 3 restores it, but an exception between passes 1 and 3 leaves the list interleaved. If the input is immutable or shared, the hash map is the correct answer and O(1) is off the table: say so rather than pretending.
- Identity, not equality.
HashMap<Node,Node>works becauseNodedoesn't overrideequals/hashCode. If it did, say two nodes with the samevalcompare equal, the map collapses distinct nodes into one copy and the output is silently wrong. Worth flagging; it survives a unit test built from distinct values. - Recursion is not O(1). A recursive copy is O(n) stack, which is worse than the map in practice: it blows the stack around 10k nodes on a default 512 KB–1 MB thread stack.
If they ask for a doubly linked list with random pointers, the same weave works; you just also fix prev in pass 3.
Curated: · Written: · Reviewed:
Q&A-10Convert a binary search tree in place into a sorted, circular doubly linked list.
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
The 90-second answer
In-place means no new nodes: reuse left as prev and right as next, and rewire during a single in-order traversal, because in-order on a BST yields sorted order. Keep two pointers (prev, the last node visited, and head, the first) and after the walk close the ring: tail.right = head, head.left = tail.
python
Python 3.11
class Node: slots = ("val", "left", "right") def init(self, v): self.val = v self.left = self.right = None
def flatten(root): if root is None: return None prev = head = None
def walk(node):
nonlocal prev, head
if node is None:
return
walk(node.left) # left subtree first
if prev is None:
head = node # smallest node becomes the head
else:
prev.right = node # prev.next = node
node.left = prev # node.prev = prev
prev = node
walk(node.right) # node.right is still intact here
walk(root)
prev.right = head # close the circle
head.left = prev
return head
The ordering inside walk is the whole trick. node.left is overwritten only after the left subtree is finished, and node.right is untouched until we recurse into it, so no child pointer is lost.
Trace on
4
/ \
2 5
/ \
1 3
In-order visits 1, 2, 3, 4, 5.
| visit | prev before | pointer writes |
|---|---|---|
| 1 | None | head = 1 |
| 2 | 1 | 1.right = 2, 2.left = 1 |
| 3 | 2 | 2.right = 3, 3.left = 2 |
| 4 | 3 | 3.right = 4, 4.left = 3 |
| 5 | 4 | 4.right = 5, 5.left = 4 |
| close | 5 | 5.right = 1, 1.left = 5 |
Result: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 1. Verify by walking right n times and checking you land back on head and the values are non-decreasing, then walk left n times.
Complexity and the space question
| Approach | Time | Aux space |
|---|---|---|
| Recursive in-order (above) | O(n) | O(h) call stack |
| Morris threading | O(n) | O(1) |
O(h) is fine for a balanced tree, log₂(10⁶) ≈ 20 frames, but a degenerate tree built from sorted inserts is a linked list already, and 10⁵ nodes blows Python's default 1000-frame limit with RecursionError. If the interviewer pushes on "in place", that's the follow-up they want: Morris traversal threads each node's in-order predecessor to its successor via the predecessor's right pointer, walks without a stack, and unthreads on the second visit. One ordering caveat when you merge it with the rewiring: clear the thread (pred.right = None) before you set node.left = prev, because the thread is how you find pred on the return trip.
Failure modes I'd name
- Forgetting the closing pair. You get a sorted doubly linked list, not a circular one; a test that walks
rightn+1 times segfaults or loops forever. Asserthead.left.right is head. - Returning
rootinstead ofhead. The caller wants the minimum node;rootis somewhere in the middle and itsleftnow points backwards. - Rewiring before recursing right. If you write
node.right = nextbefore descending, you lose the right subtree. Save it or reorder. - Single-node and empty trees.
root is NonereturnsNone; one node must self-link (n.right = n.left = n), which the close step handles only ifprevwas set: it is, sincehead = nodeandprev = node.
On Apple's side this pattern shows up where a sorted on-device index is built once and then iterated in both directions without a second allocation: the reason "in place" is in the question at all.
Curated: · Written: · Reviewed:
Q&A-11Given a binary tree, a target node, and a distance K, how do you return all nodes exactly K away from the target?
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
Two directions from the target: descendants at depth K, and nodes reached by walking up some number of ancestors and then down into a sibling subtree. The clean way to unify them is to treat the tree as an undirected graph: one pass to record each node's parent, then BFS from the target, stopping at depth K. O(n) time, O(n) space.
python
Python 3.11
from collections import deque
def distance_k(root, target, k): if root is None or k < 0: return [] parent = {} stack = [root] while stack: node = stack.pop() for child in (node.left, node.right): if child is not None: parent[child] = node stack.append(child)
seen = {target}
frontier = deque([(target, 0)])
out = []
while frontier:
node, d = frontier.popleft()
if d == k:
out.append(node)
continue # never expand past k
for nb in (node.left, node.right, parent.get(node)):
if nb is not None and nb not in seen:
seen.add(nb)
frontier.append((nb, d + 1))
return out
Trace. Tree [3,5,1,6,2,0,8,null,null,7,4], target 5, K = 2. Level 0: {5}. Level 1: 3 (parent), 6, 2. Level 2: from 3 → 1; from 6 → nothing new; from 2 → 7, 4. Result [1, 7, 4]. Note 3 is distance 1 and must not appear: the continue at d == k is what enforces that.
If the interviewer pushes back on memory. The parent map costs O(n) extra. A DFS that returns the distance from each node up to the target avoids it: dfs(node) returns -1 if the target isn't in that subtree, otherwise the distance. When the value equals K, emit the node; when it's d ≥ 0 and d < K, descend into the other child looking for nodes at K − d − 1. That's O(n) time and O(h) stack, which matters on a skewed tree: a 10M-node tree makes the dict roughly a gigabyte in CPython, while the recursion version holds only the path.
| Approach | Time | Extra space | When |
|---|---|---|---|
| Parent map + BFS | O(n) | O(n) | default; easiest to get right under pressure |
| DFS returning distance | O(n) | O(h) | memory-constrained, or tree is huge/skewed |
| BFS from target with existing parent pointers | O(n) | O(n) queue | tree already stores parents |
Failure modes I'd call out. Without the seen set, BFS bounces between a node and its parent forever. Without the depth cutoff, you return the whole tree. Python's default recursion limit is 1000, so a degenerate 100k-node chain blows the DFS version: convert to an explicit stack or raise the limit deliberately. And if the target may not be in the tree at all, the DFS variant detects it for free (root returns -1); the BFS version needs a separate containment check, otherwise it silently returns [], which is also the correct answer for a legitimate K beyond the tree's depth.
Curated: · Written: · Reviewed:
Q&A-12Write a function that determines whether two dates are exactly one month apart, within one month, or more than a month apart.
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
The 90-second answer
Four things to pin down first, because the spec is ambiguous and the interviewer is listening for whether you notice:
- Calendar month, not 30 days. "One month" is a civil-calendar concept. 30-day arithmetic is wrong for 7 of the 12 months.
- Absolute distance. Direction is a separate function; this one returns a three-way bucket.
- Date granularity in an explicit time zone. Two instants can be one month apart in UTC and not in Asia/Tokyo if they straddle local midnight. The function takes a
Calendar(which carries the zone): never.currentimplicitly. - End-of-month clamps. Jan 31 + 1 month = Feb 28, matching
Calendarandjava.time.
With those fixed, the problem collapses to one comparison: shift the earlier date forward by one calendar month and compare the later date against that boundary.
swift enum MonthGap { case withinOneMonth, exactlyOneMonth, moreThanOneMonth }
func monthGap(_ x: Date, _ y: Date, in calendar: Calendar) -> MonthGap { let (earlier, later) = x <= y ? (x, y) : (y, x) guard let boundary = calendar.date(byAdding: .month, value: 1, to: earlier) else { return .moreThanOneMonth // unreachable for real dates; defined, not a crash } switch calendar.compare(later, to: boundary, toGranularity: .day) { case .orderedSame: return .exactlyOneMonth case .orderedAscending: return .withinOneMonth case .orderedDescending: return .moreThanOneMonth } }
toGranularity: .day is what makes this a date question rather than an instant question: Jan 31 23:00 and Feb 28 01:00 land in the same bucket as Jan 31 09:00 and Feb 28 09:00. Note that identical dates return .withinOneMonth: zero elapsed is inside the boundary.
| a | b | result | why |
|---|---|---|---|
| Jan 15 | Feb 15 | exactly | boundary = Feb 15 |
| Jan 15 | Feb 14 | within | before boundary |
| Jan 15 | Feb 16 | more | after boundary |
| Jan 1 | Jan 31 | within | boundary Feb 1, not reached |
| Jan 31 | Feb 28 | exactly | clamped boundary |
| Jan 31 | Mar 1 | more | past Feb 28 |
| Feb 28 | Mar 31 | more | boundary Mar 28 |
| Jan 29 2024 | Feb 29 2024 | exactly | leap year |
| Jan 29 2023 | Feb 28 2023 | exactly | clamped |
Why not the obvious alternatives
(b - a) / 86_400 >= 30 fails twice: months run 28–31 days, and a DST day is 23 or 25 hours, so the divisor is not constant.
Completed-months arithmetic ((y2-y1)*12 + (m2-m1), decremented when b.day < a.day) answers a different question. Jan 1 to Feb 15 yields 1 completed month but is 45 days apart, which is more than a month. It counts whole months elapsed; it does not test the gap.
Without a date library, the same rule stated directly: exactly one month apart iff (b.y, b.m) is one calendar month after (a.y, a.m) and b.d == min(a.d, daysIn(b.y, b.m)). Same semantics, more code, more places to get leap years wrong.
Failure modes worth naming
- Implicit default calendar. A server in UTC and a user in Tokyo disagree about which bucket a 23:30 local timestamp falls in. Pass the zone in; make it a required parameter so callers cannot forget.
- Clamping is asymmetric. Jan 31 → Feb 28 is exactly one month, but Feb 28 → Mar 31 is more than one. If the product needs a symmetric relation, define it as "both directions satisfy the predicate", and accept that Jan 31/Feb 28 then fails. That is a product decision, not a code one; surface it rather than silently picking.
- Second-based arithmetic across DST. Never subtract timestamps and divide;
Calendarhandles the 23/25-hour days.
If the caller later needs "N months apart" generally, return the signed month count and let them bucket it, but the three-way predicate is what was asked, and it is one comparison.
Curated: · Written: · Reviewed:
Q&A-13Design cross-device wallpaper synchronization so a change on one device syncs to the user's other devices.
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
The 90-second answer
Pin the scope first: one iCloud account, N devices (iPhone, iPad, Mac, Watch), eventual consistency of seconds-to-a-minute is fine. The user expects the other device to be current by the time they pick it up. The decision that shapes everything: sync the choice, not the rendered pixels. A wallpaper is a source asset plus a per-device crop and focal point; each device renders its own rendition. That stops a 12 MP HEIC from being pushed to a Watch.
Split control plane from data plane. Control plane: one small CloudKit record per wallpaper slot in the user's private database. Data plane: the asset blob, stored once and addressed by content hash so re-selecting the same photo costs nothing.
| Field | Type | Why |
|---|---|---|
assetHash | String (SHA-256) | dedupe; content-addressed blob key |
assetRef | CKAsset | original bytes, uploaded once |
focalPoint | {x,y} | lets each device crop sensibly |
renditions | map deviceClass → cropRect | per-class overrides the user set |
version | Int64 | monotonic, server-bumped on save |
modifiedAt / modifiedBy | Date / String | ordering + audit; server clock only |
deleted | Bool | tombstone so deletes propagate |
The write path, traced
- iPhone picks a photo. Compute SHA-256; if
wallpapers/<hash>already exists in the blob store, skip upload. - Upload the asset, then save the record with
savePolicy = .ifServerRecordUnchanged: optimistic concurrency against the version the client last read. - CloudKit commits, bumps
modificationDate, and fires the zone subscription. - APNs silent push (
shouldSendContentAvailable) to the other devices. - Each device runs
CKFetchRecordZoneChangesOperationfrom its storedserverChangeToken, so a device that missed ten pushes catches up in one delta fetch. - If
versionis newer than local, download the asset (resumable, CDN-backed), render the local crop, crossfade. Write backappliedVersionfor telemetry only: never for ordering.
swift let op = CKModifyRecordsOperation(recordsToSave: [record]) op.savePolicy = .ifServerRecordUnchanged op.modifyRecordsResultBlock = { result in if case .failure(let e as CKError) = result, e.code == .serverRecordChanged { // server record wins on modifiedAt; push local into bounded history (5 deep) } }
Conflicts
Two devices edit offline. The second save gets CKError.serverRecordChanged. Resolve last-writer-wins on CloudKit's server modificationDate (never on device clocks, which skew by minutes) and keep the loser in a 5-entry history so "revert" is a real feature rather than an apology. If the losing device is the one in the user's hand, surface a non-blocking banner ("your iPad changed the wallpaper") instead of silently overwriting what they just chose.
Failure modes and how you see them
- Push dropped (offline, Low Power Mode, silent-push budget exhausted): the change-token fetch on next foreground reconciles. Symptom is a stale wallpaper until unlock, not data loss.
- Asset uploaded, record save failed: orphan blob. A 7-day TTL sweep on unreferenced hashes reclaims it.
- Record saved, asset 404 at the CDN: retry with exponential backoff, keep the last known good wallpaper on screen. Never blank to a default: that reads as a bug.
- Large asset on cellular: gate >5 MB behind Wi-Fi by default, with an explicit "sync now" affordance.
If the wallpaper is a personal photo, say where it is encrypted: CloudKit private DB is encrypted in transit and at rest, but Apple holds the keys unless the account has Advanced Data Protection enabled. That is the sentence an Apple interviewer will listen for.
Curated: · Written: · Reviewed:
Q&A-14Implement a producer-consumer queue.
The 90-second answer
A bounded blocking queue: a mutex, two condition variables, a deque, and a closed flag. Bounded because the bound is the backpressure: an unbounded queue turns overload into an OOM kill instead of a slow producer.
cpp // C++17 template <typename T> class BoundedQueue { public: explicit BoundedQueue(size_t cap) : cap_(cap) {}
bool push(T v) { // false once closed
std::unique_lock<std::mutex> lk(m_);
not_full_.wait(lk, [&]{ return closed_ || q_.size() < cap_; });
if (closed_) return false;
q_.push_back(std::move(v));
lk.unlock();
not_empty_.notify_one();
return true;
}
std::optional<T> pop() { // nullopt once closed and drained
std::unique_lock<std::mutex> lk(m_);
not_empty_.wait(lk, [&]{ return closed_ || !q_.empty(); });
if (q_.empty()) return std::nullopt;
T v = std::move(q_.front());
q_.pop_front();
lk.unlock();
not_full_.notify_one();
return v;
}
void close() {
{ std::lock_guard<std::mutex> lk(m_); closed_ = true; }
not_empty_.notify_all();
not_full_.notify_all();
}
private: std::mutex m_; std::condition_variable not_full_, not_empty_; std::deque<T> q_; size_t cap_; bool closed_ = false; };
Three details carry the correctness. The predicate lambda, because wait can return spuriously and because the condition must be re-checked under the lock. Two condition variables rather than one, because a single notify_all wakes every blocked producer and consumer, all but one re-check and go back to sleep: at 8 threads that is a measurable wake storm. And close(), because without it a producer blocked on a full queue whose consumer has died hangs forever and join() never returns.
Trace, capacity 2. P1 push(1) → [1]. P2 push(2) → [1,2]. P3 push(3) blocks on not_full_. C1 pop() takes 1, [2], notify_one on not_full_ → P3 wakes, [2,3]. close() → P4 blocked in push returns false; C2 drains 3, then pop returns nullopt and the consumer loop exits.
Alternatives, and when they win
| Approach | Throughput | When |
|---|---|---|
| mutex + 2 condvars | ~1–5 M ops/s uncontended | default; correct, easy to review |
| two counting semaphores | similar | no predicate needed, but shutdown is clumsier |
SPSC ring buffer, atomic<head/tail> acquire/release | 10–50 M ops/s | exactly one producer and one consumer |
GCD serial queue / DispatchSemaphore | — | Apple platforms, but DispatchQueue is unbounded; the semaphore supplies the bound |
The lock-free version only pays off for a single producer and single consumer. Capacity a power of two so idx & (cap-1) replaces %, and pad head and tail onto separate cache lines (128 B on Apple silicon, 64 B on x86) or the two threads ping-pong the same line and you lose most of the gain.
Failure modes I'd name
wait without a predicate: a spurious wakeup returns with an empty deque and front() is undefined behaviour. Poison pill instead of close(): works with one consumer, silently strands the others. Unbounded queue: memory climbs until the process is killed, and the kill looks like a random crash rather than the overload it was. Non-noexcept move constructor on T: a throw mid-push_back leaves the queue in a state no one reasoned about.
Curated: · Written: · Reviewed:
Q&A-15Implement a cyclic barrier.
The 90-second answer
A cyclic barrier blocks N parties until all N have arrived, then releases them all and resets for the next round. "Cyclic" is the whole point: it is reusable, unlike a latch. Clarify three things before writing code: is it fixed at N, what happens when a waiter times out or is cancelled, and does one thread need to be told it was the last to arrive (pthreads gives that thread PTHREAD_BARRIER_SERIAL_THREAD so it can do the phase's serial work).
I'd implement it with a mutex, a condition variable, a count, and a generation number. The generation is what makes it cyclic and what makes wakeups correct: a waiter records the generation it is waiting on and only proceeds when the generation has moved.
cpp // C++17, checked with g++ 13 / libstdc++ class CyclicBarrier { public: explicit CyclicBarrier(int n) : n_(n), count_(n), gen_(0) {}
// returns false if this thread timed out; barrier is then broken bool wait(std::chrono::milliseconds timeout) { std::unique_lockstd::mutex lk(m_); if (broken_) return false; const uint64_t gen = gen_; if (--count_ == 0) { // last arriver, still holding the lock ++gen_; // release this generation count_ = n_; // reset for the next round cv_.notify_all(); return true; } const bool ok = cv_.wait_for(lk, timeout, [&]{ return gen_ != gen || broken_; }); if (!ok) { broken_ = true; cv_.notify_all(); } // don't strand the others return ok; }
private: std::mutex m_; std::condition_variable cv_; int n_, count_; uint64_t gen_; bool broken_ = false; };
Trace, N = 3, two rounds
| Step | count_ | gen_ | Effect |
|---|---|---|---|
| T1 calls wait | 3 → 2 | 0 | waits on gen 0 |
| T2 calls wait | 2 → 1 | 0 | waits on gen 0 |
| T3 calls wait | 1 → 0 | 0 → 1 | resets count to 3, notify_all |
| T1, T2 wake | 3 | 1 | predicate gen_ != 0 true, return |
| T4 (round 2) | 3 → 2 | 1 | waits on gen 1: no lost wakeup |
The count reset happens under the mutex before notify_all, so a thread arriving for round 2 cannot observe a half-reset barrier. The mutex also gives the memory ordering a barrier is for: every write any thread made before wait() happens-before every read after it, in all threads.
Failure modes worth naming
- Timeout strands the barrier. If a waiter gives up and just returns,
count_stays decremented and the next round deadlocks at N−1. Either break the barrier and wake everyone (above), or make the timeout impossible. This is the bug interviewers probe for. - Spurious wakeups.
condition_variablemay wake without a notify; the predicate ongen_is what makes that harmless. A barecv_.wait(lk)is wrong. - Thread cancellation / exceptions. A thread that dies between arriving and being released has the same effect as a timeout. Scope-guard the decrement or break the barrier in the destructor path.
- Reuse after break. Once broken, the barrier must stay broken or be explicitly reset; silently un-breaking it hides the lost party.
Alternatives
A sense-reversal barrier uses one atomic counter and a per-thread sense flag: each thread fetch_adds, the last one flips a global sense and resets the count, the rest spin until the sense flips. It avoids the kernel on the fast path but burns a core per waiter, so it only wins when the phase is shorter than a context switch. C++20's std::barrier is the right default in new code: libstdc++ backs it with an atomic counter plus a futex wait, so it is cheap when uncontended and does not spin. pthread_barrier_wait is the C equivalent and hands one thread the serial role.
Don't reach for a barrier when you only need "wait for these tasks to finish once": that's a latch, std::future, or a dispatch_group. And note that Apple's dispatch_barrier_async is unrelated: it is a write barrier on a concurrent queue, not a rendezvous between threads.
Curated: · Written: · Reviewed:
Q&A-16Implement a lock without calling ready-made synchronization primitives.
The 90-second answer
First I'd pin down what "ready-made" excludes, because it changes the answer completely. If atomic read-modify-write instructions are fair game (std::atomic, __atomic_compare_exchange, ARM's LDXR/STXR exclusive pair) then a lock is a test-and-set loop with acquire/release ordering, about ten lines. If nothing is allowed, not even atomics, then I need a software-only mutual exclusion algorithm: Peterson's for two threads, Lamport's bakery for N. And I'd say out loud that those are only correct under sequential consistency, so on real hardware they still need fences: there is no lock without at least one atomic step somewhere. The only question is whether the atomicity comes from the CPU or from a syscall.
If atomics are allowed: test-and-test-and-set spinlock
cpp // C++20, clang 15 / libc++ on arm64 (Apple silicon) and x86-64 #include <atomic>
static inline void cpu_relax() { #if defined(aarch64) asm volatile("yield" ::: "memory"); // SEV-eligible hint on Apple silicon #else _mm_pause(); #endif }
class SpinLock { std::atomic_flag f_ = ATOMIC_FLAG_INIT; // the one type guaranteed lock-free public: void lock() noexcept { while (f_.test_and_set(std::memory_order_acquire)) while (f_.test(std::memory_order_relaxed)) // don't re-RMW while held cpu_relax(); } void unlock() noexcept { f_.clear(std::memory_order_release); } };
The inner test matters. A bare test_and_set loop issues an exclusive load on every iteration, so the cache line holding the flag ping-pongs between cores: each transfer is on the order of 100 ns on Apple silicon's cluster interconnect. Test-and-test-and-set spins on a shared (clean) copy and only re-issues the RMW when the line looks free, which cuts the coherence traffic by orders of magnitude under contention. The acquire on lock and release on unlock are not decoration: they stop the critical section's stores from being hoisted above the flag acquisition, which is the half of the problem candidates skip. On arm64 that's the DMB ISH the compiler emits for acquire/release; without it the lock is decorative and the data race is real, just rare enough to pass your tests and fail in the field. yield matters too: it lets the SMT sibling and the core's scheduler make progress instead of burning issue slots on a tight branch loop. If nothing is allowed: Peterson's, two threads cpp class PetersonLock { std::atomic<int> flag_[2] = {}; std::atomic<int> victim_{0}; public: void lock(int me) { int other = 1 - me; flag_[me].store(1, std::memory_order_seq_cst); victim_.store(me, std::memory_order_seq_cst); while (flag_[other].load(std::memory_order_seq_cst) == 1 && victim_.load(std::memory_order_seq_cst) == me) { /* spin */ } } void unlock(int me) { flag_[me].store(0, std::memory_order_release); } }; Trace with both threads contending. T0 wins because it wrote victim first and T1 overwrote it: | step | T0 | T1 | flag[0] | flag[1] | victim | |---|---|---|---|---|---| | 1 | flag[0]=1 | | 1 | 0 | – | | 2 | victim=0 | | 1 | 0 | 0 | | 3 | | flag[1]=1 | 1 | 1 | 0 | | 4 | | victim=1 | 1 | 1 | 1 | | 4 | reads flag[1]=1, victim=1≠0 → enters | | | | | | 5 | | reads flag[0]=1, victim=1==1 → spins | | | | Mutual exclusion holds because if both are in the loop, victim can only name one of them. For N threads, Lamport's bakery generalises it: each thread takes ticket = 1 + max(number[]) and waits while any j has number[j] != 0 && (number[j], j) < (number[i], i). It's FIFO-fair, which Peterson is not. What actually breaks | Approach | Needs | Fairness | Blocks | | --- | --- | --- | --- | | CAS spinlock | one atomic RMW | none: starvation possible | no | | Peterson | SC loads/stores, exactly 2 threads | bounded bypass | no | | Bakery | SC loads/stores, N known, ticket array | FIFO | no | | os_unfair_lock | kernel ulock | unfair, but priority-donating | yes | The spinlock's real failure mode is a preempted holder. On a single core, or when the holder gets descheduled, every waiter burns a full scheduler quantum, 10 ms of a core at 100%, and if the spinner is higher priority than the holder you have priority inversion with no bound. Detect it in Instruments' Time Profiler as a spin run sitting on one instruction, or as spin time in powermetrics. The fix isn't a better spinlock, it's a blocking lock. Second failure mode: a critical section that can page fault, take a syscall, or call out to anything that might block turns a spinlock into a deadlock generator. Keep spinlock sections to a few hundred nanoseconds of pure computation. Third: cache-line contention. Put the flag on its own 128-byte-aligned line (Apple silicon's cache line is 128 B) or every unrelated field sharing that line ping-pongs too. What I'd actually ship In Apple code I'd reach for os_unfair_lock: 4 bytes, owner-recorded, donates the holder's priority to stop exactly the inversion above, or std::mutex, which on Darwin sits on pthread_mutex and underneath that on ulock. The hand-rolled spinlock is the right answer when the critical section is a handful of instructions and you can prove it never blocks; otherwise it's a footgun. The exercise is worth doing because it's the layer os_unfair_lock is hiding.
Curated: · Written: · Reviewed:
Q&A-17Implement an event system that supports querying events within a given time window.
The 90-second answer
Assume an in-memory, single-process store on an Apple platform, events carry a monotonic timestamp, and retention is bounded to the largest query window. Use a circular buffer of events kept sorted by timestamp, guarded by a lock. Insert appends at the tail and overwrites the oldest when full; query binary-searches for the first event ≥ start and the first > end, then copies that slice. Insert is O(1) amortized, query O(log n + k) for k results, memory fixed at capacity.
swift struct Event { let timestamp: UInt64; let payload: String }
final class EventStore { private var buffer: [Event?] private var head = 0, count = 0 private let capacity: Int private let lock = NSLock()
init(capacity: Int) {
self.capacity = capacity
buffer = Array(repeating: nil, count: capacity)
}
func record(_ e: Event) {
lock.lock(); defer { lock.unlock() }
if count == capacity {
buffer[head] = e
head = (head + 1) % capacity
} else {
buffer[(head + count) % capacity] = e
count += 1
}
}
func query(from start: UInt64, to end: UInt64) -> [Event] {
lock.lock(); defer { lock.unlock() }
let lo = lowerBound { $0.timestamp >= start }
let hi = lowerBound { $0.timestamp > end }
return (lo..<hi).compactMap { buffer[(head + $0) % capacity] }
}
private func lowerBound(_ pred: (Event) -> Bool) -> Int {
var lo = 0, hi = count
while lo < hi {
let mid = (lo + hi) / 2
if pred(buffer[(head + mid) % capacity]!) { hi = mid } else { lo = mid + 1 }
}
return lo
}
}
Trace: capacity 5, events at t=100,150,200,250,300. query(160, 260) → lowerBound(160) = index 2 (200), lowerBound(>260) = index 4 (300), returns events at 200 and 250. Insert at 350 overwrites index 0; head becomes 1, logical order 150,200,250,300,350.
What the interviewer will push on
- Out-of-order timestamps. The ring buffer assumes monotonic insertion. If producers can deliver out of order, either insert at the sorted position (O(n) shift) or keep a small reorder buffer and merge. For unbounded out-of-order, a balanced tree (e.g.,
std::multisetor a skip list) gives O(log n) insert and query. - Clock source. Use
ContinuousClock(Swift 5.7+, iOS 16+) ormach_continuous_time();Dateis wall-clock and jumps on NTP or user changes. If events come from other devices, normalize to a common clock and handle skew. - Lock contention.
NSLockserializes readers and writers. For read-heavy workloads, snapshot the buffer under lock and query the immutable copy, or useDispatchQueuewith concurrent reads and barrier writes.OSAllocatedUnfairLockis cheaper thanNSLockbut not recursive. - Retention vs query window. A fixed capacity drops old events. If a query can span more than capacity, you need a larger buffer or a persistent store (e.g., append-only log with a time index). Track overwritten-event count and query-miss rate.
| Structure | Insert | Query | Memory | Use when |
|---|---|---|---|---|
| Ring buffer + binary search | O(1) amortized | O(log n + k) | fixed | monotonic, bounded retention |
| Deque + linear scan | O(1) | O(n) | fixed | small n, simple |
| Sorted array + insertion | O(n) | O(log n + k) | dynamic | out-of-order, small n |
| Balanced BST | O(log n) | O(log n + k) | dynamic | out-of-order, unbounded |
| Time buckets | O(1) | O(buckets + k) | fixed | approximate windows, high throughput |
On Apple's platforms, keep the lock off the main thread; if this backs a UI feature, expose an async API and hop to a background queue. For a service, the same structure works per shard, but you'll want a time-series database once retention exceeds memory.
Curated: · Written: · Reviewed:
Q&A-18Implement topological sort.
The 90-second answer
Topological sort orders a directed acyclic graph so that every edge u→v places u before v. Two things to pin down before writing code: what happens when the graph has a cycle, and whether the order must be deterministic. The second one matters more than it sounds: an Xcode build graph or a Swift package dependency graph that emits a different valid order on each run busts the build cache and turns "works on my machine" into luck.
I'd use Kahn's algorithm: compute indegrees, seed a worklist with the indegree-0 nodes, pop and decrement successors. O(V+E), and cycle detection comes free, if fewer than V nodes come out, the leftovers are exactly the nodes on or downstream of a cycle.
python import heapq from collections import defaultdict
def topo_sort(nodes, edges): """edges: (u, v) means u must come before v.""" succ = defaultdict(list) indeg = {n: 0 for n in nodes} for u, v in edges: succ[u].append(v) indeg[v] += 1
ready = [n for n in nodes if indeg[n] == 0]
heapq.heapify(ready) # min-heap => deterministic tie-break
order = []
while ready:
u = heapq.heappop(ready)
order.append(u)
for v in succ[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(ready, v)
if len(order) != len(nodes):
stuck = sorted(n for n in nodes if indeg[n] > 0)
raise ValueError(f"cycle among {stuck}")
return order
Trace. Nodes a–f, edges a→c, b→c, c→d, b→e, e→d, d→f. Indegrees: a0 b0 c2 d2 e1 f1. Heap [a,b]. Pop a → c drops to 1. Pop b → c hits 0, e hits 0; heap [c,e]. Pop c → d drops to 1. Pop e → d hits 0; heap [d]. Pop d → f hits 0. Pop f. Order: a,b,c,e,d,f. D correctly lands after both c and e.
Cost. O(V+E) with a plain FIFO queue; the heap makes it O(V log V + E), and the log factor only applies to frontier pops, which is small next to E in real graphs. Swift's stdlib has no heap: you'd pull in swift-collections or keep the frontier sorted by a stable key.
The alternative, and when it wins. DFS with three-colour marking, emitting reverse post-order: same asymptotics, and it's what a linker wants for symbol resolution. Its weakness is recursion depth equal to the longest path: a 10k-deep module chain overflows the stack, so write it iteratively with an explicit stack. Kahn's advantage is that it hands you levels for free.
Parallel waves. Everything in the frontier at any instant is mutually independent, so it's a legal parallel batch. That is how you'd drive xcodebuild -jobs N or a CI fan-out: run wave 0 (all indegree-0 targets), then the next. The number of waves is the critical path; the widest wave is your parallelism ceiling.
Failure modes I'd call out.
- Deduping one side only. If you collapse duplicate edges in
succbut still count them inindeg, nodes never reach 0 and you report a phantom cycle. Dedupe both or neither. - Self-loop u→u: indegree never clears, caught by the same check, but the error must name the loop, not just say "cycle detected". Walk predecessors back from a stuck node to print it.
- Hash-order tie-breaks. Iterating a
Setof ready nodes gives a valid-but-different order per run: flaky test ordering, cache misses. Fix with the heap or a sort on a stable key. - Scale. Dict-of-lists is fine to ~100k nodes; beyond that, CSR arrays (two int arrays, offsets and targets) cut allocation and cache misses sharply.
If the graph is a tree or already ordered, skip the sort. If you need the actual cycle contents rather than just detection, Tarjan's SCC gives you the components directly.
Curated: · Written: · Reviewed:
Q&A-19Design a distributed log system where you count keywords in the logs.
The 90-second answer
Three things decide the design: exact or approximate, how fresh the counts must be, and the ingest rate. I'll assume 2M lines/s at ~500 B each, 1 GB/s, 10-second tumbling windows, exact counts for a curated list of ~5k keywords, and approximate top-K for everything else. Under those assumptions: agents tail and push, a partitioned queue absorbs bursts, a stream processor counts locally per partition per window, and a merge stage sums partial counts into a time-series store.
The decision that shapes everything else: partition by log source, not by keyword. You don't know a line's keywords until you parse it, so keyword partitioning means a shuffle per line. Partitioning by host gives a stable, replayable assignment, and the shuffle happens once per window over pre-aggregated counters.
10k hosts ──gRPC, 1000-line batches──▶ Kafka logs.raw 200 partitions, key = host_id, 7d retention │ ▼ map: parse → Counter per (window, partition) │ emits (window, partition, keyword, count) ▼ merge: sum by (window, keyword) → Cassandra / TSDB
Why the combiner is the whole design
200 partitions at 2M lines/s is 10k lines/s each, so 100k lines per partition per 10 s window. At ~2 keyword hits per line that's 200k local increments, collapsing to at most 5k emitted counters. Across all partitions: 1M counters per window, ~100k/s, ~40 B each. About 4 MB/s through the shuffle against 1 GB/s of raw lines. Roughly 250× less data moved. Skip the combiner and the merge stage becomes the bottleneck instead of the parsers.
python
Python 3.12: per-partition map step
from collections import Counter
def count_window(lines, keywords): c = Counter() for line in lines: for tok in line.split(): if tok in keywords: c[tok] += 1 return c # emitted as (window, partition, keyword, count)
Exactly-once without a transaction
Key the sink on (window, partition, keyword). The map step is deterministic over a partition's offset range for a window, so a replay after a crash recomputes the identical number and the upsert is a no-op. The merge sums across partitions, so a rewritten partition contributes once. This breaks if you key on consumer id instead of partition id: a rebalance then double-counts. It also assumes processing-time windows per partition; event-time windows need watermarks (min across partitions) plus 60 s allowed lateness, and I'd only pay that if the dashboard must answer "when it happened" rather than "when we saw it."
Failure modes
| Failure | Symptom | Handling |
|---|---|---|
| Consumer dies mid-window | duplicate partial counts | deterministic replay + upsert on (window, partition, keyword) |
| Host clock 30 s slow | events land in a closed window | watermark = min across partitions, 60 s lateness, side output for stragglers |
| Merge stage stalls | agents block, then drop | agents spool to disk, 2 GB cap, drop-oldest with a counter exported as a metric |
| One host floods (100× normal) | hot partition, consumer lag on one task | per-source token bucket at the agent; split the key to (host, file) |
| Parser bug found after the fact | wrong counts for a day | keep raw logs 7 days and replay: the reason not to count at the agent |
Cardinality
An open keyword set is unbounded and will blow up the merge stage. For the long tail I'd run a Count-Min sketch per partition. Sizing follows from the two error parameters: width w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉. For ε = 0.1% of total and δ = 1%, that's w = 2719 → round to 2^12 = 4096, and d = ⌈4.605⌉ = 5. With 4-byte counters: 5 × 4096 × 4 = 80 KiB per partition, 16 MB across 200 partitions. The guarantee is one-sided: an estimate never underestimates, and overestimates by more than ε·N with probability at most δ. Fine for a dashboard's top-K, not fine for anything billed, which is why the curated list stays exact.
Curated: · Written: · Reviewed:
Q&A-20Implement string run-length decoding, for example a5b3c -> aaaaabbbc.
The 90-second answer
The example pins the format: the count follows the character, so a5b3c is five as, three bs, one c. Before writing code I'd confirm three things: counts can be multi-digit (a12b), a letter with no digits means one copy, and malformed input (leading digit, zero count, a count that would allocate a gigabyte) should throw rather than silently produce garbage.
Then it's one left-to-right pass: read a letter, greedily consume the digits after it, emit letter × count, repeat. O(n + m) time where m is the output length, O(m) space for the result.
swift // Swift 5.9 enum DecodeError: Error, Equatable { case malformed(index: Int) case countTooLarge(index: Int) }
func decode(_ s: String) throws -> String { let chars = Array(s) var out = "" var i = 0 while i < chars.count { let ch = chars[i] guard !ch.isNumber else { throw DecodeError.malformed(index: i) } i += 1
var count = 0
var digits = 0
while i < chars.count, chars[i].isASCII, let d = chars[i].wholeNumberValue {
count = count * 10 + d
digits += 1
if count > 1_000_000 { throw DecodeError.countTooLarge(index: i) }
i += 1
}
let n = digits == 0 ? 1 : count
guard n > 0 else { throw DecodeError.malformed(index: i) }
out.append(contentsOf: repeatElement(ch, count: n))
}
return out
}
Trace of a5b3c
| i | char | digits consumed | n | out after step |
|---|---|---|---|---|
| 0 | a | 5 | 5 | aaaaa |
| 2 | b | 3 | 3 | aaaaabbb |
| 4 | c | none | 1 | aaaaabbbc |
Edge cases I'd state out loud
| input | result | reason |
|---|---|---|
abc | abc | no digits → one copy |
a12b | 12 as then b | multi-digit count |
2a | throws malformed(0) | count with no preceding letter |
a0b | throws malformed | zero count is ambiguous, reject it |
a999999999 | throws countTooLarge | 10⁹ Characters ≈ 1 GB of UTF-8 |
"" | "" | empty in, empty out |
What an interviewer will push on
Output size is the real failure mode, not parsing. a1000000000 is a syntactically valid 12-byte input that OOMs the process. Two defences: cap the total expanded length up front (sum the counts in a cheap first pass and reject above a threshold), or change the signature to write into a sink, func decode(_ s: String, into sink: (Character, Int) throws -> Void), so the caller streams to a file or socket and memory stays O(1). I'd offer the sink version if the caller is a network path.
Character vs byte. Swift's Character is a grapheme cluster, so é or an emoji stays one unit and the decode is correct for free. Indexing UTF-8 bytes instead would split a multi-byte scalar and produce mojibake: worth saying, because the naive C-style version has exactly that bug.
Regex alternative. ([^0-9])(\d*) with a replace pass is three lines and reads well, but it backtracks on pathological input and gives you no index for the error message. The explicit loop is what I'd ship.
Inverse direction. This is the decoder for the compressor; if both live in the same codebase, round-trip property tests (decode(encode(s)) == s) catch the format disagreement, which is exactly the bug you get if one side assumes count-before-letter.
Curated: · Written: · Reviewed:
Q&A-21Given a node in a chain where each node can only access its left and right neighbors, how do you count the total number of nodes?
The 90-second answer
Four things to pin down before writing code: is the chain null-terminated or can it be circular; does the count include the node I'm handed; are nodes mutable; and is a hop cheap (a pointer dereference) or expensive (a network call). I assume null-terminated, count includes the start node, nodes immutable, hops are dereferences.
With only left and right and no head, you cannot know where you are, so you have to reach an end. The cheapest correct version walks right from the start counting, then walks left from the start counting, and adds: n-1 hops total, O(1) space, no re-walking.
swift final class Node { let value: Int var left: Node? var right: Node? }
// Swift 5.9. Null-terminated chain. O(n) time, O(1) space, exactly n-1 hops. func count(from start: Node) -> Int { var total = 1 var cur = start.right while let n = cur { total += 1; cur = n.right } cur = start.left while let n = cur { total += 1; cur = n.left } return total }
Trace on a 7-node chain, handed node 4:
| hop | right cursor | left cursor | total |
|---|---|---|---|
| 0 | 4 | 4 | 1 |
| 1 | 5 | 3 | 3 |
| 2 | 6 | 2 | 5 |
| 3 | 7 | 1 | 7 |
| 4 | nil | nil | 7 |
Six hops. The naive "walk to the left end, then count back right" costs 3 + 6 = 9, because it re-walks the segment it already crossed.
If a hop is expensive, halve the rounds. Two cursors leaving the start in opposite directions do the same n-1 hops but in ⌈n/2⌉ rounds instead of n-1: 4 sequential round-trips instead of 6 above, and 500k instead of 1M if each right is an RPC. You cannot do better than two cursors: to place a third one away from the start you have to walk it there, which costs the hops you were trying to save.
swift func countParallel(from start: Node) -> Int { var left: Node? = start, right: Node? = start var total = 1 while true { let l = left?.left, r = right?.right if l == nil && r == nil { return total } if let l { left = l; total += 1 } if let r { right = r; total += 1 } } }
The circular case is the one that bites. If the chain is a ring (a playlist, a carousel, a doubly-linked free list) both versions above loop forever. Run Floyd on right first: slow one step, fast two; if they meet it's a ring, and you count by walking right from the start until you return to it. If fast falls off the end it's null-terminated and you use the code above. That check is usually what the interviewer is waiting for, because "count the nodes" and "count the nodes in a cycle" are the same question until you ask.
What not to do. Marking nodes visited as you walk is O(1) space and terminates on rings, but it mutates shared state: a concurrent reader sees a corrupted chain, and it fails outright on immutable nodes. A Set<Node> of visited nodes is correct and O(n) space: fine for a small chain, wrong when the whole point is that it holds 10^8 nodes.
Failure modes. A concurrent splice during the walk gives a wrong count or a false ring; detect it with a version counter on the list and retry, or take a read lock. If the node you're handed is itself detached (both pointers nil) you correctly return 1: confirm that's what the caller wants and not a signal they passed the wrong node.
Curated: · Written: · Reviewed:
Q&A-22Design a distributed caching service where index metadata is stored in a database and data blobs are stored in the cache.
The 90-second answer
Two assumptions to state up front: blobs are immutable and large (1 MB–100 MB), and the cache is a latency tier, not the system of record. The database is authoritative for the index: blob_id → version, size, checksum, origin_key, ACL. The cache holds hot blob bytes keyed by (tenant, blob_id, version). Durable bytes live in an object store.
If the interviewer insists blobs exist only in the cache, I push back once. Redis replication is asynchronous: a failover promotes a replica that may be behind, so writes acknowledged by the primary but not yet replicated are lost. AOF with appendfsync everysec bounds that to roughly a second of writes; appendfsync always fsyncs per write and costs most of the throughput. That is an availability story, not durability. So either the origin stays, or the blob tier becomes a quorum-replicated store (Cassandra 4.1, RF=3, QUORUM) and Redis becomes a read cache in front of it.
Read path: metadata lookup → versioned cache lookup → origin on miss. Write path: PUT origin → insert metadata row with a new version → old cache entries die by TTL. Version in the key gives read-your-writes and makes invalidation a no-op for readers already holding the old version.
client → gateway → metadata service → metadata DB (Cassandra 4.1, RF=3, QUORUM) │ returns {version, size, checksum, origin_key} ▼ blob cache: Redis Cluster, 1 primary + 2 replicas per shard │ hit → stream chunks │ miss → fetch origin, write-through, stream ▼ origin object store (S3)
| Operation | Path | Consistency detail |
|---|---|---|
| read | metadata DB → cache → origin | versioned key, read-your-writes |
| write | origin PUT → metadata insert → cache TTL | new version; old readers keep old bytes |
| delete | metadata tombstone → cache delete | tombstone wins over cache |
| repair | anti-entropy | checksum mismatch → refetch from origin |
Worked trace. Read b_42 v7. Metadata row: 4 MB, sha256:9f…, origin key t1/b_42/v7. Cache key t1:b_42:v7. Hit at p99 8 ms. On miss, S3 fetch is ~120 ms; the node writes the blob with a 24 h TTL and streams it. If a cache node dies, Redis Cluster fails over to a replica after cluster-node-timeout (default 15000 ms): up to 15 s of elevated latency for that shard's keys, which is why the client has an origin fallback with a short timeout.
Hot keys and stampede. One blob at 10k req/s hammers origin on a cold cache. Singleflight per key per node so only one origin fetch runs; refresh at 80% of TTL with jitter; negative-cache missing metadata for 30 s. Detect stampede by origin QPS spike against a miss ratio above 20%.
Capacity. 10M blobs × 1 MB = 10 TB; if 5% are hot that is 500 GB. 100 nodes × 64 GB = 6.4 TB, enough for the hot set with headroom. For 100 MB blobs, chunk into 8 MB pieces: Redis executes commands on one thread per shard, so a single 100 MB GET blocks that shard for the whole transfer.
Eviction. allkeys-lfu with lfu-log-factor 10 and lfu-decay-time 60. The rationale is that a frequency counter resists a one-off scan of cold blobs displacing the hot set, which pure recency does not, but the 8-bit counter saturates, so I would confirm the policy by replaying a production access trace rather than assuming it.
Failure modes. Metadata hotspot on a popular blob: small metadata read cache, DB still authoritative. Stale bytes: checksum mismatch in anti-entropy triggers refetch. Cache node loss: replicas serve; re-replicate from origin, not from peers, since peers may have evicted. Security: encrypted bytes at rest, per-tenant KMS keys, TLS in transit, signed origin URLs for direct fallback.
Curated: · Written: · Reviewed:
Q&A-23Write a function that reverses a singly linked list recursively.
Reported in Apple Interview Questions & Process (2026) · Inbyte
The 90-second answer
Clarify first: singly linked, reverse in place, return the new head, list may be empty. Then state the recursive definition: the reverse of head → rest is the reverse of rest with head appended at the tail. So recurse to the end and, on the way back up, point each node's successor at its predecessor.
swift final class Node { let value: Int var next: Node? init(_ value: Int, next: Node? = nil) { self.value = value; self.next = next } }
// Swift 5.9, compiled with swiftc 5.9 on macOS 14 func reversed(_ head: Node?) -> Node? { guard let head else { return nil } // empty list guard let rest = head.next else { return head } // single node: already the new tail let newHead = reversed(rest)! // reverse the tail rest.next = head // old successor now points back head.next = nil // head becomes the tail return newHead }
head.next = nil is the line candidates drop. Without it the last two nodes point at each other and any traversal loops forever.
Trace for 1→2→3, in unwinding order:
| Call | head | rest | action | returns |
|---|---|---|---|---|
| depth 3 | 3 | nil | base case | 3 |
| depth 2 | 2 | 3 | 3.next=2, 2.next=nil | 3 |
| depth 1 | 1 | 2 | 2.next=1, 1.next=nil | 3 |
Result 3→2→1→nil. Time O(n), space O(n) on the call stack: one frame per node.
The follow-up: stack depth
The recursive call is not in tail position (rest.next = head runs after it returns), so no tail-call optimisation applies, and Swift doesn't guarantee TCO anyway. A frame here is roughly 48–64 bytes on arm64. A secondary thread on iOS gets 512 KB by default (Apple's Threading Programming Guide), which is room for about 8,000–10,000 frames before the guard page. A 100,000-node list, plausible for a photo library's edit history or a long undo chain, dies with EXC_BAD_ACCESS on the stack guard page rather than returning an error. If the length is unbounded, say so and offer the iterative version:
swift func reversedIterative(_ head: Node?) -> Node? { var prev: Node? = nil var curr = head while let node = curr { let next = node.next node.next = prev prev = node curr = next } return prev }
Same O(n) time, O(1) space, and it is what I would ship for anything user-sized.
Failure modes
- Returning
headinstead ofnewHead: the caller gets the old head, now the tail of a one-element list. Symptom is a print that shows one node. - Forgetting
head.next = nil: a two-node cycle. Detect it with Floyd's algorithm or by asserting the returned tail'snext == nilin a test. - Recursing on
headinstead ofhead.next: infinite recursion, immediate overflow. - In Swift the node must be a class. Model the list as an indirect enum and each level copies the tail: O(n²).
When not to use it
Recursion is the right answer when the interviewer asks for it or the list is bounded and small, and it generalises cleanly to reverse-in-groups-of-k and to reversing a sublist, where the same "reverse the rest, then fix the head" shape holds. For production code on a device with a 512 KB thread stack, iterative wins on every axis except the readability of the base case.
Curated: · Written: · Reviewed:
Q&A-24Why do you want to work here?
Reported in Apple Software Engineer Interview Experience — Six Onsite ...
The 90-second answer
"I'll answer this for this team rather than for Apple in general, because that's the version that's actually true. Three things.
First, the constraint I want more of. For the last two years I've shipped a capture pipeline with a 33 ms per-frame budget on hardware I don't choose and can't patch after the fact. That constraint is the interesting part of the job to me, and Apple is one of the few places where the silicon, the OS and the app are designed by the same organisation, so the constraint gets solved instead of worked around. When I watched the WWDC session on [the team's framework], the fix was in the framework, not in the app: that's the layer I want to be working at.
Second, the evidence I'd be useful here. I took our editor's cold start from 1.4 s to 380 ms on a 2019 mid-tier device. About 900 ms of that was decoding full-resolution bitmaps on the main thread; switching to a downsampled decode through CGImageSourceCreateThumbnailAtIndex with kCGImageSourceThumbnailMaxPixelSize plus a prewarmed cache got most of it. That's the same shape as the problem this team owns.
Third, what I want next. I've never worked against a Neural Engine-backed pipeline, and I've never shipped on a fixed annual OS cadence where you can't hotfix a regression on a Tuesday. I want the version of the job where getting it right the first time is the whole discipline.
What does on-call look like for this team: crash triage, or performance regressions coming out of OS betas?"
Roughly 250 words, about 90 seconds. Swap the specifics for your own; the structure is what carries it.
Choosing the shape. There are four answers people give, and they are not interchangeable: the right one depends on who is in the room and how much you actually know about the team.
| Shape | Best when | Risk | What it signals |
|---|---|---|---|
| Team-and-constraint (above) | Onsite, hiring team in the room, your evidence maps to their domain | You mis-identified the team, or you're in a generalist pool and sound like you're interviewing them | You've done the work and will stay |
| Craft / co-design | Recruiter screen, team unknown, generalist pool | Generic: every senior candidate says it | You understand Apple's structural advantage |
| Product and user | Cross-functional interviewer (PM, design), consumer-facing surface | Reads as rehearsed to an engineering manager | User empathy |
| Mission as architecture | Privacy- or security-adjacent team | Slogan unless you give the engineering version | Values fit with substance behind it |
Pick by three tests, in order. Can you name the team's actual shipped work? If no, drop to the craft answer: inventing detail about a team you can't describe is the worst outcome, because the follow-up exposes it. Do you have a number that maps to their domain? If no, lead with the constraint and the ask, and keep the evidence to one sentence. Is the interviewer an engineer? If no, the product answer earns more than the performance numbers do.
Length follows the same logic: 30 seconds for a recruiter screen, where the goal is to get to the team, and 90 seconds for the hiring manager, who is deciding whether you'll still be there in three years. The question back at the end is worth the ten seconds, it turns a monologue into a conversation, but only after you've answered. Leading with a question reads as deflecting.
Failure modes.
- Product love. Every candidate says they use the phone. It carries no information about your engineering taste.
- Naming a team you can't describe. Worse than being slightly vague.
- Privacy as a slogan. The engineering version is that on-device inference keeps data off the server, which changes the architecture: no round trip, model size capped by device memory, and the failure mode becomes a stale model rather than an outage. Say that version.
- Running from something. "I want to work on real products, not ads" sounds like escaping, and the interviewer may have friends at the place you just disparaged.
- Naming the competitor you turned down. Naming the axis you're deciding on (team size, ownership boundary, release cadence) shows you have options without sounding mercenary. Naming the company does the opposite.
Follow-ups you should expect.
- "Where else are you interviewing?" Answer honestly and name the axis, not the logos.
- "What if you're placed on a different team?" Apple hires into teams, so say what transfers: the performance-budget discipline, the debugging approach, the language.
- "What would make you leave?" Give a real answer. "If the work moved to maintaining a surface with no performance budget and no path to change it" is credible; "nothing" is not.
You can't ask about unreleased work and shouldn't try. Anchor your research on published material: WWDC sessions, Swift Evolution proposals, the Human Interface Guidelines, Apple's ML research notes, and you'll have something specific to say without probing anything you shouldn't.
Curated: · Written: · Reviewed:
Q&A-25Walk me through how you would validate whether a Sudoku board is correctly completed.
Reported in Apple interview experience - Full Stack Software engineer - Blind
The 90-second answer
Clarify first: "correctly completed" means all 81 cells hold a digit 1–9 and no digit repeats in any row, column, or 3×3 box. If the board may be partially filled, the same scan runs but empties are skipped and the completeness check is dropped: that is the difference between validating a puzzle and validating a solution, and it is one line of code.
Then: one pass over 81 cells with three bitmask arrays of nine ints. Digit d sets bit 1 << (d - 1). Before setting, AND against the row, column and box masks; any non-zero result is a duplicate.
python def is_complete_sudoku(board): rows = [0] * 9 cols = [0] * 9 boxes = [0] * 9 filled = 0 for r in range(9): for c in range(9): v = board[r][c] if v == '.': continue if len(v) != 1 or v not in '123456789': return False filled += 1 bit = 1 << (int(v) - 1) b = (r // 3) * 3 + c // 3 if rows[r] & bit or cols[c] & bit or boxes[b] & bit: return False rows[r] |= bit cols[c] |= bit boxes[b] |= bit return filled == 81
Box index is (r // 3) * 3 + c // 3. For (4, 7) that is 1*3 + 2 = 5. The common bug is (r % 3) * 3 + c % 3, which maps (4, 7) to 1*3 + 1 = 4: wrong box, and it survives small tests because it is still a bijection onto 0..8.
Trace: board[0][0] = '5' sets rows[0] = cols[0] = boxes[0] = 16. board[0][1] = '5' computes bit 16, rows[0] & 16 == 16, returns False. board[4][7] = '5' checks boxes[5].
Complexity: 81 iterations, constant space. 27 ints. Stated for an n×n board it is O(n²) time and O(n) masks.
| Approach | Time | Space | When |
|---|---|---|---|
| bitmask (above) | 81 ops | 27 ints | default |
| set per row/col/box | 81 inserts | up to 81 entries | clearer, slower constant |
| sort each row/col/box | 27 × 9 log 9 | copies | never in an interview |
Failure modes worth naming. A . passes every duplicate check, so without filled == 81 a nearly empty board validates. If the input uses ints with 0 for empty, int(v) - 1 becomes -1 and 1 << -1 raises: normalize at the boundary. Multi-character or full-width digits ('12') slip past a naive in check, hence the len(v) != 1 guard. A board that is not 9×9 raises IndexError rather than returning False; validate shape where the data enters.
Follow-up: if the board arrives as a stream, the same masks work incrementally. If you must report which cells conflict, store the cell index per bit instead of a boolean, so the second occurrence can name the first.
Curated: · Written: · Reviewed:
Curated: · Written: · Reviewed: