I interviewed at Google, here are the GOOGLE INTERVIEW QUESTIONS!

[hypn0tik]

Originally posted by: Inspector Jihad
ok this took a while...so appreciate it...


http://img265.imageshack.us/my.php?image=untitled2zw.png]

[/URL]

Lol. That picture doesn't help. I was referring to the point you had in mind.

 

[Gunslinger08]

I think it's going to look like the intersection of 4 ellipses with foci at the vertices of the square, and a diameter of 0.5 from the center to the edges perpendicular to the foci.

Edit: I lied.

 

[Armitage]

Originally posted by: vladgur
inspite of what whiners here might say, these are kewl interview brainstormers. This is not a high school test, you dont have to get all of them right. You probably wont anyways, but if you go in the right direction, if you remember your basic data structures and basic algorithms, you should be able to answer many of them or at least start in the right directions. This shows your problem solving skills much better than your ability to memorize a some language's syntax.

Exactly - this test is about problem solving and analytical thinking. It's probably somewhat irrelevant if you get the right answer, if you took a well thought out or unique approach to getting it.

 

[Armitage]

Originally posted by: EKKC
WTF? i rather be unemployed

You'd rather be unemployed then be well paid to solve interesting and challenging problems in what is reported to be an excellent work environment??

 

[Minjin]

You guys still arguing #6? The 1/4 radius circle is correct. Why? Look at the picture posted. Now draw a diagonal from the center of the circle to one of the corners. The point where it intersects the circle should be equidistant to each of the two sides, NOT THE CORNER. That means that the two sides of box that can fit in the corner will be 1/4, meaning that IT'S diaganol will be root 2 over 4. Which is of course 1/4 of the diaganol of the big square.

Mark

 

[mugs]

hypn0tik -
what you said: http://pics.bbzzdd.com/users/mugs/imadork1.gif
the correct answer: http://pics.bbzzdd.com/users/mugs/imadork2.gif

I was wrong too... it's more like a square with rounded corners.

