Interview Question: Shifted Array
Today I went to interview for Koren Tec. I was expecting more of an interview and less of a test but I got what I got. It stressed UML twice which I can’t simply pull out of my head so I decided not to even insult them with a poor attempt but to explain it. I hope I got some points for that.
They asked a lot of basic questions like what’s the difference between a Value or a Reference, between a Structure and a Class or what’s a Virtual Table. But one of the more interesting question is this: A Shifted Array is a sorted array whose elements has been shifted forward round-robin style. Write a function that receives an array and its size and determines how much it has been shifted.
The code is quite redundant but my idea for it was to scan the array and look for the point where an element is larger than the element after it. This marks the spot where the elements from the end of the array are bumping the elements from the start. The number of elements before this demarcation point is you shift value.
This gives you a nice O(n) complexity and should be good enough, in my opinion.
If you have a better idea, I would love to hear about it down in the comments.
Posted in No Category, Programming, Thinking Out Loud by Eran with 1 comment.
You can go on the same idea, just doing it binary-search style(i.e. for an array A of size n, go to place n/2 – if A[n/2] is smaller then A[1], the shift point is between them, if it is larger, it is between A[n/2] and A[n]), this should give you O(logn)