Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


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

#61 kSquared   Members   -  Reputation: 1356

Posted 09 February 2005 - 10:17 AM

Quote:
Original post by Sagar_Indurkhya
2) What is the most beautiful equation you have ever seen? Explain.

Most beautiful equation? My hat's going in the ring for general relativity:

Gμν = 8π · GTμν

Sponsor:

#62 Sagar_Indurkhya   Members   -  Reputation: 253

Posted 09 February 2005 - 10:28 AM

Quote:
Original post by furby100
Quote:
Original post by Sagar_Indurkhya
2) What is the most beautiful equation you have ever seen? Explain.


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 eip + 1 = 0


never seen that one. What is it?

#63 kSquared   Members   -  Reputation: 1356

Posted 09 February 2005 - 10:29 AM

Quote:
Original post by Sagar_Indurkhya
Quote:
Original post by furby100
However, it's almost certain most people will put eip + 1 = 0


never seen that one. What is it?

Euler's identity. It unites five of the fundamental mathematical constants: zero, one, e, pi, and i. It's the case x = pi for the more general equation e^(ix) = cos(x) + i*sin(x).

#64 JexMX   Members   -  Reputation: 206

Posted 09 February 2005 - 11:29 AM

What came first, the chicken or the egg?



#65 Samith   Members   -  Reputation: 2260

Posted 09 February 2005 - 11:50 AM

Quote:
Original post by JexMX
What came first, the chicken or the egg?


The egg, of course. The first bird genetically close enough to today's chicken to be considered a chicken was a chicken for its entire life (as in, it didn't suddenly turn into a chicken halfway through its life). That means it was born from an egg, a chicken egg.

#66 Stonicus   Members   -  Reputation: 157

Posted 10 February 2005 - 11:04 AM

I'd say the chicken. If a non-chicken lays an egg, it's not a chicken egg. What came out was a chicken, but it wasn't supposed to be, so it wasn't a chicken egg, it was a mutated relative-of-chicken egg... So the first chicken egg had to come from a chicken, but the first chicken can come from a mutated Dodo egg.


#67 Cold_Steel   Members   -  Reputation: 835

Posted 10 February 2005 - 11:30 AM

Quote:
Original post by Stonicus
I'd say the chicken. If a non-chicken lays an egg, it's not a chicken egg. What came out was a chicken, but it wasn't supposed to be, so it wasn't a chicken egg, it was a mutated relative-of-chicken egg... So the first chicken egg had to come from a chicken, but the first chicken can come from a mutated Dodo egg.
So, you say that the egg type is defined by what pooped out the egg, and not what's in the egg. Still, the question is whether the egg preceded the chicken. I don't think it matters what type of egg, just that there was indeed an egg directly related to the first chicken, that indeed preceded it.

I say egg came first.

#68 doogle   Members   -  Reputation: 475

Posted 10 February 2005 - 11:40 AM

Quote:
Original post by Coaster Kev
Why not ask Google ... err... yeah

Funny Google Response


hahahahaha

#69 vrok137   Members   -  Reputation: 241

Posted 28 March 2011 - 10:46 AM

A while back I myself had a series of phone interviews with Google, the following were a few of the questions they asked, and we were allowed to ask questions as well:

  • There exists a file directory containing at least 55 thousand plaintext documents. Some of those documents contain phone numbers that are out of date. Given a list of invalid phone numbers and their new, updated equivalents, how would you go about updating all invalid phone numbers within all files within the directory?
  • Write an algorithm that performs a binary search on a sorted, but rotated array of integers.
  • Compare and contrast various data structures utilized across multiple programming languages: Hashtable, Hashmap, Treemap, etc.
Fun, Fun Posted Image.

#70 way2lazy2care   Members   -  Reputation: 782

Posted 29 March 2011 - 06:38 AM

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 eip + 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.com/blog.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.



#71 Krohm   Crossbones+   -  Reputation: 3171

Posted 29 March 2011 - 06:55 AM

I'm all on the parallel universe thing.

#72 NotYourAverageUser   Members   -  Reputation: 500

Posted 29 March 2011 - 08:51 AM

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


Nope. that equals 2, not 0.

#73 Antheus   Members   -  Reputation: 2397

Posted 29 March 2011 - 10:42 AM

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.

What is a rotated array?

#74 way2lazy2care   Members   -  Reputation: 782

Posted 29 March 2011 - 11:52 AM

but rotated array of integers.

What is a rotated array?


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.

#75 Antheus   Members   -  Reputation: 2397

Posted 29 March 2011 - 01:44 PM

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.

#76 Alpha_ProgDes   Crossbones+   -  Reputation: 4692

Posted 31 March 2011 - 01:19 PM


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 eip + 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.

I thought since the light has less distance to travel, things would seem faster.....
Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler

#77 way2lazy2care   Members   -  Reputation: 782

Posted 31 March 2011 - 01:40 PM

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.

#78 Patric Holier   Members   -  Reputation: 98

Posted 21 April 2011 - 08:03 AM

Hi



This topic help me a lot in developing my project. I will contribute more when I finished it.

If you want to get more materials that related to this topic, you can visit: Administrative interview questions and answers



Best regards.



#79 way2lazy2care   Members   -  Reputation: 782

Posted 21 April 2011 - 12:46 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.

#80 Patric Holier   Members   -  Reputation: 98

Posted 19 May 2011 - 09:48 AM

Hi,



Good ideal, pls try to keep posting. I like this topic very much and I will digged this one. Tks again.


I found some references on this subject, please refer to everyone here: Marketing interview questions and answers

Best regards.






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