Reverse a string
This article looks at the interview question - Reverse a string in the most efficient way possible. For example an input of "abc123"
will result in the output "321cba"
.
Analysis
This is a very common interview question, it tests whether a candidate understands how string concatenation and immutability works. A simple algorithm that does the job loops through each character and constructs a string in reverse order.
function reverse (text) define result ← "" foreach character c in text result ← c + result return result
The above algorithm is not very efficient though. This is because strings are immutable which means they cannot be modified after they are created. The algorithm creates a new string every iteration which takes worst case O(n), making the algorithm O(n^2).
The string can be reversed in O(n) time with a couple of different methods: using StringBuilder
to construct the string as above, or by converting the string to a character array and back. The optimal solution largely depends on how strings are handled in the language that the function is being implemented in though.
Code
public static String reverseViaCharArray(String text) {
char[] charArray = text.toCharArray();
int start = -1;
int end = charArray.length;
while (++start < --end) {
char temp = charArray[start];
charArray[start] = charArray[end];
charArray[end] = temp;
}
return String.valueOf(charArray);
}
public static String reverseViaStringBuilderA(String text) {
StringBuilder sb = new StringBuilder();
for (int i = text.length() - 1; i >= 0; i--) {
sb.append(text.charAt(i));
}
return sb.toString();
}
public static String reverseViaStringBuilderB(String text) {
return new StringBuilder(text).reverse().toString();
}
function reverseString(text) {
var result = '';
for (var i = text.length - 1; i >= 0; i--) {
result += text[i];
}
return result;
}
Textbooks
Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.