Why Every iOS Developer Fails at DSA (And the Roadmap That Fixes Everything)

// Java - what most tutorials teach
public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return null; // This is where Swift developers get confused
}

// Swift - what you actually need to write
func twoSum(_ nums: [Int], _ target: Int) -> [Int]? {
    var numToIndex: [Int: Int] = [:]
    
    for (index, num) in nums.enumerated() {
        let complement = target - num
        
        if let complementIndex = numToIndex[complement] {
            return [complementIndex, index]
        }
        
        numToIndex[num] = index
    }
    
    return nil // Swift handles this gracefully with optionals
}

// You think you'll never use binary search...
func binarySearch<T: Comparable>(_ array: [T], _ target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return nil
}

// But you use binary search thinking all the time:
extension UITableView {
    func scrollToNearestSection(for position: CGFloat) {
        let sections = (0..<numberOfSections).map { $0 }
        
        // Binary search for the section that contains this position
        var left = 0
        var right = sections.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            let sectionRect = rect(forSection: mid)
            
            if sectionRect.contains(CGPoint(x: 0, y: position)) {
                scrollToRow(at: IndexPath(row: 0, section: mid), at: .top, animated: true)
                return
            } else if sectionRect.maxY < position {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
}

// Academic approach: "Learn merge sort"
func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let mid = array.count / 2
    let left = mergeSort(Array(array[..<mid]))
    let right = mergeSort(Array(array[mid...]))
    
    return merge(left, right)
}

// iOS developer approach: "Solve the contact search problem"
class ContactSearchManager {
    private var sortedContacts: [Contact] = []
    
    func updateContacts(_ contacts: [Contact]) {
        // Use merge sort for stable sorting of contacts
        sortedContacts = contacts.sorted { contact1, contact2 in
            // Custom comparison for iOS-specific sorting
            if contact1.isFavorite != contact2.isFavorite {
                return contact1.isFavorite && !contact2.isFavorite
            }
            return contact1.displayName.localizedCaseInsensitiveCompare(contact2.displayName) == .orderedAscending
        }
    }
    
    func searchContacts(query: String) -> [Contact] {
        // Binary search on sorted array for O(log n) performance
        return sortedContacts.filter { contact in
            contact.displayName.localizedCaseInsensitiveContains(query) ||
            contact.phoneNumbers.contains { $0.contains(query) }
        }
    }
}

// Generic tutorials miss Swift's powerful type system
protocol Searchable {
    associatedtype Element: Comparable
    func search(for element: Element) -> Int?
}

struct SortedArray<T: Comparable>: Searchable {
    private var elements: [T]
    
    init(_ elements: [T]) {
        self.elements = elements.sorted()
    }
    
    // Swift's type system prevents runtime errors
    func search(for element: T) -> Int? {
        return binarySearch(in: elements, for: element)
    }
    
    // Value semantics make this safe by default
    mutating func insert(_ element: T) {
        let insertionIndex = findInsertionPoint(for: element)
        elements.insert(element, at: insertionIndex)
    }
    
    private func binarySearch(in array: [T], for target: T) -> Int? {
        var left = 0
        var right = array.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if array[mid] == target {
                return mid
            } else if array[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return nil
    }
    
    private func findInsertionPoint(for element: T) -> Int {
        // Binary search variation for insertion point
        var left = 0
        var right = elements.count
        
        while left < right {
            let mid = left + (right - left) / 2
            
            if elements[mid] < element {
                left = mid + 1
            } else {
                right = mid
            }
        }
        
        return left
    }
}

// Understanding the difference is crucial for algorithm design
struct ValueTypeExample {
    var data: [Int]
    
    // This creates a copy - safe but potentially expensive
    func processedData() -> ValueTypeExample {
        var copy = self
        copy.data = copy.data.map { $0 * 2 }
        return copy
    }
    
    // This modifies in place - efficient but requires careful thinking
    mutating func processInPlace() {
        data = data.map { $0 * 2 }
    }
}

class ReferenceTypeExample {
    var data: [Int]
    
