Author: Deya Eldeen

One Monday morning, some new developer (Penguin 🐧) started their first new job as a software engineer, the chat between two developers (Penguin 🐧) and their team leader (Rex 🦖) went like this.

(Penguin 🐧): I have noticed that we have test cases written for almost all features in our mobile app, why would we write unit tests if we have QA team that does the testing and quality assurance?

(Rex 🦖): Yes, writing unit tests does not only guarantee that features behave correctly just after being developed / shipped, it also guarantees that when someone write any relevant code of new feature, it does not break any existing or any piece of code.

the QA team can never test everything all over again when some new feature is introduced, it’s like an investment, you spend extra time writing unit tests during developing a feature, but prevent any potential bugs from happening in the future.

A CI/CD job running all tests will prevent any developer from merging a code that breaks an existing feature (in case that feature has well written tests), there are other benefits, like tests can be a good documentation too for anyone intending to read your code.

(Penguin 🐧): my first function I wrote is about (application force update) checking, it compares a string that resembles an application version like 1.0.2, and compares it with another version like 1.1.2 to check if the app needs force update or not.

so my responsibility would be checking against all the values of minimum value 000.000.000 up to 999.999.999 value, for both target and current versions, so my test function should iterate through all possible cases, right?

(Rex 🦖): No!!, the idea of test cases, is that covers edge cases, and maybe un-expected cases like minus numbers in this example, and maybe few random usual cases, maybe have these test functions…

testWhenCurrentVersionIsLessThanRequiredVersionRequiresUpdate
testWhenRequiredVersionIsEqualToCurrentVersionRequiresNoUpdate
testMaximumMajorNumberComparesCorrectly
testMaximumMinorNumberComparesCorrectly
testMinimumPatchNumberComparesCorrectly
testMinimumMajorNumberComparesCorrectly
testMinimumMinorNumberComparesCorrectly
testMinimumPatchNumberComparesCorrectly
testMinimumNumbersComparesCorrectly
…. + some random normal cases…

keep in mind, the naming convention should show the intention of the developer, even if the test function name becomes lengthy.

covering all the cases, will cause tests to take long time, maybe few minutes in your case, you must totally avoid that, remember the unit tests criteria? the way you do it will break the first criteria “Fast”, the normal time for tests is something like 50ms or something.

Unit Tests Criteria “F.I.R.S.T”:
Fast: we can run dozens of them in a second, if not more
Isolated: should not depend on each other, or any external state.
Repeatable: they should always give the same result when they are run, like a pure function.
Self-Verifying: the test must unambiguously say whether it passed or failed, with no room for interpretation.
Timely: they should be written before or alongside the production code that you are testing.

(Penguin 🐧): But we must have high test coverage, like 100% coverage to cover all cases, don’t we?

(Rex 🦖): Test coverage means coverage on the code logic itself, like the percentage of lines tested, not on the “possible values coverage”, and by the way, test coverage is a flawed metric, it only means we have test functions that call our code, it does not mean that the test functions are good.

(Penguin 🐧): Good, yeah, any other benefits for having unit tests?

(Rex 🦖): Testing reduces maintenance costs and therefore quantity of bugs, there are also other costs to consider like customer impact, the longer an issue goes undiscovered, the more expensive it is, which can result in negative reviews & lost trust, and of course lost money!

(Penguin 🐧): But why follow TDD (Test Driven Development) methodology? why write the tests before writing the feature itself?

(Rex 🦖): There are a lot of other development methodologies, like TDD, ATDD, DDD, BDD, .. these are lengthy topic, I encourage you to read about them quickly, and the RGR lifecycle of TDD.

(Penguin 🐧): That’s really cool, how can I make sure my code is testable? and what makes it not?

(Rex 🦖): You may consider architectural patterns, that make code more separated and easily tested, like MVVM, VIPER, VIP, …, FRP may make your code easier to test, using dependency injection, and coordinator pattern, using pure functions, etc…

(Penguin 🐧): So I always need to mock stuff when testing, right?

(Rex 🦖): No, Mocks are type of test doubles, there are also Fakes, Stubs, Spies, Dummies, look them up, and know when to use each, they are so confusing at first.

(Penguin 🐧): what other tips do you have?

(Rex 🦖): yes, there are a few on top of my head

- In network testing for mobile in general, no HTTP request should be made, you test the networking feature it self.