(note that it does not look like a square, but it's 41x41 characters)
(I wrote a quick and dirty program to figure it out obviously)

Edit:
High-res (71x71 square)
Circle: http://pics.bbzzdd.com/users/mugs/imadork3.gif
Right answer: http://pics.bbzzdd.com/users/mugs/imadork4.gif

 

[ones3k]

I sent my resume and transcript to them back in sept. I go to Umass amherst.

Also incase your wondering. I was only asked questions 1-5 during my interviews, each interview was 45min long. The interviewers asked other questions, so i only had about 15minutes per problem. The other questions were questions that other interviewees were asked and told me about them.

I honestly think i needed a flawless interview in order to havea chance, since i go to a state school.

this is how i did:
interview#1: got problem #1 and problem #2 (u can do #2 with 1 page transfer if u use a B-tree with a large branching factor and store the tree (minus the leaves) in memory. )

interview#2: didnt really get problem #3 fully, i needed hints during the interview, but i got problem #4
the solution i arrived at (with hints) was basically using a binary search type routine to search the median. #4 is just base26 conversion with a shift by 1

interview#3: this was the coding one, i messed this interview up the most. I coded an initial solution that i eventually found out was wrong. The interviewer then had me write diagrams on the board describing it, eventually showing me the solution was wrong. By the time i realized this and realized the fix, it was too late and i was hosed. This problem isnt really that hard, i was just nervous i guess.

My advice fo you Mattlear if u get an interview with them, make SURE you ace the coding interview 100%. Dont try to write code too soon, take an extra 5 or 10 minutes to prove the correctness in your head before you write code. You'll have PLENTY of time to code whatever it is you're thinking of, but you WONT have time to code a wrong solution and then a correct solution =P

 

[Minjin]

Originally posted by: mugs
hypn0tik -
what you said: http://pics.bbzzdd.com/users/mugs/imadork1.gif
the correct answer: http://pics.bbzzdd.com/users/mugs/imadork2.gif

I was wrong too... it's more like a square with rounded corners.

(note that it does not look like a square, but it's 41x41 characters)
(I wrote a quick and dirty program to figure it out obviously)

I don't know whats wrong, but there's no way our figure can have straight sides. Take a piece of paper and draw a point with a line beneath it. Now draw a line that is equidistant from point to line. It can't be straight because the further you get from the perpendicular line, the longer the line segment from the point gets while the line segment going to the side remains the same.

Mark
(disclaimer: not a math wiz)

 

[mugs]

Originally posted by: Minjin

Originally posted by: mugs
hypn0tik -
what you said: http://pics.bbzzdd.com/users/mugs/imadork1.gif
the correct answer: http://pics.bbzzdd.com/users/mugs/imadork2.gif

I was wrong too... it's more like a square with rounded corners.

(note that it does not look like a square, but it's 41x41 characters)
(I wrote a quick and dirty program to figure it out obviously)

I don't know whats wrong, but there's no way our figure can have straight sides. Take a piece of paper and draw a point with a line beneath it. Now draw a line that is equidistant from point to line. It can't be straight because the further you get from the perpendicular line, the longer the line segment from the point gets while the line segment going to the side remains the same.

Mark
(disclaimer: not a math wiz)

See my edit above with the "high-res" versions... it doesn't have straight sides, but it's not a circle.

Edit: Here's the C# program I used to generate that... you can check the logic, I'm pretty sure it's sound (it won't look right since there's no "attach code" button in OT, but if you quote my post you could be able to copy and paste it out with formatting):

using System;

namespace ConsoleApplication2
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
int distFromCenterX = 0;
int distFromCenterY = 0;
double distFromCenter;
int width = 70;
int distFromLeftRight = 0;
int distFromTopBottom = 0;
//
// TODO: Add code to start application here
//
Console.Write("\n\n\n");

//Y axis = i
for(int i=0; i<=width; i++)
{
//X axis = j
for(int j=0; j<=width; j++)
{

distFromCenterX = Math.Abs(width/2 - j);
distFromCenterY = Math.Abs(width/2 - i);
distFromCenterX = distFromCenterX * distFromCenterX;
distFromCenterY = distFromCenterY * distFromCenterY;
distFromCenter = Math.Sqrt((double)(distFromCenterY + distFromCenterX));

distFromLeftRight = (width - j < width / 2 ? width - j : j);
distFromTopBottom = (width - i < width / 2 ? width - i : i);


//PRINT A CIRCLE
/*if(distFromCenter<width/4)
{
Console.Write("O");
}
else
{
Console.Write(".");
}*/

//Correct answer
if(distFromCenter < distFromLeftRight && distFromCenter < distFromTopBottom)
{
Console.Write("O");
}
else
{
Console.Write(".");
}


}
Console.Write("\n");

}

Console.Read();

}
}
}

 

[hypn0tik]

Never mind.

 

[mugs]

Originally posted by: hypn0tik
Never mind.

Heh (I was going to paste a reply, but saw you edited first )

 

[Minjin]

Alright...so would the area of that inside 'box' be equal to the area outside of it? In other words, is the area 1/2?

Mark

 

[hypn0tik]

Originally posted by: mugs

Originally posted by: hypn0tik
Never mind.

Heh (I was going to paste a reply, but saw you edited first )

Hehehe, yeah.

Can you please explain how the following lines work?

distFromLeftRight = (width - j < width / 2 ? width - j : j);
distFromTopBottom = (width - i < width / 2 ? width - i : i);

I don't quite understand the syntax contained within the brackets.

 

[JRich]

The answer is 42.

 

[mugs]

Originally posted by: hypn0tik

Originally posted by: mugs

Originally posted by: hypn0tik
Never mind.

Heh (I was going to paste a reply, but saw you edited first )

Hehehe, yeah.

Can you please explain how the following lines work?

distFromLeftRight = (width - j < width / 2 ? width - j : j);
distFromTopBottom = (width - i < width / 2 ? width - i : i);

I don't quite understand the syntax contained within the brackets.

That's just a short way of writing:
if(width - j < width / 2)
distFromLeftRight = width-j;
else
distFromLeftRight = j;

essentially what it does is find the distance to the closer sides - left or right and top or bottom.

 

[rh71]

they better be paying 6 figures for those questions.

 

[mugs]

Originally posted by: Minjin
Alright...so would the area of that inside 'box' be equal to the area outside of it? In other words, is the area 1/2?