    init(data: [Int]) {
        self.data = data
    }
    
    // This modifies the original - efficient but can cause surprising side effects
    func processData() {
        data = data.map { $0 * 2 }
    }
}

// iOS-relevant example: Table view data source
struct ContactList {
    private(set) var contacts: [Contact]
    
    // Value semantics make this safe - you can't accidentally modify the original
    func filtered(by searchText: String) -> ContactList {
        let filteredContacts = contacts.filter { contact in
            contact.name.localizedCaseInsensitiveContains(searchText)
        }
        return ContactList(contacts: filteredContacts)
    }
    
    // Clearly marked as mutating - compiler prevents accidental modifications
    mutating func sort(by criteria: ContactSortCriteria) {
        switch criteria {
        case .name:
            contacts.sort { $0.name < $1.name }
        case .dateAdded:
            contacts.sort { $0.dateAdded < $1.dateAdded }
        case .favorite:
            contacts.sort { $0.isFavorite && !$1.isFavorite }
        }
    }
}

// Traditional approach (what tutorials teach)
func findElement(in array: [Int], target: Int) -> Int {
    for i in 0..<array.count {
        if array[i] == target {
            return i
        }
    }
    return -1  // Magic number indicates "not found" - error prone!
}

// Swift approach - optionals make intent clear
func findElement(in array: [Int], target: Int) -> Int? {
    for (index, element) in array.enumerated() {
        if element == target {
            return index
        }
    }
    return nil  // Clear, type-safe indication of "not found"
}

// Even better - using Result type for operations that can fail
enum SearchError: Error {
    case emptyArray
    case targetNotFound
}

func findElementSafely(in array: [Int], target: Int) -> Result<Int, SearchError> {
    guard !array.isEmpty else {
        return .failure(.emptyArray)
    }
    
    for (index, element) in array.enumerated() {
        if element == target {
            return .success(index)
        }
    }
    
    return .failure(.targetNotFound)
}

// iOS example - safe array access for table views
extension Array {
    subscript(safe index: Int) -> Element? {
        return indices.contains(index) ? self[index] : nil
    }
}

// Usage in table view
func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
    let cell = tableView.dequeueReusableCell(withIdentifier: "Cell", for: indexPath)
    
    // Safe access prevents crashes
    if let item = dataSource[safe: indexPath.row] {
        cell.textLabel?.text = item.title
    } else {
        cell.textLabel?.text = "Error: Invalid data"
    }
    
    return cell
}

// Array - dynamic, ordered, indexed access
var numbers = [1, 2, 3, 4, 5]
numbers.append(6)                    // O(1) amortized
let first = numbers[0]               // O(1)
numbers.insert(0, at: 0)            // O(n)
numbers.remove(at: 0)               // O(n)

// Set - unordered, unique elements, fast lookup
var uniqueNumbers: Set<Int> = [1, 2, 3]
uniqueNumbers.insert(4)              // O(1) average
let contains = uniqueNumbers.contains(3)  // O(1) average
uniqueNumbers.remove(2)              // O(1) average

// Dictionary - key-value pairs, fast lookup by key
var nameToAge: [String: Int] = ["Alice": 25, "Bob": 30]
nameToAge["Charlie"] = 35            // O(1) average
let age = nameToAge["Alice"]         // O(1) average, returns Optional

// iOS example - implementing a cache using built-in collections
class ImageCache {
    private var cache: [String: UIImage] = [:]
    private var accessOrder: [String] = []
    private let maxSize: Int
    
    init(maxSize: Int = 50) {
        self.maxSize = maxSize
    }
    
    func image(for url: String) -> UIImage? {
        if let image = cache[url] {
            // Move to front of access order (LRU behavior)
            accessOrder.removeAll { $0 == url }
            accessOrder.append(url)
            return image
        }
        return nil
    }
    