- tests run alphabetically, you should not rename your tests to change their order of running, remember that tests should be independent, changing the order intentionally will break this criteria.

- Xcode provides performance tests, that compares between previous runs, where you can also change the baseline, it also gives nicely formatted test coverage markers.

- Writing no tests is better than writing flaky tests!

After reading the very popular book, grokking algorithms,
Will be blogging about algorithms and data structures… the book is very informative and easy to digest.

It’s advised you get yourself familiar with data structures before starting to solve problems… I will not go into details, my advice is to try to solve the problems without looking at the solutions

Problem: 1
return a pair of 2 distinct values (if any) that sum up to a target number, from a nonempty array that has distinct integers.

Different Solutions with different time complexities

// Time: O(n^2)
func solution1(_ array: [Int], _ targetSum: Int) -> [Int] {
    for i in 0 ..< array.count-1 {
        for j in i+1 ..< array.count {
            if array[i] + array[j] == targetSum {
                return [array[i],array[j]]
            }
        }
    }
    return []
}

// Time: O(n^2)
func solution2(_ array: [Int], _ targetSum: Int) -> [Int] {
    for i in array {
        for j in array {
            if (i != j) && targetSum == (i + j) {
                return [i,j]
            }
        }
    }
    return []
}

// Time: O(n*log(n))
func solution3(_ array: [Int], _ targetSum: Int) -> [Int] {
    let sorted = array.sorted()
    var leftPointer = 0
    var rightPointer = sorted.count - 1
    while leftPointer < rightPointer {
        let leftMost = sorted[leftPointer]
        let rightMost = sorted[rightPointer]
        let currentSum = leftMost + rightMost
        if currentSum == targetSum {
            return [leftMost, rightMost]
        } else if currentSum < targetSum {
            leftPointer = leftPointer + 1
        } else if currentSum > targetSum {
            rightPointer = rightPointer - 1
        }
    }
    return []
}

// Time: O(n)
func solution4(_ array: [Int], _ targetSum: Int) -> [Int] {
    var numberDictionary = [Int: Bool]()
    for number in array {
        let mayMatch = targetSum - number
        if let exists = numberDictionary[mayMatch], exists {
            return [mayMatch, number]
        } else {
            numberDictionary[number] = true
        }
    }
    return []
}

I’m not going to explain each code, you comment here if you have a question, will leave the analysis to you, doing a simple benchmark on a 100,000 values array, we can see these results

solution1: 31.88 s.
solution2: 18.41 s.
solution3: 0.38 s.
solution4: 0.20 s. 🏆

functions used for benchmarking

func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print("Time elapsed for \(title): \(timeElapsed) s.")
}

func timeElapsedInSecondsWhenRunningCode(operation: ()->()) -> Double {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    return Double(timeElapsed)
}

Problem: 2

Given 2 non empty arrays, write a function that determines if the second array is a subsequence of array 1.

⚠️: Keep in mind, subsequence is not the same as subarray.

// Time: O(n)
func isValidSubsequence_solution1(_ array: [Int], _ sequence: [Int]) -> Bool {
    
    // sequence is empty
    if (sequence.count == 0) {
      return false
    }
    
    // if arrays are equal, directly return true.
    if (array == sequence) {
        return true
    }
    
    // the sequence is larger than the array, return false.
    if (sequence.count > array.count) {
        return false
    }
    
    var arrIdx = 0
    var seqIdx = 0
    
    while arrIdx < array.count, seqIdx < sequence.count {
        if array[arrIdx] == sequence[seqIdx] {
            seqIdx += 1
        }
        arrIdx += 1
    }
    
    return seqIdx == sequence.count
}

// Time: O(n)
func isValidSubsequence_solution2(_ array: [Int], _ sequence: [Int]) -> Bool {
    
    // sequence is empty
    if (sequence.count == 0) {
      return false
    }
    
    // if arrays are equal, directly return true.
    if (array == sequence) {
        return true
    }
    
    // the sequence is larger than the array, return false.
    if (sequence.count > array.count) {
        return false
    }
    
    var seqIdx = 0
    
    for value in array {
        if seqIdx == sequence.count {
            break
        }
        if value == sequence[seqIdx] {
            seqIdx += 1
        }
    }
    return seqIdx == sequence.count
}

test results for these arrays

let myArray1 = Array(stride(from: -900005, through: 900005, by: 1))
let myArray2 = Array(stride(from: -900000, through: 900000, by: 1))

