Sponsored By Aspose - File Format APIs for .NET

Aspose are the market leader of .NET APIs for file business formats – natively work with DOCX, XLSX, PPT, PDF, MSG, MPP, images formats and many more!

Tricky Question

 

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!

This entry was posted in Uncategorized. Bookmark the permalink. Follow any comments here with the RSS feed for this post.

2 Responses to Tricky Question

  1. Jonathan says:

    I finally got it. This relates to the message pipeline and storing events in the file system:

    http://tech.groups.yahoo.com/group/domaindrivendesign/message/12396

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>