    func setImage(_ image: UIImage, for url: String) {
        // Remove oldest if at capacity
        if cache.count >= maxSize, cache[url] == nil {
            if let oldestURL = accessOrder.first {
                cache.removeValue(forKey: oldestURL)
                accessOrder.removeFirst()
            }
        }
        
        cache[url] = image
        accessOrder.removeAll { $0 == url }
        accessOrder.append(url)
    }
}

// iOS-Focused Array Problems
class TableViewDataSource {
    private var sections: [[CellData]] = []
    
    // Problem: Efficiently insert items while maintaining sorted order
    func insertItem(_ item: CellData, in sectionIndex: Int) {
        guard sections.indices.contains(sectionIndex) else { return }
        
        // Binary search for insertion point
        let section = sections[sectionIndex]
        var left = 0
        var right = section.count
        
        while left < right {
            let mid = left + (right - left) / 2
            if section[mid].sortKey < item.sortKey {
                left = mid + 1
            } else {
                right = mid
            }
        }
        
        sections[sectionIndex].insert(item, at: left)
    }
    
    // Problem: Efficiently find items for search functionality
    func searchItems(query: String) -> [(section: Int, row: Int)] {
        var results: [(section: Int, row: Int)] = []
        
        for (sectionIndex, section) in sections.enumerated() {
            for (rowIndex, item) in section.enumerated() {
                if item.title.localizedCaseInsensitiveContains(query) {
                    results.append((section: sectionIndex, row: rowIndex))
                }
            }
        }
        
        return results
    }
}

// String processing for iOS apps
extension String {
    // Implement efficient string search for autocomplete
    func fuzzyMatch(_ query: String) -> Bool {
        let queryLower = query.lowercased()
        let selfLower = self.lowercased()
        
        var queryIndex = queryLower.startIndex
        var selfIndex = selfLower.startIndex
        
        while queryIndex < queryLower.endIndex && selfIndex < selfLower.endIndex {
            if queryLower[queryIndex] == selfLower[selfIndex] {
                queryIndex = queryLower.index(after: queryIndex)
            }
            selfIndex = selfLower.index(after: selfIndex)
        }
        
        return queryIndex == queryLower.endIndex
    }
    
    // Implement string distance for "did you mean?" functionality
    func levenshteinDistance(to target: String) -> Int {
        let source = Array(self)
        let target = Array(target)
        
        var dp = Array(repeating: Array(repeating: 0, count: target.count + 1), count: source.count + 1)
        
        // Initialize base cases
        for i in 0...source.count {
            dp[i][0] = i
        }
        for j in 0...target.count {
            dp[0][j] = j
        }
        
        // Fill the DP table
        for i in 1...source.count {
            for j in 1...target.count {
                if source[i-1] == target[j-1] {
                    dp[i][j] = dp[i-1][j-1]
                } else {
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                }
            }
        }
        
        return dp[source.count][target.count]
    }
}

// Stack implementation for navigation history
struct NavigationStack<T> {
    private var elements: [T] = []
    
    mutating func push(_ element: T) {
        elements.append(element)
    }
    
    @discardableResult
    mutating func pop() -> T? {
        return elements.popLast()
    }
    
    func peek() -> T? {
        return elements.last
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
}

// iOS Application: Custom navigation controller
class CustomNavigationController: UIViewController {
    private var viewControllerStack = NavigationStack<UIViewController>()
    private weak var currentViewController: UIViewController?
    
    func pushViewController(_ viewController: UIViewController, animated: Bool) {
        // Remove current VC from view hierarchy
        currentViewController?.view.removeFromSuperview()
        currentViewController?.removeFromParent()
        
        // Push current VC to stack if it exists
        if let current = currentViewController {
            viewControllerStack.push(current)
        }
        
        // Set new VC as current
        currentViewController = viewController
        addChild(viewController)
        view.addSubview(viewController.view)
        viewController.didMove(toParent: self)
    }
    
