Inside Interviewing with Google

0 followers

0 Likes

So, you want to work for the most desirable company to work for in North America? Great! Google gets a tremendous volume of candidates and has to decide who are the right people for their culture, mission, and business. As the result of being a recognized "different" kind of company, you can imagine they would have unique hiring practices.

I've assembled 3 stories for you if you're interested in getting into Google. But, before you read them, a word of caution: Everyone is unique, different and is here to do meaningful work. Don't be put off or intimidated by the stories you hear. Hopefully they'll help you be a better job seeker no matter with whom you're interviewing.

- Dan.

------

From Business Insider | Nov 2009 | by Alyson Shontell

My Nightmare Interviews With Google

Google came to Syracuse’s campus to recruit new graduates when I was a senior. I attended the information session and learned which jobs I could qualify for. I created a fancy cover letter and resume, crossed my fingers and e-mailed them my documents. One week later I had an email in my inbox from Google.

Google wanted to interview me! Forbes’ #1 company to work for was interested in speaking with me about an Associate Product Marketing Manager position in Mountain View, California. I called everyone I could think of, ecstatic and day-dreaming that my job hunt might end quickly and painlessly with me surfing during lunch breaks at the Googleplex.

Everyone says your GPA doesn’t matter when you’re finding a job—those people obviously never applied to Google. My 3.6 suddenly seemed inferior. Google also wanted to know if I had received any job offers. They wanted to know who was recruiting me and how far along I was in my job search. Talk about salt on an open wound to a college senior. Sad and dejected, I ticked off the “No” [no one wants me] and “Yes” [I’m still unemployed] boxes. I should have realized then that this was shaping up to be a grueling interview process, but I was too excited to pay much notice.

To prepare for my two back-to-back conference calls, I googled Google and learned their history, products, current news, founders, locations, business models, competitors, AdWords, investors and mottos. My heart had never been in anything more and I was prepared for any curve ball they could throw. I practiced interviewing with friends and felt confident when my cell rang at 4:00pm sharp.

A young man was on the other line sounding just as nervous as I felt. The first five minutes of the allotted 30 were small talk. We went over my resume, previous internships and my career goals. My interviewer, Oliver, nervously cleared his throat between awkward silences during which he recorded my responses. I was on top of my game.

About ten minutes in, Oliver turned the tables. “I’m going to ask you a few questions that may sound strange,” he premised. I paused. Is there really any good response to a comment like that? He seemed to read my mind because he elaborated: “These questions are meant to test your analytical thinking.” Oh no. He was about to ask me the famous, ridiculously impossible Google questions I had been reading about online.

If you’ve never interviewed with the Internet giant, you may have never heard the types of questions they ask their interviewees. The searches I had done warned me that Google might inquire how much I’d pay someone to wash all of the windows in Seattle or what I’d do if I was shrunk to the size of a nickel and placed in a blender with churning blades.

“I want you to estimate,” Oliver began, “how much money you think Google makes daily from Gmail ads.” Oh. My. GOSH. Was he serious? The answer depended on so many different factors, none of which I had any clue how to guesstimate.

“Um, you mean a hard number? Maybe…$70,000?” Oliver’s hearty laugh told me my response was foolish. “Wait, can you just totally ignore that response? Scratch it out of your notes and pretend I never said that?”

“Don’t worry,” he mused, “I already did. You don’t have to give me an exact number, just tell me how you would figure out the answer.”

“Ok,” I began and I regurgitated everything I had learned about AdWords. “Google places four ads per e-mail opened in Gmail. Advertisers get to pick their click-through rates, which can be as little as $0.05, and they can set a maximum daily charge, which can be $5. The amount of money Google would make in a day would depend on the number of Gmail users, the number of e-mails those users receive and open per day, the number of advertisements they click on, and the rates the advertisers are charged.”

This answer wasn’t good enough. Now I was asked for an exact amount of revenue. “Say each G-mail user opens seven new e-mails a day. They would see 28 ads. If they click on ¼ of those ads, then only seven ads are clicked. If all advertisers are charged $0.05 per clicked ad, then the amount of revenue would be whatever $0.05 x 7 ads x the number of G-mail users is. Does that make any sense at all?”

“Kind of.” Oliver sounded confused. “You lost me at the ‘only clicking on ¼ of the ads’ comment. Let’s move on.”

The interview ended shortly afterward. Oliver politely indicated that HR would contact me again in a few weeks and he wished me good luck. My confidence was slightly bruised but I felt that, overall, I handled the interview well enough. I was left with 15 minutes to prepare for my next phone call, all of which I used to regain composure and review what I could have done better.

