Algorithms are a series of steps involved in solving a function or a part of a program. The efficiency of a chosen algorithm is calculated using Big O notation, namely runtime and space complexity.
Data Structures is the construct you choose to use to store the data of your algorithm. Example will you be using an array to store the ingredients for your awesome cake algorithm below or use a Set.
In the example below for making a cake, the algorithm would be a series of steps as listed.
Step 1: Choose a Recipe
Step 2: Choose the Right Baking Pans
Step 3: Allow Ingredients to Reach Room Temperature
Step 4: Prep the Pans
Step 5: Preheat the Oven
Step 6: Stir Together Dry Ingredients
Step 7: Combine the butter and sugar
Step 8: Add Eggs One at a Time
Step 9: Alternate Adding Dry and Wet Ingredients
Step 10: Pour Batter Into Pans and Bake
Step 11: Check Cake for Doneness
Step 12: Cool the Cake
Step 13: Assemble the Cake
Step 14: Add the First Coat of Frosting
Step 15: Frost and Decorate
In this example if we are to describe to someone the algorithm to search a photo in a photo search application, the algorithm would be similar to the steps below.
- Create an endpoint URL String to the photo Web API.
- Create a URL using the endpoint URL String.
- Use the URLSesson class to make the network request.
- Check and handle any errors returned from teh respsonse.
- Use JSONDecoder to parse the received Data to the Swift model e.g Photo.
- Return the Photo to the caller.
Pseudcode is a non-code way of explaining in "English" your thought process towards solving a problem. We use pseudocode, especially in interviews to document to the interviewer our clearly defined methodology in solving and getting to a solution for a given problem. The more defined and clear the pseudocode the easier it will be to implement your solution in code. Let's go through an example below:
Example Input: [4, 1, -89, 23]
Example Output: 23
Pseudocode
Input: array of Int Output: return an Int guard to retrieve the first value of the array, make sure it's mutable and define it as largest for each element in the array of Ints check if the current number is greater than the largest variable if it is assign the current number to the largest variable return largest
Some clarification questions can be:
- Can the array be empty?
- Can I return nil if the array is empty?
Now that we have written the pseudocode, let's convert it to compilable Swift code.
func findLargest(_ arr: [Int]) -> Int? {
guard var largest = arr.first else {
return nil
}
for currentNum in arr {
if currentNum > largest {
largest = currentNum
}
}
return largest
}Write pseudocode for the following questions and convert your pseudocode to compilable code.
Reminder as you work through the challenges practice doing the following:
- Discuss clarification questions with your peer.
- Discuss the data structure you will use and any tradeoffs it make have.
- Discuss runtime and space complexity of your solution.
Write a function that returns how many vowels are in a String
Sample Input: "Hello there! How's it going?"
Sample Output: 8
Pseudocode Solution
Input: String
Output: Int
exmaple: "alex" => 2
declare and initialize a constant Set vowels that has the vowels "aeiou"
declare and initialize a vowel counter
for each Character in the String
check if the current Character is contained in the Set, vowels
if true, increment the vowel counter variable by one
return the vowel counter
Code Solution
func countVowels(_ inputString: String) -> Int {
let vowels: Set<Character> = Set("aeiou")
var vowelCounter = 0
for char in inputString {
if vowels.contains(char) {
vowelCounter += 1
}
}
return vowelCounter
}
countVowels("Hello there! How's it going?") // 8Write a function that returns the product of an array of Ints with any zeros taken out
Sample Input: [4,0,8,3,0]
Sample Output: 96
Pseudocode Solution
Input: array on Int
Output: Int
define and initialize a product variable to 1
for each element in the input array
check if the current element is not zero
if true, add to product
return product
Code Solution
func productIgnoreZeros(_ arr: [Int]) -> Int {
var product = 1
for num in arr {
if num != 0 {
product *= num
}
}
return product
}
productIgnoreZeros([4, 0, 8, 3, 0]) // 96All Ints appear twice in an array, but one element appears only once. Write a function to find the outlier.
Sample Input: [4,0,7,8,3,0,4,3,8]
Sample Output: 7
Pseudocode Solution
Input: array of Int Outpur: Int create a frequency dictionary to store number and the count of time it appears for each number in the array store the number as the key in the frequency dictionary and increment the count of times it appears search the dictionary for the key that has a count of 1 return the key
Code Solution
func outlier(_ arr: [Int]) -> Int? {
var freqDict = [Int: Int]()
for num in arr {
if let count = freqDict[num] {
freqDict[num] = count + 1
} else {
freqDict[num] = 1
}
}
for (key, value) in freqDict {
if value == 1 {
return key
}
}
return nil
}Write a function that returns whether an Array of Ints contains any numbers divisible by 13
Sample Input: Input: [4, 1, 13, 89, 3]
Sample Output: true
Pseudocode Solution
Input: array of In t Output: Bool for each element in the array check if the current number is divisible by 13 if true, return true
Code Solution
func isDivibleBy13(_ arr: [Int]) -> Bool {
for num in arr {
if num % 13 == 0 {
return true
}
}
return false
}Write a function that reverses a String without using built-in reverse methods (i.e don't write ~.reversed()")
Sample Input: "swift rocks"
Sample Output: "skcor tfiws"
Pseudocode Solution
Input: String Output: String declare and initialize a new empty String for each character in the input String append the current character to the front of the new String return new reversed String
Code Solution
func reverseString(_ inputString: String) -> String {
var newString = ""
for char in inputString {
newString = String(char) + newString
}
return newString
}Here we have a LeetCode problem that involves more content to a problem. In pseudocoding and coming up with a solution, do the following:
- Read through the question and make your own notes in your IDE as needed, e.g Xcode or Repl.it.
- Check the Note section for clarification questions.
- Pseudocode an algorithm for your proposed solution.
- Convert your pseudocode to a working solution.
Every email consists of a local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.
Besides lowercase letters, these emails may contain '.'s or '+'s.
If you add periods ('.') between some characters in the local name part of an email address, mail sent there will
be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and
"alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)
If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows
certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com.
(Again, this rule does not apply for domain names.)
It is possible to use both of these rules at the same time.
Given a list of emails, we send one email to each address in the list. How many different addresses
actually receive mails?
Example 1:
Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2 Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails
Note:
1 <= emails[i].length <= 1001 <= emails.length <= 100- Each
emails[i]contains exactly one'@'character. - All local and domain names are non-empty.
- Local names do not start with a
'+'character.
LeetCode - Unique Email Addresses
Pseudocode Solution
Pseudocode Input: array of String Output: Int declare and initialize a Set, uniqueEmails variable that will hold unique emails for each email in emails separate the email by the "@" into a local and domain name use a helper function that returns the parsed local name create a new email using the parsed local name and the domain name insert this new email to the unique Set collection return the unique emails count
Code Solution
func uniqueEmailAddresses(_ emails: [String]) -> Int {
var uniqueEmails: Set<String> = []
for email in emails {
let localNameAndDomainName = email.components(separatedBy: "@")
guard let localName = localNameAndDomainName.first,
let domainName = localNameAndDomainName.last else { return 0 }
let modifiedLocalName = parseLocalName(localName)
let newEmail = "\(modifiedLocalName)@\(domainName)"
uniqueEmails.insert(newEmail)
}
return uniqueEmails.count
}
func parseLocalName(_ localName: String) -> String {
var modifiedName = ""
for char in localName {
if char == "+" {
return modifiedName
}
if char == "." {
continue
}
modifiedName.append(char)
}
return modifiedName
}- Big O Cheatsheet
- Understanding Space Complexity
- Interview Cake - Big O Notation
- moducode - Time & Space Complexity in Functions – Big O Notation