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? :)

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?

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...

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.

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)