• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
kSquared

Google Interview Questions

80 posts in this topic

Quote:
Original post by Coward
Quote:
Original post by Sagar_Indurkhya
3) You have 10,000 Apache servers, and 1 day to generate $1,000,000. What do you do?

Sell them for $100 each?

No, sell them for $150 each, and pretend you sold them for $100 each. :D
0

Share this post


Link to post
Share on other sites
first, if compiler doesn't optimize too well, just

void stackdir(){
int a,b;
if((&a)>(&b)){cout<<"stack grows down";}else
if((&a)<(&b))cout<<"stack grows up";}else
cout<<"something is wrong, compiler is waay too smart";
}

, that must work in debug mode with all optimizations turned off.

But if compiler is optimizing...

There is some hope that not-so-well optimizing compiler will not able to optimize that out:
int recursive_fun(int level){
if(level>1){return recursive_fun(level-1);}
if(level==1)return int(&level)-recursive_fun(0);
return int(&level);
};
...
int n=5+random()%20;
int i=recursive_fun(n);
if(i>0){cout<<"stack grows down";}else
if(i<0)cout<<"stack grows up";}else
cout<<"something is wrong, compiler is waay too smart";

If that will be optimized too, it will be needed to add some "useful load" to program, make it compute something.


as about blades. If you are n times smaller, your mass is n3 times smaller, and your surface area is n2 times smaller. Accordinly to laws of physics, if only size will be scaled, you will somehow die, the most obvious way is that you'll lose your heat quickly and die even if themperature is around 20C. Or that you'll evaporate all your water through skin, etc. Okay, let you survived. For that, time needs to be scaled apporiately. That is, your speed of chemical reactions will need to be n times faster. So you will be only n2 or less times weaker, with n3 lower mass. Somewhat like n times lower gravitation, but even cooler. With such ratio, you should be able to just jump out. Or run around that thing, using inertia force to keep in touch with walls, and get out by spiral. Also, 60 seconds should be lot longer for you, so you should have more time to think...
If you'll survive somehow without becoming relatively stronger, your clothes will be too weak to stop blades.

[Edited by - Dmytry on February 9, 2005 10:29:58 AM]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Raduprv
Quote:
Original post by Cold_Steel
They just look like flat blades. Eventually, I supposed running an empty blender would kill the motor.

Why would it kill the motor? Placing too much load might kill it, but too little wouldn't.

Anyway, to the blender question, I don't think there is any way to survive. The clothes would be so small they are unlikely to stop the motor. And even if the motor is stoped, what can you do? Your clothes are not a rope, and you can't throw them over the edge. Even if you could, you'd need some sort of anchor at the other end so they won't fall back.
The correct answer would be: "Coming at peace with yourself and with the Universe" :D

If blender is empty, motor of course consumes less power, but almost all power it consumes is lost inside motor... and if there's something in blender, some power is spend on mixing and eventually heating that drink....
0

Share this post


Link to post
Share on other sites
Even better response to this one:
Quote:
Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"

I'd get out.
0

Share this post


Link to post
Share on other sites
Googles test should be, "What is the answer to the world, universe and everything".

If you say 42, you don't get the job..
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Nemesis2k2
Quote:
Original post by Coward
Quote:
Original post by Sagar_Indurkhya
3) You have 10,000 Apache servers, and 1 day to generate $1,000,000. What do you do?

Sell them for $100 each?

No, sell them for $150 each, and pretend you sold them for $100 each. :D


Well, I am pretty sure they would be like, write some code to solve some insane problem, and generate billions of dollars overnight. Then donate the profit to charity. I don't know.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by JexMX
Googles test should be, "What is the answer to the world, universe and everything".

If you say 42, you don't get the job..

My response would be that "the world, the universe, and everything" is not a question, and so I cannot give an answer.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by kSquared
Q: "How many gas stations would you say there are in the United States?"


I would say there were five if I didn't want to answer the question properly. It doesn't ask how many you think there are.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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μν
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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).
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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:

[list][*]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.[/list]
Fun, Fun [img]http://public.gamedev.net/public/style_emoticons/default/cool.gif[/img].
0

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
[/quote]

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
[quote]
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 [i]mass[/i] (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 [i]still[/i] have a 24-inch vertical leap regardless of how small you became. So given those facts, you could simply [i]jump[/i] 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]
0

Share this post


Link to post
Share on other sites
[quote name='way2lazy2care' timestamp='1301402331' post='4791684']
What about x=0? That has the same as above, but adds in that there is some number representing no quantity at all.
[/quote]

Nope. that equals 2, not 0.
1

Share this post


Link to post
Share on other sites
[quote name='JexMX' timestamp='1107970163' post='2903430']
What came first, the chicken or the egg?[/quote]

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

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

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1301416954' post='4791786']
[quote] but rotated array of integers.[/quote]
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.
0

Share this post


Link to post
Share on other sites
[quote name='way2lazy2care' timestamp='1301421174' post='4791812']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.
[/quote]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.
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0