    func popViewController(animated: Bool) -> UIViewController? {
        guard let previousVC = viewControllerStack.pop() else { return nil }
        
        // Remove current VC
        let poppedVC = currentViewController
        currentViewController?.view.removeFromSuperview()
        currentViewController?.removeFromParent()
        
        // Restore previous VC
        currentViewController = previousVC
        addChild(previousVC)
        view.addSubview(previousVC.view)
        previousVC.didMove(toParent: self)
        
        return poppedVC
    }
}

// Queue implementation for async operations
struct TaskQueue<T> {
    private var elements: [T] = []
    
    mutating func enqueue(_ element: T) {
        elements.append(element)
    }
    
    mutating func dequeue() -> T? {
        guard !elements.isEmpty else { return nil }
        return elements.removeFirst()
    }
    
    func peek() -> T? {
        return elements.first
    }
}

// iOS Application: Download manager with queue
class DownloadManager {
    private var downloadQueue = TaskQueue<DownloadTask>()
    private var activeDownloads: Set<String> = []
    private let maxConcurrentDownloads = 3
    
    func addDownload(_ task: DownloadTask) {
        downloadQueue.enqueue(task)
        processQueue()
    }
    
    private func processQueue() {
        while activeDownloads.count < maxConcurrentDownloads,
              let nextTask = downloadQueue.dequeue() {
            
            activeDownloads.insert(nextTask.id)
            startDownload(nextTask)
        }
    }
    
    private func startDownload(_ task: DownloadTask) {
        URLSession.shared.downloadTask(with: task.url) { [weak self] _, _, _ in
            DispatchQueue.main.async {
                self?.activeDownloads.remove(task.id)
                self?.processQueue() // Process next items in queue
            }
        }.resume()
    }
}

// Custom hash table for learning (don't use in production - use Dictionary)
struct HashTable<Key: Hashable, Value> {
    private var buckets: [[(Key, Value)]]
    private var count = 0
    
    init(capacity: Int = 16) {
        buckets = Array(repeating: [], count: capacity)
    }
    
    private func index(for key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }
    
    mutating func setValue(_ value: Value, for key: Key) {
        let index = self.index(for: key)
        
        // Check if key already exists
        for (i, (existingKey, _)) in buckets[index].enumerated() {
            if existingKey == key {
                buckets[index][i] = (key, value)
                return
            }
        }
        
        // Add new key-value pair
        buckets[index].append((key, value))
        count += 1
    }
    
    func getValue(for key: Key) -> Value? {
        let index = self.index(for: key)
        
        for (existingKey, value) in buckets[index] {
            if existingKey == key {
                return value
            }
        }
        
        return nil
    }
}

// Tree implementation for hierarchical iOS data
class TreeNode<T> {
    var value: T
    var children: [TreeNode<T>] = []
    weak var parent: TreeNode<T>?
    
    init(_ value: T) {
        self.value = value
    }
    
    func addChild(_ child: TreeNode<T>) {
        children.append(child)
        child.parent = self
    }
    
    func removeChild(_ child: TreeNode<T>) {
        children.removeAll { $0 === child }
        child.parent = nil
    }
}

// iOS Application: File system browser
class FileSystemBrowser {
    private var rootNode: TreeNode<FileSystemItem>
    
    init(rootPath: String) {
        rootNode = TreeNode(FileSystemItem(name: "Root", path: rootPath, isDirectory: true))
        buildTree(for: rootNode)
    }
    
    private func buildTree(for node: TreeNode<FileSystemItem>) {
        let fileManager = FileManager.default
        guard let contents = try? fileManager.contentsOfDirectory(atPath: node.value.path) else { return }
        
        for item in contents {
            let itemPath = (node.value.path as NSString).appendingPathComponent(item)
            var isDirectory: ObjCBool = false
            
            if fileManager.fileExists(atPath: itemPath, isDirectory: &isDirectory) {
                let fileItem = FileSystemItem(
                    name: item,
                    path: itemPath,
                    isDirectory: isDirectory.boolValue
                )
                
                let childNode = TreeNode(fileItem)
                node.addChild(childNode)
                
                if isDirectory.boolValue {
                    buildTree(for: childNode) // Recursive tree building
                }
            }
        }
    }
    