Time elapsed for solution1: 28.102 s.
Time elapsed for solution2: 14.446 s. 🏆

can you guess why Solution 2 is better, even though they have same time complexity? 🤓

Problem 3:

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array with the squares of the original integers also sorted in ascending order.

let me add 4 solutions along with explanation.

// Bad solution, appending is expensive, it's better to init an array with the length
func sortedSquaredArray_solution1(_ array: [Int]) -> [Int] {
    var sortedSquares = [Int]()
    for value in array {
        sortedSquares.append(value * value)
    }
    return sortedSquares.sorted()
}

// Time: O(nlog(n)) | Space O(n)
func sortedSquaredArray_solution2(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)
    for (idx, value) in array.enumerated() {
        sortedSquares[idx] = value * value
    }
    return sortedSquares.sorted()
}

// same as before, but higher order functions is tuned for high performance
func sortedSquaredArray_solution3(_ array: [Int]) -> [Int] {
    return array.map { $0 * $0 }.sorted()
}

// Time: O(n) | Space O(n)
func sortedSquaredArray_solution4(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)
    
    var smallerValueIdx : Int = 0
    var largerValueIdx : Int = array.count - 1
    
    for idx in stride(from: array.count - 1, through: 0, by: -1) {
        let smallerValue = array[smallerValueIdx]
        let largerValue = array[largerValueIdx]
        if abs(smallerValue) > abs(largerValue) {
            sortedSquares[idx] = smallerValue * smallerValue
            smallerValueIdx += 1
        } else {
            sortedSquares[idx] = largerValue * largerValue
            largerValueIdx -= 1
        }
    }
    return sortedSquares
}

for the following input

let myArraySortedSquares = Array(stride(from: -5000000, through: 5000000, by: 1))

Time elapsed for solution1: 6.786 s.
Time elapsed for solution2: 6.275 s.
Time elapsed for solution3: 5.106 s.
Time elapsed for solution4: 1.637 s. 🥇

Problem 4:

2 chess teams, competed for 1,000,000 times 🧐

given a 2D array of matches [host, guest]

Example
[[“Nepomniachtchi”, “Grischuk”], [“Karjakin”, “Grischuk”], [“Nepomniachtchi”, “Keymer”], [“Ding Liren”, “Grischuk”], [“Karjakin”, “Andreikin”], [“Carlsen”, “Gukesh D”], [“Aronian”, “Gukesh D”], [“Carlsen”, “Andreikin”], [“Nepomniachtchi”, “Gukesh D”], [“Aronian”, “Gukesh D”]]

and an array of results, where 1 means host team won
Example
[1, 1, 0, 0, 0, 0, 0, 1, 1, 1]

find the winning player, 

** for sake of simplicity, assume there is no draw in total points between players.

import Foundation

let HOST_TEAM_WON = 1
let WIN_POINTS = 1

// O(n) time | O(k) space , where n: are matches and k is the number of teams
func chessWinner(_ matches: [[String]], _ results: [Int]) -> String {
    var bestPlayer = ""
    var scores = [String: Int]()
    scores[bestPlayer] = 0
    for (idx, match) in matches.enumerated() {
        let (host, guest) = (match[0], match[1])
        let winning = (results[idx] == HOST_TEAM_WON) ? (host) : (guest)
        if scores[winning] == nil { scores[winning] = 0}
        scores[winning] = scores[winning]! + WIN_POINTS
        if scores[winning]! > scores[bestPlayer]! {
            bestPlayer = winning
        }
    }
    return bestPlayer
}


func generateData() -> ([[String]] , [Int]) {
    
    let players1 = ["Carlsen", "Ding Liren", "Nepomniachtchi", "Karjakin", "Aronian"]
    let players2 = ["Keymer", "Vitiugov", "Gukesh D", "Andreikin", "Grischuk"]

    var matches = [[String]] ()
    var results = [Int]()

    let possibleResults = [0,1]
    
    for _ in 0 ..< 10 {
        matches.append([players1.randomElement() ?? "", players2.randomElement() ?? ""])
        results.append(possibleResults.randomElement() ?? 0)
    }
    print(matches)
    print(results)
    
    return (matches, results)
}

func problem_04_solutions() {
    let data = generateData()
    printTimeElapsedWhenRunningCode(title:"solution1") {
        let winner = chessWinner(data.0, data.1)
        print(winner)
    }
}