Skip to content
Tech Interview Prep

Real Interview Questions for the Software Engineer at Apple

New

Interview Q&A

25 questions · Flow follows Relevance until this set has a learning order.

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

CallMap keys afterList, MRU → LRUReturns
put(1,1)11—
put(2,2)1,22,1—
get(1)1,21,21
put(3,3)1,33,1— (evicts 2)
get(2)1,31,3-1
put(1,10)1,31,3— (update, no evict)
get(1)1,31,310

What the interviewer will push on

  • get must refresh recency. The classic bug is a get that 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, put is a no-op and get always misses; the lru !== head guard keeps a one-element cache from unlinking a sentinel.
  • Thread safety. A single os_unfair_lock or NSLock around both methods is correct but serialises every read. If reads dominate, shard by hash(key) % N into N independent LRUs: you lose global LRU order but keep O(1) and cut contention N-fold. Apple's NSCache is 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 LinkedHashMap with accessOrder=true plus a removeEldestEntry override, and Python's OrderedDict with move_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, get should return Int? rather than the -1 sentinel 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.

inputcompressedlengthsreturned
aabcccccaaaa2b1c5a310 < 11a2b1c5a3
abca1b1c16 > 3abc
11 × aa113 < 11a11
""——""

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.

ComponentHoldsNever holds
Key directory (IDS)Apple ID → device identity keys, signed prekeysprivate keys
Transparency logappend-only Merkle log of key-directory entries—
Message queueciphertext per destination device, TTLplaintext, session keys
APNsdevice token, opaque queue idmessage content
Clientratchet state, plaintextother devices' private keys

Trace: Alice (2 devices) → Bob (3 devices)

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

PlaneHoldsStoreAccess path
Metadataasset rows, albums, versions, change logsharded on library_id, 3× replicated per regionapp servers, strong per-library
Bloboriginals + derivatives, immutableobject store, erasure-coded, 2+ regionssigned URL, client → store direct
Edge256 px thumbs, 1024 px previewsCDN, hash-named immutable URLs95%+ 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:

tactionslotstamps[slot]counts[slot]query result
1000hit10010001—
1000hit10010002—
1050hit15010501—
1050query———3 (lo=751)
1301query———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.

Approachhitquerymemoryexactness
deque of timestampsO(1) amortizedO(k) evictO(hits in window)exact
300-slot ring bufferO(1)O(300)O(300)±1 s at edges
Redis sorted setO(log n)O(log n + m)O(hits in window)exact, shared
Redis per-second keysO(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):

Patht_comb (max/min)Setup slackHold slack
typical700 / 120 ps1000+50-60-700-40 = +250 ps60+120-30-50 = +100 ps
long logic980 / 120 ps-30 ps, violation+100 ps
short logic700 / 0 ps+250 ps60+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 dpairpush 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:

AfterList shapeRandom wiring
pass 1A A' B B' C C'none yet
pass 2unchangedA'.random = A.random.next = C'; B'.random = A'; C'.random = C'
pass 3A 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. random can be null, and null.next throws. Same for the last copy in pass 3: copy.next.next dereferences 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 because Node doesn't override equals/hashCode. If it did, say two nodes with the same val compare 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.

visitprev beforepointer writes
1Nonehead = 1
211.right = 2, 2.left = 1
322.right = 3, 3.left = 2
433.right = 4, 4.left = 3
544.right = 5, 5.left = 4
close55.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