    func searchFiles(matching query: String) -> [FileSystemItem] {
        return searchInTree(rootNode, query: query)
    }
    
    private func searchInTree(_ node: TreeNode<FileSystemItem>, query: String) -> [FileSystemItem] {
        var results: [FileSystemItem] = []
        
        // Check current node
        if node.value.name.localizedCaseInsensitiveContains(query) {
            results.append(node.value)
        }
        
        // Recursively search children
        for child in node.children {
            results.append(contentsOf: searchInTree(child, query: query))
        }
        
        return results
    }
}

struct FileSystemItem {
    let name: String
    let path: String
    let isDirectory: Bool
}

// Merge sort implementation for stable sorting (preserves equal element order)
func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let middle = array.count / 2
    let left = mergeSort(Array(array[0..<middle]))
    let right = mergeSort(Array(array[middle..<array.count]))
    
    return merge(left, right)
}

func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var result: [T] = []
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] <= right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    result.append(contentsOf: left[leftIndex...])
    result.append(contentsOf: right[rightIndex...])
    
    return result
}

// iOS Application: Sorting contacts with multiple criteria
struct Contact {
    let name: String
    let phoneNumber: String
    let isFavorite: Bool
    let dateAdded: Date
}

class ContactSorter {
    enum SortCriteria {
        case name
        case dateAdded
        case favorite
        case combined
    }
    
    func sortContacts(_ contacts: [Contact], by criteria: SortCriteria) -> [Contact] {
        switch criteria {
        case .name:
            return contacts.sorted { $0.name.localizedCaseInsensitiveCompare($1.name) == .orderedAscending }
            
        case .dateAdded:
            return contacts.sorted { $0.dateAdded < $1.dateAdded }
            
        case .favorite:
            return contacts.sorted { $0.isFavorite && !$1.isFavorite }
            
        case .combined:
            // Multi-level sorting: favorites first, then by name
            return contacts.sorted { contact1, contact2 in
                if contact1.isFavorite != contact2.isFavorite {
                    return contact1.isFavorite && !contact2.isFavorite
                }
                return contact1.name.localizedCaseInsensitiveCompare(contact2.name) == .orderedAscending
            }
        }
    }
    
    // Quick sort for in-place sorting when memory is constrained
    func quickSortInPlace<T: Comparable>(_ array: inout [T], low: Int = 0, high: Int? = nil) {
        let high = high ?? array.count - 1
        guard low < high else { return }
        
        let pivotIndex = partition(&array, low: low, high: high)
        quickSortInPlace(&array, low: low, high: pivotIndex - 1)
        quickSortInPlace(&array, low: pivotIndex + 1, high: high)
    }
    
    private func partition<T: Comparable>(_ array: inout [T], low: Int, high: Int) -> Int {
        let pivot = array[high]
        var i = low
        
        for j in low..<high {
            if array[j] <= pivot {
                array.swapAt(i, j)
                i += 1
            }
        }
        
        array.swapAt(i, high)
        return i
    }
}

// Binary search implementation
func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return nil
}

// Graph implementation for social networks, navigation, etc.
class Graph<T: Hashable> {
    private var adjacencyList: [T: Set<T>] = [:]
    
    func addVertex(_ vertex: T) {
        adjacencyList[vertex] = Set<T>()
    }
    
    func addEdge(_ source: T, _ destination: T) {
        adjacencyList[source]?.insert(destination)
        adjacencyList[destination]?.insert(source) // Undirected graph
    }
    
    func breadthFirstSearch(from start: T, to target: T) -> [T]? {
        guard adjacencyList[start] != nil else { return nil }
        
        var queue: [T] = [start]
        var visited: Set<T> = [start]
        var parent: [T: T] = [:]
        
        while !queue.isEmpty {
            let current = queue.removeFirst()
            
            if current == target {
                // Reconstruct path
                var path: [T] = []
                var node: T? = target
                
                while let currentNode = node {
                    path.insert(currentNode, at: 0)
                    node = parent[currentNode]
                }
                
                return path
            }
            
            if let neighbors = adjacencyList[current] {
                for neighbor in neighbors {
                    if !visited.contains(neighbor) {
                        visited.insert(neighbor)
                        parent[neighbor] = current
                        queue.append(neighbor)
                    }
                }
            }
        }
        
        return nil
    }
}

// iOS Application: Friend recommendation system
class SocialNetworkAnalyzer {
    private let socialGraph = Graph<String>()
    
    init() {
        setupSampleData()
    }
    
    private func setupSampleData() {
        let users = ["Alice", "Bob", "Charlie", "Diana", "Eve", "Frank"]
        users.forEach { socialGraph.addVertex($0) }
        
        // Add friendships
        socialGraph.addEdge("Alice", "Bob")
        socialGraph.addEdge("Bob", "Charlie")
        socialGraph.addEdge("Charlie", "Diana")
        socialGraph.addEdge("Alice", "Eve")
        socialGraph.addEdge("Eve", "Frank")
    }
    
    func findMutualConnectionPath(from user1: String, to user2: String) -> [String]? {
        return socialGraph.breadthFirstSearch(from: user1, to: user2)
    }
    
    func suggestFriends(for user: String) -> [String] {
        // Find friends of friends who aren't direct friends
        guard let directFriends = socialGraph.adjacencyList[user] else { return [] }
        
        var friendsOfFriends: Set<String> = []
        
        for friend in directFriends {
            if let friendsFriends = socialGraph.adjacencyList[friend] {
                for friendOfFriend in friendsFriends {
                    if friendOfFriend != user && !directFriends.contains(friendOfFriend) {
                        friendsOfFriends.insert(friendOfFriend)
                    }
                }
            }
        }
        
        return Array(friendsOfFriends)
    }
}

// Classic DP: Fibonacci with memoization
class DynamicProgramming {
    private var fibCache: [Int: Int] = [:]
    
    func fibonacci(_ n: Int) -> Int {
        if n <= 1 { return n }
        
        if let cached = fibCache[n] {
            return cached
        }
        
        let result = fibonacci(n - 1) + fibonacci(n - 2)
        fibCache[n] = result
        return result
    }
    
    // iOS Application: Optimal image cache size calculation
    func optimalCacheSize(images: [(size: Int, value: Int)], maxMemory: Int) -> Int {
        let n = images.count
        var dp = Array(repeating: Array(repeating: 0, count: maxMemory + 1), count: n + 1)
        
        for i in 1...n {
            let currentImage = images[i - 1]
            
            for memory in 1...maxMemory {
                if currentImage.size <= memory {
                    // Either include or exclude current image
                    dp[i][memory] = max(
                        dp[i - 1][memory], // Exclude
                        dp[i - 1][memory - currentImage.size] + currentImage.value // Include
                    )
                } else {
                    dp[i][memory] = dp[i - 1][memory] // Can't include
                }
            }
        }
        
        return dp[n][maxMemory]
    }
    
    // iOS Application: Minimum edit distance for autocorrect
    func minimumEditDistance(_ word1: String, _ word2: String) -> Int {
        let chars1 = Array(word1)
        let chars2 = Array(word2)
        let m = chars1.count
        let n = chars2.count
        
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
        
        // Initialize base cases
        for i in 0...m { dp[i][0] = i }
        for j in 0...n { dp[0][j] = j }
        
        // Fill DP table
        for i in 1...m {
            for j in 1...n {
                if chars1[i - 1] == chars2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1]
                } else {
                    dp[i][j] = 1 + min(
                        dp[i - 1][j],     // Deletion
                        dp[i][j - 1],     // Insertion
                        dp[i - 1][j - 1]  // Substitution
                    )
                }
            }
        }
        
        return dp[m][n]
    }
}

// iOS Application: Text autocorrect system
class AutocorrectEngine {
    private let dp = DynamicProgramming()
    private let dictionary: [String]
    
    init(dictionary: [String]) {
        self.dictionary = dictionary.sorted() // Keep sorted for binary search
    }
    
    func suggestCorrections(for input: String, maxDistance: Int = 2) -> [String] {
        var suggestions: [(word: String, distance: Int)] = []
        
        for word in dictionary {
            let distance = dp.minimumEditDistance(input, word)
            if distance <= maxDistance {
                suggestions.append((word: word, distance: distance))
            }
        }
        
        // Sort by distance (closest first)
        suggestions.sort { $0.distance < $1.distance }
        return suggestions.map { $0.word }
    }
}

// Trie for efficient string searching (autocomplete, spell check)
class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord = false
    var word: String?
}

class Trie {
    private let root = TrieNode()
    
    func insert(_ word: String) {
        var current = root
        
        for char in word {
            if current.children[char] == nil {
                current.children[char] = TrieNode()
            }
            current = current.children[char]!
        }
        
        current.isEndOfWord = true
        current.word = word
    }
    
    func search(_ word: String) -> Bool {
        var current = root
        
        for char in word {
            guard let next = current.children[char] else {
                return false
            }
            current = next
        }
        
        return current.isEndOfWord
    }
    
    func autocomplete(_ prefix: String) -> [String] {
        var current = root
        
        // Navigate to prefix
        for char in prefix {
            guard let next = current.children[char] else {
                return []
            }
            current = next
        }
        
        // Collect all words with this prefix
        var results: [String] = []
        collectWords(from: current, results: &results)
        return results
    }
    
    private func collectWords(from node: TrieNode, results: inout [String]) {
        if node.isEndOfWord, let word = node.word {
            results.append(word)
        }
        
        for child in node.children.values {
            collectWords(from: child, results: &results)
        }
    }
}

// iOS Application: Smart search with autocomplete
class SmartSearchEngine {
    private let trie = Trie()
    private let searchHistory: [String]
    
    init(searchTerms: [String]) {
        self.searchHistory = searchTerms
        
        // Build trie from search history
        for term in searchTerms {
            trie.insert(term.lowercased())
        }
    }
    
    func getSuggestions(for query: String, limit: Int = 5) -> [String] {
        let lowercaseQuery = query.lowercased()
        let suggestions = trie.autocomplete(lowercaseQuery)
        
        // Sort by relevance (could include factors like search frequency)
        let sortedSuggestions = suggestions.sorted { suggestion1, suggestion2 in
            let freq1 = searchHistory.filter { $0.lowercased() == suggestion1 }.count
            let freq2 = searchHistory.filter { $0.lowercased() == suggestion2 }.count
            return freq1 > freq2
        }
        
        return Array(sortedSuggestions.prefix(limit))
    }
}

// LRU Cache implementation using HashMap + Doubly Linked List
class LRUCache<Key: Hashable, Value> {
    private class Node {
        var key: Key
        var value: Value
        var prev: Node?
        var next: Node?
        
        init(key: Key, value: Value) {
            self.key = key
            self.value = value
        }
    }
    
    private let capacity: Int
    private var cache: [Key: Node] = [:]
    private let head = Node(key: "" as! Key, value: "" as! Value) // Dummy head
    private let tail = Node(key: "" as! Key, value: "" as! Value) // Dummy tail
    
    init(capacity: Int) {
        self.capacity = capacity
        head.next = tail
        tail.prev = head
    }
    
    func get(_ key: Key) -> Value? {
        guard let node = cache[key] else { return nil }
        
        // Move to front (most recently used)
        moveToFront(node)
        return node.value
    }
    
    func put(_ key: Key, _ value: Value) {
        if let existingNode = cache[key] {
            // Update existing
            existingNode.value = value
            moveToFront(existingNode)
        } else {
            // Add new
            let newNode = Node(key: key, value: value)
            cache[key] = newNode
            addToFront(newNode)
            
            if cache.count > capacity {
                // Remove least recently used (tail.prev)
                if let lru = tail.prev {
                    removeNode(lru)
                    cache.removeValue(forKey: lru.key)
                }
            }
        }
    }
    