I thought Oliver was intimidating; the woman I spoke with next put him to shame. I gathered from Anna’s cold greeting that she did not have much time for me. We got right down to business. “Name a piece of technology you’ve read about recently.”

“Ok, today I was reading about Nike and Apple working together to make a shoe with a chip in it that helps you run in time with your music.”

“Now tell me your own creative execution for an ad for that product.”

My mind swirled as I pulled some crazy concoction out of my ass. “Well, Nike is known for having inspirational ads with little copy. I guess I would have a person running in Nike shoes, listening to their I-Pod, looking exhausted. The music would then pick up and each stride would coincide with the beat. The runner would get a second wind, reach their goal, and the “Just Do It” line would appear on the screen above an I-pod with a Nike swoosh background.”

She laughed a little before continuing which I took as an encouraging sign. “Now I’m going to ask you math problems.” Math?! I hadn’t taken a math course since freshman year of college. I was in trouble.

“Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?” I froze. The problem sounded easy but I didn’t want to cause an awkward silence trying to solve it.

“Um…well, ok. So, 20 out of 100 people click on the ad. Every ten clicks make one dollar…and you need 20 of them…” That’s as far as I got before I resorted to guessing answers, none of which were right. I was panicking and I couldn’t do a thing about it. My nerves were taking over. Anna could sense this and began to give me hints. None of them helped my frazzled brain.

After five painful minutes the annoyed interviewer gave me the answer. “100 people make two dollars, and two times ten is twenty. The answer is 100 people times 10 which is 1,000 people.” She made it sound so easy; I felt like a moron. As if she enjoyed my misery, she immediately fired off another math problem.

“Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.” This time I remained poised.

“There are about 300 million people in the nation” I began. “Let’s say 10 million of those are college students at four year schools. Only ¼ of those 10 million are seniors, so that would be roughly 2-3 million. If half of those students graduate with jobs, you’re looking at about 1.5 million kids.”

“Would you say that number seems high, low, or just about right?”

“I would say it sounds low, but maybe that’s because I’m going through the job-search process and I’m wishing the number was higher.”

I didn’t even get a sympathetic laugh. “That’s all. Good luck with your job search.” The phone clicked-- I was stunned. The abrupt sign-off was a clear indication that I wouldn’t be considered for round 2. Interviewing can be demoralizing, and that’s just how I felt as I sat with my cell in my hand, vowing to switch to Yahoo for life.

------

Google Questions that Will Make You Feel Stupid

by Nicholas Carlson | Silicon Valley Insider | Nov 4, 2009

Google is back to hiring again.
That's good news for thousands of junior managers and software developers out there hoping to find safe harbor during this recessionary storm.

The bad news:

- Google prefers Ivy Leaguers.
- It cares about your GPA, even if you're in your 30's.
- It wants people who want to change the world.

Seattle job coach Lewis Lin put together a list of 140 questions his clients have been asked by Google (article follows this one). We've added a link to the whole list at the end. In the meantime, here are a list of the 30 questions you'd get asked by Google:

Job: Product Manager

How many golf balls can fit in a school bus?

Answer: This is one of those questions Google asks just to see if the applicant can explain the key challenge to solving the problem.
Reader Matt Beuchamp came up with a dandy answer, writing:

I figure a standard school bus is about 8ft wide by 6ft high by 20 feet long - this is just a guess based on the thousands of hours I have been trapped behind school buses while traffic in all directions is stopped.

That means 960 cubic feet and since there are 1728 cubic inches in a cubit foot, that means about 1.6 million cubic inches.

I calculate the volume of a golf ball to be about 2.5 cubic inches (4/3 * pi * .85) as .85 inches is the radius of a golf ball.

Divide that 2.5 cubic inches into 1.6 million and you come up with 660,000 golf balls. However, since there are seats and crap in there taking up space and also since the spherical shape of a golf ball means there will be considerable empty space between them when stacked, I'll round down to 500,000 golf balls.

Which sounds ludicrous. I would have spitballed no more than 100k. But I stand by my math.

Of course, if we are talking about the kind of bus that George Bush went to school on or Barney Frank rides to work every day, it would be half that....or 250,000 golf balls.

Job: Product Manager

How much should you charge to wash all the windows in Seattle?

Answer: This is one of those questions where the trick is to come up with an easier answer than the one that's seemingly being called for. We'd say. "$10 per window."

Job: Product Manager

