Write better code: Day 3 - Rotation Point

This post originally appeared on Arjun Rajkumar 's blog. Arjun is a web developer based in Bangalore, India.

--

Day 3: Question 2

I opened up a dictionary to a page in the middle and started flipping through, looking for words I didn't know. I put each word I didn't know at increasing indices in a huge array I created in memory. When I reached the end of the dictionary, I started from the beginning and did the same thing until I reached the page I started at.

Now I have an array of words that are mostly alphabetical, except they start somewhere in the middle of the alphabet, reach the end, and then start from the beginning of the alphabet. In other words, this is an alphabetically ordered array that has been "rotated." For example:

words = [
    'ptolemaic',
    'retrograde',
    'supplant',
    'undulate',
    'xenoepist',
    'asymptote',  # <-- rotates here!
    'babka',
    'banoffee',
    'engender',
    'karpatka',
    'othellolagkage',
]

Write a method for finding the index of the "rotation point," which is where I started working from the beginning of the dictionary. This array is huge (there are lots of words I don't know) so we want to be efficient here.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Comments

[Arjun Rajkumar]

This was very similar to binary search as it was mostly sorted. Just had to keep splitting until the mid word was lesser than starting word.

def rotation_point(words)
  starting_index = 0
  ending_index = words.length - 1

  while starting_index < ending_index

    puts "\n#{words[starting_index]}"
    puts "#{words[ending_index]}"

    mid = (starting_index + ending_index) /2
    puts "#{mid}"
    puts "#{words[mid]}"
    if words[mid] < words[0]
      ending_index = mid 
    else
      starting_index = mid
    end

    return ending_index if starting_index + 1 == ending_index
  end
end

Binary search so its O[logn] time and space if O[1]

[Phil Ashby]

Nice. There is a similar real world problem when writing journalling file systems: they need to find the rotation point of the journal, even after a system failure that didn't permit saving that information anywhere well known. The solution is similar too, a binary search through disk blocks looking for the point where the journal index goes down instead of up :)