Tags: interview, interview process, questions |
Posted by Admin on
10/26/2012 8:37 AM |
Comments (0)

There is nothing like the feeling of elation after you know you ace'd your interview.
Or, maybe you gave it your best shot but fell short.
Either way or in between, this is the perfect place, to share your experience. Take a few minutes to answer any or all of the questions below in the comments section.
All comments will be reviewed for appropriateness before being posted and your name/user id will not appear anywhere in website. This is your chance to give real and honest feedback in a completely anonymous way!
1. What company were you interviewed by and which location?
2. What position were you being considered for?
3. What kind of interview was it? i.e., phone, first round in person, final, etc.?
4. How were you treated by the company before, during, and after the interview?
5. What was your general impression of the company?
6. Please share some of the interview questions.
7. Do you think you'll get an offer and if so, do you think you'll accept?
The Googleinterview process is Infamous for it’s mind boggling and creative methods to test new candidates. Here are two I’ve selected for you to first try to solve yourself, then see Google’s perfect answer.
Q. How many golf balls will fit in a Mini?
A.
We will use a new mini opposed to a classic mini shape.
It is shorter than a person, so maybe its 4.5 feet high, but with the clearance off the floor, lets say roughly 4 foot. There’s space for two people to sit side by side, with roughly 2.5 feet per person. So that’s 5 feet wide. It’s probably two people long, which is approximately ten feet. However the bonnet takes up half the length, so the usable length is 5 feet. The interior volume, then, is about 4 X 5 X 5, which is 100 cubic feet.
A golf ball is somewhat bigger than an inch in diameter. Let’s say that 10 golf balls line up to make a foot. A cubic lattice of 10 X 10 X 10 golf balls, an even thousand, would just about occupy a cubic foot. That gives a quick answer of about 100 X 1,000 = 100,000
Or ….. take into consideration that each ball could be packed more densely given the shape of each. Effectively resting in an imaginary Lucite cude whose edges equal the ball’s diameter. You stack those Lucite cubes like building blocks. This would mean that the balls occupy about 52 per cent of the space. Break out of the imaginary Lucite boxes, and you can pack far more balls in a volume. This is an empirical fact. Physicists have done experiments by pouring steel balls into big flasks and calculating the density. The resulting random packing occupies anywhere from 55 to 64 per cent of the space. That’s denser than a cubic lattice. It’s also a fairly large range. How you fill the container matters. When the spheres are added gradually and gently, like sand pouring through an hourglass, the density is at the low-end of the range. When the container is shaken vigorously, the spheres settle into a denser packing of up to 64 per cent.
Where does this leave us? Someone willing to painstakingly stack golf balls in the cannonball pattern can pack about 42 per cent more gold balls in the mini than you’d estimate from a cubic lattice (or as above). That seems an absurd amount of labor, even for an absurd question. The reported density of stirred random packing is a more realistic goal. You might achieve that by pouring golf balls into the mini and stirring with a stick to settle them. That would give a density of about 20 per cent more than that of a cubic lattice. You might therefore increase your final estimate by 20 per cent, from 100,000 to 120,000.
For the record, the Mini website states a Mini Cooper Hardtop is 145.6 inches long, 75.3 inches wide (including mirror) and 55.4 inches high. The regulation diameter of a golf ball is 1.690 inches, give or take 0.005 inches.
Q. It’s raining and you have to get to your car at the far end of the car park. Are you better off running or not, if the goal is to minimize how wet you get?
What if you have an umbrella?
A.
To answer this question, you must reconcile two conflicting trains of thought. The case for running is this; the longer you are in the rain, the more drops fall on your head, and the wetter you get. Running shortens your exposure to the elements and thereby keep you drier.
There’s also a case for not running; In moving horizontally, you slam into raindrops that wouldn’t have touched you had you been standing still. A person who runs in the rain for a minute gets wetter than a person who just stands in the rain for a minute.
That valid point is mostly besides the point. You have to get to your car and there’s nothing to be done about that. Imagine yourself zipping across the car park at infinite speed. Your senses are infinitely accelerated, too, so you don’t slam into cars. From your point of view, external time has stopped. It’s like the bullet time effect in a movie. All the raindrops hand motionless in the air. Not one drop will fail on your head or back or sides during the trip. The front of your clothing will sop up every single raindrop hanging in the path from shelter to car.
When you travel at normal speed, you’re fated to run into those raindrops or, rather their successors. At normal speed, you also have drops falling on your head. The number of raindrops you encounter will depend on the length of your horizontal path and also on the time it takes to travel that path. The length of the path is a given. The only thing you can control is the time it takes. To stay as dry as possible, you should run as fast as possible. Running makes you less wet –provided you don’t have an umbrella.
Had you an umbrella as wide as a city block, and where you able to hold it, it wouldn’t matter whether you sauntered or sprinted. You’d be dry as toast.
Most umbrellas are barely big enough to keep the user dry when he or she is standing in general, vertical rain. In practice, you expect to get a little wet.
Umbrellas work by creating a rain shadow, a zone where there are no raindrops. In a vertical downpour, and with a circular umbrella, the rain shadow is a cylinder. When the rain is coming at an angle, the rain shadow becomes a skewed cylinder. However, as every seasoned umbrella user knows, its best to point the umbrella in the direction of the driving rain. This makes the rain shadow a proper cylinder again. Now pointed at an angle to the vertical,
The standing human body doesn’t fit so well into a slanted cylinder. Were a hurricane driving the rain at you horizontally, you would have to hold the umbrella horizontally, and a tree foot diameter would protect only about half your body. The rest would get soaked.
Wind is bad, and so is motion. The skilled umbrella wielder knows to tilt the umbrella forward, in the direction of the motion, to get the maximum coverage. In fact, wind and motion are indistinguishable as far as optimal umbrella pointing goes. Running at ten miles an hour in windless, vertical rain demands the same tilt as standing still in ten-mile an hour wind. Either way, the raindrops are coming at you ten miles an hour, horizontally, in addition to their downward velocity.
In vertical rain, you’re best off walking slowly. The umbrella will not have to be tilted much, and your body should fit within the rain shadow. Ideally, you should walk no faster than the speed where the rain shadow just covers your feet. Then you’d stay dry.
Reality is messier than that, there are always going to be gusts of wind, spatter from pavement, and runoff from the umbrella itself. The rain hitting the top of the umbrella does not disappear: it slides off the umbrella and falls in a cylindrical sheet encircling the rain shadow. There is more rain in that run off zone than anywhere else. That means that any part of your body that intersects the runoff zone gets wetter faster than it would have you not used an umbrella at all.
The advantage of slowness diminishes in high headwinds.
The umbrella has to be pitched at such angle that your lower body is out of the rain showdown. You’ll get half soaked no matter what you do.
All that reasoning boils down to the advice you may have heard from mum: walk if you’ve got an umbrella: run if you don’t.

Tags: algorithm, questions, puzzle, software engineer, tech leader, |
Posted by Admin on
1/26/2011 2:16 PM |
Comments (0)

Here’s a list of 150 Google interview questions. Don't ask us where we got it from...
Product Marketing ManagerWhy 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’s 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?
How much money you think Google makes daily from Gmail ads?
Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.
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?
Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.
Product ManagerHow 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?
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?
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?
How many vacuum’s are made per year in USA?
Software EngineerWhy 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;
};
Software Engineer in TestEfficiently 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 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.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
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.
Create a cache with fast look up that only stores the N most recently accessed items.
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?
Given two files that has list of words (one per line), write a program to show the intersection.
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.
Quantitative Compensation AnalystWhat is the yearly standard deviation of a stock given the monthly standard deviation?
How many resumes does Google receive each year for software engineering?
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?
What is the probability of breaking a stick into 3 pieces and forming a triangle?
Engineering ManagerYou’re 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?
AdWords AssociateHow would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
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 announce that at least one husband has been
unfaithful. What happens?
Any answers? :)

Tags: product marketing manager, questions |
Posted by Admin on
2/9/2010 1:15 PM |
Comments (0)