In a country in which people want only boys every family continues to have children until they get a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Answer: This one caused quite the debate, but we figured it out following these steps:
1. Imagine you have 10 couples who have 10 babies. 5 will be girls. 5 will be boys. (Total babies made: 10, with 5 boys and 5 girls)
2. The 5 couples who had girls will have 5 babies. Half (2.5) will be girls. Half (2.5) will be boys.
3. Add 2.5 boys to the 5 already born and 2.5 girls to the 5 already born. (Total babies made: 15, with 7.5 boys and 7.5 girls.)
4. The 2.5 couples that had girls will have 2.5 babies. Half (1.25) will be boys and half (1.25) will be girls.
5. Add 1.25 boys to the 7.5 boys already born and 1.25 girls to the 7.5 already born. (Total babies: 17.5 with 8.75 boys and 8.75 girls).
6. And so on, maintianing a 50/50 population.

Job: Product Manager

How many piano tuners are there in the entire world?

Answer: We'd answer "However many the market dictates. If pianos need tuning once a week, and it takes an hour to tune a piano and a piano tuner works 8 hours a day for 5 days a week 40 pianos need tuning each week. We'd answer one for every 40 pianos."

On Wikipedia, they call this a Fermi problem.

The classic Fermi problem, generally attributed to Fermi,[2] is "How many piano tuners are there in Chicago?" A typical solution to this problem would involve multiplying together a series of estimates that would yield the correct answer if the estimates were correct. For example, we might make the following assumptions:

There are approximately 5,000,000 people living in Chicago.
On average, there are two persons in each household in Chicago.
Roughly one household in twenty has a piano that is tuned regularly.
Pianos that are tuned regularly are tuned on average about once per year.
It takes a piano tuner about two hours to tune a piano, including travel time.
Each piano tuner works eight hours in a day, five days in a week, and 50 weeks in a year.
From these assumptions we can compute that the number of piano tunings in a single year in Chicago is
(5,000,000 persons in Chicago) / (2 persons/household) × (1 piano/20 households) × (1 piano tuning per piano per year) = 125,000 piano tunings per year in Chicago.
And we can similarly calculate that the average piano tuner performs
(50 weeks/year)×(5 days/week)×(8 hours/day)×(1 piano tuning per 2 hours per piano tuner) = 1000 piano tunings per year per piano tuner.
Dividing gives
(125,000 piano tuning per year in Chicago) / (1000 piano tunings per year per piano tuner) = 125 piano tuners in Chicago.

A famous example of a Fermi-problem-like estimate is the Drake equation, which seeks to estimate the number of intelligent civilizations in the galaxy. The basic question of why, if there are a significant number of such civilizations, ours has never encountered any others is called the Fermi paradox.

Job: Software Engineer
Why are manhole covers round?
Answer: So it doesn't fall through the manhole (when the plane ordinarily flush with the plane of the street goes perpendicular to the street.)

Job: Product Manager

Design an evacuation plan for San Francisco.

Answer: Again, this one is all about the interviewer seeing how the interviewee would attack the problem. We'd start our answer by asking, "what kind of disaster are we planning for?"

Job: Product Manager

How many times a day does a clock's hands overlap?

Answer: 22 times. From WikiAnswers:
AM
12:00
1:05
2:11
3:16
4:22
5:27
6:33
7:38
8:44
9:49
10:55

PM
12:00
1:05
2:11
3:16
4:22
5:27
6:33
7:38
8:44
9:49
10:55

Job: Software Engineer

Explain the significance of "dead beef."

Answer: Our (wrong) answer: Beef is always dead. Calling something "dead beef" is redundant -- a no-no for coders.

The actual answer, from a reader:
DEADBEEF is a hexadecimal value that has was used in debugging back in the mainframe/assembly days because it was easy to see when marking and finding specific memory in pages of hex dumps. Most computer science graduates have seen this at least in their assembly language classes in college and that's why they expect software engineers to know it.

From wikipedia: "0xDEADBEEF ("dead beef") is used by IBM RS/6000 systems, Mac OS on 32-bit PowerPC processors and the Commodore Amiga as a magic debug value. On Sun Microsystems' Solaris, it marks freed kernel memory. On OpenVMS running on Alpha processors, DEAD_BEEF can be seen by pressing CTRL-T.[3]"

Job: Software Engineer

A man pushed his car to a hotel and lost his fortune. What happened?

Answer: He landed on Boardwalk. (Painful, right?)

Job: Software Engineer

You need to check that your friend, Bob, has your correct phone number , but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Answer: Since you are just "checking," you ask him to call you at a certain time. If he doesn't, he doesn't have your number.