    private func moveToFront(_ node: Node) {
        removeNode(node)
        addToFront(node)
    }
    
    private func addToFront(_ node: Node) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }
    
    private func removeNode(_ node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }
}

// iOS Application: Image cache with size-based eviction
class AdvancedImageCache {
    private let lruCache: LRUCache<String, UIImage>
    private var totalMemoryUsage: Int = 0
    private let maxMemoryUsage: Int
    private var imageSizes: [String: Int] = [:]
    
    init(maxMemoryMB: Int = 50) {
        self.maxMemoryUsage = maxMemoryMB * 1024 * 1024 // Convert to bytes
        self.lruCache = LRUCache(capacity: 100) // Max 100 images
    }
    
    func image(for url: String) -> UIImage? {
        return lruCache.get(url)
    }
    
    func setImage(_ image: UIImage, for url: String) {
        let imageSize = estimateImageSize(image)
        
        // Evict images if necessary to make room
        while totalMemoryUsage + imageSize > maxMemoryUsage && !imageSizes.isEmpty {
            // This is simplified - in reality, LRU cache would handle eviction
            if let oldestURL = imageSizes.keys.first {
                if let oldSize = imageSizes.removeValue(forKey: oldestURL) {
                    totalMemoryUsage -= oldSize
                }
            }
        }
        
        lruCache.put(url, image)
        imageSizes[url] = imageSize
        totalMemoryUsage += imageSize
    }
    
    private func estimateImageSize(_ image: UIImage) -> Int {
        return Int(image.size.width * image.size.height * 4) // 4 bytes per pixel (RGBA)
    }
}

// Common interview patterns and how to recognize them

class InterviewPatterns {
    // Pattern 1: Two Pointers
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int]? {
        var left = 0
        var right = numbers.count - 1
        
        while left < right {
            let sum = numbers[left] + numbers[right]
            
            if sum == target {
                return [left, right]
            } else if sum < target {
                left += 1
            } else {
                right -= 1
            }
        }
        
        return nil
    }
    
    // Pattern 2: Sliding Window
    func maxSubarraySum(_ nums: [Int], _ k: Int) -> Int {
        guard nums.count >= k else { return 0 }
        
        // Calculate sum of first window
        var windowSum = nums[0..<k].reduce(0, +)
        var maxSum = windowSum
        
        // Slide the window
        for i in k..<nums.count {
            windowSum = windowSum - nums[i - k] + nums[i]
            maxSum = max(maxSum, windowSum)
        }
        
        return maxSum
    }
    
    // Pattern 3: Fast and Slow Pointers (Floyd's Cycle Detection)
    func hasCycle<T>(_ head: ListNode<T>?) -> Bool {
        var slow = head
        var fast = head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            
            if slow === fast {
                return true
            }
        }
        
        return false
    }
    
    // Pattern 4: Merge Intervals
    func mergeIntervals(_ intervals: [[Int]]) -> [[Int]] {
        guard !intervals.isEmpty else { return [] }
        
        let sorted = intervals.sorted { $0[0] < $1[0] }
        var merged: [[Int]] = [sorted[0]]
        
        for current in sorted.dropFirst() {
            let lastMerged = merged[merged.count - 1]
            
            if current[0] <= lastMerged[1] {
                // Overlapping intervals - merge them
                merged[merged.count - 1] = [lastMerged[0], max(lastMerged[1], current[1])]
            } else {
                // Non-overlapping - add to result
                merged.append(current)
            }
        }
        
        return merged
    }
    
    // Pattern 5: Top K Elements (using heap/priority queue)
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        // Count frequencies
        var frequencyMap: [Int: Int] = [:]
        for num in nums {
            frequencyMap[num, default: 0] += 1
        }
        
        // Sort by frequency and take top k
        let sorted = frequencyMap.sorted { $0.value > $1.value }
        return Array(sorted.prefix(k).map { $0.key })
    }
}

class ListNode<T> {
    var val: T
    var next: ListNode?
    init(_ val: T) {
        self.val = val
    }