// Arrays
import Foundation
import XCTest
// 1,2,5 11
// Uber set
class Solution {
class Solution {
func partitionString(s: String) -> [String] {
var partitions = [String]()
var currentPartition = ""
var seenLetters = Set<Character>()
for letter in s {
if seenLetters.contains(letter) {
partitions.append(currentPartition)
currentPartition = ""
seenLetters.removeAll()
}
currentPartition += String(letter)
seenLetters.insert(letter)
}
if !currentPartition.isEmpty {
partitions.append(currentPartition)
}
return partitions
}
func topKFrequent(nums: [Int], k: Int) -> [Int] {
// Create a dictionary to keep track of the frequency of each element
var frequencyDict = [Int: Int]()
for num in nums {
frequencyDict[num, default: 0] += 1
}
// Create a min heap to store the elements based on their frequency
var heap = MinHeap<(Int, Int)> { $0.1 < $1.1 }
for (num, frequency) in frequencyDict {
heap.push((num, frequency))
if heap.count > k {
heap.pop()
}
}
// Extract the k most frequent elements from the heap
var result = [Int]()
while !heap.isEmpty {
result.append(heap.pop()!.0)
}
return result.reversed()
}
func longestConsecutive(_ nums: [Int]) -> Int {
var longestConSeq = 0
let set = Set(nums)
for num in set {
if !set.contains(num - 1) {
// new min element
var currentConSeq = 1
var currentNum = num
while set.contains(currentNum + 1) {
currentConSeq += 1
currentNum += 1
}
longestConSeq = max(longestConSeq, currentConSeq)
}
}
return longestConSeq
}
}
func sort(_ nums: [Int]) -> [Int] {
print(nums)
let sorted = quickSort(m: nums)
return sorted
}
func quickSort(m: [Int]) -> [Int] {
if m.count < 1 {
return m
}
let pivot = m[m.count / 2]
let less = m.filter { $0 < pivot }
let equal = m.filter { $0 == pivot }
let more = m.filter { $0 > pivot }
return quickSort(m: less) + equal + quickSort(m: more)
}
func isPalindrome(_ s: String) -> Bool {
let s = s.lowercased().filter { (c: Character) -> Bool in c.isLetter || c.isNumber }
var left = 0
var right = s.count - 1
while left < right {
if s[s.index(s.startIndex, offsetBy: left)] != s[s.index(s.startIndex, offsetBy: right)] {
return false
}
left += 1
right -= 1
}
return true
}
func sortColors(nums: inout [Int]) {
// Count the number of 0's, 1's, and 2's
var counts = [Int](repeating: 0, count: 3)
print(counts)
for num in nums {
counts[num] += 1
}
// Overwrite the array with the sorted values
var index = 0
print(counts)
for (i, count) in counts.enumerated() {
for _ in 0 ..< count {
nums[index] = i
index += 1
}
}
}
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var counter: [Int: Int] = [:]
// print(nums)
for num in nums {
counter[num] = 1 + (counter[num] ?? 0)
}
print(counter)
let sortedKeys = counter.keys.sorted { $1 < $0 }
let sortedValues = sortedKeys.map { counter[$0]! }
print("sorted vales \(sortedValues)")
return Array(sortedValues[0 ..< k])
}
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
var dp = Array(repeating: Int.max, count: amount + 1)
dp[0] = 0
for coin in coins {
for i in coin ... amount {
// print("i: \(i), coin: \(coin), dp[i]: \(dp[i]), dp[i - coin]: \(dp[i - coin])")
if dp[i - coin] != Int.max {
dp[i] = min(dp[i], dp[i - coin] + 1)
}
}
}
return dp[amount] == Int.max ? -1 : dp[amount]
}
func productExceptSelf(_ nums: [Int]) -> [Int] {
var answer = [Int]()
for (index, num) in nums.enumerated() {
var numsCopy = nums
numsCopy.remove(at: index)
print(num, numsCopy)
answer.append(numsCopy.reduce(1, *))
// answer[num] = numsCopy.reduce(1, *)
}
return answer
}
func productExceptSelf2(_ nums: [Int]) -> [Int] {
print(nums)
var result = [Int](repeating: 1, count: nums.count)
var left = 1
var right = 1
for i in 0 ..< nums.count {
result[i] *= left
// print("result", result)
left *= nums[i]
// print("left", left)
// print("left \(left) result", result)
}
for i in (0 ..< nums.count).reversed() {
result[i] *= right
right *= nums[i]
// print("right \(right) result", result)
// print("right", right)
}
return result
}
func containsDuplicate(_ nums: [Int]) -> Bool {
var nums = nums
nums.sort()
var left = 0
var right = 1
while right < nums.count {
if nums[left] == nums[right] {
return true
}
left += 1
right += 1
}
return false
}
func climbStairs(_ n: Int) -> Int {
if n <= 2 {
return n
}
var a = 1
var b = 2
for _ in 2 ..< n {
let c = a + b
a = b
b = c
}
return b
}
func maxProfit(_ prices: [Int]) -> Int {
var maxProfit = 0
var minPrice = Int.max
for price in prices {
if price < minPrice {
minPrice = price
} else if price - minPrice > maxProfit {
maxProfit = price - minPrice
}
}
return maxProfit
}
func search(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = (left + right) / 2
if target == nums[mid] {
return mid
}
if target > nums[mid] {
left = mid + 1
} else if target > nums[mid] {
right = mid - 1
}
}
return 0
}
}
// print(Solution().productExceptSelf([1, 2, 3, 4]))
// print(Solution().productExceptSelf([-1, 1, 0, -3, 3]))
// print(Solution().productExceptSelf2([1, 2, 3, 4]))
// print(Solution().containsDuplicate([1, 2, 3, 1]))
// print(Solution().climbStairs(3))
// print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))
// print(Solution().search([-1, 0, 3, 5, 9, 12], 9))
// print(Solution().productExceptSelf2([-1, 1, 0, -3, 3]))
// print(Solution().coinChange([1, 2, 5], 11))
// print(Solution().topKFrequent([1, 1, 1, 2, 2, 3], 2))
// var nums = [2, 0, 1, 1, 0, 2, 1]
// Solution().sortColors(nums: &nums)
// print(nums) // Output: [0, 0, 1, 1, 1, 2, 2]
print(Solution().sort([2, 0, 1, 1, 0, 2, 1]))
// Problem: Write a function that takes a string as input and checks whether it can be a valid palindrome by removing at most one character from it.
func isPalindromeOneLess(_ s: String) -> Bool {
for index in 0 ..< s.count {
var s2 = s
let indexls = s2.index(s2.startIndex, offsetBy: index)
s2.remove(at: indexls)
var left = 0
var right = s2.count - 1
while left <= right {
let ls = s2.index(s2.startIndex, offsetBy: left)
let rs = s2.index(s2.startIndex, offsetBy: right)
if s2[ls] != s2[rs] { break }
left += 1
right -= 1
}
if left > right {
return true
}
}
return false
}
// Problem: Reverse words in string
func reverseWords(_ s: String) -> String {
var words = s.components(separatedBy: " ")
var left = 0
var right = words.count - 1
while left < right {
words.swapAt(left, right)
left += 1
right -= 1
}
return words.joined(separator: " ")
}
// Problem: Sum of Three Values
// Brute force
//
// optimizations
// 1. sort nums and move i and j intelligently
func hasSumOfThreeValues(_ target: Int, nums: [Int]) -> Bool {
let arrSequence = 0 ..< nums.count
let minusFirstArrSequence = arrSequence.dropFirst()
let newTarget = target - nums[0]
for i in minusFirstArrSequence {
for j in minusFirstArrSequence.reversed() {
if nums[i] + nums[j] == newTarget {
return true
}
}
}
return false
}
class StreamingDiscounts {
let discounts = ["hbo", "netflix", "disney"]
// for (i,item) in discounts.enumerated() {
// print(i)
// print(item)
//
func doSomething() {
for i in 0 ..< discounts.count {
print(discounts[i])
for e in (0 ... discounts[i].count - 1).reversed() {
print(e, terminator: ",")
print(discounts[i][discounts[i].index(discounts[i].startIndex, offsetBy: e)])
}
for c in 0 ..< discounts[i].count {
print(c, terminator: ",")
// access characters in string using index
// do not print in new line
print(discounts[i][discounts[i].index(discounts[i].startIndex, offsetBy: c)])
}
}
}
}
// document the code above
// create a class called Discounts
func reverse(strings: [String]) -> [String] {
var result: [String] = []
for string in strings {
var reversedString = ""
for c in string.reversed() {
reversedString += String(c)
}
result.append(reversedString)
}
return result
}
// Problem: Valid Palindrome
func isPalindrome(_ str: String) -> Bool {
for i in 0 ..< str.count {
for j in (0 ..< str.count).reversed() {
if i == j {
let c = str.index(str.startIndex, offsetBy: i)
let d = str.index(str.startIndex, offsetBy: j)
return str[c] == str[d]
}
}
}
return false
}
// PROBLEM: Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
func containsDuplicate(_ nums: [Int]) -> Bool {
var set = Set<Int>()
for num in nums {
if set.contains(num) {
return true
}
set.insert(num)
}
return false
}
// Two pointer approach
func containsDuplicateTwoPointer(_ nums: [Int]) -> Bool {
var nums = nums
nums.sort()
var left = 0
var right = 1
while right < nums.count {
if nums[left] == nums[right] {
return true
}
left += 1
right += 1
}
return false
}
// print(isPalindrome("racecar"))
// assert(isPalindrome("racecar"),true)
// print(StreamingDiscounts().doSomething())
// print(hasSumOfThreeValues(11,nums:[1,2,3,4,5]))
// print(hasSumOfThreeValues(41,nums:[1,2,3,4,5]))
// print(reverseWords( "The quick brown fox")) // should print "fox brown quick The"
// print(reverseWords( "Hello, world!")) // should print "world! Hello,"
// print(reverseWords( "abc def ghi")) // should print "ghi def abc"
// print(isPalindromeOneLess( "RACEACAR"))
// assert(isPalindromeOneLess("RACEACAR"), true)
assert(containsDuplicate([1, 2, 3, 4, 5]) == false, "should be false")
assert(containsDuplicateTwoPointer([1, 2, 3, 4, 5]) == false, "should be false")
assert(containsDuplicate([1, 2, 3, 4, 4]) == true, "should be true")
assert(containsDuplicateTwoPointer([1, 2, 3, 4, 4]) == true, "should be true")
// arraysNext.swift
Solution.testNext()
Solution.printNext()
class Solution {
static func testNext() {
// let s = Solution()
// s.smallerNumbersThanCurrent([6,5,4,8])
}
static func printNext() {
let s = Solution()
// print("SOLUTION -", s.smallerNumbersThanCurrent([6,5,4,8]))
// print("SOLUTION -", s.smallerNumbersThanCurrent([7,7,7,7]))
print("SOLUTION -", s.happyNumber(num: 28))
}
// Write an algorithm to determine if a number is happy.
//
// A happy number is a number defined by the following process:
//
// Starting with any positive integer, replace the number by the sum of the squares of its digits.
// Repeat the process until the number equals 1
// (where it will stay), or it loops endlessly in a cycle which does not include 1
// Those numbers for which this process ends in 1 are happy. Return TRUE if n is a happy number, and FALSE if not.
func happyNumber(num: Int) -> Bool {
var slow = num
var fast = num
while true {
slow = squareSum(slow)
fast = squareSum(fast)
fast = squareSum(fast)
if fast == 1 {
return true
}
if slow == fast {
return false
}
}
}
func squareSum(_ num: Int) -> Int {
var n = num
var sum = 0
while n > 0 {
let digit = n % 10
sum += digit * digit
n /= 10
}
return sum
}
// Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
func smallerNumbersThanCurrent(_ nums: [Int]) -> [Int] {
var smaller = [Int]()
for i in 0 ..< nums.count {
var counter = [Int]()
for j in 0 ..< nums.count {
// print(nums[i],nums[j], terminator: " ")
if j != i, nums[j] < nums[i] {
// print("<")
counter.append(nums[j])
}
}
smaller.append(counter.count)
}
return smaller
}
// PROBLEM: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
func twoSumKK(_ nums: [Int], _ target: Int) -> [Int] {
var result = [Int]()
for i in 0 ..< nums.count {
for j in i + 1 ..< nums.count {
if nums[i] + nums[j] == target {
result.append(i)
result.append(j)
}
}
}
return result
}
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
// declare empty int array named numbersResult
var numbersResult = [Int]()
// loop through nums array
for (index, num) in nums.enumerated() {
// loop through nums array again
for (index2, num2) in nums.enumerated() {
// check if num + num2 == target
if num + num2 == target {
// check if index != index2
if index != index2 {
// append index and index2 to numbersResult
numbersResult.append(index)
numbersResult.append(index2)
// return numbersResult
return numbersResult
}
}
}
}
// return empty array
return []
}
}
// print(Solution().twoSumKK([2,7,11,15], 9))
// PROBLEM: We can’t sell before buying a stock, that is, the array index at which stock is bought will always be less than the index at which the stock is sold.
// SOLUTION: We can use a greedy approach to solve this problem. We will keep track of the minimum price of the stock and the maximum profit we can make by buying and selling the stock. We will iterate over the array and update the minimum price and maximum profit accordingly.
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max
var maxProfit = 0
for price in prices {
minPrice = min(minPrice, price)
maxProfit = max(maxProfit, price - minPrice)
}
return maxProfit
}
// print(maxProfit([7, 1, 5, 3, 6, 4]))
// PROBLEM: Given an array of positive integers nums and a positive integer target, find the window size of the shortest contiguous subarray whose sum is greater than or equal to the target value. If no subarray is found, 0 is returned.
func shortestTarget(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = 0
var shortest = 0
while right < nums.count {
let window = nums[left ... right]
let sum = window.reduce(0, +)
print(window, sum)
if sum >= target {
if shortest == 0 {
shortest = window.count
} else {
shortest = min(shortest, window.count)
}
left += 1
} else {
right += 1
}
}
return shortest
}
// print(shortestTarget([1,2,3,4,5], 11)
// print(shortestTarget([1,2,7,1,8], 9))
// print(shortestTarget([7,2,4,6,5,8], 6))
// PROBLEM: Given a string, inputString find the longest substring without repeating characters, and return the length of that longest substring.
func longestNonRepeatingSubString(S: String) -> String {
var longest = ""
let s = Array(S)
var left = 0
var right = 0
var seenString = ""
while right < s.count {
if !seenString.contains(String(s[right])) {
seenString.append(String(s[right]))
right += 1
} else {
if seenString.count > longest.count {
longest = seenString
}
seenString = ""
left += 1
right = left
}
}
if seenString.count > longest.count {
longest = seenString
}
return longest
}
func longestNonRepeatingSubString1(S: String) -> String {
// let longest = ""
let s = Array(S)
let left = 0
var right = s.count - 1
var seenString = ""
while left <= right {
print(s[right], right)
if seenString.contains(String(s[right])) {
print("seend")
break
} else {
seenString.append(String(s[right]))
}
// left += 1
right -= 1
}
return seenString
}
// print(longestNonRepeatingSubString(S: "bbbbbbb"))
// PROBLEM: Given two strings—s and t, find the smallest window substring of t. The smallest window substring is the shortest sequence of characters in s that includes all of the characters present in t. The frequency of each character in this sequence should be greater than or equal to the frequency of each character in t. The order of the characters doesn’t matter here.
func minWindowSubstring(s: String, t: String) -> String {
// Initialize left and right pointers
var left = 0
var right = 0
// Initialize a dictionary to store the frequency of each character in t
var tCharCounts = [Character: Int]()
for c in t {
tCharCounts[c] = (tCharCounts[c] ?? 0) + 1
}
// Initialize variables to store the minimum window size and the corresponding window
var minWindowSize = Int.max
var minWindow = ""
// Slide the window until the right pointer reaches the end of s
while right < s.count {
// Decrement the frequency of the character at the right pointer in the dictionary
let c = s[s.index(s.startIndex, offsetBy: right)]
if let count = tCharCounts[c] {
tCharCounts[c] = count - 1
if tCharCounts[c] == 0 {
tCharCounts.removeValue(forKey: c)
}
}
// If the dictionary is empty, we have found a valid window
if tCharCounts.isEmpty {
// Update the minimum window size and the corresponding window if necessary
if right - left + 1 < minWindowSize {
minWindowSize = right - left + 1
minWindow = String(s[s.index(s.startIndex, offsetBy: left) ... s.index(s.startIndex, offsetBy: right)])
}
// Move the left pointer to the right until the character at the left pointer is no longer in the dictionary or the dictionary is not empty
while left < right, !tCharCounts.keys.contains(s[s.index(s.startIndex, offsetBy: left)]) {
left += 1
}
// Remove the character at the left pointer from the dictionary
let c = s[s.index(s.startIndex, offsetBy: left)]
if let count = tCharCounts[c] {
tCharCounts[c] = count + 1
if tCharCounts[c] ?? 0 > 0 {
tCharCounts.removeValue(forKey: c)
}
}
// Move the left pointer to the right
left += 1
}
// Increment the right pointer
right += 1
}
return minWindow
}
// PROBLEM: Given a string s that represents a DNA sequence, and a number k, return all the contiguous sequences (substrings) of length k that occur more than once in the string. The order of the returned subsequences does not matter. If no repeated subsequence is found, the function should return an empty set.
func findRepeatedSubsequences(_ s: String, _ k: Int) -> [String] {
var result: [String] = []
var map: [String: Int] = [:]
for i in 0 ..< s.count - k + 1 {
let sub = String(s[s.index(s.startIndex, offsetBy: i) ..< s.index(s.startIndex, offsetBy: i + k)])
if let count = map[sub] {
if count == 1 {
result.append(sub)
}
map[sub] = count + 1
} else {
map[sub] = 1
}
}
return result
}
// PROBLEM: Given strings str1 and str2, find the minimum (contiguous) substring subStr of str1, such that every character of str2 appears in subStr in the same order as it is present in str2.
func minWindow(_ S: String, _ T: String) -> String {
let s = Array(S)
let t = Array(T)
var minWindow = ""
for i in 0 ..< s.count {
for j in i ..< s.count {
let window = s[i ... j]
var count = 0
for c in t {
if window.contains(c) {
count += 1
}
if count == t.count {
let wString = String(window)
if minWindow == "" || wString.count < minWindow.count {
minWindow = wString
}
}
if count == t.count {
break
}
}
}
}
return minWindow
}
// PROBLEM: Given an integer array and a window of size w, find the current maximum value in the window as it slides through the entire array.
func maximumValueInSlidingWindow(
_ k: Int,
nums: [Int]
) -> [Int] {
var left = 0
var right = k
var maxValues = [Int]()
while right <= nums.count {
let window = nums[left ..< right]
let max = window.max()!
maxValues.append(max)
left += 1
right += 1
}
return maxValues
}
// print(maximumValueInSlidingWindow(3, nums: [1,2,3,4,5,6,7,8,9,10]))
// print(minWindow("abcdebdde", "bde")) // should print "bcde"
// print(minWindow("abcdebdde", "bdea")) // should print ""
// print(minWindow("abcdefg", "df")) // should print "def"
// print(findRepeatedSubsequences("AAAAACCCCCAAAAACCCCCC",8))
// binancetest.swift
func getAnagramPeriod(input_str: String) -> Int {
// Write your code here
var frequency = [Character: Int]()
for c in input_str {
if frequency[c] != nil {
frequency[c]! += 1
} else {
frequency[c] = 1
}
}
print(frequency)
var minLength = 0
for (c,f) in frequency {
print(c,f,minLength)
minLength += String(f).count
}
return minLength
}
print(getAnagramPeriod(input_str: "bbaaababababaabb"))
// print(smallestRepeatingPattern(input_str:"abcbcacba"))
//
// cardeck.swift
//
// Design a deck of cards
// 1. Create a card class
// 2. Create a deck class
// 3. Create a player class
// 4. Create a game class
import Foundation
// 1. Create a card class that conforms to Equatable
class Card {
var color: String
var value: String
var image: String
init(color: String, value: String, image: String) {
self.color = color
self.value = value
self.image = image
}
}
extension Card: Equatable {
static func == (lhs: Card, rhs: Card) -> Bool {
return
lhs.value == rhs.value
}
}
// 2. Create a deck class
class Deck {
var cards: [Card] = []
init() {
let colors = ["Hearts", "Diamonds", "Spades", "Clubs"]
let values = ["2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"]
for color in colors {
for value in values {
let card = Card(color: color, value: value, image: "\(value)_of_\(color)")
cards.append(card)
}
}
}
func drawCard() -> Card {
let randomIndex = Int.random(in: 0..<cards.count)
return cards.remove(at: randomIndex)
}
}
// 3. Create a player class
class Player {
var name: String
var hand: [Card] = []
init(name: String) {
self.name = name
}
func draw(deck: Deck) {
let card = deck.drawCard()
hand.append(card)
}
func discard(card: Card) {
if let index = hand.firstIndex(of: card) {
hand.remove(at: index)
}
}
}
// 4. Create a game class
class Game {
var deck: Deck
var players: [Player] = []
init() {
deck = Deck()
}
func addPlayer(player: Player) {
players.append(player)
}
func deal() {
for _ in 1...5 {
for player in players {
player.draw(deck: deck)
}
}
}
func play() {
for player in players {
for card in player.hand {
print(card.image)
}
}
}
}
// Create a Game
let game = Game()
// closures.swift
let counter = 1
let c = {
print(counter)
}
c()
class ExampleClass {
var counter = 1
lazy var closure: () -> Void = { [weak self] in
guard let self = self else {
return
}
print(self.counter)
}
}
// codable.swift
import Foundation
// Chapter 1 - Non trivial example
let json1 = """
[
{
"name": {
"first_name": "Taylor",
"last_name": "Swift"
},
"age": 26
}
]
"""
// User struct - root
// conform to Codable
struct User: Codable {
var name: String
var age: Int
enum CodingKeys: String, CodingKey {
case name, age
}
init(from decoder: Decoder) throws {
let container = try decoder.container(keyedBy: CodingKeys.self)
let nameContainer = try container.nestedContainer(keyedBy: Name.CodingKeys.self, forKey: .name)
let firstName = try nameContainer.decode(String.self, forKey: .firstName)
let lastName = try nameContainer.decode(String.self, forKey: .lastName)
name = firstName + " " + lastName
age = try container.decode(Int.self, forKey: .age)
}
func encode(to encoder: Encoder) throws {
var container = encoder.container(keyedBy: CodingKeys.self)
var nameContainer = container.nestedContainer(keyedBy: Name.CodingKeys.self, forKey: .name)
let names = name.components(separatedBy: " ")
try nameContainer.encode(names[0], forKey: .firstName)
try nameContainer.encode(names[1], forKey: .lastName)
try container.encode(age, forKey: .age)
}
}
// Name struct - nested
struct Name: Codable {
var firstName: String
var lastName: String
enum CodingKeys: String, CodingKey {
case firstName = "first_name"
case lastName = "last_name"
}
}
let data = Data(json1.utf8)
let decoder = JSONDecoder()
let users = try decoder.decode([User].self, from: data)
print(users)
/// Chapter 2 follows a more complicated example with nested structures, mismatched keys, and timestamps.
let json2 = """
{
"aircraft": {
"identification": "NA12345",
"color": "Blue/White"
},
"route": ["KTTD", "KHIO"],
"departure_time": {
"proposed": "2018-04-20T15:07:24-07:00",
"actual": "2018-04-20T15:07:24-07:00"
},
"flight_rules": "IFR",
"remarks": null
}
""".data(using: .utf8)!
public struct FlightPlan: Codable {
public var aircraft: Aircraft
public var route: [String]
public var flightRules: FlightRules
private var departureDates: [String: Date]
public var proposedDepartureDate: Date? {
departureDates["proposed"]
}
public var actualDepartureDate: Date? {
departureDates["actual"]
}
public var remarks: String?
private enum CodingKeys: String, CodingKey {
case aircraft
case flightRules = "flight_rules"
case route
case departureDates = "departure_time"
case remarks
}
}
public struct Aircraft: Codable {
public var identification: String
public var color: String
}
public enum FlightRules: String, Codable {
case visual = "VFR"
case instrument = "IFR"
}
let decoder2 = JSONDecoder()
decoder2.dateDecodingStrategy = .iso8601
let plan = try! decoder2.decode(FlightPlan.self, from: json2)
/// 3 - On the fly
let json3 = """
{
"coordinates": [
{
"latitude": 37.332,
"longitude": -122.011
},
[-122.011, 37.332],
"37.332, -122.011"
]
}
""".data(using: .utf8)!
import Foundation
public struct Coordinate: Decodable {
public var latitude: Double
public var longitude: Double
public var elevation: Double?
private enum CodingKeys: String, CodingKey {
case latitude
case longitude
case elevation
}
public init(from decoder: Decoder) throws {
if let container =
try? decoder.container(keyedBy: CodingKeys.self)
{
latitude =
try container.decode(Double.self, forKey: .latitude)
longitude =
try container.decode(Double.self, forKey: .longitude)
elevation =
try container.decodeIfPresent(Double.self,
forKey: .elevation)
} else if var container = try? decoder.unkeyedContainer() {
longitude = try container.decode(Double.self)
latitude = try container.decode(Double.self)
elevation = try container.decodeIfPresent(Double.self)
} else if let container = try? decoder.singleValueContainer() {
let string = try container.decode(String.self)
let scanner = Scanner(string: string)
scanner.charactersToBeSkipped = CharacterSet(charactersIn: "[ ,]")
var longitude = Double()
var latitude = Double()
guard scanner.scanDouble(&longitude),
scanner.scanDouble(&latitude)
else {
throw DecodingError.decoding
// dataCorruptedError(
// in: container,
// debugDescription: "Invalid coordinate string"
// )
}
self.latitude = latitude
self.longitude = longitude
elevation = nil
} else {
let context = DecodingError.decoding
throw context
}
}
}
let decoder3 = JSONDecoder()
let coordinates = try! decoder.decode([String: [Coordinate]].self, from: json3)["coordinates"]
print(coordinates!)
/// 4 - AnyDecodable
public struct AnyDecodable: Decodable {
public let value: Any
public init(_ value: Any?) {
self.value = value ?? ()
}
public init(from decoder: Decoder) throws {
let container = try decoder.singleValueContainer()
if container.decodeNil() {
value = ()
} else if let bool = try? container.decode(Bool.self) {
value = bool
} else if let int = try? container.decode(Int.self) {
value = int
} else if let uint = try? container.decode(UInt.self) {
value = uint
} else if let double = try? container.decode(Double.self) {
value = double
} else if let string = try? container.decode(String.self) {
value = string
} else if let array = try? container.decode([AnyDecodable].self) {
value = array.map(\.value)
} else if let dictionary = try? container.decode([String: AnyDecodable].self) {
value = dictionary.mapValues { $0.value }
} else {
throw DecodingError.decoding
// dataCorruptedError(in: container, debugDescription: "AnyCodable value cannot be decoded")
}
}
}
import Foundation
let json4 = """
{
"title": "Sint Pariatur Enim ut Lorem Eiusmod",
"body": "Cillum deserunt ullamco minim nulla et nulla ea ex eiusmod ea exercitation qui irure irure. Ut laboris amet Lorem deserunt consequat irure dolore quis elit eiusmod. Dolore duis velit consequat dolore. Qui aliquip ad id eiusmod in do officia. Non fugiat esse laborum enim pariatur cillum. Minim aliquip minim exercitation anim adipisicing amet. Culpa proident adipisicing labore enim ullamco veniam.",
"metadata": {
"key": "value"
}
}
""".data(using: .utf8)!
public struct Report: Decodable {
public var title: String
public var body: String
public var metadata: [String: AnyDecodable]
}
let decoder4 = JSONDecoder()
let report = try decoder4.decode(Report.self, from: json4)
print(report.title)
print(report.body)
print(report.metadata["key"] ?? "")
/// 5 - Safe Decodable
import Foundation
enum DecodingError: Error {
case decoding
}
struct Safe<Base: Decodable>: Decodable {
let value: Base?
init(from decoder: Decoder) throws {
do {
let container = try decoder.singleValueContainer()
self.value = try container.decode(Base.self)
} catch {
self.value = nil
}
}
}
extension JSONDecoder {
func decodeSafelyArray<T: Decodable>(of type: T.Type, from data: Data) -> [T] {
guard let array = try? decode([Safe<T>].self, from: data) else { return [] }
return array.compactMap { $0.value }
}
}
/// 6 -
import Foundation
let json6 = """
{
"points": ["KSQL", "KWVI"],
"KSQL": {
"code": "KSQL",
"name": "San Carlos Airport"
},
"KWVI": {
"code": "KWVI",
"name": "Watsonville Municipal Airport"
}
}
""".data(using: .utf8)!
public struct Route: Decodable {
public struct Airport: Decodable {
public var code: String
public var name: String
}
public var points: [Airport]
private struct CodingKeys: CodingKey {
var stringValue: String
var intValue: Int? {
return nil
}
init?(stringValue: String) {
self.stringValue = stringValue
}
init?(intValue: Int) {
return nil
}
static let points =
CodingKeys(stringValue: "points")!
}
public init(from coder: Decoder) throws {
let container = try coder.container(keyedBy: CodingKeys.self)
var points: [Airport] = []
let codes = try container.decode([String].self, forKey: .points)
for code in codes {
let key = CodingKeys(stringValue: code)!
let airport = try container.decode(Airport.self, forKey: key)
points.append(airport)
}
self.points = points
}
}
let decoder6 = JSONDecoder()
let route = try decoder6.decode(Route.self, from: json6)
print(route.points.map{ $0.code })
//
// concurrency.swift
//
import Foundation
// let group = DispatchGroup()
// MARK: - Concurrency
// 3 - Structured Concurrency
// 3.1 - Tasks
// 3.1.1 - Creating Tasks
// 3.1.2 - Task Priority
// 3.1.3 - Task Cancellation
// 3.1.4 - Task Options
// 3.1.5 - Task Groups
// 3.1.6 - Task Local Values
// 3.1.7 - Task Handle
// 3.1.8 - Task Status
// 3.1.9 - Task Execution Order
// 3.1.10 - Task and Dispatch Queue
// 3.1.11 - Task and Operation Queue
// 3.1.12 - Task and Run Loop
// 3.1.13 - Task and Thread
// 3.1.14 - Task and GCD
// 3.1.15 - Task and Locks
// 3.1.16 - Task and Actor
// 3.1.17 - Task and Dispatch Group
// 3.1.18 - Task and Dispatch Semaphore
// 3.1.19 - Task and Dispatch Work Item
// 3.1.20 - Task and Dispatch Source
// 3.1.21 - Task and Dispatch Barrier
// 3.1.22 - Task and Dispatch I/O
// 3.1.23 - Task and Dispatch Data
func task1() async {
print("Task 1")
}
// 2 - New structured concurrency
let q = DispatchQueue(label: "com.example.myqueue")
let f = Flight()
let writeQ = DispatchQueue(label: "com.example.writequeue")
// q.async {
// print(" \(f.bookSeat())")
// }
// writeQ.async {
// print(" \(f.getAvailableSeats())")
// }
class Flight {
var company: String = "American Airlines"
var availableSeats: [String] = ["1A", "1B", "1C"]
func getAvailableSeats() -> [String] {
return availableSeats
}
func bookSeat() -> String {
let bookedSeat = availableSeats.removeFirst()
return "Seat \(bookedSeat) booked"
}
}
// 1 - Command line concurrency with GCD
fetchFeed { feed, _ in
// print("ok")
// print(feed!)
exit(EXIT_SUCCESS)
}
func fetchFeed(completion: @escaping (String?, Error?) -> Void) {
print("start")
// group.enter()
URLSession.shared.dataTask(with: URL(string: "https://jsonplaceholder.typicode.com/posts")!) { data, _, _ in
// group.leave()
let feed = String(data: data!, encoding: .utf8)
DispatchQueue.main.async {
completion(feed, nil)
}
}.resume()
}
dispatchMain()
//
// hackerrank.swift
//
import Foundation
print(getMoviesTitles(input:["spi"]))
func getMoviesTitles(input: [String]) -> [[String]] {
var movieTitles = [[String]]()
var searchResults = [String: [String]]()
let baseURL = "https://jsonmock.hackerrank.com/api/moviesdata/search/?Title="
for inputString in input {
if let previousResults = searchResults[inputString] {
movieTitles.append(previousResults)
} else {
var movieTitle = [String]()
let urlString = baseURL + inputString
guard let url = URL(string: urlString) else { return movieTitles }
var sema = DispatchSemaphore( value: 0 )
let task = URLSession.shared.dataTask(with: url) { (data, response, error) in
if let error = error {
print(error)
return
}
guard let data = data else { return }
do {
let json = try JSONSerialization.jsonObject(with: data, options: [])
if let dict = json as? [String: Any],
let data = dict["data"] as? [[String: Any]] {
for movie in data {
if let title = movie["Title"] as? String {
movieTitle.append(title)
}
}
}
} catch {
print(error)
}
searchResults[inputString] = movieTitle
movieTitles.append(movieTitle)
sema.signal()
}
task.resume()
sema.wait()
}
}
return movieTitles
}
//
// hashtable.swift
//
// Solution
class Solution {
static let s = Solution()
static func test() {
var table = HashTable<String, Int>(capacity: 10)
assert(table.description != "", "Failed to create hashtable")
table["a"] = 1
print(table.description)
}
}
public struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
init(capacity: Int) {
assert(capacity > 0)
buckets = Array<Bucket>(repeating:[], count: capacity)
}
private func index(key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
public subscript(key: Key) -> Value? {
get {
return get(key: key)
}
set {
if let value = newValue {
// update
update(key: key, value: value)
}
else {
// remove
}
}
}
private func get(key: Key) -> Value? {
for element in buckets[index(key: key)] {
if element.key == key {
return element.value
}
}
}
private mutating func update(key: Key, value: Value) {
for (index, element) in buckets[index(key: key)].enumerated() {
if element.key == key {
buckets[index(key: key)].value = value
return
}
}
buckets[index(key: key)].append((key: key, value: value))
}
}
extension HashTable: CustomStringConvertible {
public var description: String {
return buckets.description
}
}
// Hashes, Stacks, Binary Search
protocol HashMappable {
var hashValue: Int { get }
mutating func put(key: String, value: Int)
func get(key: String) -> Int?
mutating func remove(key: String) -> Int?
}
struct HashMapDictionary: HashMappable {
var map: [String: Int]
var hashValue: Int {
map.hashValue
}
mutating func put(key: String, value: Int) {
map[key] = value
}
func get(key: String) -> Int? {
map[key]
}
mutating func remove(key: String) -> Int? {
map.removeValue(forKey: key)
}
}
extension HashMapDictionary: Equatable {
static func == (lhs: HashMapDictionary, rhs: HashMapDictionary) -> Bool {
lhs.hashValue == rhs.hashValue
}
}
extension HashMapDictionary: CustomStringConvertible {
var description: String {
map.description
}
}
//
// linkedlists.swift
//
import XCTest
Solution.testNext()
Solution.printNext()
// Node
class Node {
var value: Int
var next: Node?
init(value: Int, next: Node? = nil) {
self.value = value
self.next = next
}
// print list
func printList() {
var node = self
while let next = node.next {
print(node.value)
node = next
}
print(node.value)
}
// Implement a function to check if a linked list is empty
func isEmpty() -> Bool {
next == nil
}
func size() -> Int {
var count = 1
var current = self
while current.next != nil {
count += 1
current = current.next!
}
return count
}
func addAtHead(_ value: Int) -> Node {
let newNode = Node(value: value)
newNode.next = self
return newNode
}
func addAtTail(_ value: Int) -> Node {
var current = self
while current.next != nil {
current = current.next!
}
current.next = Node(value: value)
return self
}
@discardableResult func addAtIndex(_ index: Int, _ value: Int) -> Node {
if index == 0 {
return addAtHead(value)
}
var current = self
var i = 0
while i < index - 1 {
current = current.next!
i += 1
}
let newNode = Node(value: value)
newNode.next = current.next
current.next = newNode
return self
}
func reverse() -> Node {
var current = self
var previous: Node?
var next: Node?
while current.next != nil {
next = current.next
current.next = previous
previous = current
current = next!
}
current.next = previous
return current
}
func hasCycle() -> Bool {
var current = self
var slow: Node? = current
var fast: Node? = current
while fast != nil, fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}
func middleNode() -> Node {
var slow = self
var fast = self
while fast.next != nil, fast.next?.next != nil {
slow = slow.next!
fast = fast.next!.next!
}
return slow
}
func removeNthFromEnd(head: Node?, n: Int) -> Node? {
var fast = head
var slow = head
for _ in 1 ... n {
fast = fast?.next
}
if fast == nil {
return head?.next
}
while fast?.next != nil {
fast = fast?.next
slow = slow?.next
}
slow?.next = slow?.next?.next
return head
}
func removeNthFromEnd(_ head: Node?, _ n: Int) -> Node? {
var slow = head
var fast = head
var counter = 0
for i in 1 ... n {
fast = fast?.next
print("first")
counter += 1
}
// now fast is at n
if fast?.next == nil {
return head // improve
}
print("counter \(counter)")
if counter > n {
return head
}
while fast?.next != nil {
slow = slow?.next!
fast = fast?.next!
print("final")
}
slow?.next = slow?.next?.next
return head
}
}
class Solution {
static let s = Solution()
static let testLinkedList = {
// initialize linked list with test nodes with integer values all even
// test case 1
// LinkedList(head: Node(value: 0, next: Node(value: 1, next: Node(value: 2))))
// test case 2
let one = Node(value: 1)
let two = Node(value: 2, next: one)
// one.next = two
return LinkedList(head: Node(value: 0, next: one))
}()
static func testNext() {
// testFindMiddleNode()
// testIsPalindrome()
// testEmpty()
// testSize()
// testAddAtHead()
print("testAddAtIndex")
testAddAtIndex()
print("test reverse")
let list = Node(value: 0, next: Node(value: 1, next: Node(value: 2)))
list.printList()
list.reverse().printList()
print("test hasCycle")
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
let node4 = Node(value: 4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 // create a loop by linking node4 to node2
if node1.hasCycle() {
print("has cycle")
} else {
print("no cycle")
}
print("test mid")
let list2 = Node(value: 0, next: Node(value: 1, next: Node(value: 2, next: Node(value: 3))))
print(list2.middleNode().value)
// test remoce from nth node
print(Solution())
}
static func testAddAtIndex() {
let list = Node(value: 0, next: Node(value: 1, next: Node(value: 2)))
list.addAtIndex(1, 3)
list.printList()
}
static func testAddAtHead() {
let head = Node(value: 0)
print(head.addAtHead(1).addAtHead(2).printList())
// print(head.value)
}
static func testEmpty() {
let empty = Node(value: 1, next: nil)
assert(empty.isEmpty() == true)
}
static func testSize() {
let empty = Node(value: 1, next: nil)
assert(empty.size() == 1)
let one = Node(value: 1)
let two = Node(value: 2, next: one)
assert(two.size() == 2)
}
static func testIsPalindrome() {
let list = LinkedList()
// empty
assert(list.isPalindrome() == false)
// assert(list.isPalindrome() == true)
// Test list with one element
list.head = Node(value: 1)
// list.head?.next = Node(value: 2)
assert(list.isPalindrome() == true)
// Test list with two element
list.head = Node(value: 1, next: Node(value: 2))
assert(list.isPalindrome() == false)
// Test list with two element palindrome
list.head = Node(value: 1, next: Node(value: 1))
assert(list.isPalindrome() == true)
print("testIsPalindrome passed")
}
static func testFindMiddleNode() {
let list = LinkedList()
// Test empty list
var middleNode = list.findMiddleNode()
assert(middleNode == nil)
// Test list with one element
list.head = Node(value: 1)
middleNode = list.findMiddleNode()
assert(middleNode?.value == 1)
// Test list with two elements
list.head?.next = Node(value: 2)
middleNode = list.findMiddleNode()
assert(middleNode?.value == 2)
// Test list with three elements
list.head?.next?.next = Node(value: 3)
middleNode = list.findMiddleNode()
assert(middleNode?.value == 2)
// Test list with four elements
list.head?.next?.next?.next = Node(value: 4)
middleNode = list.findMiddleNode()
assert(middleNode?.value == 3)
}
static func printNext() {
// print("SOLUTION - \(testLinkedList.reverse()!.description)")
}
// Check if a linked list contains a cycle or not. If a cycle exists, return TRUE. Otherwise, return FALSE.
func hasCycle(_ list: LinkedList) -> Bool {
var slow = list.head
var fast = list.head
while fast != nil, fast?.next != nil {
print(slow?.value ?? "NA", terminator: " ")
print(fast?.value ?? "NA")
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
print(slow?.value ?? "NA", terminator: " ")
print(fast?.value ?? "NA")
}
return false
}
}
// Linked List
class LinkedList {
var head: Node?
init(head: Node? = nil) {
self.head = head
}
// reverse
func reverse() -> LinkedList? {
var head = head
var p: Node?
var n: Node? = head?.next
while head != nil {
head?.next = p
p = head
head = n
n = head?.next
}
return LinkedList(head: p)
}
// For the given head of the linked list, find out if the linked list is a palindrome or not. Return TRUE if the linked list is a palindrome. Otherwise, return FALSE.
func isPalindrome() -> Bool {
if head == nil {
return false
}
if head?.next == nil {
return true
}
// find middle node
let middle = findMiddleNode()
// reverse second half
let reversed = LinkedList(head: middle).reverse()
// compare first half and second half
var first = head
var second = reversed?.head
while first != nil, second != nil {
if first?.value != second?.value {
return false
}
first = first?.next
second = second?.next
}
return true
}
// Given a singly linked list, return the middle node of the linked list. If the number of nodes in the linked list is even, return the second middle node.
func findMiddleNode() -> Node? {
guard head != nil else {
return nil
}
guard head?.next != nil else {
return head
}
var slow = head
var fast = head
while fast?.next != nil {
fast = fast?.next?.next
slow = slow?.next
}
return slow
}
}
extension LinkedList: Sequence {
// implement the makeIterator() method
func makeIterator() -> LinkedListIterator {
LinkedListIterator(currentNode: head)
}
}
// define the Iterator type
class LinkedListIterator: IteratorProtocol {
var currentNode: Node?
init(currentNode: Node?) {
self.currentNode = currentNode
}
// implement the next() method
func next() -> Node? {
defer { currentNode = currentNode?.next }
return currentNode
}
}
extension LinkedList: CustomStringConvertible {
var description: String {
var h = head
// traverse h and print value
var s = ""
while h != nil {
s += "\(h?.value ?? -1) "
h = h?.next
}
return s
}
}
import Foundation
print("Problem: Implement a min heap with extract_min and insert methods.")
struct MinHeap {
var arr: [Int] = []
func extract_min() -> Int {
arr.min { $0 < $1 } ?? 0
}
mutating func insert(_ item:Int) {
arr.append(item)
}
}
struct MinHeapTest {
static func testMinHeap() {
var h = MinHeap()
h.insert(10)
h.insert(3)
print(h.extract_min())
assert(h.extract_min() == 3)
}
}
MinHeapTest.testMinHeap()
//
// main2.swift
//
import Foundation
print("Problem: Compress a string such that 'AAABCCDDDD' becomes 'A3BC2D4'. Only compress the string if it saves space.")
struct CompressString {
func compress(_ str: String) -> String {
var compressed = ""
var lastChar: Character?
var charCount = 0
for char in str {
if char == lastChar {
charCount += 1
} else {
if let lastChar = lastChar {
compressed.append(lastChar)
compressed.append(String(charCount))
}
lastChar = char
charCount = 1
}
}
// if let lastChar = lastChar {
// compressed.append(lastChar)
// compressed.append(String(charCount))
// }
return compressed.count < str.count ? compressed : str // return the shorter of the two
}
}
struct CompressStringTest {
static func test() {
let cs = CompressString()
print(cs.compress("AAABCCDDDD"))
// assert(cs.compress("AAABCCDDDD") == "")
// assert(cs.compress("AAABCCDDDD") == "A3BC2D4")
}
}
CompressStringTest.test()
//
// stacks.swift
//
import XCTest
// valid parentheses
func isValid(_ s: String) -> Bool {
var stack: [Character] = []
for c in s {
if c == "(" {
stack.append(")")
} else if c == "{" {
stack.append("}")
} else if c == "[" {
stack.append("]")
} else if stack.isEmpty || stack.popLast() != c {
return false
}
}
return stack.isEmpty
}
u
// min stack - english description
struct MinStack {
var array = [Int]()
var minArray = [Int]()
mutating func push(_ val: Int) {
array.append(val)
minArray.append(min(val,minArray[0]))
}
mutating func pop() -> Int? {
minArray.popLast()
return array.popLast()
}
func getMin() -> Int {
minArray.last
}
func top() -> Int? {
array.last
}
}
// var stack = Stack<Int>()
// print(stack.push(10))
// print(stack.pop())
struct Stack<T> {
private var array: [T] = []
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
extension Stack: CustomStringConvertible {
public var description: String {
return array.description
}
}
// MARK: - Unit Tests
import XCTest
class StackTests: XCTestCase {
func testStack() {
let stack = Stack<Int>()
assert(stack.isEmpty == true)
// XCTAssertTrue(stack.isEmpty)
// XCTAssertEqual(stack.count, 0)
// XCTAssertNil(stack.top)
//
// stack.push(1)
// stack.push(2)
// stack.push(3)
//
// XCTAssertFalse(stack.isEmpty)
// XCTAssertEqual(stack.count, 3)
// XCTAssertEqual(stack.top, 3)
//
// XCTAssertEqual(stack.pop(), 3)
// XCTAssertEqual(stack.pop(), 2)
// XCTAssertEqual(stack.pop(), 1)
// XCTAssertNil(stack.pop())
// XCTAssertTrue(stack.isEmpty)
// XCTAssertEqual(stack.count, 0)
// XCTAssertNil(stack.top)
}
}
StackTests.defaultTestSuite.run()
//
// string-problem.swift
//
// Problem: Determine if a string is a permutation of another string
// Solution: Sort the strings and compare them
// Time Complexity: O(n log n)
// Space Complexity: O(n)
func isPermutation(s1: String, s2: String) -> Bool {
// Check if the strings have the same length
if s1.count != s2.count {
return false
}
// Create frequency maps for both strings
var s1Map = [Character: Int]()
var s2Map = [Character: Int]()
for c in s1 {
s1Map[c, default: 0] += 1
}
for c in s2 {
s2Map[c, default: 0] += 1
}
// Compare the frequency maps
return s1Map == s2Map
}
// Test the function
print(isPermutation(s1: "abc", s2: "cba")) // True
print(isPermutation(s1: "abc", s2: "def")) // False
print(isPermutation(s1: "abc", s2: "ab")) // False
print(isPermutation(s1: "abc", s2: "abcd")) // False
enum CardType {
case debit
case credit
}
protocol CardDetailsProtocol {
}
extension String: CardDetailsProtocol {
}
protocol Card {
associatedType CardDetails = CardDetailsProtocol
var cardDetails: CardDetails { get set }
var type: CardType { get set }
func validate(details: CardDetails)
}
struct Card1: Card {
var cardDetails: CardDetails = ""
func validate(details: String) {
//
}
typealias CardDetails = String
var type: CardType = .debit
}
//
// topproblems.swift
//
// print(Solution().majorityElement([2,2,1,1,1,2,2]))
// print test data for allDuplicates
// print(Solution().allDuplicates([4, 3, 2, 7, 8, 2, 3, 1]))
// print test data for maxProfit
// print(Solution().maxProfit([7,1,5,3,6,4]))
// print(Solution().maxProfit([7,6,4,3,1]))
// print test data for twoSum
// print(Solution().twoSum([2, 7, 11, 15], 9))
// print test data for sortedSquares
print(Solution().sortedSquares([-4,-1,0,3,10]))
class Solution {
// Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. could you find an O(n) solution using a different approach?
func sortedSquares(_ nums: [Int]) -> [Int] {
print(nums)
var result = [Int]()
var left = 0, right = nums.count - 1
while left <= right {
if abs(nums[left]) > abs(nums[right]) {
print("left: \(nums[left])")
result.append(nums[left] * nums[left])
left += 1
} else {
print("right: \(nums[right])")
result.append(nums[right] * nums[right])
right -= 1
}
print("result: \(result)")
}
return result.reversed()
}
// Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var result = [Int]()
var left = 0
var right = nums.count - 1
while left < right {
let sum = nums[left] + nums[right]
if sum == target {
result.append(left)
result.append(right)
return result
} else if sum < target {
left += 1
} else {
right -= 1
}
}
return result
}
// You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0
func maxProfit(_ prices: [Int]) -> Int {
print(prices)
var maxProfit = 0
var minPrice = Int.max
for price in prices {
print("price: \(price)", terminator: ", ")
if price < minPrice {
print("\(price) < \(minPrice)", terminator: " ")
minPrice = price
print("minPrice: \(minPrice)")
} else if price - minPrice > maxProfit {
print("\(price) - \(minPrice) > \(maxProfit)")
maxProfit = price - minPrice
print("maxProfit: \(maxProfit)")
}
}
return maxProfit
}
// Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
func allDuplicates(_ nums: [Int]) -> [Int] {
var dupes: [Int] = []
var nums = nums
print(nums)
for i in 0 ..< nums.count {
let index = abs(nums[i]) - 1
print("nums[\(i)] = \(nums[i])", terminator: " ")
print("nums[\(index)] = \(nums[index])", terminator: " ")
if nums[index] < 0 {
dupes.append(index + 1)
print("dupes: \(dupes)")
} else {
nums[index] *= -1
print("*nums[\(index)] = \(nums[index])", terminator: " ")
}
print("")
}
return dupes
}
// Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
func setZeroes(_: inout [[Int]]) {}
// find majority element
func majorityElement(_ nums: [Int]) -> Int {
var counts = [Int: Int]()
for i in 0 ..< nums.count {
if counts.contains(where: { $0.key == nums[i] }) {
counts[nums[i]]! += 1
} else {
counts[nums[i]] = 1
}
print(counts)
}
return counts.filter { $0.value > nums.count / 2 }.first!.key
}
// Convert 1d array into 2d array
func make2D(_ nums: [Int], _: Int, _ c: Int) -> [[Int]] {
// declare dictionary to save character counts
var result = [[Int]]()
var temp = [Int]()
var count = 0
for i in 0 ..< nums.count {
if count == c {
result.append(temp)
temp = [Int]()
count = 0
}
temp.append(nums[i])
count += 1
}
if temp.count > 0 {
result.append(temp)
}
return result
}
func make2DKK(_ nums: [Int], _: Int, _ n: Int) -> [[Int]] {
var twod = [[Int]]()
for (index, num) in nums.enumerated() {
if index % n == 0 {
twod.append([num])
} else {
twod[twod.count - 1].append(num)
}
}
return twod
}
// Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
// There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.
func findDuplicate(_ nums: [Int]) -> Int {
print(nums)
var slow = nums[0]
var fast = nums[0]
repeat {
print("slow: \(slow), fast: \(fast)")
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
fast = nums[0]
// slow = nums[0]
while slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
func findDuplicate2(_ nums: [Int]) -> Int {
var nums = nums
print(nums)
let rangeArray = Array(0 ... nums.count)
// var dupe = 0
for (index, num) in rangeArray.enumerated() {
print(index, num)
if let index = nums.firstIndex(of: num) {
nums.remove(at: index)
}
}
print(nums)
return nums.first ?? 0
}
}
// Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
func doSomething(nums: [Int]) -> Int? {
// var missing: Int?
var rangeArray = Array(0 ... nums.count)
print(rangeArray)
for num in nums {
if let rr = rangeArray.firstIndex(of: num) {
// print("Removed \(num) at \(rr)")
rangeArray.remove(at: rr)
}
}
// assert(rangeArray.count == 1,"range array solution")
return rangeArray.first
}
// print(doSomething(nums: [3,0,1]) ?? "NA")
// print(doSomething(nums: [0,1]) ?? "NA")
// print(doSomething(nums: [9,6,4,2,3,5,7,0,1]) ?? "NA")
//
// trees.swift
//
// trees, dfs, BST, bfs
// Given the preorder and inorder traversal of a binary tree, it's possible to reconstruct the original tree by using the following steps: Take the first element of the preorder traversal, which is the root node of the tree. Find the index of the root node in the inorder traversal. The elements before it in the inorder traversal are the left subtree, and the elements after it are the right subtree. Recursively construct the left and right subtrees of the root node using the corresponding elements from the preorder and inorder traversals.
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
guard !preorder.isEmpty && !inorder.isEmpty else { return nil }
let rootValue = preorder[0]
let root = TreeNode(value: rootValue)
guard preorder.count > 1 else { return root }
let rootIndexInorder = inorder.firstIndex(of: rootValue)!
let leftInorder = Array(inorder[0..<rootIndexInorder])
let rightInorder = Array(inorder[rootIndexInorder+1..<inorder.count])
let leftPreorder = Array(preorder[1..<1+leftInorder.count])
let rightPreorder = Array(preorder[1+leftInorder.count..<preorder.count])
root.left = buildTree(leftPreorder, leftInorder)
root.right = buildTree(rightPreorder, rightInorder)
return root
}
// Create a binary tree
let root1 = TreeNode(value: 1,
left: TreeNode(value: 2,
left: TreeNode(value: 4),
right: TreeNode(value: 5)),
right: TreeNode(value: 3,
right: TreeNode(value: 7)))
// Find the maximum depth of the binary tree
// let maxDepth = maxDepth(root: root)
// print(maxDepth) // Output: 3
func maxDepth(root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxDepth(root: root.left), maxDepth(root: root.right)) + 1
}
// Create a binary tree
let root = TreeNode(value: 1,
left: TreeNode(value: 2,
left: TreeNode(value: 4),
right: TreeNode(value: 5)),
right: TreeNode(value: 3,
right: TreeNode(value: 7)))
// Perform level order traversal of the binary tree
// levelOrderTraversal(root: root)
// Output: 1 2 3 4 5 7
class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(value: Int, left: TreeNode? = nil, right: TreeNode? = nil) {
self.value = value
self.left = left
self.right = right
}
}
func levelOrderTraversal(root: TreeNode?) {
guard let root = root else { return }
var queue = [TreeNode]()
queue.append(root)
var result = [Int]()
while !queue.isEmpty {
let node = queue.removeFirst()
print(node.value)
result.append(node.value)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
print(result)
}
class Node {
var value: Int
var left: Node?
var right: Node?
init(value: Int, left: Node? = nil, right: Node? = nil) {
self.value = value
self.left = left
self.right = right
}
}
class BST {
var root: Node?
func insert(_ value: Int) {
guard let root = root else {
self.root = Node(value: value)
return
}
var current = root
while true {
if value < current.value {
if let left = current.left {
current = left
} else {
current.left = Node(value: value)
break
}
} else {
if let right = current.right {
current = right
} else {
current.right = Node(value: value)
break
}
}
}
}
func search(_ value: Int) -> Bool {
var current = root
while current != nil {
if value == current?.value {
return true
} else if value < current?.value ?? -1 {
current = current?.left
} else {
current = current?.right
}
}
return false
}
}
//
// workflow.swift
//
func unique(_ str: String) -> Bool {
let str = str
let counter: [String: Bool] = [:]
for index in 0..<str.count {
if counter[index] 1= nil {
counter[index] = true
} else {
return false
}
return true
}
}
unique("123445")
``