Too simple? A reader suggest: "In that case you need a check-sum. Have Bob add all the digits of your phone number together, write down the total, and pass that back to you."

Job: Engineering Manager

You're a captain of a pirate ship and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?

Answer: You divide the booty evenly between the top 51% of the crew.

Job: Product Manager

You have eight balls all the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Answer: Reader Hyloka nailed this one first:
Take 6 of the 8 balls and put 3 on each side of the scale. If the heavy ball isn't in the group of 6, you know it's one of the remaining 2 and so you put those two in the scale and determine which one. If the heavy ball is in the 6, you have narrowed it down to 3. Of those 3, pick any 2 and put them on the scale. If the heavy ball is in that group of 2, you know which one it is. If both balls are of equal weight, then the heavy ball is the one you sat to the side.

Job: Product Manager

You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Answer: The maximum egg drops for this method is 14 times.
Instead of partitioning the floors by 10, Start at the 14th floor, and then go up 13 floors, then 12, then 11, then 10, 9, 8, 7, 6, 5, 4 until you get to the 99th floor, then here. If the egg were to break at the 100th floor, it would take 12 drops (or 11 if you assume that it would break at the 100th floor). Say, for example, that the 49th floor was the highest floor, the number of drops would be the 14th, 27th, 39th, 50th (the egg would break on the 50th floor) plus the 40, 41,42,43,44,45,46,47,48, and 49th floor for a total of 14 drops.

Job: Product Manager

Explain a database in three sentences to your eight-year-old nephew.

Answer: The point here is to test the applicant's ability to communicate complex ideas in simple language. Here's our attempt, "A database is a machine that remembers lots of information about lots of things. People use them to help remember that information. Go play outside."

Job: Product Manager

You are shrunk to a 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?

Answer: This one is all about the judging interviewee's creativity. We'd try to break the electric motor.

Job: Product Manager

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Answer

Job: Product Manager

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

Answer

Job: Product Manager

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it's only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Answer

Job: Product Manager

You are at a party with a friend and 10 people are present including you and the friend. Your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

Answer

Job: Product Manager

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

Answer

Job: Product Manager

What is the probability of breaking a stick into 3 pieces and forming a triangle?

Answer

Job: Product Manager

There's a latency problem in South Africa. Diagnose it.

Answer

Job: Software Engineer

How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?

Answer

Job: Software Engineer

What's 2 to the power of 64?

Answer

Job: Software Engineer

Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

Answer

Job: Software Engineer

You're given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also.

Answer

Job: Software Engineer

How long it would take to sort 1 trillion numbers? Come up with a good estimate.

Answer

Job: Software Engineer

Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.

Answer

Job: Quantitative Compensation Analyst

How many resumes does Google receive each year for software engineering?

Answer

Job: Quantitative Compensation Analyst

You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don't know where the circular list begins, i.e.: 38, 40, 55, 89, 6, 13, 20, 23, 36.

Answer

-----

140 Google Interview Questions

in Seattle Interview Coach | Oct 24, 2009 by Lewis Lin

Here's a list of 140 Google interview questions. Many of our clients have interviewed and received Google job offers. The following questions are for these roles:

Product Marketing Manager

Product Manager

Software Engineer

Software Engineer in Test

Quantitative Compensation Analyst

Engineering Manager

AdWords Associate

Google Interview Questions: Product Marketing Manager

Why do you want to join Google?

What do you know about Google's product and technology?

If you are Product Manager for Google's Adwords, how do you plan to market this?

What would you say during an AdWords or AdSense product seminar?

Who are Google competitors, and how does Google compete with them?

Have you ever used Google's products? Gmail?

What's a creative way of marketing Google's brand name and product?

If you are the product marketing manager for Google's Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?

Google Interview Questions: Product Manager

How would you boost the GMail subscription base?

What is the most efficient way to sort a million integers?

How would you re-position Google's offerings to counteract competitive threats from Microsoft?

How many golf balls can fit in a school bus?

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?

How much should you charge to wash all the windows in Seattle?

How would you find out if a machine's stack grows up or down in memory?

Explain a database in three sentences to your eight-year-old nephew.

How many times a day does a clock's hands overlap?

You have to get from point A to point B. You don't know if you can get there. What would you do?

Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it's only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

How many piano tuners are there in the entire world?

You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Describe a technical problem you had and how you solved it.

How would you design a simple search engine?

Design an evacuation plan for San Francisco.

There's a latency problem in South Africa. Diagnose it.

What are three long term challenges facing google?

