Algorithms & Data structures, Problem #004
5 (1)

Click to rate this post!
[Total: 1 Average: 5]

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)
    }
}

Algorithms & Data structures, Problem #003
5 (2)

Click to rate this post!
[Total: 2 Average: 5]

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. πŸ₯‡

First solution, used appending, which is expensive, second one, have a fixed size array with only writing, next, we reduce the time by using higher order functions that have performance tuned implementations out of the box like parallelism etc.

solution 4 can be optimized even more, you have an idea how?

Algorithms & Data structures, Problem #002
5 (1)

Click to rate this post!
[Total: 1 Average: 5]
photo from unsplash

Problem statement: 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? πŸ€“