The interesting things that you would face during Interviews are mostly in the form of puzzles and challenges. These are meant to not tickle your brain but instead it can stump you. On top of that, if you really give it a thought, some of these questions or scenarios are based off bad architecture and structures. There are possibilities that you would never ever get the change to use any of these but then again, you might just…who knows. In this article we shall look at the simple way to rotate an array in place. So if you had an array of numbers like so, [1, 2, 3, 4, 5, 6, 7] and you wanted to rotate 3 elements, you would be left with [4, 5, 6, 7, 1, 2, 3].
The first thing that comes to mind with Swift is to simply use swift functions to achieve the outcome.
First Go
The first go is to use inbuilt swift function and methodologies. Swift has some amazing functions to get array slices and ranges. You can access the arrays with passing a range, which returns a slice. So arr[iStart..<iEnd] returns a slice from the array that has a range from iStart upto iEnd
var arrInt = [1, 2, 3, 4, 5, 6, 7] let len = arrInt.count let n = 3 let result = arrInt[n..<len] + arrInt[0..<n]
Swift has quite a few functions in-built that help you in reversing arrays, they are the simple methods called reverse() and reversed() . Where reverse() does an in-place reverse and reversed() returns a new reversed array.
I recollect this person that was discussing this with me have his jaw fall open and say, “NO!!, that is too easy, can it be done without using any functions”. Well there can be but the question is why would you want to be McGyver and do everything from scratch if you already have it provided to you.
Second Attempt
Ok, point taken, the array might be a large array and working with the slices creates a new array, so while the complexity might be low, it is creating a non-memory efficient solution. The person went on to explain, what if the array was a large array with like 4MB worth of data. I looked at him straight, first for dissing the functionality that was already available in a language, next for even suggesting such an absurd situation. I can understand that it is memory inefficient, but if it was a large array of 4MB, this is definitely not the way I would approach this problem. I would architect a more efficient way to deal with things. Worse case, say it was not possible because it was image data or something like that, why would I want to rotate an array. It didn’t make sense, however, the problem remained to be solved.
The way to solve that is by reversing, and it is quite simple because at the end it achieves what you were after.
Look at the graphic, it outlines the whole article in an image form.
First, let us write the reverse function, and also note that we need to get it to work with in-memory swap, which means we cannot allocate new memory for the array.
a side note on that first.
When we want to swap two numbers, we can do that by using a third temporary variable like so
var a = 1 var b = 2 let c = a a = b b = a
and done, we have swapped the values of a and b
With Swift and using tuples, we can use a slightly different way such as
var a = 1 var b = 2 (a,b) = (b,a)
and done, we don’t need a third variable.
lastly, swift has an in-built function called swap that takes two inout parameters and swaps their values in memory.
var a = 1 var b = 2 swap(&a, &b)
and done, swapped.
Now back to reversing our array, the idea is to have two pointers, one that is at the start of the array and one at the end. swapping the elements and moving in till the middle of the array.
Since we shall reverse the array in-place, we need to send it by reference so we use the inout to do so.
func reverse(_ array: inout [Int], startP: Int, endP: Int){
var _st = startP
var _nd = endP
while _nd > _st {
swap(&array[_st], &array[_nd])
_st += 1
_nd -= 1
}
}
note: using the swapfunction is the fastest way to swap two variables as compared to the other methods listed above.
In the above code, since swift passes parameters by value, the variables are immutable so to be able to change that, we created temporary variables _st and _nd.
This works, however since we are working with trying to optimize a solution, we can further reduce that by using a single variable as
func reverse(_ array: inout [Int], startP: Int, endP: Int){
var _index = 0
while endP - _index > startP + _index {
swap(&array[startP + _index], &array[endP - _index])
_index += 1
}
}
func rotate(array : inout [Int], count: Int){
let len = theArray.count
reverse(array, startP: 0, endP: count-1)
reverse(array, startP: count, endP: len)
reverse(array, startP: 0, endP: len)
}
Now let us call it as
var theArray [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] rotate(&theArray, count: 3) print(theArray)
NOTE: Fixed some inconsistencies in variable names, thanks to Jose Gutierrez. The variable will be called len, thanks. I would have wanted to fix it to length, but the graphic has len, so just keeping it consistent.
Finding a solution
Solutions are generally not as straight forward, however can be simple. Well, if you are in an interview situation, you would now know how to solve this issue.As for the person that brought this problem to me, well here is a pure swift solution with an in-place rotation. However you must also understand that languages evolve to provide more features. Everything can be done in Machine Language, however that developed into Assembly, C, Pascal, C++, Objective-C, Java, C#, Swift and the list goes on. Each new language was created to resolve issues with an earlier one or introduce features that are important. It would be worth considering the features in the newer languages and moving out of the Java mind-set.