Google Interview Questions: Software Engineer

Why are manhole covers round?

What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?

A man pushed his car to a hotel and lost his fortune. What happened?

Explain the significance of "dead beef".

Write a C program which measures the the speed of a context switch on a UNIX/Linux system.

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Describe the algorithm for a depth-first graph traversal.

Design a class library for writing card games.

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

How are cookies passed in the HTTP protocol?

Design the SQL database tables for a car rental database.

Write a regular expression which matches a email address.

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

Explain how congestion control works in the TCP protocol.

In Java, what is the difference between final, finally, and finalize?

What is multithreaded programming? What is a deadlock?

Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D...AA,AB,AC,... AAA..) and returns a corresponding integer value (A=1,B=2,... AA=26..).

You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.

Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.

You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don't know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.

Describe the data structure that is used to manage memory. (stack)

What's the difference between local and global variables?

If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)

In Java, what is the difference between static, final, and const. (if you don't know Java they will ask something similar for C or C++).

Talk about your class projects or work projects (pick something easy)... then describe how you could make them more efficient (in terms of algorithms).

Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.

Write some code to reverse a string.

Implement division (without using the divide operator, obviously).

Write some code to find all permutations of the letters in a particular string.

What method would you use to look up a word in a dictionary?

Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?

What is the C-language command for opening a connection with a foreign host over the internet?

Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software.

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

There is a linked list of numbers of length N. N is very large and you don't know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).

Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.

You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also.

You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.

How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.

Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn

Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.

Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?

How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?

Let's say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same?

Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?

Given a binary tree, programmatically you need to prove it is a binary search tree.

You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?

Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.

Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Write a function to find the middle node of a single link list.

Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Implement put/get methods of a fixed size cache with LRU replacement algorithm.

You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity

How does C++ deal with constructors and deconstructors of a class and its child class?

Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.

What's 2 to the power of 64?

Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?

How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list.

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

How long it would take to sort 1 trillion numbers? Come up with a good estimate.

Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n

There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?

How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?

Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.

Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.

What's the difference between a hashtable and a hashmap?

If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?

How would you reverse the image on an n by n matrix where each pixel is represented by a bit?

Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).

Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space.

Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.

What sort would you use if you had a large data set on disk and a small amount of ram to work with?

What sort would you use if you required tight max time bounds and wanted highly regular performance.

How would you store 1 million phone numbers?

Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.)

What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {
char a;
char* b;
};

Google Interview Questions: Software Engineer in Test

Efficiently implement 3 stacks in a single array.

Given an array of integers which is circularly sorted, how do you find a given integer.

Write a program to find depth of binary search tree without using recursion.

Find the maximum rectangle (in terms of area) under a histogram in linear time.

Most phones now

0 Replies

Subgroup Membership is required to post Replies

Join Better Jobs Faster now

Topic	Replies	Views	Last Reply
Job Networking Groups Dan DeMaioNewton over 5 years ago	0	432	Dan DeMaioNewton over 5 years ago
Read: How to Write a Cover Letter (+ Samples) Dan DeMaioNewton over 5 years ago	1	232	Howie Lyhte over 5 years ago
Keep up to date with the latest ways to get better jobs faster Sheila Whittier over 5 years ago	0	210	Sheila Whittier over 5 years ago

Setup Information

Inside Interviewing with Google

My Nightmare Interviews With Google

Google Questions that Will Make You Feel Stupid

How many golf balls can fit in a school bus?

Answer: This is one of those questions Google asks just to see if the applicant can explain the key challenge to solving the problem. Reader Matt Beuchamp came up with a dandy answer, writing:

How much should you charge to wash all the windows in Seattle?

In a country in which people want only boys every family continues to have children until they get a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

How many piano tuners are there in the entire world?

Design an evacuation plan for San Francisco.

How many times a day does a clock's hands overlap?

Explain the significance of "dead beef."

A man pushed his car to a hotel and lost his fortune. What happened?

You're a captain of a pirate ship and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?

You have eight balls all the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Explain a database in three sentences to your eight-year-old nephew.

You are shrunk to a 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?

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

What is the probability of breaking a stick into 3 pieces and forming a triangle?

There's a latency problem in South Africa. Diagnose it.

How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?

What's 2 to the power of 64?

Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

How long it would take to sort 1 trillion numbers? Come up with a good estimate.

Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.

How many resumes does Google receive each year for software engineering?

140 Google Interview Questions

Answer: This is one of those questions Google asks just to see if the applicant can explain the key challenge to solving the problem.
Reader Matt Beuchamp came up with a dandy answer, writing: