Apple Software Engineer Coding Interview

Approach: Implement a thread-safe LRU cache using a combination of a dictionary for O(1) lookups and a doubly linked list for tracking usage order. Use a dispatch queue for thread safety.

Key Apple Engineering Values to Demonstrate:

• Attention to detail in edge case handling
• Clean, readable Swift code with proper memory management
• Thread safety with performance considerations
• Elegant API design that feels "Apple-like"

Implementation:

import Foundation

// Node for doubly linked list
fileprivate class Node {
    let key: Key
    var value: Value
    var prev: Node?
    var next: Node?
    
    init(key: Key, value: Value) {
        self.key = key
        self.value = value
    }
}

class LRUCache {
    private let capacity: Int
    private var cache: [Key: Node] = [:]
    private let head = Node(key: nil as! Key, value: nil as! Value)
    private let tail = Node(key: nil as! Key, value: nil as! Value)
    private let queue = DispatchQueue(label: "com.apple.lrucache", attributes: .concurrent)
    
    init(capacity: Int) {
        self.capacity = max(0, capacity)
        head.next = tail
        tail.prev = head
    }
    
    func get(_ key: Key) -> Value? {
        var result: Value?
        
        queue.sync(flags: .barrier) {
            if let node = cache[key] {
                // Move accessed node to front (most recently used)
                removeNode(node)
                addToFront(node)
                result = node.value
            }
        }
        
        return result
    }
    
    func set(_ key: Key, value: Value) {
        queue.sync(flags: .barrier) {
            if let existingNode = cache[key] {
                // Update existing value and move to front
                existingNode.value = value
                removeNode(existingNode)
                addToFront(existingNode)
            } else {
                // Create new node
                let newNode = Node(key: key, value: value)
                
                // Check if we need to evict
                if cache.count >= capacity {
                    // Remove least recently used (from tail)
                    if let lruNode = tail.prev, lruNode !== head {
                        removeNode(lruNode)
                        cache.removeValue(forKey: lruNode.key)
                    }
                }
                
                // Add new node
                cache[key] = newNode
                addToFront(newNode)
            }
        }
    }
    
    private func removeNode(_ node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }
    
    private func addToFront(_ node: Node) {
        node.next = head.next
        node.prev = head
        head.next?.prev = node
        head.next = node
    }
    
    var count: Int {
        var result = 0
        queue.sync { result = cache.count }
        return result
    }
    
    func clear() {
        queue.sync(flags: .barrier) {
            cache.removeAll()
            head.next = tail
            tail.prev = head
        }
    }
}

Key Points to Explain:

• Thread safety using a concurrent dispatch queue with barrier flags for write operations
• Efficient O(1) operations for both get and set
• Clean Swift API design with proper access control
• Handling edge cases like capacity of 0
• Memory management considerations with proper node linking/unlinking

Follow-up Discussion Points: How you might extend this for distributed caching, handling cache invalidation, or implementing time-based expiration.