Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your help!

We need 7 developers from Canada and 18 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a $50 Amazon gift card. Click here to get started!


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: 2405

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