Jump to content
  • Advertisement
Sign in to follow this  
kSquared

Google Interview Questions

This topic is 2868 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement

What came first, the chicken or the egg?


This is a perfect example of a leaky abstraction. Neither chicken nor egg are actual entities, both are just a blob of same cells.

but rotated array of integers.[/quote]
What is a rotated array?

Share this post


Link to post
Share on other sites

but rotated array of integers.

What is a rotated array?
[/quote]

A rotated array is an array where the first piece of data might not be the first element.

ex: [4,5,1,2,3] would be a sorted rotated array.

edit: as far as writing a binary search on it, you could just write a function to translate their element index into their data index and perform a binary search using that function to access the elements the way you would normally do a binary search. Not sure if that's the optimal solution, but it seems to be the simplest on my mental state atm.

double edit: I think it's actually better to find where your array gets split, then run a binary search on the half that should contain the element. Since you have to search for the spot where it's split anyway, this uses that step to also eliminate some of the elements before starting the binary search even starts.

Share this post


Link to post
Share on other sites
ex: [4,5,1,2,3] would be a sorted rotated array.

edit: as far as writing a binary search on it, you could just write a function to translate their element index into their data index and perform a binary search using that function to access the elements the way you would normally do a binary search. Not sure if that's the optimal solution, but it seems to be the simplest on my mental state atm.

double edit: I think it's actually better to find where your array gets split, then run a binary search on the half that should contain the element. Since you have to search for the spot where it's split anyway, this uses that step to also eliminate some of the elements before starting the binary search even starts.
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)

In example above, we have:
left = 4
mid = 1
right = 3
There are now two intervals, left and right. Determine which is correct and which is incorrect.

Instead of usual binary search, which tests against midpoint, test against intervals. Does x lie in correct interval? If yes, perform regular binary search. If no, repeat the above.

This has same complexity as regular binary search and it avoids finding the pivot/rotation point, meaning array could be rotated arbitrarily between searches. A practical application could be something like set of indexed data or time series in a ring buffer.

Share this post


Link to post
Share on other sites

[quote name='furby100' timestamp='1107964749' post='2903243']
x=2. This equation is satisfied by 2. It follows that there are numbers that satisfy the equation x = 2. From that, it follows that there are numbers. From this simple equation one can settle one of the deepest philosophical questions about mathematics. Certainly a beautiful result.


However, it's almost certain most people will put e[sup]i[font="symbol"]p[/font][/sup] + 1 = 0


What about x=0? That has the same as above, but adds in that there is some number representing no quantity at all.

On the blender:
http://www.realkato....log.php?pid=857

If you suppose that it were somehow physically possible to shrink yourself to that size without diminishing your normal human capabilities, then you should consider that your strength (a function of the area of your cross-section, proportional to the square of your height) has been reduced about 4900 times, but your mass (a function of your volume, proportional to the cube of your height, given that your density remains the same) has been reduced 343000 times. If you currently have a 24-inch vertical leap, you'd still have a 24-inch vertical leap regardless of how small you became. So given those facts, you could simply jump out of the blender.

Another interesting thing to note: you'd actually have what seems to be 70 minutes to come up with the solution, because time would travel 70 times slower for you at that size. The speed of light and the speed of electrons is constant, but when you're tiny, photons and electrons have less distance to travel.[/quote]
[/quote]
I thought since the light has less distance to travel, things would seem faster.....

Share this post


Link to post
Share on other sites

I thought since the light has less distance to travel, things would seem faster.....


You will go faster and the rest of the environment will appear to be slower as, in theory, you should perceive your increased speed to be the same as your speed now.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

[quote name='Antheus' timestamp='1301427890' post='4791860']
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.
[/quote]

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!