Someone gave me a tricky little question the other day that they had supposedly received in an interview at google and were stumped by. Its not really that tough but …
You have a circular queue of ordered items, come up with an algorithm for finding whether or not an item with the value of k is in it.
My first question: is the circular queue implemented as a list or within an array. Answer within an array (I was 1/2 expecting a problem to have to implement with a skip list for some reason).
A naive implementation would be to Iterate from head-tail end and then from beginning to tail, this will produce a result in O(n)
Can we do better? Spoiler below
We can do a binary search but it becomes a bit more tricky as things are not always sorted the way that we want. From above we know that if we have head or tail in a segment … the beginning of the segment to tail is sorted and we know that from head to the end of the segment is sorted. Coming though some other important examples.
Consider some examples when we go to split the data into 2 smaller arrays.
9 0 1 2 3 4 5 6 7 8
head = 1
tail = 0
3 4 5 6 7 8 9 0 1 2
head = 7
tail = 6
if head and tail are both on the same segment … that side is not sorted properly
0 1 2 3 4 5 6 7 8 9
head = 0
tail = 9
If head is in one and tail is in the other then both are sorted perfectly.
If later we have neither head nor tail in our segments we know that they are sorted properly in their entirety.
By utilizing this information we can now trivially change our binary search algorithm to take into account the areas that may not be sorted correctly and issue a binary search!