exact opposite of reality: people are overworked, overstressed, and underpaid.
Efficiently implement 3 stacks in a single array.
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.
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?
Explain a database in three sentences to your eight-year-old nephew.
How would you store 1 million phone numbers?
Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Given an array of integers which is circularly sorted, how do you find a given integer.
Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
What do you know about Googles product and technology?
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.
Youre supposed to ask open-ended questions that test problem solving and general knowledge, then get into specifics. Once answered, you pick a topic in the answer and you dive in deeper. The goal to to find out where the candidates run out of ideas. Typically you want to test general knowledge, and find an area that you two can really dig deep into. At that point, you send the candidate to the whiteboard and have them start writing code.
Imagine you have a closet full of shirts. Its very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
Write a function to find the middle node of a single link list.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,DAA,AB,AC, AAA..) and returns a corresponding integer value (A=1,B=2, AA=26..).
How would you design a simple search engine?
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?
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?
Explain how congestion control works in the TCP protocol.
How would you deal with an angry or frustrated advertisers on the phone?
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?
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.
How much money you think Google makes daily from Gmail ads?
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?
interesting article. some questions are impossible to answer ?
What is the most efficient way to sort a million integers?
They also arent the best paid. Google is famous for underpaying their employees. They make up for it with their very generous benefits package. But in terms of straight salary, theyre about 20% below other valley tech companies.
$500 per share? Check out Warren Buffets Berkshire Hathaway
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
They dont have some of the happiest employees. Average software engineer is only there for a few years before they move on. In fact, if youve been there for a while and NOT been headhunted, it sort of looks weird. In any case, its long hours, and working on weekends is not at all uncommon (I once worked 11 weeks straight without a day off, and many of those were 14-16 hour days). They give you breakfast, lunch and dinner for a reason, you know.
January 20, 2013 at 5:16 pm, No one said:
Implement division (without using the divide operator, obviously).
What is the probability of breaking a stick into 3 pieces and forming a triangle?
Design an evacuation plan for San Francisco.
sounds like *someone* didnt get hired. ?
February 19, 2015 at 11:51 am, MR said:
Well now its 2014 and we know why so ma
Design the SQL database tables for a car rental database.
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.
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
What is the yearly standard deviation of a stock given the monthly standard deviation?
Nov, 2014: back to USD$ 535 I guess the first comment may have a point.
What is the size of the C structure below on a 32-bit system? On a 64-bit?
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.
November 11, 2009 at 4:24 am, Anonymous said:
If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
Design a class library for writing card games.
Find the maximum rectangle (in terms of area) under a histogram in linear time.
In Java, what is the difference between final, finally, and finalize?
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?
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?
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?
You think youll get rich with an option strike price above $500/share? Sorry. NEXT.
Describe a technical problem you had and how you solved it.
My God, i dont think they expect candidates to answer all of those questions
Your links at the top of this post are linking to your edit URLs. You need to update those to point to the published URL.
August 05, 2011 at 9:36 am, tdi78 said:
November 19, 2009 at 7:16 am, hari babu said:
Hi Lewis. Just read the article re. the Google questions in todays Guardian. Any chance of you giving answers to the 10 questions featured?
Write a regular expression which matches a email address.
How much should you charge to wash all the windows in Seattle?
Whats a creative way of marketing Googles brand name and product?
That ones easy: you dont. I remember reading that its impossible to speak to a real person at Googles AdWords department.
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 its 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?
If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building?
i posted your article on other readers to enjoy and learn from.
What sort would you use if you required tight max time bounds and wanted highly regular performance.
Another question How do you check a list of Google interview questions to ensure there are no duplicates?
How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
Especially those working on Half Life 3, they seem to have no work to do whatsoever
October 11, 2012 at 2:04 pm, Joe said:
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.
November 04, 2009 at 7:43 pm, Financial Samurai said:
So you dont bother with asking questions with simple factoid answers. For example, you arent going to ask what a mutex is, youre going to talk about them when the candidates code on the whiteboard has a race condition or whatever.
April 11, 2012 at 7:33 pm, foo bar said:
By the way, I interviewed a few hundred people for SWE positions while I was at Google. Many of your example questions not only arent asked, theyre explicitly forbidden. You are not allowed to ask frivolous brainteaser crap about manhole covers (there are actually two shapes which wont fall back into the hole, in case you were curious) or why 0xDEADBEEF is 3735928559 in decimal. You dont ask that nonsense because the questions are crap and tell you absolutely nothing about the candidate.
Whats the difference between a hashtable and a hashmap?
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!)
Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it?
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?
In Java, what is the difference between static, final, and const. (if you dont know Java they will ask something similar for C or C++).
January 07, 2014 at 7:27 am, Me said:
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.
What is the C-language command for opening a connection with a foreign host over the internet?
You have to get from point A to point B. You dont know if you can get there. What would you do?
November 13, 2009 at 11:47 pm, Anonymous said:
Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
November 19, 2009 at 10:44 am, BillR said:
November 06, 2009 at 7:48 am, Anonymous said:
Lets 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?
How many resumes does Google receive each year for software engineering?
How many times a day does a clocks hands overlap?
November 06, 2009 at 7:14 am, Sha said:
What would you say during an AdWords or AdSense product seminar?
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?
November 06, 2009 at 8:20 am, Mike said:
Explain the significance of dead beef.
How would you re-position Googles offerings to counteract competitive threats from Microsoft?
November 05, 2009 at 2:25 pm, Anonymous said:
A man pushed his car to a hotel and lost his fortune. What happened?
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).
Does anyone tell me if anyone gives an interview for the position of technical program Manager ..???
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.
Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
These interview questions are largely urban myth. I never heard 90% of these asked, and brain teasers have been banned for like 5 years at the company.
What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
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)?
What is multithreaded programming? What is a deadlock?
Theres a latency problem in South Africa. Diagnose it.
If you are the product marketing manager for Googles Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?
Engineers at Valve seem pretty happy.
Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.
Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office?
Heres a list of 140 Google interview questions. Many of our clients have interviewed and received Google job offers. Contact us for afree 15 minute interview analysisbefore your Google interview.
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?
Write some code to reverse a string.
June 28, 2014 at 12:08 pm, Billy WM said:
Great questions! But, the time to join Google was 5 years ago, not today.
Youre the 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?
How would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
Even if the strike prices are above $500 a share, they have some of the happiest employees. Not to mention, some of the best paying jobs in the valley. Not too shabby.
How would you deal with an angry or frustrated advertisers on the phone?
Write a program to find depth of binary search tree without using recursion.
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.
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.
Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.
November 05, 2009 at 2:38 am, Lewis, AKA Seattle Interview Coach said:
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
How does C++ deal with constructors and deconstructors of a class and its child class?
How many vacuums are made per year in USA?
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.
Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
I definitely got some questions like these when I screened for an engineering position very recently. (Very recently: Still dont know if I got the job) I didnt get silly brain teasers, but I did get questions about sort algorithm runtimes, and had to write some example code for them. It was not excessively hard, but unlike most of my interviews where I tell them what I know, they actually make you demonstrate it. For an hour. This is the one time where you can answer the question Where where I ever use this bit of knowledge when I couldnt look it up online? Answer: In a Google interview.
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?
How long it would take to sort 1 trillion numbers? Come up with a good estimate.
Describe the algorithm for a depth-first graph traversal.
If you are Product Manager for Googles Adwords, how do you plan to market this?
Some real advice: When given open-ended questions, immediately ask questions in return that would help define the constraints. They want you to sort something, ask if its a list of INTs, that sort of thing. But the best advice I can give anyone interviewing there is to sharpen your ability to understand engineers for whom English is a second language. Chances are very good that youll be interviewing with someone who is difficult to understand. Sad, but true.
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?
What sort would you use if you had a large data set on disk and a small amount of ram to work with?
November 18, 2014 at 9:23 am, Ricardo said:
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?
November 05, 2009 at 1:30 am, Tony Ruscoe said:
Create a cache with fast look up that only stores the N most recently accessed items.
There is a linked list of numbers of length N. N is very large and you dont 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).
What method would you use to look up a word in a dictionary?
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).
September 25, 2012 at 4:25 pm, The Future said:
Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
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 dont know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
How many golf balls can fit in a school bus?
Given a binary tree, programmatically you need to prove it is a binary search tree.
Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.
Im sure someone said that about Berkshire some years ago too.
My favorite question was to ask them to write a little program that solved a rubiks cube. Its got a bunch of possible answers and some that I saw were actually quite creative. (The best way, again in case youre curious, is to open the cube up and treat it as an asymmetrical grid. You go through it row and column and match up the six colors.)
If you liked this article, let us know by clickingLike.
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 PCs) 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.
Implement put/get methods of a fixed size cache with LRU replacement algorithm.
May 22, 2012 at 10:45 pm, Abhinav said:
November 05, 2009 at 10:27 am, Tony Symons said:
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.
SEE ALSO:Google PM interview class,Google Software Engineer interview class,Google Product Marketing interview class
good information, usefull for people attending for interviews.
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.
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
November 07, 2009 at 10:10 pm, schulz said:
Interesting .. btw i am curious to know the anwers also.. where could we find ?
You know there was a stock split right? That makes it worth double
December 12, 2013 at 2:27 am, QL said:
Imagine you have a closet full of shirts. Its very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
Name a tech job where this is not true
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.)
Fast forward to nowat 750 per share. You could have gotten rich.
What are three long term challenges facing Google?
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.
August 26, 2011 at 12:36 am, arshad said:
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 we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
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?
Who are Googles competitors, and how does Google compete with them?
How many piano tuners are there in the entire world?
How are cookies passed in the HTTP protocol?
How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?
November 16, 2009 at 10:55 am, Oliver Mezquita said:
Whats the difference between local and global variables?
Describe the data structure that is used to manage memory. (stack)
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?
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?
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.
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.
How would you find out if a machines stack grows up or down in memory?
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.)
Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.
How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
JUST PUBLISHED:60+ KILLER Salary Negotiation Scriptsto help you get a higher salary.
What kind of data structure would you use to index annagrams of words? e.g. if there exists the word top in the database, the query for pot should list that.
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.
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.
SEE ALSO:Google PM interview class,Google Software Engineer interview class,Google Product Marketing interview class
Write some code to find all permutations of the letters in a particular string.
November 04, 2009 at 10:06 pm, Zen Capitalist said:
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.
Similarly, you dont ask How would you store a million phone numbers?, you ask How would you sort a million phone numbers on a machine that only had 256KB of memory? You want to see if they can figure out how to solve the problem creatively given your constraints. And when they write it out, you ask OK, so that solution is O(n log n) how can you make it more efficient? And if they dont know about Big O notation, well then you immediately know youre not hiring that person.
Name a piece of technology youve read about recently. Now tell me your own creative execution for an ad for that product.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Link to Google interview questions for:
Have you ever used Googles products? Gmail?
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.
July 06, 2012 at 10:36 am, DrKeek said:
Given two files that has list of words (one per line), write a program to show the intersection.
How would you boost the GMail subscription base?