Oursky-answer1.swift

import Foundation

// Question 1
var dictionary1 = ["Hi","Hello","HelloWorld", "HiWorld", "HelloWorldWideWeb", "HelloWWWW"]
var dictionary2 = ["Oursky","OurSky","OurskyLimited", "OurskyHK", "SkymakersDigitalLTD", "SkymakersDigitalLtd"]

// O(n * m) => n = dictionary count, m = sum(every words's char)
// 分析，本題中有提到 ID, IP 這種連續大寫字母的縮寫只能算一個單詞。所以設計一個判斷，當連續為大寫時不計入單詞。
func findMaxWords(words: [String]) -> String {
    var maxWordsCount = 0
    var maxWords = ""
    for word in words {
        var wordsCount = 0
        var isAbbr = false
        
        for char in word {
            if char.isUppercase && !isAbbr {
                wordsCount += 1
                isAbbr = true
            } else if char.isLowercase && isAbbr {
                isAbbr = false
            }
        }
        
        if wordsCount > maxWordsCount{
            maxWordsCount = wordsCount
            maxWords = word
        }
    }
    
    return maxWords
}

findMaxWords(words: dictionary1)
findMaxWords(words: dictionary2)

Oursky-answer2.swift

import Foundation

// Question 2
// 未來可將儲存類型設計為泛型，這邊以 Int 作為示例
struct CacheData {
    var lastAccessedTime = Date.now
    var score: Double
    var weight: Double
    var value: Int
}

class OurCache {
    var cacheMaxItemCount = 5
    var dictionary: Dictionary<String, CacheData> = [:]
    var sortedKey: [String] = []
    
    // O(1) 使用 map，時間複雜度為 O(1)
    func get(_ key: String) -> Int {
        if dictionary[key] == nil {
            return -1
        }
        
        dictionary[key]!.lastAccessedTime = Date.now
        dictionary[key]!.score = dictionary[key]!.weight
        
        return dictionary[key]!.value
    }
    
    // O(nlogn), 時間複雜度為最大為排序 O(nlogn)
    // 我們使用一組陣列來維護緩存的順序，將 score 最低的排在最後面。那麼如果緩存已滿，需要進行淘汰時，只要將陣列中的最後一個剔除就可以了。
    func put(_ key: String, _ value: Int, _ weight: Double) {
        
        // O(n)
        for (key, value) in dictionary {
            
            let timeIntervalSinceNow = abs(value.lastAccessedTime.timeIntervalSinceNow) + 1
            
            let score = value.weight  / timeIntervalSinceNow
            dictionary[key]?.score = score
        }
        
        // O(1)
        dictionary[key] = CacheData(score: weight, weight: weight, value: value)
        
        // O(nlogn) + O(n)
        sortedKey = dictionary.sorted(by:  { $0.value.score > $1.value.score}).map({$0.key})
        
        if dictionary.count <= cacheMaxItemCount {
            return
        }
        
        // O(1) + O(1)
        dictionary[sortedKey.removeLast()] = nil
    }
}

let ourCache = OurCache()

ourCache.put("H", 1, 10)
ourCache.put("I", 2, 10)
ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

ourCache.get("H")

ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

ourCache.put("J", 3, 10)
ourCache.put("K", 4, 10)
ourCache.put("L", 5, 10)
ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

ourCache.get("H")

ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

ourCache.put("M", 6, 10)

ourCache.get("J")

ourCache.put("N", 7, 10)

ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

ourCache.put("O", 8, 10)
ourCache.sortedKey.forEach({
    print("\($0): \(ourCache.dictionary[$0]!)")
})

print(ourCache.dictionary)

Oursky-answer3.swift

// Question 3
func recur(_ n: Int, _ cur: Double) -> Double {
    if (n < 2) {
        return 0
    }

    if (n == 2) {
        return 1 / Double(n) + cur
    }
    
    return recur(n - 1, (cur + 1) / Double(n * (n - 1)))
}

// 分析: - 其實 下一個 cur = 當前的(cur) + 1 / n * n - 1, n > 2，當 n = 2 時也就是遞歸的終止條件，返回 1 / 2 + cur
// 不使用 While，使用 n to 3 的方式，比如 6, 5, 4, 3
func recur2(_ n: Int, _ cur: Double) -> Double {
    var current: Double = Double(cur)
    for i in (3...n).reversed() {
        current = (current + 1) / Double((i * (i - 1)))
    }

    return 1 / 2.0 + current
}

recur(3, 10)
recur2(3, 10)

recur(4, 15)
recur2(4, 15)

recur(15, 15)
recur2(15, 15)

recur(7, 5.6)
recur2(7, 5.6)

recur(6, 26)
recur2(6, 26)