## Refresher: Problem Solving (1-4)5 (1)

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

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

``````

## iOS/Android Developer Security Basics5 (2)

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

I couldn’t find a single place that covers the mobile developer security (must know) basics, this will be again like a chat between two developers (Lulu ๐ฉ๐ผโ๐ป) and (Sam ๐ฆ)

๐ฉ๐ผโ๐ป: What are the risks of not having good security precautions? I can see we spend big money on security.
๐ฆ: There are over 500 reported incidents of data-breach each year, It’s estimated that each incident costs 3.5M~5.0M USD on average.
If you look at statistics, you can see that remote jobs increased these costs by 15%, since attackers would have more opportunities of attacking a target that is spread on different locations.

๐ฉ๐ผโ๐ป: When people talk about security, the server is being presented as the bottleneck, why would a mobile developer be concerned with security if the website is secure?
๐ฆ: The weakest link is the bottleneck, if the client is poorly written, you should expect a lot of attacks on the server, also, users spend about 90% of their time on mobile rather than web browsers.

๐ฉ๐ผโ๐ป: But you are an iOS developer, and I develop for Android, would your tips and hints be applicable to Android too? oh, I almost forgot that both are based on Linux.
๐ฆ: wait, they are not both based on Linux, iOS is aย Unix-like Operating Systemย which isย based on Darwin(BSD)ย operating system, while Android is Linux-based Operating Systemย and is an open source mobile operating system, there are a lot of precautions that are applicable on both OSs.

๐ฉ๐ผโ๐ป: I was asking myself in the past, why not rely on HTTPS and that’s it?
๐ฆ: HTTPS protects users from other users, it doesn’t protect the server or the application sensitive data itself.

๐ฉ๐ผโ๐ป: What are the mobile weak points? what can be hacked?
๐ฆ: Network , Disk, USB Port, etc…

๐ฉ๐ผโ๐ป: That looks like a lot of terminology, can you explain the basics?
๐ฆ: You will be good to go if you know these as a start.

๐ฉ๐ผโ๐ป: Why would people with a jailbroken device be a threat on the app itself, a jailbreak only make the user hackable, right?
๐ฆ: No, The best practice, is to prevent people with Jailbroken devices from running your app, see my x04_checker repo, iOS Developers can use it to prevent jailbroken devices from running their applications.

Jailbreaking is the process of exploiting the flaws of a locked-down electronic device to install software other than what the manufacturer has made available for that device. It allows the owner to gain full access to the root of the operating system and access all the features, you must know that 100% jailbreak detection is not possible, we need to make (bypassing jailbreak detection) time-consuming, because an attacker can steal the developer info, and thus steal the app info.

๐ฉ๐ผโ๐ป: They say debugging and print statements can be a security vulnerability, is this true?
๐ฆ: Print normally only works on development builds, print will still send the data to the usb interface.

As you mentioned print, It’s a heavy command though, even if your debugging device is not connected in debug mode with Xcode, leaving print statement of heavy objects might make your app slower during development, but anyway, this is not our topic.

Keep in mind, NSLog will be left even in Distribution builds, any normal user can see the logs using the macOS console app, I used them when debugging opening the app using a notification when it’s terminated, this is not easy to do in Xcode directly, anyway, just use NSLog carefully, and treat the error log files with care, don’t log sensitive data, or leave trace of code symbols.

๐ฆ: Certificate pinning simply prevents people from having the victim installing an incorrect certificate and making altered requests, you simply make the certificate a static asset in the binary, so an attacker can not have the victim installing another fake certificate to have them impersonated.

๐ฉ๐ผโ๐ป: What about sensitive static strings?
๐ฆ: Never have your sensitive strings inside plist or any asset file, this is the most basic tip you should never miss.
๐ฉ๐ผโ๐ป: Wait Sam, I downloaded a facebook apk online, and ran a simple command to scan the binary for strings that look similar to google api keys, that begin with AIz, and I can see this, any explanation why this is not hidden in the binary?

` strings targetFile | grep "targetString"`

๐ฆ: There are multiple ways google makes sure that a request is authentic, from comparing hashes, to domain binding to bundle ids etc… again, you need to have your sensitive data hidden, this is not an excuse.

๐ฉ๐ผโ๐ป: Why is it said to be risky to use 3rd party libraries when developing sensitive apps like banks?
๐จ๐ปโ๐ป: In normal cases, libraries are fine, just make sure that they are being audited, NPM libraries had a lot of these, for sensitive apps, it’s better to avoid them altogether.

๐ฉ๐ผโ๐ป: If I follow all of these tips, I will be completely secure?
๐ฆ: The sad news is, No, there are a lot of other attacks, like URL-scheme attacks, when you define a url scheme, your app responds to that scheme, so for instance, you create a scheme myapp://. all links starting with your scheme will directly launch your app. A universal link doesn’t include your scheme in the url but they will still launch your application, apple allows other apps to the register the same url.
๐ฉ๐ผโ๐ป: the alternative is universal links?
๐ฆ: correct!

๐ฉ๐ผโ๐ป: That was a huge amount of info for a starter, any final thoughts?
๐ฆ: 100% Security for any Application is not possible but we can try to make the attacking/cracking of iOS App as much harder as possible.