Mark

Hmmm... now ain't that a tickler. I haven't a clue.

 

[hypn0tik]

Well the only qualm I have with the program is that you can only consider integer values of x and y of a given point (x,y) on the grid.

Edit: Thanks for the clarification of the code.

 

[zainali]

how is the pay and benefits?

 

[mugs]

Originally posted by: hypn0tik
Well the only qualm I have with the program is that you can only consider integer values of x and y of a given point (x,y) on the grid.

Edit: Thanks for the clarification of the code.

Well yeah, it's only meant to give you an approximation of what it would look like... albeit skewed due to the characters being taller than they are wide. It'd look better if I used graphics and did a higher "resolution", but no matter what the resolution there will always be a discrete interval between each "pixel" (in this case each character is a pixel and that interval is 1... or you could look at it as having a height and width of 1 and the interval would be 1/71).

 

[The Green Bean]

WHOA!! Those are pretty difficult questions...especially if interviewed verbally :Q

 

[hypn0tik]

Originally posted by: mugs

Originally posted by: hypn0tik
Well the only qualm I have with the program is that you can only consider integer values of x and y of a given point (x,y) on the grid.

Edit: Thanks for the clarification of the code.

Well yeah, it's only meant to give you an approximation of what it would look like... albeit skewed due to the characters being taller than they are wide. It'd look better if I used graphics and did a higher "resolution", but no matter what the resolution there will always be a discrete interval between each "pixel" (in this case each character is a pixel and that interval is 1... or you could look at it as having a height and width of 1 and the interval would be 1/71).

What you say is true. However, if you look closely at your 'right' answer, you have the potential to get a circle out of it if you 'fill in the blanks' so to speak.

 

[Suspicious-Teach8788]

Originally posted by: EKKC

Originally posted by: ronin2kr6
Ironic if someone could have googled the answers before hand

maybe they allow you a laptop or pda to the interview so you can google the answers!!!

That is the test. The perfect google employee would know to use their resources and hence use google. THey test you to see if you open IE or Firefox and they also see if you dare use Yahoo or some other search engine other than Google.

 

[mugs]

Originally posted by: hypn0tik

Originally posted by: mugs

Originally posted by: hypn0tik
Well the only qualm I have with the program is that you can only consider integer values of x and y of a given point (x,y) on the grid.

Edit: Thanks for the clarification of the code.

Well yeah, it's only meant to give you an approximation of what it would look like... albeit skewed due to the characters being taller than they are wide. It'd look better if I used graphics and did a higher "resolution", but no matter what the resolution there will always be a discrete interval between each "pixel" (in this case each character is a pixel and that interval is 1... or you could look at it as having a height and width of 1 and the interval would be 1/71).

What you say is true. However, if you look closely at your 'right' answer, you have the potential to get a circle out of it if you 'fill in the blanks' so to speak.

Yeah... but if it was a circle it'd look like the example of a circle I made. Remember, we know 4 points (N,S,E,W to use my compass example) are 1/4 from the center, so if it was a circle it'd have to be a circle of radius 1/4. But it doesn't look like the circle of radius 1/4 that I generated.

 

[hypn0tik]

Originally posted by: mugs

Originally posted by: hypn0tik

Originally posted by: mugs

Originally posted by: hypn0tik
Well the only qualm I have with the program is that you can only consider integer values of x and y of a given point (x,y) on the grid.

Edit: Thanks for the clarification of the code.

Well yeah, it's only meant to give you an approximation of what it would look like... albeit skewed due to the characters being taller than they are wide. It'd look better if I used graphics and did a higher "resolution", but no matter what the resolution there will always be a discrete interval between each "pixel" (in this case each character is a pixel and that interval is 1... or you could look at it as having a height and width of 1 and the interval would be 1/71).

What you say is true. However, if you look closely at your 'right' answer, you have the potential to get a circle out of it if you 'fill in the blanks' so to speak.

Yeah... but if it was a circle it'd look like the example of a circle I made. Remember, we know 4 points (N,S,E,W to use my compass example) are 1/4 from the center, so if it was a circle it'd have to be a circle of radius 1/4. But it doesn't look like the circle of radius 1/4 that I generated.

Good point. I guess I'm wrong.