So I decided to compile a list containing all the interview questions (some with my version of the answer) I could find for the Associate Product Manager and Product Manager position for Google.Before I post them, here is a little something I found.Google is aware of these questions (they must be since I used them to find these questions), so it is not far fetched to assume that the questions you will be asked on your google interview won’t be similar to that listed below. I found that interviewers are encouraged to come up with their own questions and there is a list of ‘banned’ questions (questions widely known and listed in sites like mine). If you get a question from this list and they figure out (since you were to quick to answer), they will either make it harder or ask another one…That being said, use this list as a way to prepare yourself from past questions asked for associate product manger and product manager.Questions in green are most recent questions (questions asked within 6-month period position).1) How many buses does the local transportation corporation own?My Answer: Estimate what the local population is (say 100,000), and percentage who would use local transportation (say 75%). From there estimate how many major routes you have (routes to say from city A to city B/downtown/mall/universities). How many buses will be traveling those routes (taking into account when the busiest times are should have the most buses out and remember that some of these buses go both ways e.g travel from city A to city B and back to city A.) Take into account how many you can fit into a bus, you can estimate how many buses a local transportation corp could potentially own.2)How would you handle someone who is just not doing the work, doesn’t get along with anyone, and is generally not working out?My Answer: Response to this question reflects on the individuals management and leadership style. But the candidate being interviewed should also keep in mind what company or team policy is when addressing the above issue.3)How many bottles of shampoo are produced in the world a year?My Answer:approximate 30 million = population of Canadaapproximate 6 billion = World Population23% of the world’s population is 3rd world population2% of the world’s population don’t use shampoo b/c they are bald or use soap25% total25% of 30 million don’t use shampoo, use soap, are bald, or cannot afford to purchase shampoo (third world) (-7.5 million) =22.5millionOne bottle of Shampoo lasts approximately 2 months, giving us 6 bottles a year per person.22.5million *6 = 133.1 million bottles in Canada6 billion – 25% = 4.5 billion4.5 billion *6 = 27.0 billion bottle per year4) You have 15 horses that run various speeds. You own a race track on which you can race the horses, and this track holds a maximum of 5 horses per race. If you have no stopwatch or other means of telling exactly how fast the horses are, how many races would you need to run between the horses to be ABSOLUTELY SURE which horses are first, second, and third fastest?My AnswerRace 1: Horse 1,2,3,4,5 => Assume 1,2,3 win in that orderRace 2: Horse 6,7,8,9,10 => Assume 6,7,8 win in that orderRace 3: Horse 11,12,13,14,15 =>Assume 11,12,13 win in that orderRace 4: Horse 1, 6, 11 (all first place winners) =>Assume 1 wins first (1 is the fastest) for the sake of simplicity and 6 and 11 came 2nd and 3rd placeRace 5: Horse 6, 11, 2, 7, 3 - Notice I did not choose horse 12 in this race because we assumed from Race 4 that horse 11 came in third place so it is of no value having horse 12 in the race.Total Race 51st Place is Horse 1, 2nd and 3rd Place is found from Race 55) Follow up, now you have 16 horses. How many races would you need to conduct to find first, second, and third?My AnswerFirst three races are identical to the above three racesAssumption 1:Race 4: Horse 16, 1, 6, 11 => Assume 16 wins first, and Horse 1 and 6 came second and third.Race 5: Horse 1, 6, 2, 7, 3 =>Notice I did not choose any horses from Race 3 results, this is because we know that horse 11 did not come out in the top 3 in Race 4.Total Race 5Assumption 2:Race 4: Horse 16, 1, 6, 11 => Assume 1 wins first, and Horse 6 and 16 came second and third.Race 5: Horse 6, 16, 2, 7, 3=>Notice I did not choose any horses from Race 3 results, this is because we know that horse 11 did not come out in the top 3 in Race 4.Total Race 56) Tell me about yourself? -Yep, they still ask this question7) How would you boost the GMail subscription base?8 ) What is the most efficient way to sort a million integers?9) How would you re-position Google’s offerings to counteract competitive threats from Microsoft?10) You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density.11) You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?12) How much should you charge to wash all the windows in Seattle?13) How would you find out if a machine’s stack grows up or down in memory?14) You have to get from point A to point B. You don’t know if you can get there. What would you do?15) How many piano tuners are there in the entire world?16) 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?Weighing 1: weight 3 balls on each side.If( 3 balls are equal)Weighing 2: weight the last 2 balls. The heavier is one of these.ElseWeighing 2: weight the heavier group from the first, put 1 ball on each weigh – if they are the same, the heavier one is the one you didn’t weigh…else the heavier one will be shown.17) 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.18 ) Describe a technical problem you had and how you solved it.19) How would you design a simple search engine?20) Design an evacuation plan for San Francisco.21) There’s a latency problem in South Africa. Diagnose it.22) What are three long term challenges facing Google?23) What do you know about Google’s product and technology?24) If you are Product Manager for Google’s Adwords, how do you plan to market this?25) What would you say during an AdWords or AdSense product seminar?26) Who are Google’s competitors, and how does Google compete with them?27) What’s a creative way of marketing Google’s brand name and product?28 ) 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?29) How much money you think Google makes daily from Gmail ads?30) Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.31) 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?32) Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.33) If you were given the land prices in the Bay Area, what would you pick, the mean or the median? Why?34) Estimate the revenue of various free web services from Google and competitors.35) You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently36) What is Google’s primary source of revenue?Adwords, Advertisement, TVAds37) How will you make Google win in (specific regional zone)?38 ) What website do you visit the most and what would you do as PM for that website?39) Airports are inefficient. What would you do to improve them?40) It is difficult to remember what you read, especially after many years. Contemplate how to address this.41) If Google were to offer a TV commercial service, how would you implement this?42) What is your favorite google product and what would you change about it?43) How would you design google maps?44) What google product do you like the best and how would you improve it?45) Why is a good user interface good for the company?Good user interface encourage the visitor to stay longer on the page, explore other pages, click on advertisement, and retreive and access information easily. Companies can build their identities on a good user interface since users will associate them with it. A good UI (e.g. Google Search Engine) can become their brand and if it is done right, it saves a lot of money in re-doing it or advertising.46) What is the marginal cost of a gigabyte in gmail?47) Name three web sites (non-Google sites) that I visit often and like. Comment on what I like about the user interface / design.48 ) Follow up with the above, choose one of the three sites and comment on what new feature/project I would work on and how I would design it.49) Elevator design – concentrate on if there is only one elevator in the building(what would I change in the design). Then moved up to having two elevators in a building..50) How many vacuum’s are made per year in USA?51) If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?Answer: 7.5 degrees ( 30 degrees between ‘3′ and ‘4′, 30/4 = 7.5 degrees)52) 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: Recursion Problem – If the women in the village know instantly when other men in the village have cheated, we can use this to our advantage in answering the question. If one man has cheated on their wife, then his wife will know he cheats since no one else is cheating and will thus meet his demise. Take example if two men cheats, one of the wives will know one cheating husband in the village and must wait one day to see if she hears of another man cheating – if not, she knows her husband has cheated and therefore kills him.53) 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: P(30min) = 0.95 ; Pbar(30min) = 0.05; Pbar(10min)=(1/3)^(0.05)=0.368 ; P(10min)=1-Pbar(10min) = 0.6312 = 63.12%54) 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: Classic Microsoft question.Trip A –> B A < — B Total TimeTrip 1 1min, 2 min 2 minTrip 2 1 min 3 minTrip 3 5 min, 10 min 13minTrip 4 2 min 15minTrip 5 1min, 2 min 17 min55) 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: Probability of someone sharing a birthday with you is P(share b-day) = 1/365 ; hence P(no share b-day)=364/365. I wouldn’t take the bet.56) 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 : Anyone who knows me knows I have a mild case of OCD. I would have my closet organized (install shelving units) and compartmentalize some sections visually. I have a section for shirts I would wear out and section for shirts I would wear at home (worn out, great for spring cleaning). Then in each section I would organize the shirts by color from white to black. A relatively simple question, but I think Google asks this to check your organizational skills and for a software engineer – grouping (think hash tables)57) Explain a database in three sentences to your eight-year-old nephew.Answer: There are many answers to this question.1) Dictionary is like a database. You have word and what the word means.When I think of a database, I think of a filling cabinet my parents have where each hanging folder contains information. One folder has my grades, another has my birth certificate and birth hair, another has some pictures of me and my art work in elementary…etc.58 ) How would you re-position Google’s offerings to counteract competitive threats from Microsoft?Answer : My first thought – remove the awful word…’work around’ from Google’s work practice. This was my most hated two words I heard from there.59) 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.)Answer:If you have 2 Pirates involved, only one pirate needs to support with pirate ‘2’s decision (namely pirate ‘2′ himself). Pirate ‘2′ would be highest in chain and hence can take all 100 gold coins since half would agree with this decision.If you have 3 Pirates involved, pirate ‘3′ needs only one other pirate to support him. Pirate ‘3′ is aware of the 2 pirate scenario if he dies and hence offers pirate ‘1′ 1 piece of gold to vote in his favor. Pirate ‘1′ will take the offer because 1 piece of gold is better than none. So end result is Pirate ‘1′ gets 1 piece of gold and Pirate ‘3′ takes 99 piece of gold (leaving Pirate ‘2′ with nothing).If you have 4 Pirates involved, you only need one other pirate to support you. Pirate ‘4′ is aware of the 3 pirate scenario if he dies and hence can offer pirate ‘1′ 2 pieces of gold to have his vote, but pirate ‘4′ is greedy. Instead he offers 1 piece of gold to pirate ‘2′. This gives him the vote from one other pirate he needs for support.Draw a table showing the 2-4 pirate scenarios, and you will notice a pattern. From this you can easily come up with a solution for the 5 Pirate scenarios. 1 2 3 4 52 100 3 1 99 4 1 99 5 1 1 9860) How many golf balls can fit in a school bus?Answer:Calculate size of bus (approx in feet 8lengthx6widthx20depth) = 960 sq. feet (convert to sql inches *1728) = 1,658,880; golf ball is 2.5 cubic inches (4/3* pi*0.85inches radius) ; 1,658,880/2.5=663,552 ; don’t foget seats and such so round down to say 500,000Got any Google Interview Questions that are not listed here? Feel free to add them in the comment box.61) How many people run marathon in UK every year?62) Describe the operation of Layer 2 (Data Link Layer) of the 7-layer ISO stack in as much detail as possible.63) How do you code integer division without using divider (‘/’)int x =20; int y = 5;log(x) – log(y) = log(answer)10^(answer) = 4 = answer;64) What are three things Google should know before releasing a product in Country XYZ?65) A man pushed his car to a hotel and lost his fortune. What happened?66) How would you determine if someone has won a game of tic-tac-toe on a board of any size?67) How many resumes does Google receive each year for software engineering?68) How would you design google maps?
It was hard to follow tech news this week without getting icky
lawyer-stuff all over you. AT&T filed suit against Verizon, Intel
got sued by New York State, an alleged cable modem hacker got indicted,
and EMI sued to stop a tiny music Web site from sharing The Beatles'
love. Also: A former high-tech CEO looks for better position in D.C.,
and Google seeks employees who speak nothing but geek. Do you have the
qualifications to ace this week's quiz? Give yourself 10 points and a
pat on the back for each correct answer. Now hand over your résumé and
begin.
1. The Beatles' music will finally be available in disc-less digital
form this December. Where will you soon be able to find the Fab Four?
a. On Apple's iTunes Storeb. At BlueBeat.comc. On Verizon phonesd. On an apple-shaped USB drive
2. New York State Attorney General Andrew Cuomo is beating on Intel
like a drum, accusing the chip giant of all manner of bad behavior.
Which of the following is one of the official charges?
a. Misleading advertising
b. Strong-arming PC makers using bribery and coercion
c. Shipping defective merchandise
d. Charging exorbitant early termination fees
3. AT&T is suing Verizon. What's the dispute about?
a. Verizon's attempts to wrest the iPhone from AT&T
b. AT&T's claim to offer the "fastest 3G network"
c. Verizon's exorbitant early termination fees
d. Maps
4. Pew Research has conducted a study of the dominant ways people
interact. How many days per year, on average, do Americans communicate
via cell phone?
a. 210
b. 195
c. 125
d. 72
5. Watch your back, Twitter. A new microblog has formed and it's
apparently got God on its side. What's this new blessed blog called?
a. TweetBabyJesus
b. HeavenlyTwits
c. ChristianChirp
d. ChristianTwerp
6. "The decisions made in Washington impact every family and every
business, of any size, in America. Throughout my career, I've brought
people together and solved problems, and that is what I plan to do in
government: Set aside ego and partisanship and work to develop
solutions to our problems." What former high-tech CEO plans to bring
the hard-won lessons of business management to Washington, D.C.?
a. Jerry Yang
b. Carly Fiorina
c. Hector Ruiz
d. Meg Whitman
7. Alleged cable modem hacker Ryan Harris was indicted this week by
federal prosecutors in California. What is Harris's hacker alias?
a. DerCable
b. DerEngel
c. DerSpiegel
d. DerWeinerschnitzel
8. Careers coach Lewis Lin has released a list of 140 questions
Google asks of prospective employees. Which of the following questions
is not on Lin's list?
a. How many golf balls can fit in a school bus?
b. There's a latency problem in South Africa. Diagnose it.
c. Explain the significance of "dead meat."
d. Why are manhole covers round?
9. The Doodle -- the six-letter logo that adorns Google's otherwise
sparse home page -- changed multiple times in the last week to honor
various icons of childhood. Which of the following was not a Google
Doodle?
a. Wallace and Gromit
b. Sesame Street
c. Asterix & Obelix
d. The Great Pumpkin
10. Take the number of iPhones Apple sold the first weekend it was
available in China and multiply by the new early termination fee
Verizon plans to charge users of smartphones who bail on their
contracts. Add the volume of apps in the iPhone Store, rounded to the
nearest large number. Download that to your Windows Mobile phone and
pray someone will buy you an iPhone for Christmas. What do you get?
a. 1,850,000
b. 185,000
c. 18,500
d. 1,850
Answer key
Question 1: The Beatles' music will finally be available in
disc-less digital form this December. Where will you soon be able to
find the Fab Four?
Correct Answer: On an apple-shaped USB drive
The digitally remastered tunes will be available from record company
EMI on a 16GB key drive shipped in a container made to resemble Apple
Corp.'s Granny Smith-style logo. At press time BlueBeat.com, which was
selling Beatles tracks for 25 cents each, found itself sued by EMI. The
odds of the site surviving until December? Tomorrow never knows.
Question 2: New York State Attorney General Andrew Cuomo is
beating on Intel like a drum, accusing the chip giant of all manner of
bad behavior. Which of the following is one of the official charges?
Correct Answer: Strong-arming PC makers using bribery and coercion
Cuomo's 83-page complaint echoes what the European Union fined Intel
$1.5 billion for, and AMD has been suing Intel over since 2005 -- the
company kicked back billions to computer makers who agreed to limit the
use of AMD chips in their machines, and threatened those who would not
be bribed. Others argue that, with the price of computers plummeting
regardless of Intel's bad behavior, the harm to consumers is largely
imaginary. Looks like somebody's running for governor.
Question 3: AT&T is suing Verizon. What's the dispute about?
Correct Answer: Maps
More specifically, AT&T is suing Verizon over an ad campaign
showing maps of their respective 3G coverage, with Verizon's mostly
full and AT&T's nearly empty. AT&T claims the map ad is
misleading because it implies AT&T offers no data coverage over
much of the United States, when it in fact offers slower 2G service.
Thus suggesting a new AT&T ad slogan: Slow service is better than
no service.
Question 4: Pew Research has conducted a study of the
dominant ways people interact. How many days per year, on average, do
Americans communicate via cell phone?
Correct Answer: 195
According to the Pew Internet & American Life Project, Americans
communicate face to face an average of 210 days a year, followed by
mobile phones (195 days), texting and landlines (tied at 125), e-mail
(72), instant messaging (55), and social networks (39). Their
conclusion: Technology is not turning us into hermits. The caveat? Pew
did not release data showing how many people talk on their phones,
text, or e-mail during face-to-face meetings.
Question 5: Watch your back, Twitter. A new microblog has
formed and it's apparently got God on its side. What's this new blessed
blog called?
Correct Answer: ChristianChirp
The service was launched by Net entrepreneur James L. Paris after
Twitter allegedly shut down his account temporarily for "posting an
article in support of Rush Limbaugh." FYI, Paris's other venture,
ChristianMoney.com, aims to "help you make the most of God's money."
Because, after all, He's got more money than, well, Himself.
Question 6: "The decisions made in Washington impact every
family and every business, of any size, in America. Throughout my
career, I've brought people together and solved problems, and that is
what I plan to do in government: Set aside ego and partisanship and
work to develop solutions to our problems." What former high-tech CEO
plans to bring the hard-won lessons of business management to
Washington, D.C.?
Correct Answer: Carly Fiorina
The former HP chief confirmed long-standing rumors by officially
joining the U.S. Senate race in California. She'll be fighting
Republican Assemblyman Chuck Devore for the chance to challenge Senator
Barbara Boxer a year from now. Considering the shape HP was in when she
left, Fiorina might have a better shot running on the Amnesia Party
ticket.
Question 7: Alleged cable modem hacker Ryan Harris was
indicted this week by federal prosecutors in California. What is
Harris's hacker alias?
Correct Answer: DerEngel
Harris, author of "Hacking the Cable Modem," has been charged with
conspiracy and fraud for allegedly selling software and modded modems
that allowed customers to access cable ISPs and/or boost their
bandwidth for free. He's facing up to 20 years in prison and a $250,000
fine. No word yet whether he also plans to run for the Senate in
California.
Question 8: Careers coach Lewis Lin has released a list of
140 questions Google asks of prospective employees. Which of the
following questions is not on Lin's list?
Correct Answer: Explain the significance of "dead meat."
The actual question is "Explain the significance of 'dead beef',"
the answer to which involves hexidecimal code. The other questions on
Lin's list are equally baffling to the uninitiated. So unless you bone
up before the interview, you are in fact dead meat. So much for those
dreams of a comfortable retirement fueled by Google stock options.
Question 9: The Doodle -- the six-letter logo that adorns
Google's otherwise sparse home page -- changed multiple times in the
last week to honor various icons of childhood. Which of the following
was not a Google Doodle?
Correct Answer: The Great Pumpkin
However, which Google Doodle you saw depended on where you were
sitting. Googlers in the United Kingdom saw Wallace and Gromit (in
honor of the animated duo's 20th anniversary). U.S. searchers saw the
Doodle visited by the Cookie Monster, Big Bird, and others (Sesame
Street turned 40 this week). Ancient Gauls Asterix & Obelix got the
Doodle treatment for their 50th anniversary (visible in 43 countries,
but not the States). Also in the mix: various Doodles for Halloween and
the Day of the Dead (in Mexico). Do you suppose Google has a Chief
Doodle Officer, and if so, what kind of questions would you need to
answer to get that job?
Question 10: Take the number of iPhones Apple sold the first
weekend it was available in China and multiply by the new early
termination fee Verizon plans to charge users of smartphones who bail
on their contracts. Add the volume of apps in the iPhone Store, rounded
to the nearest large number. Download that to your Windows Mobile phone
and pray someone will buy you an iPhone for Christmas. What do you get?
Correct Answer: 1,850,000
China Unicom signed up 5,000 new subscribers, or one iPhone for
every 263,000 people. (By contrast, Apple sold 1 million 3GS models
over a similar time frame in Europe and the United States.) Verizon
plans to ding its customers $350 for weaseling out of their
commitments, minus $10 for every month they stayed in contract -- or
roughly double what it charged in the past. Apple proudly announced its
iPhone Store now serves more than 100,000 apps. So 5K * 350 + 100K =
1,850,000. Subtract the apps related to beer drinking, plastic surgery,
or farting, though, and you're down to around 10,000. Come back next
week for another gaseous quiz.
Original story - www.infoworld.com/node/99198

I just got done reading the Google Interview Questions over at Gizmodo and came to only one conclusion about them, and it is the same problem I have with most “clever” interview questions.
Why bother?
What does this tell you about the candidate?
Can they perform under pressure?
Can they think on their feet?
Do they already know the answer?
Have they heard this one before?
I am sure, somewhere, someone found that in the framework of an
actual interview these questions have some utility, but mostly I find
that they serve only three purposes for the company doing the hiring:
To demonstrate how clever the interviewer actually is.
Give a poor interviewer a crutch to lean on.
Give a lazy interviewer (see point two above) something to ask rather than actually do real work during the interview process.
I guess I have been lucky when hiring employees for my company
in that they are all people I have had the pleasure of working with in
the past at other gigs. I don’t think I have ever asked a “clever”
interview question in my entire career. I’d rather the interviewee
demonstrate a clear understanding of their chosen profession than their
ability to “answer a pop quiz.”
I have been asked “clever” questions, and they are mostly unoriginal and something the interviewer looked up on the internet.
What the questions are supposed to do is provide insight in to how you think, how you perform under pressure, and so on.
The problem is that the lazy interviewer doesn’t give a damn about
how you perform, just whether your answer matches up. And the poor
interviewer doesn’t have the skills to usefully evaluate your
performance so they, again, focus on the answer you gave.
Usually if you don’t give the exact right answer they have memorised
or have written down in front of them, in their eyes, you failed. On
the whole, the interviewer generally isn’t smart enough to actually
understand the question themselves, or even come up with something
original.
What the questions are supposed to do is
I’m angry at lazy, poor interviewers the and companies they work
for. But I am even angrier still at people who focus so much on these
questions, because the questions themselves are self-serving,
self-fulfilling prophecies – “Look at how clever we are to ask these
kinds of questions!” and so it goes “Gosh darn it, that must be a
top-flight company if they ask interview questions only they know the
answers to.”
Perhaps I am sore because I cannot answer the questions satisfactorily?
I answered each and every one, except for #8, to a satisfactory
level in under a minute with the CTO of the company I am currently
consulting for acting as the “heckling interviewer.” And boy can he
heckle. The heckling provided a “realistic interview scenario” to apply
a little pressure.
The “How many lines can be drawn in a 2D plane” stumped me because I
simply didn’t understand the question as stated until I got up and drew
it out on the whiteboard. Total time to solve: less than 3 minutes.
And question #9 is just plain silly. The answer is obviously
0×10000000000000000. Proof that the interviewer was attempting to be
clever but the interviewee was being cleverer. Also, ignores the fact
that any competent software engineer knows their powers of two, off by
heart, all the way up to 128 bits.

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: 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 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.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
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.
Create a cache with fast look up that only stores the N most recently accessed items.
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?
Given two files that has list of words (one per line), write a program to show the intersection.
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.
Google Interview: Quantitative Compensation Analyst
What is the yearly standard deviation of a stock given the monthly standard deviation?
How many resumes does Google receive each year for software engineering?
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?
What is the probability of breaking a stick into 3 pieces and forming a triangle?
Google Interview: Engineering Manager
You're
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?
Google Interview: AdWords Associate
How would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
How would you deal with an angry or frustrated advertisers on the phone?

Question: Binary Search Tree Validity
Write a function to determine whether a given binary tree of distinct integers is a
valid binary search tree. Assume that each node contains a pointer to its left child, a
pointer to its right child, and an integer, but not a pointer to its parent. You may use
any language you like.
Good Answer: Note that it's not enough to write a recursive function that just checks
if the left and right nodes of each node are less than and greater than the current
node (and calls that recursively). You need to make sure that all the nodes of the
subtree starting at your current node are within the valid range of values allowed by
the current node's ancestors. Therefore you can solve this recursively by writing a
helper function that accepts a current node, the smallest allowed value, and the
largest allowed value for that subtree. An example of this is the following (in Java):
boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
}
The running time of this algorithm is O(n).
Question: Odd Man Out
You're given an unsorted array of integers where every integer appears exactly
twice, except for one integer which appears only once. Write an algorithm (in a
language of your choice) that finds the integer that appears only once.
Good Answer: Set up a hash set that we will put the integers from the array into.
Have a second variable that will keep a sum. Start going through the array and for
each integer, check to see if it's already in the hash set. If it is not, add that integer to
the sum and store that integer in the hash set. If it is in the hash set, subtract that
integer from the sum. When the algorithm finishes going through the array, the sum
variable should be equal to the integer we were looking for, since it is the only
number we never subtracted from the sum. This takes O(n) time and O(n) space.
int oddManOut(int[] array) {
HashSet<Integer> s = new HashSet<Integer>();
int sum = 0;
for (int i = 0; i < array.length; i++) {
if (s.contains(array[i])) {
sum = sum - array[i];
} else {
s.add(array[i]);
sum = sum + array[i];
}
}
return sum;
}
Really Awesome Answer: XOR all the values of the array together! Since XOR is
commutative and is its own inverse, each integer in the array that appears twice will
cancel itself out, and we'll be left with the integer we're looking for. This takes O(n)
time and O(1) space. We told you bitwise stuff was handy!
int oddManOut(int[] array) {
int val = 0;
for (int i = 0; i < array.length; i++) {
val ^= array[i];
}
return val;
}
Question: Design a Poker Game
(Don't ask all these questions at the same time; ask one after another, since they
build upon each other.) Without writing any actual code, describe as much as
possible how you would design a poker game program. What classes would you
have? What relationships would they have with each other? What would be the
basic flow of the program and how would those classes play a part? If you then
wanted to add a new type of poker game (such as Texas Hold 'em), how would that
fit into your design?
Answer: There are so many possible answers to this problem that it would be
difficult to say that one answer is the best. Look to make sure that they make
classes to simulate the basic parts of a poker game (perhaps a hand, the pot, a game
type or rules, a round, the deck, etc.). Using inheritance (subclassing in objectoriented
programming) where it makes sense is also good for reusability and
extendibility. Using design patters (such as Model‐View‐Controller,
Listener/Observer, or the Singleton pattern) is also a good thing. The main point is
for them to get used to thinking about how they would design a system. Most
importantly, they need to think about simplicity, reusability, and extendibility in
their design.
Question: Leader Election
Describe a technique to identify a "leader" among a group of 10 identical servers
that are all connected to every other server. There are no prior distinguishing
characteristics of any of them and the same program to identify the leader starts
running on all of them at the same time. After an answer is given, ask how much
network traffic it requires and, if "ties" are possible, ask how you can break ties.
Good Answer: Have each server wait a random amount of time and then say "I'm it."
The "I'm it" announcement is time‐stamped, and the computer that time‐stamped its
announcement first is elected the leader. This approach requires sending out 9
messages. If there is a tie, the computers can repeat the procedure.
Note that other answers are possible, but every correct answer will use randomness
in some way.
Question: Queue Using Stacks
Describe a queue data structure that is implemented using one or more stacks.
Don't worry about running time. Write the enqueue and dequeue operations for the
queue. You may use any language you like.
Good answer: You can use two stacks: an "incoming" stack and an "outgoing" stack.
The enqueue and dequeue operations would look like this (in Java):
Stack in;
Stack out;
void enqueue(int value) {
while (!out.isEmpty())
in.push(out.pop());
in.push(value);
}
int dequeue() {
while (!in.isEmpty())
out.push(in.pop());
return out.pop();
}
Question: Instant Messaging
Describe a design for an instant messaging program where there are several
servers, clients are connected to each server, and the servers communicate with
each other. Describe the classes, interfaces, and so on that you would use and how
you would organize them.
Answer: As in the previous design questions, there is no best answer. Good topics to
discuss are how each client communicates with a server, how the servers maintain
state with the other servers, how state information is communicated between
servers and clients, and the speed/reliability of their design.
Question: Maximal Subarray
Given an array, describe an algorithm to identify the subarray with the maximum
sum. For example, if the input is [1, ‐3, 5, ‐2, 9, ‐8, ‐6, 4], the output would be [5, ‐2,
9].
Good Answer: Observe that the sum of a subarray from element i to element j is
equal to the sum of the subarray from element 1 to element j minus the subarray
from element 1 to element i ‐ 1. Our algorithm will iterate through the array. The
algorithm keeps track of the sum x of the elements no later than the element. It will
also keep track of the minimum sum y of the subarray from the first element to an
element no later than the current element. Finally, It will also keep track of the
subarray z with the maximum sum so far. At each step, we update x by adding the
current element to it. We update y by checking whether x < y; if so, we set y to be x.
We update z by checking whether y ‐ x is greater than z; if so, we set z to be y ‐ x.
For example, with the sample input, our algorithm would do the following:
Current element | x | y | z
----------------------------------
1 | 1 | 0 | 1
-3 | -2 | -2 | 0
5 | 3 | -2 | 5
-2 | 1 | -2 | 5
9 | 10 | -2 | 12
-8 | 2 | -2 | 12
-6 | -4 | -4 | 12
4 | 0 | -4 | 12
Surprisingly, this problem is equivalent to the stock market problem described in
handout 3. Given an array a1, you can "convert" it to an array a2 for the stock
market problem by setting each element a2[i] to be a1[0] + a1[1] + ... + a1[i].
Question: Obstacle Avoidance
Given an n x n grid with a person and obstacles, how would you find a path for the
person to a particular destination? The person is permitted to move left, right, up,
and down.
Good Answer: Use the A* algorithm or another fast path‐finding algorithm. (It is
described on Wikipedia.)

1. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.
2. Given a circularly sorted array, describe the fastest way to locate the largest element.
3. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.
4. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.
5. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
6. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.
7. Implement a special
type of integer iterator. It will be a wrapper over a regular integer
iterator, except that this iterator will only iterate over negative
numbers. Show how you’d write the next() and hasNext() functions to
work with the next negative integer instead of just the next integer.
8. You are making an AI to play Tic-Tac-To. Make
a function that takes a board position as an input and returns a good
position to play. Describe how you’d represent the board, and how you’d
determine where to play next.
9. You are given 1001 numbers in an array. There are 1000 unique
numbers and 1 duplicate. How do you locate the duplicate as quickly as
possible?
10. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?.

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?
What method would you use to look up a word in a dictionary?
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 announce that at least one husband has
been unfaithful. What happens?
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?
How do you cut a rectangular cake into two equal pieces when someone
has already taken a rectangular piece from it? The removed piece an be
any size or at any place in the cake. You are only allowed one straight
cut.
How many piano tuners are there in the entire world?
What gives you joy?
Mike has $20 more than Todd. How much does each have given that
combined they have $21 between them. You can’t use fractions in the
answer. Hint: This is a trick question, pay close attention to the
condition)
How many times a day a clock’s hands overlap?
Two MIT math graduates bump into each other. They hadn’t seen each other in over 20 years.
The first grad says to the second: “how have you been?”
Second: “Great! I got married and I have three daughters now”
First: “Really? how old are they?”
Second:
“Well, the product of their ages is 72, and the sum of their ages is
the same as the number on that building over there..”
First: “Right, ok.. oh wait.. I still don’t know”
second: “Oh sorry, the oldest one just started to play the piano”
First: “Wonderful! my oldest is the same age!” Problem: How old are the daughters?
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?
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)?
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?
You have an empty room, and a group of people waiting outside the
room. At each step, you may either get one person into the room, or get
one out. Can you make subsequent steps, so that every possible
combination of people is achieved exactly once?

Tags: questions, phone interview, |
Posted by Admin on
12/27/2008 10:32 AM |
Comments (0)

Dec 1st, 4:00 pm. I had a paper
that morning, on 'Object Oriented Modeling'. Didn't sleep last night
preparing for the paper. So, my condition wasn't its best for the
interview.
They called at ten past four in the evening. The
interviewer wanted to start off with the interview (coding questions)
right away. So did I.
He asked me what my favorite language was (C++, C#). He then gave me a problem -
'You are given a string of characters. You are required to calculate the frequencies of each distinct character in the string.'
The solution is quite simple. I proposed 2 solutions.
'There are 2 sorted lists of integers. You need to merge the 2 lists into a third larger list which should also be sorted.'
Solution to this problem is also quite simple. I gave him an array-based solution, O(m+n).
He asked me to write the solution using linked lists. I did that too.
'Now suppose there are k
lists, all sorted, instead of 2. And you want to merge all of those
lists into a single large list which should also be sorted. How will
you do that?'
I began to think over. Within 30 secs, he
dropped a hint and i picked it up instantly. Using his hint, i gave him
a solution of O(k*n). He asked me if i could do it better. I tried and
proposed a couple of other algorithms, some better than others, but
none as good as O(k*n). The interviewer was actually testing as to
whether i can think of alternative solutions. He told me that your
first solution was optimal. I just wanted to check if you can give
other solutions. I was happy i could think of 3-4 alternatives to the
same problem.
Like other interviewers, he too asked me if i had
questions. I asked him about the 'procedure of the interview process at
Google', since this third phone screen was unexpected. He said,
"This
is your 3rd phone screen right? So according to my feedback, they will
be inviting you onsite very soon. You will have 2-4 rounds of
interviews at Google office."
and i was like... :D
Yet,
this time too, i was not satisfied with my performance. I wished i get
another chance to do the same interview and i would do better..
End of this (final) phone screen.
Read on,
Onsite Interview @ Google, Hyderabad.
..signing off
Original story...
Tags: questions, phone interview, |
Posted by Admin on
12/27/2008 10:31 AM |
Comments (0)

Nov 12th, 5:00 pm. This one was interesting. Not the interview itself, but some of the events related to it.
I had put up a status message on my orkut profile - "Nov 12th - Big Day.."
Since
i thought this interview was final phone screen and would decide on my
onsite chances, i considered it big. A friend of mine, thought all the
while that the day is big for me, since its her birthday. :-P
Another
funny thing was with my cell phone. It couldn't take calls. I could
make outgoing calls, but incoming calls were rejected on the caller's
side. I spoke to the customer care. He said it would take atleast 24
hours to repair the 'technical problem'. I informed about this problem
to my recruiter by sending out a mail to her at 12:30pm. Requested her
to make arrangements for the interview call to be made at another
number. They didn't reply at all. Until 5:00pm, i didnt know if i was
going to be interviewed that evening, at all.
Well, finally the
phone rang (at my friend's phone). I was quite confident this time
compared to the last phone screen. The interviewer asked me if i was
comfortable and if it was a good time to start with the interview. We
got started.
He asked me which programming language i was
comfortable with. I told C++ & C#. Then he asked me to rate myself
in C on a scale of 10. I rated myself 8.
Cool, he wanted me to implement atoi() in C.
But first, i was supposed to say what atoi() is. And i gave a very naive answer to that (after having myself rated 8!). All i knew was atoi()
parsed the input string/array of numeric characters and returned the
corresponding integer based on the radix (also passed as an argument to
the function). He humbly explained me what the function is "generally"
expected to do. :-)
Oh, i forgot to mention. In the beginning of
the interview, he asked me to have my laptop in front of me, with an
internet connection. He shared a google doc with me, where i was
supposed to write codes so that he could see them in real time. I wrote
a pretty good code for the atoi() implementation. I am sure he liked it!
In
the middle of discussion on my solution for his first problem, he asked
a couple of other simple questions. After this, he gave me a puzzle. I
did what i could do worst for this.
'You
have a transparent jar of marbles. You can determine the number of
marbles in the jar at any time. You and your friend play a game. In
each turn, a player draws one or two marbles from the jar. The player
who draws the last marble, wins the game. Is it possible to play with a
strategy such that you can win the game? Is it possible to determine
who will win/lose the game?'
As soon as he asked, i told
him that i have heard of a similar puzzle earlier. He told me to answer
to it anyway. I tried a couple of paths down to solution, but all were
wrong. Strange thing is, i have had this puzzle solved twice earlier. I
really screwed big time. Solution is quite simple. Readers are welcome
to post comments on it.
With that, my second phone screen ended.
A good code, and a bad puzzle. I wished i had just one more chance to
do this interview again. I would do much, much better.
They took
long time to respond. My hopes were fading. On Nov 26th, i got a mail
finally informing about my 3rd phone screen scheduled on the 1st of
Dec, 2008. My final semester exams were already on..
Too long post, huh.
Read on,
Third Phone Screen with Google.
Tags: questions, phone interview, |
Posted by Admin on
12/27/2008 10:29 AM |
Comments (0)

Nov 3rd, 5:00 pm. I was a
little nervous. As for pre-interview preps, i took all my important
papers (projects, semester mark sheets, etc) and placed them on my
table. I had also some of my codes opened on my laptop screen for quick
reference, if needed. Though, none of such preps ever was of any use.
Finally the phone rang. It was a female interviewer.
"Hi, is this Rajat?".. and the interview began.
First
question she asked was about my recent academic projects. I talked
about one or two projects of mine. She then asked me what programming
activities i involve myself in, other than college courses'. I
mentioned TopCoder, GCJ, SPOJ and other such contests. She showed some
interest in my standings in these contests.
Next, she asked a problem and wanted me to code on that.
'Given a set of integers, how would you find out the 2nd maximum element?'
I
gave two solutions to this question, the second one being optimal. But
i wont talk about it here right now, since it will kill readers'
imagination. I
wrote a code for the same and dictated it back to her. The code had a
small bug. It wouldn't run for a corner case. I dont know if she
noticed that bug. Next question was,
'There is a town with N people numbered 0 to N-1. Some people of this town knows some other people. The relation between them is not necessarily symmetric. i.e. If a knows b, doesn't mean b knows a. This
town needs a mayor. The requisite for being a mayor is that he should
be famous and impartial. Being famous means that he should be known to
everyone in the town. Being impartial means that he should not know
anyone in the town. Consider a function knows(i, j) that return true if i knows j or false otherwise. Write a program to return the list of people who are eligible for the mayor's post.'
In
google interviews, for every question, we are supposed to first propose
the logic/algorithm to solve the question, and then write code for it.
So was the case for this question too. I proposed an algorithm to solve
this problem. She guided me through indirect hints(by asking questions
that would lead me to her hint) to arrive at an almost optimal
solution. I say 'almost' because even at the end of the interview, she
kept on saying that there's a small bug in the code (and never revealed
what it was), which i had not been able to figure out yet! Guess, it
was one of the Google's interview pattern - say there is a bug even if
there isn't any, to confuse the interviewee.
The interivew
lasted for around 1hr 5 mins. She asked me if i had any questions. I
asked about work culture at Google. Quite expected. She wished me best
and advised to continue with coding at Topcoder and GCJ, and solving
puzzles. She also said that the HR people will get back to me soon.
With that it ended..
I was expecting a 'Thank you' call from
Google, given the kind of average perfomance i had shown at the
interview. Really wished i had a chance to give this interview once
more and i would give my best this time.
To my surprise, i got a call for my second phone interivew on 7th Nov. :-)
Read on,
Second Phone Screen with Google.
Original story...
Was surfing through some blogs , and found this one interesting. Some of the questions asked by Google Inc. in their interview :
1. How many golf balls can fit in a school bus?
2. 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?
3. How much should you charge to wash all the windows in Seattle?
4. How would you find out if a machine’s stack grows up or down in memory?
5. Explain a database in three sentences to your eight-year-old nephew.
6. How many times a day does a clock’s hands overlap?
7. You have to get from point A to point B. You don’t know if you can get there. What would you do?
8. 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?
9. This one is interesting. 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?
10. 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?
11. 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)?
12. 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!)
13. 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?
14. 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?
15. How many piano tuners are there in the entire world?
16. 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?
17. 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 hisplan,
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.)
Any answers??

This was originally posted in mathNEWS, a publication put out by
students at the University of Waterloo. Pretty interesting stuff, good
to read up on if you are going for a high end Google-type job.
Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.
Given a circularly sorted array, describe the fastest way to locate the largest element.
Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.
Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node.
If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one.
Implement a special type of integer iterator. It will be a
wrapper over a regular integer iterator, except that this iterator will
only iterate over negative numbers. Show how you’d write the next() and
hasNext() functions to work with the next negative integer instead of
just the next integer.
You are making an AI to play Tic-Tac-To. Make a function
that takes a board position as an input and returns a good position to
play. Describe how you’d represent the board, and how you’d determine
where to play next.
You are given 1001 numbers in an array. There are 1000
unique numbers and 1 duplicate. How do you locate the duplicate as
quickly as possible?
Say you are implementing exponentiation for a certain
processor. How would you minimize the number of multiplications
required for this operation?.
I have been in interviews that have asked very technical, industry
specific questions. However they always tend to be more strait forward
right or wrong questions. Never seen anything this open-ended before.

This is the last part of posts describing my own experience interviewing with Google. You may find the first interview here and then follow the traces until this last one.
Time
had already passed (almost a month) after three successive interviews
with Google and this last one was most probably the critical one. I did
not prepare for this as much as the previous. The whole thing tires you
up and at some point it seems better to relax and concentrate on the
psychology rather than the technical stuff.
I was only asked two technical questions, and since my language of choice
was Java the interviewer wanted to see some Java code for the answers.
In summary, this interview was perfect. While in all previous
interviews, mostly the first and the second, I had some important flaws
in my performance, but this one was different. And all this because I
was playing in my field.
Google at some point asks for a CV.
However, the way I see it, Google and other major software companies
search always for something unconventional in the candidate's
application. You could say of course you know 5 or 10 programming
languages, or that you can build an internet spider in 1 minute,
however there might be some knowledge you have, that is somewhat rare
and hence you should mention. In my case, this is Number Theory.
For
me, number theory is a passion that has not passed over time. It was
love in the first sight, when I became aware of it, maybe at the age of
15 or so, and from that time it was the field mathematics that I was
really feeling comfortable with. Anyway, it is not hard to see why it
has been named as the "Queen Of Mathematics". First, it is very easy to
grasp the basics (primes, divisors etc) since they are inherently
tractable by the human brain. After all, every human being starts my
learning how to count, which is the first step of the true
intelligence, aka understanding that 5 ice creams and 5 cars, share
something in common: that they are 5. This helps solving silly cases
like, if I ate 5 ice creams and then I ate 1 more, how many did I eat?
There is no need to think of ice creams, nor the eating process. All
you have to do is to construct the proper model for this situation: use
natural numbers and solve 5+1.
Another great thing with number
theory, is that your 'lab' can be a blank piece of paper. You can argue
that 15 is divisible by 3, but all you need is a paper to perform the
division. While a physicist might say that in light speeds some
hypo-atomic elements, called mambojambions, are created, he still needs
a gigantic, CERN-like laboratory to test his theories.
Anyway, I
myself was raised in a Pythagorean culture(numbers are holy) and so I
claimed in my CV to know some number theory stuff. Although I was a
little worried if I would be able to defend such claims (after I would
be talking to Google), it soon proved to be a wise decision. Both in
phone and on site interviews with Google, there was no better time for
me than doing number theory. And to much of my surprise, and despite
that Google's name is inspired by a natural number (or a unit of
measure if you wish), all the 'Googlers' that I spoke and met with, did
lack elementary knowledge on the field. This time, (I assume) the
interviewer had dug in my profile and wanted to see for himself. Every
question and conversation was related to Number Theory.
So, the first question was about sets: "Create a function, called powerSet(), that will output the power set of the input set." The
power set in Algebra theory is the set of all subsets of a set
(no..bull-set!) If a set has N elements then the power set will have
2^N elements. So if a set is denoted by {a,b} with a,b as elements then
the power set is { {},{a},{b},{a,b} }.
The {} is the empty set. Note
that all elements of the power set are sets. Recursion can help for
solving this problem. If for example the powerSet function can produce power sets for sets that have at most N elements how should we solve for the N+1 case?
If we denote sets with capital letters and the initial set as A, we can use the following algorithm
1. define B set initially empty
2. a = extract one element from A
3. add powerSet(A) to B
4. for every set in B, say X, add a, and then add it to B
5. return B
Making the proper checks, this yields a function that can produce the power set of a set. For the Java case you can use the java.util.Set interface
to write the code. I was asked to write the Java code but not asked any
further questions, like complexity, runtime and so on. So we moved to
the next and final question.
This was: "Create a function, called findZeros(), that will compute the number of zeros in the decimal representation of n!". Now
this is interesting and despite seemingly easy it has subtle points.
For example, 5! = 1.2.3.4.5= 120 has one zero and 10! =
1.2.3.4.5.6.7.8.9.10 = 3628800 and has two zeros. Now the obvious
answer is to produce this C-style pseudo code:
int findZeros(int n) {
z<-0;
N<- n!
while ( N%10==0) { z++; N/=10;} return z;
}
It seems right but has a terrible flaw: it fails at very 'small' values of n, in our 4-byte world, for n=15. Using some Java code like below, we can verify this case.
int n=1,i=2,m=1;
while(n>=m) {
m=n; n*=i;
System.out.println("Previous value "+m+" Current value "+n+" Counter "+i);
i++; }
System.out.println("OOPS! Overflow!");
So, if our code works only for 14 cases, it is pretty much useless. We should do better than that.
For number theory geeks, like myself, this means show time! The equation below is called the Legendre's formula
and basically computes the factorization of n!. The exponent in which prime p is
'participating' in the factorization is the sum in the figure. Now, we
should use it for our case. 10 is the product 2x5. So, the exponents of
2 and 5 in the factorization of n! defines
how many zeros we get. For example, 10! = 1.2.3.4.5.6.7.8.9.10 =
(2^8).(3^3).(5^2).7 So 2 is found 8 times and 5 is found 2 times in the
factorization, hence if we pair up the 2's and 5's we get two zeros.
Now, there are obviously more 2's than 5's in the expansion so finally
we have to answer at the question:
What is the exponent of 5 in the factorization of n!?
Based on the reasoning above this is equal to the number of zeros of n!.
Based on Legendre's formula we have to calculate:
[n/5]+[n/5^2]+[n/5^3]+... to infinite. This is done for example by the following Java code
calculateZeros(int n) {
int s=0,r,p=5;
while((r=(n/p)) !=0)
{s+=r;
p*=p;}
System.out.println(n+"! has "+s+" zero"+((s==1)?"":"s"));
}
For example, 25 = 1.2.3....23.24.25 = 15511210043330985984000000. Running the above code will produce the message 25! has 6 zeros. Instead of messing with a number with 26 digits (25!) you only have to deal with the number 25. Why?
In the sum S(n) = [n/5]+[n/5^2]+[n/5^3]... the first term, [n/5], computes how many numbers up to n are
multiples of 5. For the 25 case there are 5 of them: 5,10,15,20,25. The
second computes all multiples of 25, i.e. only one. The third and all
others are zero. A number that in its factorization, the prime 5 is in
the power of k, e.g. 10 = 2.5 and k=1 or 25 = 5^2 and k=2, participates in the first k terms of the sum by adding one to each term. Hence its overall contribution is k, hence the sum S(n) calculates the power of 5 in the factorization of n!, and therefore the number of zeros in the decimal representation, Q.E.D.
That was it! There
is no other way to handle such big values and the solution can deal
with really gigantic numbers without explicit calculation. The
interviewer had elementary number theoretic knowledge
but was able to follow the reasoning and we had a very nice
conversation after that. He seemed to be fond of such mathematical
tricks as the one we dealt with.
In summary, I think this was
the interview question that booked me the plane ticket to fly to the
Google site. I was very satisfied after we hang up and I was impatient
for the outcome but deep inside I was sure it was an ideal interview
session and that my chances were great. The next morning I received a
phone call from Google inviting me for the on site interviews. Mission
was accomplished.
This post ends a series of posts in which I
wrote about my phone interviews with Google along with many interview
questions. For the on site interviews I am bound to an NDA so maybe I
will post them encrypted! That's all for now about Google interview
questions. Until, I come back for the on site experience remember a
small tribute to Number Theory: "Die
ganzen Zahlen hat der liebe Gott gemacht, alles andere ist
Menschenwerk" (Numbers were created by good Lord. Everything else is
human's work-Leopold Kronecker)

Tags: mountain view, california, questions, answers |
Posted by Admin on
11/11/2008 2:18 PM |
Comments (0)

This is the 3rd interview I had with Google. You can find the previous and the questions asked here:
* First Google interview
* Second interview
In
the 3rd interview I talked with a woman software engineer from Mountain
View. As usually it lasted for about 45 minutes but there was a
surprise waiting at the last question..But let's take things from the
beginning.
The first question was a hard test for my memory: "How do you test your code?"
This is a fair one for software engineers. But not for my style. I
personally like things that are quick and dirty. For larger projects I
use some of my own class libraries that employ some kind of logging,
measure method execution time and so on. But saying "Well, I use my own class libraries." I thought would not be a good answer. Nor a professional one.
So
talking about Java, I made the mistake of mentioning the JUnit
framework. I had used for some time (long ago) but the time had passed
so I had forgotten even the basics. And of course the interviewer
started the questions (How the JUnit handles exception and others)
To tell you a secret I had already opened in my browser a JUnit site
(some kind of tutorial I guess) but this didn't help at all. So, don't
do it. It will only make things worse. Trying to think logically didn't
help either. The interviewer kept pushing, until I 'broke' and admitted
that I couldn't answer. That was it. We moved to the next question.
All next questions were really typical, the kind you find in tech interview sites:
* "What is a Unix kernel?"
* "What is the difference between interfaces and abstractt classes?"
* "What is the difference between threads and processes?"
* "What is inheritance, polymorphism and encapsulation?"
* "What is overriding and what is overloading?"
I think there is no need to elaborate further on that. You most probably have come across these concepts and have your own mind.
Which
brings us to the last question. Actually it was a puzzle including
programming with handicaps, i.e. with small processor, low memory etc.
The puzzle was this:
"You have 1000
integers. All are less than 1000 and greater or equal to 1. Among them,
999 are distinct and there is one that is found twice. How can you find
the duplicate?" To this I gave an answer I think is optimal. The idea is simple. If you denote the duplicate number by d and the sum of all the integers by S then the following equation holds:
S-d= 499500 since S-d is the sum 1+2+3...+999 which is equal to 499500 by applying the formula 1+2+3...+n = n*(n+1)/2
Now
the good thing is that we can be able to find the duplicate even we
have capacity for one integer, or when reading from a stream and so on.
We can optimize even if we apply modulus to the first equation: d = (S-500) (mod 1000) Now if d
is equal to a positive number mod1000 then this is the duplicate,
otherwise the duplicate is the negative part plus 1000. For example is
1 was the duplicate, then d=1(mod 1000) and the duplicate had to be the 1. If the duplicate was 600, then d=-400(mod 1000) so the duplicate had to be -400+1000=600. This means we do not need to have storage for integer (int type) but only the byte type is enough.
While
fairly easy to grasp the interviewer had difficulties in understanding
how this would work, so she asked for an example when we have 10
integers. I replied this would transform the equation to d =S-45 but then the counter question was disappointing: "How did you compute 45?"
It is quite obvious however that I had to compute 1+2...+9 which is
equal to 45 when applying the formula that Gauss found when he was 8.
But the interviewer started computed 'by hand' the sum, adding the
numbers from 1 up to 9, which left me speechless for some seconds. I
mentioned that there was a formula for that but she didn't listen,
still being concentrating on her computations. I didn't bother
elaborating on the modulus idea since obviously would not give me any
more credit.
After that, the interview had finished. I didn't ask anything, saying something like 'I have many questions but I do not wish to spend any more of your time'
and we ended the conversation. In overall the last incident was really
awkward. To that time I believed that all Google engineers had a good
mathematical background. The engineer that I spoke with, did lack
elementary skills. So in my eyes, the myth had been destroyed and it is
a good advice to anybody, not bother berating himself more than he
should. If you already knew the formula for the sum of consecutive
integers, you have a good reason to feel more confident.
Tags: mountain view, california, questions, answers |
Posted by Admin on
11/10/2008 2:15 PM |
Comments (0)

This continues from my first Google interview described here
In overall, the second one was harder in terms of questions and
expectations. I was called again from Mountain View sharply at the time
we had arranged.
The conversation began with an interesting question: "What would you change in the Java programming language?"
This has more than one questions embedded and it is educating listening
to all possible answers. For example, one of my suggestions was having
'mechanisms' much like the properties fields in C# to ease development (programming get/set
methods seems very tiring to me)Since the question was referring to the
language and not to the Virtual Machine anything you find tiring or
absent in Java is probably a valid answer.
We
next proceeded to a C programming question. My interviewer knew that I
was not a C-guru so he was gentle on that. The question was something
like this. What is the output of this C program?
main() {
char X[500] = "Hello World";
printf("%s",X+5);
}
I
knew it had to do something with memory allocation but I was not
succinct on that. I said that the output would be blank and I guess I
was right (the interviewers never tell you directly if you are right or wrong) So we said OK and moved on.
The 3rd question was about creating random functions. It is the type of questions where given a function randX that provides uniformly numbers from 1 to X, to generate a another randY. The actual question was about making rand8 from rand6. It is easy to establish how to get a rand2 from rand6. Then you can get rand8 from rand2.
This
was a straightforward case. However, this problem appears very often in
such situations and deserves some attention. You may find unlimited nonsense by searching for 'create rand7 from rand5' which is also a frequent question. Trying these forums/blogs etc you will get endless efforts of shifting from one rand to another using common arithmetic functions (addition, mod etc). This is nonsense. You will have to shift to elementary analysis for a while to get some good results.
In the general case consider you have to generate randX from randY where Y > X. Now consider that this yields the division: Y = n*X+r So, you can one group of Y elements into X groups of n elements and one more group with r elements. Now number the X groups as 1,2,3..X Then, create a 'machine' that uses the algorithm:
m = randY();
IF m belongs to one of the X groups return its number
ELSE restart the machine
The probability in every run of the algorithm to return one specific value from 1 to X is a =n/Y and the probability that the algorithm restarts is b = r/Y. So, the overall probability that the machine will output one number from 1 to X is :
P = a+a*b+a*b*b+a*b*b*b+... = a*(1+b+b*b+...) = a/(1-b).
By substitution we get, P = 1/X
In other words, we have generated the function randX
Now, if we wish to increase the rand range, for example get rand7 from rand5 you can create rand25 from rand5
(two rand5 calls) and then use the above method. Shifting to infinity
is inevitable in some cases and all other efforts are in vain.
Back
to the interviews, the final question had to do with designing and
analyzing an algorithm. This had to calculate all representations of an
integer as a sum of cubes. You can find many similar examples in
algorithms textbooks so presenting this story here is trivial. What is
interesting is that, we started a discussion on an incident that was
directly related to the problem. This is usually called as the 'cab number story'. Back in the days when Ramanujan was in Cambridge and was working with G.H. Hardy,
he had frequent health problems. One day, Hardy visited Ramanujan to
the hospital and to start a discussion he mentioned the number of the
taxi cab that brought him there. He said something like "..The cab number was 1729. I think this number is not interesting at all." A few seconds Ramanujan (which was extremely competent with numbers and calculations) replied: "You
are not right Mr.Hardy. 1729 is very interesting. It is the smallest
number that can be written as a sum of cubes in two different ways."
This
was a nice way to close the interview. We didn't have much time left,
so we said some relaxing things and then ended the interview
conversation. All in all, it went well and my interviewer was a really
nice person. Our discussion was interesting and I soon got the news
that I was to pass to the next level. Having acquaintance with math and
generally science history certainly helps!
First off, I’ll spare you the suspense. I did NOT get offered a job at Google… but I did have a lot of fun!
I was first contacted back in December by a Google talent recruiter. Mike had been in the middle of his Google interviews, so it was an exciting time.
Was I interested? Definitely! There are few in the software industry
that wouldn’t jump at a chance to work for Google - one might call them
the Mecca of the software industry (but only if it doesn’t offend
anyone; if it does, let’s just call it a pretty neat place to work).
I first received an email from the recruiter asking if I was
interested, and where I wanted to look for a position. She told me that
she thought there was a good fit for me for a Java position in Mountain
View, but I asked her about looking for a job in Waterloo. Was it a
mistake? Maybe, but she did mention that I could look into a position
in Mountain View if the Waterloo position didn’t work out.
Over the Christmas holidays, the recruited emailed me to let me know
that the Waterloo position was a C++ position, and that perhaps I would
have a better chance finding interest in Mountain View, but the next
day she emailed me back to let me know that the Waterloo offices were
interested.
I was excited. One of my goals, new years resolutions if you will,
was to step out of my comfort zone with regards to software
development. It seems that every script I needed to write was being
written in Perl and Bash script and every piece of software I was
writing professionally was in Java. I wanted get out of the habbit of
relying on Java/Perl/Bash. This seemed like a good opportunity as C++
is one of many languages I wanted to work on this year.
Well, I guess what you really want to know is what sorts of things I
was asked on my interviews. Well, before that, there are a lot of
things that need to be reviewed; first and foremost, asymptotic notation and complexity.
The interview questions consisted of asking me to come up with a
semi-high level algorithm and then to explain the asymptotic complexity
of each part as I went along, and then what the final complexity of the
algorithm would be.
The next thing that should be reviewed is your basic sorting
algorithms and their respective complexities. I made sure to know heap
sort, bubble sort, selection sort, binary sort, merge sort, quick sort
and insertion sort. Also important, you should know the memory
requirements that each algorithm uses to run (in big-O notation). I was
asked in my first interview to not only minimize the runtime, but also
the memory footprint (ie. insertion sort although is O(n^2) in runtime,
it is O(1) with regards to memory).
The next thing I reviewed was memory structures. Hash’s, binary
trees, n-tier trees, etc and the properties that each one possesses. If
the interviewer asks you about a binary tree, make sure you know the
properties that make a binary tree special so that you can leverage it
in your solution.
Now, on to the interviews.
The first interview started with a quick introduction from Steve
about where he worked within Google (Google NYC) and what he worked on
there (Google maps). Then it was right down to business. The first
questions (from my memory, so don’t blame me if it isn’t 100% correct)
was as follows:
Given a binary tree, and two leaves, can you find the lowest common node of those leaves?
I won’t give you the answer here. I’ll let you work it out for a bit
and perhaps if there is enough discussion in the comments, I’ll leave
the answer there. When giving my answer to the interviewer, I think I
could have been a lot clearer. I was nervous; very nervous. I really
didn’t know what to expect, even though Mike prepared me the night
before. The answer I gave was right (as far as a solution and its
complexity) however, about 10 minutes after completing my interview, I
figured out a way to better leverage the binary tree structure which
would have also given a much clearer answer. Also, I was asked to
minimize both the runtime and memory usage in my solution.
The next interview I had was about 2 weeks later and it was with
Chris (also from the Google NYC offices) but he worked for Google’s
blog search. This one started a little different; he asked about what I
had worked on at my previous companies and more specifically what I
felt the coolest project was. I had so many to choose from at Pason,
but I went with the biggest and more complex, the DataStream project.
After that, he asked me my ideal problem to solve was if I could
leverage all that is Google. This really caught me off guard. I should
have known it was going to come; I even read about someone who was
asked a similar questions. I spent so much time preparing for the
technical part of the interview, I forgot about the lighter part. I
wish I could have done it over. My answer was a lame scheduling mash-up
for Google maps. I really needed to think bigger… hell, my friends and
I have talked for years about cool stuff that we could do if only we
had a company that was as big as Google.
I felt like an idiot, but what can you do. No sense dwelling on
that. There were two technical questions that comprised this part of
the interview. The first was:
If you were designing the Vector class in Java, how would you code the add(Object) method?
Deceptive; not hard per se, but there are a few things that need to be worried about when solving this question.
The next question was the algorithm question:
If you were given an unordered set of plane tickets
which represented legs in a trip, can you figure out the order in which
to use the tickets?
This was a really fun problem to work on, and again, I’ll save the
answer for the comments. Remember that they want you to come up with
the lowest runtime algorithm that you can.
Three days after I completed this interview, I got my letter letting
me know that they were not going to be offering me a position. Was I
disappointed? Sure. I have to admit that I thought about how neat it
would be to work at Google, but it wasn’t all bad. It helped me fulfill
another one of my new years resolutions - to get back into studying the
“science” of computer science, and although stressful, the whole
experience was a lot of fun.

Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“.
It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.
After that day, I looked for other well-known interview questions
and I discovered that Google has a totally different approach, focusing
on algorithms, data structures and complexity.
For instance, one of Google interview questions says:
There is an array A[N] of N integers. You have to
compose an array Output[N+1] such that Output[i] will be equal to the
product of all the elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.
Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].
We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].
We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:
view plaincopy to clipboardprint?
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:
view plaincopy to clipboardprint?
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.
With these functions we can just define an input array and apply them to get the result.
The following is the complete F# code:
view plaincopy to clipboardprint?
#light
let input = [ 4; 3; 2; 1; 2 ]
let answer values =
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
values |> firstpass 1 |> secondpass 1 values

I sat in the waiting room with one other applicant. He was older
than me by about ten years. Judging by our clothes, it was clear that
we were taking different approaches to this once-in-a-lifetime
opportunity.
He dressed professionally. Black suit, white shirt, striped tie. His
dress shoes were polished, and their shine matched well with that of
his belt buckle.
I dressed casually. Blue jeans. Sneakers. A brown collared sweater
that hid the geeky maroon “Computer Wizard” t-shirt that I was using as
an undershirt.
I was trying to dress the part. I had heard that Google’s dress code
was simply “You must wear clothes,” so I wore something I might wear to
the office if I got the job. Sitting across from Mr. Business Suit, I
started wondering if I made a huge mistake.
For whatever reason, Mr. Business Suit hadn’t acknowledged my
presence since I arrived. He sat cross-legged with a magazine in his
lap, half-heartedly thumbing through it without looking up. He kept
this up until the Hiring Manager opened the door to the adjacent office
and called his name: “Don?”
Don set his magazine down and stood up.
“Good luck,” I said hopefully.
He nodded at me and followed the Hiring Manager out of the room. I
took pleasure noticing that the Hiring Manager wore sneakers and jeans.
Now that I was the only applicant left in the room, I started
reviewing the materials I brought with me to the interview. In my
“Portfolio” (a thin 3-ring binder) I had:
Loose copies of my resume
How-To Instructions and Screenshots from three of my Open Source Projects
Two Letters of Recommendation from previous Employers
A Thank You Card that I planned to mail immediately following the interview
I imagined that I had at least ten minutes until the Hiring Manager
asked for me. I was therefore surprised when a petite woman entered the
room and called my name: “Shaun?”
“Yes?”
“I’m Stacy,” she said, extending her arm.
I stood up, tucked the Portfolio under my arm, and shook her hand.
“Shaun Boyd. How do you do?”
“Just fine, thanks. I have good news for you.”
“Oh? What’s that?”
“Your application has been fast-tracked. I’ll be giving you a quick
tour of our facility, and then I’ll introduce you to the team that’s
interested in your background.”
“Oh my, that is good news,” I said through a huge smile. “How exciting!”
“Definitely. Follow me.”
As I followed her through the double doors and down the corridor,
Stacy filled me in on what being “fast-tracked” meant. She explained
that I still needed to be interviewed, but because my application was
unanimously selected by an existing project team I was exempt from the
first-tier “initial screening” interview. I would start at the
second-tier interview, which would be conducted by current members of
the team I might be working with. Stacy, a Senior Hiring Manager, would
sit in during this interview to see how I interacted with the team
members, and to answer any HR questions I might have about the position.
Stacy led me into her office and told me to have a seat. She typed
an instant message onto her screen, sent it, and then proceeded to copy
and paste the same message to four or five other people. She toggled
through the responses for a few minutes before speaking to me again.
“We have almost 30 minutes until the entire team will be available
to meet with you. Would you like to join me for some Free Lunch in the
cafeteria?”
“Absolutely,” I said.
The cafeteria was intimidating. Nearly every station had at least
half-a-dozen Google employees in line for their Free Lunch. Since they
were already familiar with the selection and ordering process, they
moved around the cafeteria with ease while I stood in place holding an
empty tray. Stacy pointed to the different stations, told me the type
of cuisine that was served there, and encouraged me to not be shy.
“Everything is always free, tasty, and nutritious,” she said, more
or less reciting everything I had heard about Google’s cafeteria
verbatim.
I got into the line for Chinese cuisine. I asked for a helping of
General Tso’s Chicken over white rice. The chef asked me if I’d like
some orange slices to go with my entree, and I said “Yes please!”
I joined Stacy at a round table in the center of the cafeteria. She
introduced me to Tom and Anu, two of the team members who would be
interviewing me once we finished our lunch. She then busted my chops a
little by telling them how I chose to get Free Lunch instead of a tour
of the facility, but they said I made the right choice. Anu scolded me
for not taking advantage of the Slurpee machine.
Tom asked about the Portfolio I was carrying. I paged through it
briefly, and explained that it was basically a detailed addendum to my
application. I said that I’d like to show it to the entire team during
the interview, if they’d be interested. He gave me the impression that
they would be.
Once we finished lunch, we returned our trays and left the
cafeteria. The four of us rode the elevator up together and got off on
the floor where the meeting with the entire team would take place. I
followed Stacy around a corner and through a large wooden door.
I stepped onto the boat and felt disoriented. I suddenly found
myself on a sailboat with my father, in the middle of the Atlantic
Ocean, rocking violently in a complete mess of a thunderstorm. My dad
was signaling for me to grab the lines near the bow, but before I could
grab a hold of them a giant wave crashed into the broad side of the
boat and knocked me overboard. Right before I hit the surface of the
water, I woke up.
…
I’m jobless in Michigan. For the past month, I’ve been relentlessly
applying to and interviewing for various local jobs with little to no
success. As of last night, the job hunting process has permeated my
subconscious mind to the point where I’m literally dreaming about it.
What I experienced in my dream was so vivid that I felt compelled to
share it above. No, it never happened. No, it’s not an accurate
representation of the application and interview process at Google. It
is, however, more interesting than my recent experiences in the real
world.
If I misled you, I’m sorry. I just wanted to take a break from
writing cover letters to write something enjoyable. I hope some readers
will enjoy reading it as much as I enjoyed writing it.
Original story

So the economy is really bad and your job might be on the line,
Google is always looking for new talent. Here are 2 questions that they
asked a friend of mine. What would you answer?
1. You have been shrunk down to the size of a nickel and tossed
into a blender. You are told that the blender blades will start in 60
seconds.What would you do to save your life?
2. 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.
* 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)
* 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.
* You can use only custom written applications or available free open-source software.
So what do you think, could you answer these questions?
And don’t forget, if you have any tech questions then don’t hesitate to ask in our forums
Original story

Sudoku
Write an algorithm for Soduku puzzle
Dictionary Lookup
What method would you use to look up a name in a dictionary?
Stack Growth
How would you find out if a machine's stack grows up or down in memory?
Random
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.
DFS
Describe the algorithm for a depth-first graph traversal.
Card Game
Design a class library for writing card games.
Phone Numner
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?
Special Debugging
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?
Next Prime
Given a number, describe an algorithm to find the next number which is prime.
Order functions
Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
BST
what is the best and worst performance time for a hash tree and binary search tree?
String
What is the best and worst time for the operation 'equals'
How do you spedup the 'equals' operation
Write a function (and dictate it to your interviewer) that reverse the
order of words in a sentence. The final algorithm should work
in-place!! E.g.: "This is a sample" --> "sample a is This"
Multi Threading
Trade offs between a multi threaded and single threaded implementation ?
N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
N N-1
There are a set of 'n' integers. Describe an algorithm to find for each
of all its subsets of n-1 integers the product of its integers.
Sorting
Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort,Shell,Radix,Heap
If you had a million integers how would you sort them and how much memeory would that consume?
Check for Square
Describe an alogrithm to find out if an integer is a square?
Adwords
How would you determine if adwords was up and running and serving contextual content ?
NXN Matrix
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.
Division
Implement division (without using the divide operator, obviously).
Infinite Queries
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.
Trees
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.
Minimum of List
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.
Google Home Server
Design a web server that serves the Google homepage. a) What are the
requirements. b) Design a multi threaded web server that uses shared
memory instead of disk access. c) Design a work load balancer for their
data centers. d) Design a DNS server that returns the IP address of a
data center that has the best connectivity relative to your IP.
SnS Link Amazon Interview Questions Puzzles and Algorithms

Tags: questions, comparsion |
Posted by Admin on
9/2/2008 1:53 PM |
Comments (0)

Dream of landing a coding job at an
A-list tech company? It might be a good idea to prep for your
interviews by pondering how many golf balls can fit inside a school
bus. Or how much you would charge for washing all the windows in
Seattle. Or why, exactly, manhole covers are round and not, say,
square.
Seemingly random questions like these have become
commonplace in Silicon Valley and other tech outposts, where companies
aren't as interested in the correct answer to a tough question as they
are in how a prospective employee might try to solve it. Since
businesses today have to be able to react quickly to shifting market
dynamics, they want more than engineers with high IQs and good college
transcripts. They want people who can think on their feet.
Microsoft (Charts, Fortune 500)
often gets credit for bringing so-called open-ended logic-problem
screening tools into vogue in the late 1980s, when Redmond interviewers
peppered job candidates with offbeat questions like How much does a 747
weigh? "We want to gauge people's creativity," says Warren Ashton,
recruiting manager at Microsoft. The manhole cover problem is Ashton's
personal favorite.
Google: No. 1 best company to work for
The most common answer, he
says, is that a square manhole cover, tipped at an angle, could fall
through the hole. "But some people recognize that you can roll a round
manhole cover from site to site. Others figure that you save money by
making it round because of tooling requirements. You want to see people
taking their conclusions as far as possible."
Such questions
are more relevant to a high-tech job interview than you might think.
"Employers want to see if you can make an estimate in the ballpark,
within an order of magnitude," says Mark Jen, a former Google (Charts, Fortune 500)
employee who is now a program manager at Tagged. Coders are constantly
making educated guesses rather than calculating exact answers, so a
good interview should probe how well a candidate handles such
estimates. That's why Amazon.com (Charts, Fortune 500)
interviewers, for example, have been known to ask job candidates to
guess how many gas stations there are in the United States or to
ballpark that bill for washing all of Seattle's windows.
But
today's interviews go beyond seat-of-the-pants estimation. Author,
design consultant, and veteran coder Bruce Eckel likes to have job
candidates describe a chicken using a programming language. eBay (Charts, Fortune 500)
often hits candidates with a word problem that goes like this: 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.)
Can you pass the Google test?
But no company has taken
brainteaser recruiting quite as far as Google, which famously reeled in
engineers three years ago by posting complex math problems on a
billboard along Highway 101 in Silicon Valley. Passing motorists were
invited to submit their solutions to an undisclosed website. (The
site's URL was hidden in the answer.)
If you got to the site,
you were asked a second, more difficult question. If you answered that
one correctly, you were invited to submit your resume. Once you got to
the Googleplex for an interview, a favorite question was this: 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?
It's not just employees who have to
adjust to the new screening processes. Employers are also prepping for
interviews in ways they never did before. When LinkedIn founder Reid
Hoffman was searching for a new CEO earlier this year, he took an
unusual approach to checking references. Having set his sights on a
particular candidate, he used the LinkedIn network to find what he
calls "off-balance references": 23 former associates who were not
preapproved by the candidate. Some were friends of friends - two
degrees removed, in LinkedIn parlance. Some had no idea who Hoffman was
or why he was calling.
Life inside Google
The unscripted references
helped to prepare the team that interviewed Hoffman's final choice.
Equally important, Hoffman got unfiltered information about a potential
top-tier employee, minimizing the likelihood of getting duped.
"Normally it's a low bar for someone to give you two or three people
who'll say nice things about them," Hoffman says. "Our way of doing it
requires a bit of detective work, and you need to put a story together.
But you quickly sense if a person is good or a sham."
Getting a
handle on a candidate's people skills can be just as important - and
just as tricky. At aQuantive, a digital marketing company, job
applicants go through an extensive interview loop and in most cases
must win the approval of everyone who met them before getting an offer.
"We jokingly liken it to organ rejection," says Kem Day, director of
recruiting. "But by reaching a better decision up front, we make sure
that whoever we hire will get support from within the company."
Clearly,
technical skills alone are not going to cut it in today's high-tech
environment. "It used to be that if you could spell 'engineer,' you got
a shot," says Beverly Principal, assistant director of Stanford
University's Career Development Center. "Now there is much more concern
about employees being able to work with the company and grow to the
next level." That, and being able to survive when shrunk to the size of
a nickel.
How many golf balls can fit in a school bus?
About 500,000, assuming the bus is 50 balls high, 50 balls wide, and 200 balls long
You're shrunk and trapped in a blender that will turn on in 60 seconds. What do you do?
Some options:
1. Use the measurement marks to climb out
2. Try to unscrew the glass
3. Risk riding out the air current
How much should you charge to wash all the windows in Seattle?
Assuming 10,000 city blocks, 600 windows per block, five minutes per window, and a rate of $20 per hour, about $10 million.
Original story
Given a number, describe an algorithm to find the next number which is prime.
There are 8 stones which are similar except one which is heavier
than the others. To find it, you are given a pan balance. What is the
minimal number of weighing needed to find out the heaviest stone ?
Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If
the pan is remains balanced, the heavier is in the remaining (2). use
pan again to find which is heavy from (2). (Total pan use 2)
If the pan does not remain balanced when weighing (3,3), pick the
set of stones that outweigh other. Divide it into (1,1,1). use pan to
weigh first two. It it remains balanced, the remaining stone is the
heavier, otherwise the one outweighing other is heavier(total pan use
2)
[These questions from 'Taher']
Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
Answer: n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n
what is the best and worst performance time for a hash tree and binary search tree?
Answer:
Best is O(c), worst is O(log n)
Questions regarding a string Class
* What do you need when you instantiate a string ( i said a byte array and possibly the length) ?
* What is the best and worst time for the operation 'equals'
* How do you spedup the 'equals' operation (i said used hash MD5 for example)
This still has some problem ( a hash can be the same for unequal strings)
-> Use Boyer–Moore string search algorithm => O(n)
Trade offs between a multi threaded and single threaded implementation ?
N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.
For example, let consider (6, 3, 1, 2). We need to find these products :
6 * 3 * 1 = 18
6 * 3 * 2 = 36
3 * 1 * 2 = 6
6 * 1 * 2 = 12
last one is simple
int mul = 1;
for i = 1 to N
mul *=a[i];
for i= 1 to N
a[i] = mul/a[i];
(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this.
Here's the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output
for (int i = 1; i <= n; i++)
{
if (i == 1)
print x[2,n];
else if (i == n)
print x[1,n-1];
else
print x[1,i-1] * x[i+1,n];
}
To build the table, start along the diagonal (x[i,i] = ni). Then do
successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k+1]).
1. Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort
2. If you had a million integers how would you sort them and how much memeory would that consume?
Binary tree - requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB
Insertion sort - can be done in under 4 MB
3.Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn't
a) simple answer - start at 2 and divide the integer by each
successive value. If it divides evenly before you reach half way then
it is.
b) complex answer after much leading - Do the bitwise AND of n and
(n-1). If it is zero then it is a square (I think this is wrong. This
actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
C)
i=2;
while(!NO)
{
if((i*i)==Number)
{
NO;
return True;}
if((i*i)>Number)
{
NO;
return false;}
i++;
}
4. How would you determine if adwords was up and running and serving contextual content ?
5428907816463810488188
Here are some questions I got on my first interview with Google (slightly altered for NDA reasons).
1 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.
2 Write some code to reverse a string.
3 Implement division (without using the divide operator, obviously).
4 Write some code to find all permutations of the letters in a particular string.
5 You have to get from point A to point B. You don’t know if you can get there. What would you do?
6 What method would you use to look up a word in a dictionary?
7 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?
8 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?
Phone interview
1. Describe the data structure that is used to manage memory. (stack)
2. whats the difference between local and global variables?
3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
4. 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++).
5. Talk about your class projects or work projects (pick something
easy)… then describe how you could make them more efficient (in terms
of algorithms).
In person interview
1. In Java, what is the difference between final, finally, and finalize?
2. What is multithreaded programming? What is a deadlock?
3. Write a function (with helper functions if needed) called toExcel
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..).
4. 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.
5. 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.
6. 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.
Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/Google_Interview_Questions"
Here is a bunch more:
How many golf balls can fit in a school bus? This is a Fermi question.
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.)

I gathered some of the important and top interview questions of Google from different people interviews. I hope This post helps those who are preparing for the Google Interview.
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 ?
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 ?
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
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code
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
Classic - Egg Problem
You are given 2 eggs.You have access to a 100-storey 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 100 th floor.Both
eggs are identical.You need to figure out the highest floor of a
100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Tags: algorithm, questions, answers, c++ questions |
Posted by Admin on
7/29/2008 12:59 AM |
Comments (0)

1. Reverse a singly linked list
//
// iterative version
//
Node* ReverseList( Node ** List )
{
Node *temp1 = *List;
Node * temp2 = NULL;
Node * temp3 = NULL;
while ( temp1 )
{
*List = temp1; //set the head to last node
temp2= temp1->pNext; // save the next ptr in temp2
temp1->pNext = temp3; // change next to privous
temp3 = temp1;
temp1 = temp2;
}
return *List;
}
2. Delete a node in double linked list
void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}
3. Sort a linked list
//sorting in descending order
struct node
{
int value;
node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers
Sort( Node *Head)
{
node* first,second,temp;
first= Head;
while(first!=null)
{
second=first->NEXT;
while(second!=null)
{
if(first->value < second->value)
{
temp = new node();
temp->value=first->value;
first->value=second->value;
second->value=temp->value;
delete temp;
}
second=second->NEXT;
}
first=first->NEXT;
}
}
4. Reverse a string
void ReverseString (char *String)
{
char *Begin = String;
char *End = String + strlen(String) - 1;
char TempChar = '\0';
while (Begin < End)
{
TempChar = *Begin;
*Begin = *End;
*End = TempChar;
Begin++;
End--;
}
}
5. Insert a node a sorted linked list
void sortedInsert(Node * head, Node* newNode)
{
Node *current = head;
// traverse the list until you find item bigger the // new node value
//
while (current!= NULL && current->data < newNode->data)
{
current = current->next);
}
//
// insert the new node before the big item
//
newNode->next = current->next;
current = newNode;
}
6. Covert a string to upper case
void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
S++;
}
}
7. Multiple a number by 7 without using * and + operator.
NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8
NewNum = NewNum - Num; // 8 – 1 = 7
8.
Write a function that takes in a string parameter and checks to see
whether or not it is an integer, and if it is then return the integer
value.
#include
int strtoint(char *s)
{
int index = 0, flag = 0;
while( *(s+index) != '\0')
{
if( (*(s + index) >= '0') &&
*(s + index) <= '9')
{
flag = 1;
index++;
}
else
{
flag = 0;
break;
}
}
if( flag == 1 )
return atoi(s);
else
return 0;
}
main()
{
printf("%d",strtoint("0123"));
printf("\n%d",strtoint("0123ii"));
}
9. Print a data from a binary tree – In-order(ascending)
//
// recursive version
//
Void PrintTree ( struct * node node )
{
if ( node == NULL )
return;
PrintTree(node->left );
Printf(“%d”, node->data);
PrintTree(node->right );
}
10. print integer using only putchar
//
// recursive version
//
void PrintNum ( int Num )
{
if ( Num == 0 )
return;
PrintNum ( Num / 10 );
Puthcar ( ‘0’+ Num % 10 );
}
11. Find the factorial of number
//
// recursive version
//
int Factorial( int Num )
{
If ( num > 0 )
return Num * Factorial ( Num –1 );
else
return 1;
}
//
// iterative version
//
int Factorial( int Num )
{
int I
int result = 1;
for ( I= Num; I > 0; I-- )
{
result = result * I;
}
return result;
}
12. Generate Fib numbers:
int fib( n ) // recursive version
{
if ( n < 2 )
return 1;
else
return fib ( n –1 ) + fib ( n –2 );
}
int fib( n ) //iterative version
{
int f1 =1, f2 = 1;
if ( n < 2 )
return 1;
for ( i = 1; i < N; i++)
{
f = f1 + f2;
f1= f2;
f = f1;
}
return f;
}
13. Write a function that finds the last instance of a character in a string
char *lastchar(char *String, char ch)
{
char *pStr = NULL;
// traverse the entire string
while( * String ++ != NULL )
{
if( *String == ch )
pStr = String;
}
return pStr;
}
14. Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
15. Counting set bits in a number.
First version:
int CoutSetBits(int Num)
{
for(int count=0; Num; Num >>= 1)
{
if (Num & 1)
count++;
}
return count;
}
Optimized version:
int CoutSetBits(int Num)
{
for(int count =0; Num; count++)
{
Num &= Num -1;
}
}
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“.
It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.
After that day, I looked for other well-known interview questions
and I discovered that Google has a totally different approach, focusing
on algorithms, data structures and complexity.
For instance, one of Google interview questions says:
There is an array A[N] of N integers. You have to
compose an array Output[N+1] such that Output[i] will be equal to the
product of all the elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.
Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].
We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].
We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.
With these functions we can just define an input array and apply them to get the result.
The following is the complete F# code:
let input = [ 4; 3; 2; 1; 2 ]
let answer values =
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
values |> firstpass 1 |> secondpass 1 values
Original story

I thought it might be useful to collect some
of the questions I or my friends have been asked over the years. I've
had a number of jobs in the computer industry with the side effect that
I've been to a lot of interviews. Obviously these are all centered
around Linux System Administration since that's my profession.
So to dive right in, here are some questions I remember:
Name the three packets exchanged in the
setup of a TCP connection. Followup: name the three packets exchanged
when a client closes a TCP connection.
Answer: SYN, SYN/ACK, SYN
Followup: FIN, ACK, FIN, ACK
Three times are kept for every unix file. What are they?
Answer: atime, ctime, and mtime. The atime is
the access time, i.e. the last time the file was read. ctime seems like
it should be the creation time, but it isn't. In fact, there is no way
to determine when a file was created in Unix. ctime stands for change time,
and it is a record of the last time the file's inode was changed. This
happens for example when the permissions or ownership on the file are
modified.
Finally, the mtime is the time the file was modified, i.e. when the actual file was written to.
How many computers can you put on a /17 network?
Interviewers love these sorts of questions. I
personally hate them, but maybe that's just me. The answer to this
particular question is 32766. The quick formula is (2^(32-17))-2, i.e.
subtract the cidr # from 32, raise 2 to that power, and subtract 2. Why
subtract 2? Because all 0s and all 1s are not valid system addresses.
All 1s is the broadcast address. All 0s is technically a valid address,
but for historical reasons you can't use it. Thus for any address range
you always have to subtract 2 entries to get the number of usable
addresses.
A followup question is what is the netmask?
Answer: 255.255.128.0. To calculate, observe that in binary a /17 cidr
can be written as:
11111111 11111111 10000000 00000000
the first two octets are 255 (all ones). The
last is 0 (all zeros). Thus the only one you need to convert to decimal
is 10000000. To do this, dust off your binary knowledge:
10000000 = (0x2^0) + (0x2^1) + (0x2^2) + (0X2^3) + (0x2^4) + (0x2^5) + (0x2^6) + (1x2^7)
2^7 is 128, so it's 0+0+0+0+0+0+0+128 = 128. The netmask is therefore 255.255.128.0.
I suspect there's an easier way to do that.
What's an inode? Followup: what key piece of information about a file is not stored in the inode?
An inode is the on-disk data structure that
describes a file and contains key information such as owner and
permission. The answer to the followup is the filename - that is stored
in the directory. Followup to followup: this also explains the
difference between ctime and mtime.
What's the first startup script executed on a Fedora system?
Answer: /etc/rc.d/rc.sysinit
Put the following operations in order from
slowest to fastest: read cpu register, disk seek, read from main
memory, write to pci bus.
Answer: disk seek, write to pci bus, read from main memory, read cpu register
Compare the output of two processes using diff. Don't use temporary files.
Answer: use NamedPipesInBash, i.e.:
# diff <(process one) <(process two)
(this one is kind of extra credit)
What does the sticky bit do when applied to a file? A directory?
Describe RAID levels 0,1,5, and 0+1. What's the difference between 0+1 and 1+0?
What's the difference between my and local in perl? Give examples of usage of both.
Write a script that takes an input word and a corpus of text, and finds all anagrams of the input word in the text.
A pretty good way to do this in perl is to read
the input line by line. Then break each line into words by word
boundary (\b). Alphabetize the letters of the imput word and each word
in the line. If they are a match, you've found an anagram.
What are the three fundamental data types in Perl?
array, hash, scalar
Define a zombie process. Followup: when and why does init become the parent of a process?
A process becomes a zombie when it's parent
exits without calling wait().
If parent dies before child, init (PID 1) becomes parent of such child.
This is necessary to reclaim process state after child exits.
In bash, what variable contains the exit status of the last executed process?
$?

- Next posts
- 1
- 2
- Previous posts