Security is not always about “make accessing the data impossible”. sometimes it is about cost and likelihood of retrieval versus importance of the data.

More tips on top of my head:

• Avoid Objective-C if possible, itโs very easy to reverse engineer.
• Don’t write sensitive data into logs.
• Disable Keyboard caching (3rd party keyboard)
• Password/Pin should not be exposed during user interaction – Don’t include sensitive data in backup.
• User Credentials should be stored in (keystore, keychainโฆ).
• SSL Pinning.
• App Transport Security – Certificate Pinning.
• Integrity Check.
• Prevent Running on rooted devices.
• Detect JailBreak, (Jail Monkey library).
• Use WebView carefully.
• Securing Data on disk.
• Securing Data across a network connection.
• Secure application logic.
• prevent Reverse Engineering (even if there is no sensitive data, if your app is novel, you don’t want people to see the code)
• Don’t share sensitive data with 3rd party
• Avoid keywords like (โjailโ,โsecurityโ,โcydiaโ,โaptโ) in variable & function names
• Hide the JB check deep in the app, not in appdelegateโฆ
• Some Jailbreaks are permanent, and are done by exploiting security flaws in hardware.

## GPS Hardware basics for mobile developers.4.7 (3)

Click to rate this post!
[Total: 3 Average: 4.7]

Mobile software engineers (iOS and Android), are normally not familiar with how GPS works, instead of just getting Lat/Lon readings, and doing geo operations with it, why not become familiar with how GPS works? ๐ค

This will not be a lengthy article, it will be a chat between an iOS developer (Alex ๐จ๐ปโ๐ป) and an electrical engineer (Sarah ๐ฉ๐ผโ๐ป).

๐จ๐ปโ๐ป: So what does GPS stand for?
๐ฉ๐ผโ๐ป: It stands for (Global Positioning System).

๐จ๐ปโ๐ป: Who created it? and what for?
๐ฉ๐ผโ๐ป: The GPS project was launched in the USA back in 1973 due to limitations of old navigation systems.

๐จ๐ปโ๐ป: I know it works without internet, but do I need cellular service to use GPS?
๐ฉ๐ผโ๐ป: No.

๐จ๐ปโ๐ป: How come it works without internet or cellular service?
๐ฉ๐ผโ๐ป: You get readings from satellites, there are about 24 artificial satellites in 6 orbits.

๐จ๐ปโ๐ป: So a mobile needs to connect to all of these?
๐ฉ๐ผโ๐ป: Of course not, when you are stationary, you need to be exposed to 3 of them, when you are moving, you will need to be exposed to 4.

๐จ๐ปโ๐ป: So how come it identifies me? and send me data?
๐ฉ๐ผโ๐ป: The Satellites don’t identify you, they only emit synchronous pulses all the time everywhere.

๐จ๐ปโ๐ป: And how does my mobile give me back the (latitude, longitude, and altitude)?
๐ฉ๐ผโ๐ป: It compares the receive time of these pulses from each satellite, and use calculations to determine a point on earth, since the distance between these satellites is constant, and they have atomic clocks, the calculations will not be difficult.

๐จ๐ปโ๐ป: The service is totally free, and I don’t have any subscription for GPS, how?
๐ฉ๐ผโ๐ป: GPS is not the only service for (Global Navigation Satellite Systems), there are many like (GLONASS, BeiDou, Galileo…), there are other commercial solutions that I don’t know much about, there are a lot of details, I heard retail GPS receivers are designed to not work if the tracked object is moving fastly, you get the idea ๐ง?
๐จ๐ปโ๐ป: ah! yes.

๐จ๐ปโ๐ป: What is the error margin?
๐ฉ๐ผโ๐ป: It’s variable, but you can say between 15 to 50 meters, some commercial systems use other inertial systems to give more accurate estimations.

๐จ๐ปโ๐ป: What is the minimum detectable value?
๐ฉ๐ผโ๐ป: You mean the resolution? theoretically, as far as I know, it’s one inch, but practically it’s about 3 meters.

๐จ๐ปโ๐ป: I once tried to use the GPS inside a big hospital, it didn’t serve any purpose, the readings were not accurate.
๐ฉ๐ผโ๐ป: GPS does not work indoors.
๐จ๐ปโ๐ป: But I saw some readings on my maps application.
๐ฉ๐ผโ๐ป: it’s the last point that was read, some devices like Huawei also augment (Accel/Gyro) sensor data, to mimic a basic INS to give your readings inside buildings, but it’s not reliable.

๐จ๐ปโ๐ป: And what is used for indoor navigation systems?
๐ฉ๐ผโ๐ป: They use beacons and Bluetooth and other technologies, read about apple air tags!

๐จ๐ปโ๐ป: You mentioned sensors, why can’t we use the basic sensors like accelerometer/gyroscope of the mobile to calculate the position?
๐ฉ๐ผโ๐ป: when you “integrate” the acceleration twice, the error will explode fastly, and it will become useless in a short time of movement, even if this works, this will not give you an absolute position, and you have to deal with drifting and gimbal lock and a lot of complexities.

๐จ๐ปโ๐ป: That was a lot of information, thank you.
๐ฉ๐ผโ๐ป: Welcome!, see you soon.