ApproachTimeAux space
Recursive in-order (above)O(n)O(h) call stack
Morris threadingO(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 right n+1 times segfaults or loops forever. Assert head.left.right is head.
  • Returning root instead of head. The caller wants the minimum node; root is somewhere in the middle and its left now points backwards.
  • Rewiring before recursing right. If you write node.right = next before descending, you lose the right subtree. Save it or reorder.
  • Single-node and empty trees. root is None returns None; one node must self-link (n.right = n.left = n), which the close step handles only if prev was set: it is, since head = node and prev = 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.

ApproachTimeExtra spaceWhen
Parent map + BFSO(n)O(n)default; easiest to get right under pressure
DFS returning distanceO(n)O(h)memory-constrained, or tree is huge/skewed
BFS from target with existing parent pointersO(n)O(n) queuetree 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:

  1. Calendar month, not 30 days. "One month" is a civil-calendar concept. 30-day arithmetic is wrong for 7 of the 12 months.
  2. Absolute distance. Direction is a separate function; this one returns a three-way bucket.
  3. 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 .current implicitly.
  4. End-of-month clamps. Jan 31 + 1 month = Feb 28, matching Calendar and java.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.

abresultwhy
Jan 15Feb 15exactlyboundary = Feb 15
Jan 15Feb 14withinbefore boundary
Jan 15Feb 16moreafter boundary
Jan 1Jan 31withinboundary Feb 1, not reached
Jan 31Feb 28exactlyclamped boundary
Jan 31Mar 1morepast Feb 28
Feb 28Mar 31moreboundary Mar 28
Jan 29 2024Feb 29 2024exactlyleap year
Jan 29 2023Feb 28 2023exactlyclamped

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; Calendar handles 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.

FieldTypeWhy
assetHashString (SHA-256)dedupe; content-addressed blob key
assetRefCKAssetoriginal bytes, uploaded once
focalPoint{x,y}lets each device crop sensibly
renditionsmap deviceClass → cropRectper-class overrides the user set
versionInt64monotonic, server-bumped on save
modifiedAt / modifiedByDate / Stringordering + audit; server clock only
deletedBooltombstone so deletes propagate

The write path, traced

  1. iPhone picks a photo. Compute SHA-256; if wallpapers/<hash> already exists in the blob store, skip upload.
  2. Upload the asset, then save the record with savePolicy = .ifServerRecordUnchanged: optimistic concurrency against the version the client last read.
  3. CloudKit commits, bumps modificationDate, and fires the zone subscription.
  4. APNs silent push (shouldSendContentAvailable) to the other devices.
  5. Each device runs CKFetchRecordZoneChangesOperation from its stored serverChangeToken, so a device that missed ten pushes catches up in one delta fetch.
  6. If version is newer than local, download the asset (resumable, CDN-backed), render the local crop, crossfade. Write back appliedVersion for 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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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

ApproachThroughputWhen
mutex + 2 condvars~1–5 M ops/s uncontendeddefault; correct, easy to review
two counting semaphoressimilarno predicate needed, but shutdown is clumsier
SPSC ring buffer, atomic<head/tail> acquire/release10–50 M ops/sexactly 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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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

Stepcount_gen_Effect
T1 calls wait3 → 20waits on gen 0
T2 calls wait2 → 10waits on gen 0
T3 calls wait1 → 00 → 1resets count to 3, notify_all
T1, T2 wake31predicate gen_ != 0 true, return
T4 (round 2)3 → 21waits 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_variable may wake without a notify; the predicate on gen_ is what makes that harmless. A bare cv_.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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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::multiset or a skip list) gives O(log n) insert and query.
  • Clock source. Use ContinuousClock (Swift 5.7+, iOS 16+) or mach_continuous_time(); Date is 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. NSLock serializes readers and writers. For read-heavy workloads, snapshot the buffer under lock and query the immutable copy, or use DispatchQueue with concurrent reads and barrier writes. OSAllocatedUnfairLock is cheaper than NSLock but 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.
StructureInsertQueryMemoryUse when
Ring buffer + binary searchO(1) amortizedO(log n + k)fixedmonotonic, bounded retention
Deque + linear scanO(1)O(n)fixedsmall n, simple
Sorted array + insertionO(n)O(log n + k)dynamicout-of-order, small n
Balanced BSTO(log n)O(log n + k)dynamicout-of-order, unbounded
Time bucketsO(1)O(buckets + k)fixedapproximate 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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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 succ but still count them in indeg, 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 Set of 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.

Reported in Apple Software Engineer Interview Experience — Three Phone Rounds, Three Virtual Onsite Rounds, Rejected | PracHub

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

FailureSymptomHandling
Consumer dies mid-windowduplicate partial countsdeterministic replay + upsert on (window, partition, keyword)
Host clock 30 s slowevents land in a closed windowwatermark = min across partitions, 60 s lateness, side output for stragglers
Merge stage stallsagents block, then dropagents 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 taskper-source token bucket at the agent; split the key to (host, file)
Parser bug found after the factwrong counts for a daykeep 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.

Reported in prachub.com › interview-experiences › apple-softwareApple Software Engineer Interview Experience — Two Phone ...

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

ichardigits consumednout after step
0a55aaaaa
2b33aaaaabbb
4cnone1aaaaabbbc

Edge cases I'd state out loud

inputresultreason
abcabcno digits → one copy
a12b12 as then bmulti-digit count
2athrows malformed(0)count with no preceding letter
a0bthrows malformedzero count is ambiguous, reject it
a999999999throws countTooLarge10⁹ 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?

Reported in prachub.com › interview-experiences › apple-softwareApple Software Engineer Interview Experience — Two Phone ...

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:

hopright cursorleft cursortotal
0441
1533
2625
3717
4nilnil7

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.

Reported in prachub.com › interview-experiences › apple-softwareApple Software Engineer Interview Experience — Two Phone ...

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)

OperationPathConsistency detail
readmetadata DB → cache → originversioned key, read-your-writes
writeorigin PUT → metadata insert → cache TTLnew version; old readers keep old bytes
deletemetadata tombstone → cache deletetombstone wins over cache
repairanti-entropychecksum 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:

Callheadrestactionreturns
depth 33nilbase case3
depth 2233.next=2, 2.next=nil3
depth 1122.next=1, 1.next=nil3

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 head instead of newHead: 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's next == nil in a test.
  • Recursing on head instead of head.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.

ShapeBest whenRiskWhat it signals
Team-and-constraint (above)Onsite, hiring team in the room, your evidence maps to their domainYou mis-identified the team, or you're in a generalist pool and sound like you're interviewing themYou've done the work and will stay
Craft / co-designRecruiter screen, team unknown, generalist poolGeneric: every senior candidate says itYou understand Apple's structural advantage
Product and userCross-functional interviewer (PM, design), consumer-facing surfaceReads as rehearsed to an engineering managerUser empathy
Mission as architecturePrivacy- or security-adjacent teamSlogan unless you give the engineering versionValues 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.

ApproachTimeSpaceWhen
bitmask (above)81 ops27 intsdefault
set per row/col/box81 insertsup to 81 entriesclearer, slower constant
sort each row/col/box27 × 9 log 9copiesnever 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: