Given two-dimensional array now walk it spirally
One of those brain-twisters you might be asked if you apply for Software Engineer position at a decent company.
The interviewer goes to the white board and draws a 2d array.
Write a function that walks that array in spiral and outputs:
How to walk it spirally (over engineered)
Like always with programming there are tons of ways to tackle a problem. Only efficient solutions counts.
Here’s my take on this one:
- Shave off sides of the 2d matrix(array)
- Append contents of the side to result array
Hold ye horses sire… How the hell did you shave other sides off???
The answer is that we have to transpose the matrix every time before we take off one side. But not the first time!
Basically we need to turn that two-dimensional array -90°.
In any case we just identified two main functions here
to turn the matrix
to shave off top row
Let’s write some tests for identified functions
We would have to use
Code below will make our tests pass.
Awesome, right? Well, NO.
How to really walk two-dimensional array spirally
Obviously solution above is over engineered and most likely you won’t get a job :(. It’s fun to play with matrixes but when it comes to real life you should never use code above in production.
Spiral problem solved by keeping track of the coordinates for the traversed two-dimensional array.
- identify coordinates
- keep reference of the current side being shaved off
Function above runs 80% faster than overengineered solution in which you need to rotate arrays.