 |
| Ace Your Coding Interviews with Swift: Common Algorithm Questions |
Question 1: Find the Missing Number
You are given an array of integers from 1 to N, where one number is missing. Write a function to find and return the missing number.
Input:
An array of integers from 1 to N (inclusive), with one number missing.The length of the array (N).
Output:
The missing number.
Example:
Input: [1, 2, 4, 5, 6] (N = 6)
Output: 3
You need to implement a function called findMissingNumber in Swift to solve this problem. Here's a possible solution:
func findMissingNumber(_ nums: [Int]) -> Int {
let n = nums.count + 1 // The original length of the array
let expectedSum = n * (n + 1) / 2
let actualSum = nums.reduce(0, +)
return expectedSum - actualSum
}
// Example usage:
let nums = [1, 2, 4, 5, 6]
let missingNumber = findMissingNumber(nums)
print("Missing Number:", missingNumber) // Output will be 3
In this solution, we calculate the sum of integers from 1 to N using the formula for the sum of an arithmetic series (expectedSum). We also calculate the actual sum of the elements in the given array (actualSum). The missing number can then be found by subtracting actualSum from expectedSum.
Question 2: Maximum Element in a Stack
You have to implement a data structure that supports the following two operations:
Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Get maximum: Retrieve the maximum element from the stack.
The "Get maximum" operation should be performed in O(1) time complexity.
Example:
Push 3 Push 7 Push 1 Push 5 Get maximum (should return 7) Pop Pop Get maximum (should return 3)
You need to implement this data structure and the three operations efficiently. Here's a possible Swift solution using two stacks:
class MaxStack { private var stack = [Int]() private var maxStack = [Int]() func push(_ value: Int) { stack.append(value) if maxStack.isEmpty || value >= maxStack.last! { maxStack.append(value) } } func pop() { if let value = stack.popLast() { if value == maxStack.last { maxStack.popLast() } } } func getMax() -> Int? { return maxStack.last } } // Example usage: let maxStack = MaxStack() maxStack.push(3) maxStack.push(7) maxStack.push(1) maxStack.push(5) print(maxStack.getMax()) // Output: 7 maxStack.pop() maxStack.pop() print(maxStack.getMax()) // Output: 3
This Swift solution defines a MaxStack class that uses two stacks: one for the actual elements and another for tracking the maximum elements. The push operation adds elements to both stacks, the pop operation removes elements from both stacks if necessary, and the getMax operation retrieves the maximum element in O(1) time complexity by checking the top of the maxStack.
Question 3: Longest Common Prefix
Write a function longestCommonPrefix that takes an array of strings as input and returns the longest common prefix of those strings.
Example:
Input: ["flower", "flow", "flight"]
Output: "fl"
Input: ["dog", "racecar", "car"]
Output: "" (No common prefix)
You need to implement the longestCommonPrefix function to solve this problem. Here's a possible Swift solution:
func longestCommonPrefix(_ strs: [String]) -> String {
guard strs.count > 0 else {
return ""
}
var commonPrefix = strs[0]
for i in 1..<strs.count {
let currentString = strs[i]
while !currentString.hasPrefix(commonPrefix) {
commonPrefix = String(commonPrefix.dropLast())
if commonPrefix.isEmpty {
return ""
}
}
}
return commonPrefix
}
// Example usage:
let input1 = ["flower", "flow", "flight"]
let result1 = longestCommonPrefix(input1)
print("Longest Common Prefix 1: \(result1)")
let input2 = ["dog", "racecar", "car"]
let result2 = longestCommonPrefix(input2)
print("Longest Common Prefix 2: \(result2)")
In this example, we define the longestCommonPrefix function, which iterates through the array of strings and finds the common prefix character by character. We start with the assumption that the first string in the array is the common prefix and compare it with the rest of the strings.
Question 4: Find the Missing Number
You are given an array containing n distinct numbers taken from 0, 1, 2, ..., n. It means there is one number missing from this sequence. Write a Swift function to find and return the missing number.
Example:
Input: [3, 0, 1]
Output: 2
You need to implement the findMissingNumber function to solve this problem. Here's a possible Swift solution:
func findMissingNumber(_ nums: [Int]) -> Int {
let n = nums.count
let expectedSum = (n * (n + 1)) / 2
let actualSum = nums.reduce(0, +)
return expectedSum - actualSum
}
// Example usage:
let nums = [3, 0, 1]
let missingNumber = findMissingNumber(nums)
print("Missing Number:", missingNumber)
In this example, we calculate the sum of all numbers from 0 to n using the formula (n * (n + 1)) / 2. Then, we calculate the actual sum of the elements in the given array. The difference between the expected sum and the actual sum will be the missing number.
Question 5: Calculate the Sum of Array Elements
You are given an array of integers. Write a Swift function to calculate and return the sum of all the elements in the array.
Example:
Input: [1, 2, 3, 4, 5]
Output: 15
Input: [10, 20, 30]
Output: 60
func sumOfArrayElements(_ arr: [Int]) -> Int {
var sum = 0
for num in arr {
sum += num
}
return sum
}
// Example usage:
let arr1 = [1, 2, 3, 4, 5]
let arr2 = [10, 20, 30]
let result1 = sumOfArrayElements(arr1)
let result2 = sumOfArrayElements(arr2)
print("Sum of arr1:", result1)
print("Sum of arr2:", result2)
Question 6: Reverse a String
Write a Swift function that takes a string as input and returns the reverse of the string.
Example:
Input: "Hello, World!"
Output: "!dlroW ,olleH"
You need to implement the reverseString function to solve this problem. Here's a possible Swift solution:
func reverseString(_ input: String) -> String { let reversed = String(input.reversed()) return reversed } // Example usage: let input = "Hello, World!" let reversed = reverseString(input) print(reversed)
Thanks for reading and happy coding. 🙂
0 Comments