An interview question I solved

LRUCache.swift

//
//  main.swift
//  LRUCache
//
//  Created by Paul Wood on 9/19/19.
//  Copyright © 2019 Paul Wood. All rights reserved.
//

import Foundation

public class LRUCache {
  
  public enum Error: Swift.Error {
    case exceedsCapacity
  }
  
  private struct StorePairing {
    let key: String
    let value: String
    let node: Node
  }
  
  private let maxCapacity: Int
  private var currentCapacity: Int = 0
  private var head: Node?
  private var tail: Node?
  private var store: [String/*Key*/: StorePairing] = [:]
  
  init(capacity: Int){
    self.maxCapacity = capacity
  }
  
  private class Node {
    let key: String
    let cost: Int
    var prev: Node?
    var next: Node?
    init(key: String, cost: Int) {
      self.key = key
      self.cost = cost
    }
    
    deinit {
      print("removed \(key), atCost: \(cost)") // Helpful way of confirming that something is removed from the cache
    }
  }
  
  fileprivate func createNewHead(_ cost: Int, _ key: String, _ value: String) -> Result<Void, LRUCache.Error> {
    let newHead = Node(key: key, cost: cost)
    let newPair = StorePairing(key: key, value: value, node: newHead)
    if let currentHead = self.head {
      currentHead.prev = newHead
      newHead.next = currentHead
    }
    self.head = newHead
    if self.tail == nil { // Empty Cache State
      self.tail = newHead
    }
    store[key] = newPair
    currentCapacity += cost
    return .success(())
  }
  
  private func moveNodeToFront(_ pair: LRUCache.StorePairing) {
    // We found it cost does not change
    if tail !== head { // Only if there is more than one item in the list do we do this logic
      let newHead = pair.node
      if newHead === tail {
        tail = newHead.prev
      }
      newHead.prev?.next = newHead.next
      newHead.next?.prev = newHead.prev
      newHead.prev = nil
      newHead.next = self.head
      head = newHead
    }
  }
  
  private func resizeForCost(_ cost: Int) {
    while (self.currentCapacity + cost > maxCapacity){
      if self.tail === self.head {
        self.currentCapacity = 0
        self.head = nil
        self.tail = nil
        return
      }
      
      let toRemove = self.tail!
      store[toRemove.key] = nil
      self.currentCapacity -= toRemove.cost
      self.tail = toRemove.prev
      toRemove.prev?.next = nil
      toRemove.prev = nil //toRemove should now have no references
    }
  }
  
  func add(key: String, value: String, cost: Int) -> Result<Void, LRUCache.Error> {
    if cost > maxCapacity {
      return .failure(.exceedsCapacity)
    }
    
    if head == nil {
      return createNewHead(cost, key, value)
    }
    
    if let pair = store[key] {
      moveNodeToFront(pair)
      return .success(())
    }
    
    if self.currentCapacity + cost > maxCapacity {
      resizeForCost(cost)
    }
    return createNewHead(cost, key, value)
  }
  
  subscript(key: String) -> String? /*Return Value*/ {
    if let pair = store[key] {
      moveNodeToFront(pair)
      return pair.value
    }
    return nil
  }
}

struct Food {
  let name: String
  let cost: Int
}

extension LRUCache {
  func addFood(_ food: Food) -> Result<Void, LRUCache.Error> {
    return self.add(key: food.name, value: food.name, cost: food.cost)
  }
}

// Setup some test

var apple = Food(name:"Apple", cost: 20)
var banana = Food(name:"Banana", cost: 30)
var peach = Food(name:"Peach", cost: 40)
var bread = Food(name:"Bread", cost: 40)
var chips = Food(name:"Chips", cost: 110)

let foodCache = LRUCache(capacity: 100)


var r = foodCache.addFood(apple)
print(r)
print("\(foodCache["Apple"])")
r = foodCache.addFood(apple)
print(r)
r = foodCache.addFood(banana)
print(r)
r = foodCache.addFood(peach)
print("\(foodCache["Apple"])")
print(r)
r = foodCache.addFood(bread)
print(r)
print("\(foodCache["Apple"])")
r = foodCache.addFood(chips)
print(r)

let chipsBreak = LRUCache(capacity: 100)
let shouldBeFailure = chipsBreak.addFood(chips)
print(shouldBeFailure)