Jump to content

  • Log In with Google      Sign In   
  • Create Account


Google Interview Questions


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
81 replies to this topic

#81 Antheus   Members   -  Reputation: 2397

Posted 19 May 2011 - 04:51 PM


Binary search has worst-case O(logn).
Finding split point is O(n), so finding the point of rotation is several times more expensive than search itself.

Since array is sorted, recursive split can be used to determine which half is out of order. Predicates for binary search are: left < mid < right (equalities optional)

Oooo. I like that. I didn't realize it before.


And in my crusade against spambots, I accidentally downvoted this post. And apparently I cannot undo it. So someone upvote it.

Sponsor:

#82 way2lazy2care   Members   -  Reputation: 782

Posted 19 May 2011 - 05:10 PM

And in my crusade against spambots, I accidentally downvoted this post. And apparently I cannot undo it. So someone upvote it.


I thought we were friends :'(




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS