As new or even experienced developers we often hear the key to advancing in one’s career is becoming more familiar with algorithms. As the term implies, this way of approaching problems isn’t a one-size-fits-all solution but does contain some common elements. In this essay, we’ll review some popular techniques. Consider this question from Quora:
Q: I’ve heard a lot about algorithms. I’m a beginner. How do programmers learn to think and solve problems algorithmically? Is there a process for this kind of thinking?
Reversing Strings
No technical interview would be complete without a basic test on String manipulation. While there are many ways this can be achieved, a popular test involves evaluating a String to see if it qualifies as a palindrome. For example, the phrase “was it a car or a cat I saw” can be read either forward or backward, often making for funny anecdotes.
The Conventional Approach
This question makes for a good interview topic is because it deals with the reversing of Strings. An essential task, being able to reverse the order of content has many uses, including when it comes to data sorting and/or organizing. To answer our question, one approach would be to simply call a function to reverse our proposed String, which would then be compared to our original (unchanged) String. For example:
func isPalidrome(sequence: String) -> Bool {
var characters = Array(sequence)
characters.reverse() //swift sdk - O(n) linear time
return sequence == String(characters) ? true : false
}
Like this article? Get more content like this when you sign-up for the weekly iOS Computer Science Lab.
Even though this solution is satisfactory, we’ve borrowed the ability to reverse our proposed String from the Swift SDK. This operation occurs in O(n) - linear time which implies the entire sequence must be reversed (and copied) before we can determine a true or false outcome. Could there be a more efficient solution?
Rethinking The Problem
A key aspect to thinking algorithmically is to consider the minimum data needed to answer question. For example, instead of comparing two Strings, perhaps we can compare specific characters or substrings. Why? Because the length of a String varies. While checking the validity of a few words may prove efficient, the speed of our function will lessen depending on the amount of data it processes.
An alternate approach could be to compare the first and last characters of our String to see if they indeed match. If no match is found, we only compared two characters. This new way of thinking improves the best case efficiency to O(1) - constant time.
In Swift, this can be expressed as:
func isPalidrome(sequence: String) -> Bool {
var pstatus: Bool = false
//convert to array
let characters = Array(sequence)
var findex: Int = characters.startIndex
var bindex: Int = characters.endIndex - 1
//obtain starting value
let fvalue = String(characters[findex])
let bvalue = String(characters[bindex])
//compare the forward and backward indices
while findex < bindex {
if fvalue == bvalue {
pstatus = true
//update indices
findex += 1
bindex -= 1
continue
}
else {
return false
}
} //end while
return pstatus
}