Tags: , , | Posted by Admin on 10/26/2012 8:37 AM | Comments (0)
There is nothing like the feeling of elation after you know you ace'd your interview.   Or, maybe you gave it your best shot but fell short.   Either way or in between, this is the perfect place, to share your experience.  Take a few minutes to answer any or all of the questions below in the comments section.   All comments will be reviewed for appropriateness before being posted and your name/user id will not appear anywhere in website.  This is your chance to give real and honest feedback in a completely anonymous way! 1.  What company were you interviewed by and which location? 2.  What position were you being considered for? 3.  What kind of interview was it?  i.e., phone, first round in person, final, etc.? 4.  How were you treated by the company before, during, and after the interview? 5.  What was your general impression of the company? 6.  Please share some of the interview questions. 7.  Do you think you'll get an offer and if so, do you think you'll accept?      
Tags: , | Posted by Admin on 7/4/2012 9:16 AM | Comments (0)
The Googleinterview process is Infamous for it’s mind boggling and creative methods to test new candidates. Here are two I’ve selected for you to first try to solve yourself, then see Google’s perfect answer. Q. How many golf balls will fit in a Mini? A. We will use a new mini opposed to a classic mini shape. It is shorter than a person, so maybe its 4.5 feet high, but with the clearance off the floor, lets say roughly 4 foot. There’s space for two people to sit side by side, with roughly 2.5 feet per person. So that’s 5 feet wide. It’s probably two people long, which is approximately ten feet. However the bonnet takes up half the length, so the usable length is 5 feet. The interior volume, then, is about 4 X 5 X 5, which is 100 cubic feet. A golf ball is somewhat bigger than an inch in diameter. Let’s say that 10 golf balls line up to make a foot. A cubic lattice of 10 X 10 X 10 golf balls, an even thousand, would just about occupy a cubic foot. That gives a quick answer of about 100 X 1,000 = 100,000 Or ….. take into consideration that each ball could be packed more densely given the shape of each. Effectively resting in an imaginary Lucite cude whose edges equal the ball’s diameter. You stack those Lucite cubes like building blocks. This would mean that the balls occupy about 52 per cent of the space. Break out of the imaginary Lucite boxes, and you can pack far more balls in a volume. This is an empirical fact. Physicists have done experiments by pouring steel balls into big flasks and calculating the density. The resulting random packing occupies anywhere from 55 to 64 per cent of the space. That’s denser than a cubic lattice. It’s also a fairly large range. How you fill the container matters. When the spheres are added gradually and gently, like sand pouring through an hourglass, the density is at the low-end of the range. When the container is shaken vigorously, the spheres settle into a denser packing of up to 64 per cent. Where does this leave us? Someone willing to painstakingly stack golf balls in the cannonball pattern can pack about 42 per cent more gold balls in the mini than you’d estimate from a cubic lattice (or as above). That seems an absurd amount of labor, even for an absurd question. The reported density of stirred random packing is a more realistic goal. You might achieve that by pouring golf balls into the mini and stirring with a stick to settle them. That would give a density of about 20 per cent more than that of a cubic lattice. You might therefore increase your final estimate by 20 per cent, from 100,000 to 120,000. For the record, the Mini website states a Mini Cooper Hardtop is 145.6 inches long, 75.3 inches wide (including mirror) and 55.4 inches high. The regulation diameter of a golf ball is 1.690 inches, give or take 0.005 inches. Q. It’s raining and you have to get to your car at the far end of the car park. Are you better off running or not, if the goal is to minimize how wet you get? What if you have an umbrella? A. To answer this question, you must reconcile two conflicting trains of thought. The case for running is this; the longer you are in the rain, the more drops fall on your head, and the wetter you get. Running shortens your exposure to the elements and thereby keep you drier. There’s also a case for not running; In moving horizontally, you slam into raindrops that wouldn’t have touched you had you been standing still. A person who runs in the rain for a minute gets wetter than a person who just stands in the rain for a minute. That valid point is mostly besides the point. You have to get to your car and there’s nothing to be done about that. Imagine yourself zipping across the car park at infinite speed. Your senses are infinitely accelerated, too, so you don’t slam into cars. From your point of view, external time has stopped. It’s like the bullet time effect in a movie. All the raindrops hand motionless in the air. Not one drop will fail on your head or back or sides during the trip. The front of your clothing will sop up every single raindrop hanging in the path from shelter to car. When you travel at normal speed, you’re fated to run into those raindrops or, rather their successors. At normal speed, you also have drops falling on your head. The number of raindrops you encounter will depend on the length of your horizontal path and also on the time it takes to travel that path. The length of the path is a given. The only thing you can control is the time it takes. To stay as dry as possible, you should run as fast as possible. Running makes you less wet –provided you don’t have an umbrella. Had you an umbrella as wide as a city block, and where you able to hold it, it wouldn’t matter whether you sauntered or sprinted. You’d be dry as toast. Most umbrellas are barely big enough to keep the user dry when he or she is standing in general, vertical rain. In practice, you expect to get a little wet. Umbrellas work by creating a rain shadow, a zone where there are no raindrops. In a vertical downpour, and with a circular umbrella, the rain shadow is a cylinder. When the rain is coming at an angle, the rain shadow becomes a skewed cylinder. However, as every seasoned umbrella user knows, its best to point the umbrella in the direction of the driving rain. This makes the rain shadow a proper cylinder again. Now pointed at an angle to the vertical, The standing human body doesn’t fit so well into a slanted cylinder. Were a hurricane driving the rain at you horizontally, you would have to hold the umbrella horizontally, and a tree foot diameter would protect only about half your body. The rest would get soaked. Wind is bad, and so is motion. The skilled umbrella wielder knows to tilt the umbrella forward, in the direction of the motion, to get the maximum coverage. In fact, wind and motion are indistinguishable as far as optimal umbrella pointing goes. Running at ten miles an hour in windless, vertical rain demands the same tilt as standing still in ten-mile an hour wind. Either way, the raindrops are coming at you ten miles an hour, horizontally, in addition to their downward velocity. In vertical rain, you’re best off walking slowly. The umbrella will not have to be tilted much, and your body should fit within the rain shadow. Ideally, you should walk no faster than the speed where the rain shadow just covers your feet. Then you’d stay dry. Reality is messier than that, there are always going to be gusts of wind, spatter from pavement, and runoff from the umbrella itself. The rain hitting the top of the umbrella does not disappear: it slides off the umbrella and falls in a cylindrical sheet encircling the rain shadow. There is more rain in that run off zone than anywhere else. That means that any part of your body that intersects the runoff zone gets wetter faster than it would have you not used an umbrella at all. The advantage of slowness diminishes in high headwinds. The umbrella has to be pitched at such angle that your lower body is out of the rain showdown. You’ll get half soaked no matter what you do. All that reasoning boils down to the advice you may have heard from mum: walk if you’ve got an umbrella: run if you don’t.
Tags: , , , , , | Posted by Admin on 1/26/2011 2:16 PM | Comments (0)
Here’s a list of 150 Google interview questions. Don't ask us where we got it from... Product Marketing ManagerWhy do you want to join Google? What do you know about Google’s product and technology? If you are Product Manager for Google’s Adwords, how do you plan to market this? What would you say during an AdWords or AdSense product seminar? Who are Google’s competitors, and how does Google compete with them? Have you ever used Google’s products? Gmail? What’s a creative way of marketing Google’s brand name and product? If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months? How much money you think Google makes daily from Gmail ads? Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product. Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20? Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year. Product ManagerHow would you boost the GMail subscription base? What is the most efficient way to sort a million integers? How would you re-position Google’s offerings to counteract competitive threats from Microsoft? How many golf balls can fit in a school bus? You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? How much should you charge to wash all the windows in Seattle? How would you find out if a machine’s stack grows up or down in memory? Explain a database in three sentences to your eight-year-old nephew. How many times a day does a clock’s hands overlap? You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager? How many piano tuners are there in the entire world? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process. Describe a technical problem you had and how you solved it. How would you design a simple search engine? Design an evacuation plan for San Francisco. There’s a latency problem in South Africa. Diagnose it. What are three long term challenges facing Google? Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it? If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building? How many vacuum’s are made per year in USA? Software EngineerWhy are manhole covers round? What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation? A man pushed his car to a hotel and lost his fortune. What happened? Explain the significance of “dead beef”. Write a C program which measures the the speed of a context switch on a UNIX/Linux system. Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7. Describe the algorithm for a depth-first graph traversal. Design a class library for writing card games. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How are cookies passed in the HTTP protocol? Design the SQL database tables for a car rental database. Write a regular expression which matches a email address. Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N. You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? Explain how congestion control works in the TCP protocol. In Java, what is the difference between final, finally, and finalize? What is multithreaded programming? What is a deadlock? Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..). You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Describe the data structure that is used to manage memory. (stack) What’s the difference between local and global variables? If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this) In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++). Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms). Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. Write some code to reverse a string. Implement division (without using the divide operator, obviously). Write some code to find all permutations of the letters in a particular string. What method would you use to look up a word in a dictionary? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? What is the C-language command for opening a connection with a foreign host over the internet? Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n). Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game? So your data structure should consider this condition also. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed. How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better? How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points? Let’s say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? Given a binary tree, programmatically you need to prove it is a binary search tree. You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one? Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge? Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change. Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? Write a function to find the middle node of a single link list. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Implement put/get methods of a fixed size cache with LRU replacement algorithm. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a solution in O(n) time complexity How does C++ deal with constructors and deconstructors of a class and its child class? Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list. What’s 2 to the power of 64? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How long it would take to sort 1 trillion numbers? Come up with a good estimate. Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it? How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three? Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element. Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists. What’s the difference between a hashtable and a hashmap? If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers? How would you reverse the image on an n by n matrix where each pixel is represented by a bit? Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t). Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space. Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road. What sort would you use if you had a large data set on disk and a small amount of ram to work with? What sort would you use if you required tight max time bounds and wanted highly regular performance. How would you store 1 million phone numbers? Design a 2D dungeon crawling game. It must allow for various items in the maze – walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.) What is the size of the C structure below on a 32-bit system? On a 64-bit? struct foo { char a; char* b; }; Software Engineer in TestEfficiently implement 3 stacks in a single array. Given an array of integers which is circularly sorted, how do you find a given integer. Write a program to find depth of binary search tree without using recursion. Find the maximum rectangle (in terms of area) under a histogram in linear time. Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type. Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python. How would you determine if someone has won a game of tic-tac-toe on a board of any size? Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. Create a cache with fast look up that only stores the N most recently accessed items. How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices? Given two files that has list of words (one per line), write a program to show the intersection. What kind of data structure would you use to index annagrams of words? e.g. if there exists the word “top” in the database, the query for “pot” should list that. Quantitative Compensation AnalystWhat is the yearly standard deviation of a stock given the monthly standard deviation? How many resumes does Google receive each year for software engineering? Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office? What is the probability of breaking a stick into 3 pieces and forming a triangle? Engineering ManagerYou’re the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive? AdWords AssociateHow would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions? How would you deal with an angry or frustrated advertisers on the phone?
Tags: , | Posted by Admin on 12/19/2010 11:37 AM | Comments (0)
Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens? Any answers? :)
Tags: , | Posted by Admin on 2/9/2010 1:15 PM | Comments (0)
So I decided to compile a list containing all the interview questions (some with my version of the answer) I could find for the Associate Product Manager and Product Manager position for Google.Before I post them, here is a little something I found.Google is aware of these questions (they must be since I used them to find these questions), so it is not far fetched to assume that the questions you will be asked on your google interview won’t be similar to that listed below. I found that interviewers are encouraged to come up with their own questions and there is a list of ‘banned’ questions (questions widely known and listed in sites like mine). If you get a question from this list and they figure out (since you were to quick to answer), they will either make it harder or ask another one…That being said, use this list as a way to prepare yourself from past questions asked for associate product manger and product manager.Questions in green are most recent questions (questions asked within 6-month period position).1) How many buses does the local transportation corporation own?My Answer: Estimate what the local population is (say 100,000), and percentage who would use local transportation (say 75%). From there estimate how many major routes you have (routes to say from city A to city B/downtown/mall/universities). How many buses will be traveling those routes (taking into account when the busiest times are should have the most buses out and remember that some of these buses go both ways e.g travel from city A to city B and back to city A.) Take into account how many you can fit into a bus, you can estimate how many buses a local transportation corp could potentially own.2)How would you handle someone who is just not doing the work, doesn’t get along with anyone, and is generally not working out?My Answer: Response to this question reflects on the individuals management and leadership style. But the candidate being interviewed should also keep in mind what company or team policy is when addressing the above issue.3)How many bottles of shampoo are produced in the world a year?My Answer:approximate 30 million = population of Canadaapproximate 6 billion = World Population23% of the world’s population is 3rd world population2% of the world’s population don’t use shampoo b/c they are bald or use soap25% total25% of 30 million don’t use shampoo, use soap, are bald, or cannot afford to purchase shampoo (third world) (-7.5 million) =22.5millionOne bottle of Shampoo lasts approximately 2 months, giving us 6 bottles a year per person.22.5million *6 = 133.1 million bottles in Canada6 billion – 25% = 4.5 billion4.5 billion *6 = 27.0 billion bottle per year4) You have 15 horses that run various speeds. You own a race track on which you can race the horses, and this track holds a maximum of 5 horses per race. If you have no stopwatch or other means of telling exactly how fast the horses are, how many races would you need to run between the horses to be ABSOLUTELY SURE which horses are first, second, and third fastest?My AnswerRace 1: Horse 1,2,3,4,5 => Assume 1,2,3 win in that orderRace 2: Horse 6,7,8,9,10 => Assume 6,7,8 win in that orderRace 3: Horse 11,12,13,14,15 =>Assume 11,12,13 win in that orderRace 4: Horse 1, 6, 11 (all first place winners) =>Assume 1 wins first (1 is the fastest) for the sake of simplicity and 6 and 11 came 2nd and 3rd placeRace 5: Horse 6, 11, 2, 7, 3 - Notice I did not choose horse 12 in this race because we assumed from Race 4 that horse 11 came in third place so it is of no value having horse 12 in the race.Total Race 51st Place is Horse 1, 2nd and 3rd Place is found from Race 55) Follow up, now you have 16 horses. How many races would you need to conduct to find first, second, and third?My AnswerFirst three races are identical to the above three racesAssumption 1:Race 4: Horse 16, 1, 6, 11 => Assume 16 wins first, and Horse 1 and 6 came second and third.Race 5: Horse 1, 6, 2, 7, 3 =>Notice I did not choose any horses from Race 3 results, this is because we know that horse 11 did not come out in the top 3 in Race 4.Total Race 5Assumption 2:Race 4: Horse 16, 1, 6, 11 => Assume 1 wins first, and Horse 6 and 16 came second and third.Race 5: Horse 6, 16, 2, 7, 3=>Notice I did not choose any horses from Race 3 results, this is because we know that horse 11 did not come out in the top 3 in Race 4.Total Race 56) Tell me about yourself? -Yep, they still ask this question7) How would you boost the GMail subscription base?8 ) What is the most efficient way to sort a million integers?9) How would you re-position Google’s offerings to counteract competitive threats from Microsoft?10) You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density.11) You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?12) How much should you charge to wash all the windows in Seattle?13) How would you find out if a machine’s stack grows up or down in memory?14) You have to get from point A to point B. You don’t know if you can get there. What would you do?15) How many piano tuners are there in the entire world?16) You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?Weighing 1: weight 3 balls on each side.If( 3 balls are equal)Weighing 2: weight the last 2 balls. The heavier is one of these.ElseWeighing 2: weight the heavier group from the first, put 1 ball on each weigh – if they are the same, the heavier one is the one you didn’t weigh…else the heavier one will be shown.17) You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.18 ) Describe a technical problem you had and how you solved it.19) How would you design a simple search engine?20) Design an evacuation plan for San Francisco.21) There’s a latency problem in South Africa. Diagnose it.22) What are three long term challenges facing Google?23) What do you know about Google’s product and technology?24) If you are Product Manager for Google’s Adwords, how do you plan to market this?25) What would you say during an AdWords or AdSense product seminar?26) Who are Google’s competitors, and how does Google compete with them?27) What’s a creative way of marketing Google’s brand name and product?28 ) If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?29) How much money you think Google makes daily from Gmail ads?30) Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.31) Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?32) Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.33) If you were given the land prices in the Bay Area, what would you pick, the mean or the median? Why?34) Estimate the revenue of various free web services from Google and competitors.35) You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently36) What is Google’s primary source of revenue?Adwords, Advertisement, TVAds37) How will you make Google win in (specific regional zone)?38 ) What website do you visit the most and what would you do as PM for that website?39) Airports are inefficient. What would you do to improve them?40) It is difficult to remember what you read, especially after many years. Contemplate how to address this.41) If Google were to offer a TV commercial service, how would you implement this?42) What is your favorite google product and what would you change about it?43) How would you design google maps?44) What google product do you like the best and how would you improve it?45) Why is a good user interface good for the company?Good user interface encourage the visitor to stay longer on the page, explore other pages, click on advertisement, and retreive and access information easily. Companies can build their identities on a good user interface since users will associate them with it. A good UI (e.g. Google Search Engine) can become their brand and if it is done right, it saves a lot of money in re-doing it or advertising.46) What is the marginal cost of a gigabyte in gmail?47) Name three web sites (non-Google sites) that I visit often and like. Comment on what I like about the user interface / design.48 ) Follow up with the above, choose one of the three sites and comment on what new feature/project I would work on and how I would design it.49) Elevator design – concentrate on if there is only one elevator in the building(what would I change in the design). Then moved up to having two elevators in a building..50) How many vacuum’s are made per year in USA?51) If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?Answer: 7.5 degrees ( 30 degrees between ‘3′ and ‘4′, 30/4 = 7.5 degrees)52) Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?Answer: Recursion Problem – If the women in the village know instantly when other men in the village have cheated, we can use this to our advantage in answering the question. If one man has cheated on their wife, then his wife will know he cheats since no one else is cheating and will thus meet his demise. Take example if two men cheats, one of the wives will know one cheating husband in the village and must wait one day to see if she hears of another man cheating – if not, she knows her husband has cheated and therefore kills him.53) If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?Answer: P(30min) = 0.95 ; Pbar(30min) = 0.05; Pbar(10min)=(1/3)^(0.05)=0.368 ; P(10min)=1-Pbar(10min) = 0.6312 = 63.12%54) Four people need to cross a rickety rope bridge to get back to their camp at night…Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?Answer: Classic Microsoft question.Trip A –> B A < — B Total TimeTrip 1 1min, 2 min   2 minTrip 2   1 min 3 minTrip 3 5 min, 10 min   13minTrip 4   2 min 15minTrip 5 1min, 2 min   17 min55) You are at a party with a friend and 10 people are present including you and the friend…Your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?Answer: Probability of someone sharing a birthday with you is P(share b-day) = 1/365 ; hence P(no share b-day)=364/365. I wouldn’t take the bet.56) Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?Answer : Anyone who knows me knows I have a mild case of OCD. I would have my closet organized (install shelving units) and compartmentalize some sections visually. I have a section for shirts I would wear out and section for shirts I would wear at home (worn out, great for spring cleaning). Then in each section I would organize the shirts by color from white to black. A relatively simple question, but I think Google asks this to check your organizational skills and for a software engineer – grouping (think hash tables)57) Explain a database in three sentences to your eight-year-old nephew.Answer: There are many answers to this question.1) Dictionary is like a database. You have word and what the word means.When I think of a database, I think of a filling cabinet my parents have where each hanging folder contains information. One folder has my grades, another has my birth certificate and birth hair, another has some pictures of me and my art work in elementary…etc.58 ) How would you re-position Google’s offerings to counteract competitive threats from Microsoft?Answer : My first thought – remove the awful word…’work around’ from Google’s work practice. This was my most hated two words I heard from there.59) You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)Answer:If you have 2 Pirates involved, only one pirate needs to support with pirate ‘2’s decision (namely pirate ‘2′ himself). Pirate ‘2′ would be highest in chain and hence can take all 100 gold coins since half would agree with this decision.If you have 3 Pirates involved, pirate ‘3′ needs only one other pirate to support him. Pirate ‘3′ is aware of the 2 pirate scenario if he dies and hence offers pirate ‘1′ 1 piece of gold to vote in his favor. Pirate ‘1′ will take the offer because 1 piece of gold is better than none. So end result is Pirate ‘1′ gets 1 piece of gold and Pirate ‘3′ takes 99 piece of gold (leaving Pirate ‘2′ with nothing).If you have 4 Pirates involved, you only need one other pirate to support you. Pirate ‘4′ is aware of the 3 pirate scenario if he dies and hence can offer pirate ‘1′ 2 pieces of gold to have his vote, but pirate ‘4′ is greedy. Instead he offers 1 piece of gold to pirate ‘2′. This gives him the vote from one other pirate he needs for support.Draw a table showing the 2-4 pirate scenarios, and you will notice a pattern. From this you can easily come up with a solution for the 5 Pirate scenarios.  1 2 3 4 52   100      3 1   99    4   1   99  5 1   1   9860) How many golf balls can fit in a school bus?Answer:Calculate size of bus (approx in feet 8lengthx6widthx20depth) = 960 sq. feet (convert to sql inches *1728) = 1,658,880; golf ball is 2.5 cubic inches (4/3* pi*0.85inches radius) ; 1,658,880/2.5=663,552 ; don’t foget seats and such so round down to say 500,000Got any Google Interview Questions that are not listed here? Feel free to add them in the comment box.61) How many people run marathon in UK every year?62) Describe the operation of Layer 2 (Data Link Layer) of the 7-layer ISO stack in as much detail as possible.63) How do you code integer division without using divider (‘/’)int x =20; int y = 5;log(x) – log(y) = log(answer)10^(answer) = 4 = answer;64) What are three things Google should know before releasing a product in Country XYZ?65) A man pushed his car to a hotel and lost his fortune. What happened?66) How would you determine if someone has won a game of tic-tac-toe on a board of any size?67) How many resumes does Google receive each year for software engineering?68) How would you design google maps?
Tags: , | Posted by Admin on 12/3/2009 10:38 AM | Comments (0)
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
Tags: , | Posted by Admin on 11/19/2009 2:39 PM | Comments (0)
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.
Tags: , | Posted by Admin on 10/25/2009 8:35 AM | Comments (0)
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?
Tags: | Posted by Admin on 9/13/2009 11:11 AM | Comments (0)
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.)
Tags: , | Posted by Admin on 8/1/2009 10:49 PM | Comments (0)
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?.
Tags: , , | Posted by Admin on 7/28/2009 10:48 PM | Comments (0)
You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? What method would you use to look up a word in a dictionary? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut. How many piano tuners are there in the entire world? What gives you joy? Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can’t use fractions in the answer. Hint: This is a trick question, pay close attention to the condition) How many times a day a clock’s hands overlap? Two MIT math graduates bump into each other. They hadn’t seen each other in over 20 years. The first grad says to the second: “how have you been?” Second: “Great! I got married and I have three daughters now” First: “Really? how old are they?” Second: “Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..” First: “Right, ok.. oh wait.. I still don’t know” second: “Oh sorry, the oldest one just started to play the piano” First: “Wonderful! my oldest is the same age!” Problem: How old are the daughters? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country? You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?
Tags: , , | Posted by Admin on 12/27/2008 10:32 AM | Comments (0)
Dec 1st, 4:00 pm. I had a paper that morning, on 'Object Oriented Modeling'. Didn't sleep last night preparing for the paper. So, my condition wasn't its best for the interview. They called at ten past four in the evening. The interviewer wanted to start off with the interview (coding questions) right away. So did I. He asked me what my favorite language was (C++, C#). He then gave me a problem - 'You are given a string of characters. You are required to calculate the frequencies of each distinct character in the string.' The solution is quite simple. I proposed 2 solutions. 'There are 2 sorted lists of integers. You need to merge the 2 lists into a third larger list which should also be sorted.' Solution to this problem is also quite simple. I gave him an array-based solution, O(m+n). He asked me to write the solution using linked lists. I did that too. 'Now suppose there are k lists, all sorted, instead of 2. And you want to merge all of those lists into a single large list which should also be sorted. How will you do that?' I began to think over. Within 30 secs, he dropped a hint and i picked it up instantly. Using his hint, i gave him a solution of O(k*n). He asked me if i could do it better. I tried and proposed a couple of other algorithms, some better than others, but none as good as O(k*n). The interviewer was actually testing as to whether i can think of alternative solutions. He told me that your first solution was optimal. I just wanted to check if you can give other solutions. I was happy i could think of 3-4 alternatives to the same problem. Like other interviewers, he too asked me if i had questions. I asked him about the 'procedure of the interview process at Google', since this third phone screen was unexpected. He said, "This is your 3rd phone screen right? So according to my feedback, they will be inviting you onsite very soon. You will have 2-4 rounds of interviews at Google office." and i was like... :D Yet, this time too, i was not satisfied with my performance. I wished i get another chance to do the same interview and i would do better.. End of this (final) phone screen. Read on, Onsite Interview @ Google, Hyderabad. ..signing off Original story...
Tags: , , | Posted by Admin on 12/27/2008 10:31 AM | Comments (0)
Nov 12th, 5:00 pm. This one was interesting. Not the interview itself, but some of the events related to it. I had put up a status message on my orkut profile - "Nov 12th - Big Day.." Since i thought this interview was final phone screen and would decide on my onsite chances, i considered it big. A friend of mine, thought all the while that the day is big for me, since its her birthday. :-P Another funny thing was with my cell phone. It couldn't take calls. I could make outgoing calls, but incoming calls were rejected on the caller's side. I spoke to the customer care. He said it would take atleast 24 hours to repair the 'technical problem'. I informed about this problem to my recruiter by sending out a mail to her at 12:30pm. Requested her to make arrangements for the interview call to be made at another number. They didn't reply at all. Until 5:00pm, i didnt know if i was going to be interviewed that evening, at all. Well, finally the phone rang (at my friend's phone). I was quite confident this time compared to the last phone screen. The interviewer asked me if i was comfortable and if it was a good time to start with the interview. We got started. He asked me which programming language i was comfortable with. I told C++ & C#. Then he asked me to rate myself in C on a scale of 10. I rated myself 8. Cool, he wanted me to implement atoi() in C. But first, i was supposed to say what atoi() is. And i gave a very naive answer to that (after having myself rated 8!). All i knew was atoi() parsed the input string/array of numeric characters and returned the corresponding integer based on the radix (also passed as an argument to the function). He humbly explained me what the function is "generally" expected to do. :-) Oh, i forgot to mention. In the beginning of the interview, he asked me to have my laptop in front of me, with an internet connection. He shared a google doc with me, where i was supposed to write codes so that he could see them in real time. I wrote a pretty good code for the atoi() implementation. I am sure he liked it! In the middle of discussion on my solution for his first problem, he asked a couple of other simple questions. After this, he gave me a puzzle. I did what i could do worst for this. 'You have a transparent jar of marbles. You can determine the number of marbles in the jar at any time. You and your friend play a game. In each turn, a player draws one or two marbles from the jar. The player who draws the last marble, wins the game. Is it possible to play with a strategy such that you can win the game? Is it possible to determine who will win/lose the game?' As soon as he asked, i told him that i have heard of a similar puzzle earlier. He told me to answer to it anyway. I tried a couple of paths down to solution, but all were wrong. Strange thing is, i have had this puzzle solved twice earlier. I really screwed big time. Solution is quite simple. Readers are welcome to post comments on it. With that, my second phone screen ended. A good code, and a bad puzzle. I wished i had just one more chance to do this interview again. I would do much, much better. They took long time to respond. My hopes were fading. On Nov 26th, i got a mail finally informing about my 3rd phone screen scheduled on the 1st of Dec, 2008. My final semester exams were already on.. Too long post, huh. Read on, Third Phone Screen with Google.
Tags: , , | Posted by Admin on 12/27/2008 10:29 AM | Comments (0)
Nov 3rd, 5:00 pm. I was a little nervous. As for pre-interview preps, i took all my important papers (projects, semester mark sheets, etc) and placed them on my table. I had also some of my codes opened on my laptop screen for quick reference, if needed. Though, none of such preps ever was of any use. Finally the phone rang. It was a female interviewer. "Hi, is this Rajat?".. and the interview began. First question she asked was about my recent academic projects. I talked about one or two projects of mine. She then asked me what programming activities i involve myself in, other than college courses'. I mentioned TopCoder, GCJ, SPOJ and other such contests. She showed some interest in my standings in these contests. Next, she asked a problem and wanted me to code on that. 'Given a set of integers, how would you find out the 2nd maximum element?' I gave two solutions to this question, the second one being optimal. But i wont talk about it here right now, since it will kill readers' imagination. I wrote a code for the same and dictated it back to her. The code had a small bug. It wouldn't run for a corner case. I dont know if she noticed that bug. Next question was, 'There is a town with N people numbered 0 to N-1. Some people of this town knows some other people. The relation between them is not necessarily symmetric. i.e. If a knows b, doesn't mean b knows a. This town needs a mayor. The requisite for being a mayor is that he should be famous and impartial. Being famous means that he should be known to everyone in the town. Being impartial means that he should not know anyone in the town. Consider a function knows(i, j) that return true if i knows j or false otherwise. Write a program to return the list of people who are eligible for the mayor's post.' In google interviews, for every question, we are supposed to first propose the logic/algorithm to solve the question, and then write code for it. So was the case for this question too. I proposed an algorithm to solve this problem. She guided me through indirect hints(by asking questions that would lead me to her hint) to arrive at an almost optimal solution. I say 'almost' because even at the end of the interview, she kept on saying that there's a small bug in the code (and never revealed what it was), which i had not been able to figure out yet! Guess, it was one of the Google's interview pattern - say there is a bug even if there isn't any, to confuse the interviewee. The interivew lasted for around 1hr 5 mins. She asked me if i had any questions. I asked about work culture at Google. Quite expected. She wished me best and advised to continue with coding at Topcoder and GCJ, and solving puzzles. She also said that the HR people will get back to me soon. With that it ended.. I was expecting a 'Thank you' call from Google, given the kind of average perfomance i had shown at the interview. Really wished i had a chance to give this interview once more and i would give my best this time. To my surprise, i got a call for my second phone interivew on 7th Nov. :-) Read on, Second Phone Screen with Google. Original story...
Tags: , | Posted by Admin on 12/26/2008 10:04 AM | Comments (0)
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??
Tags: , | Posted by Admin on 12/21/2008 2:27 AM | Comments (0)
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.
Tags: , | Posted by Admin on 11/12/2008 2:20 PM | Comments (0)
This is the last part of posts describing my own experience interviewing with Google. You may find the first interview here and then follow the traces until this last one. Time had already passed (almost a month) after three successive interviews with Google and this last one was most probably the critical one. I did not prepare for this as much as the previous. The whole thing tires you up and at some point it seems better to relax and concentrate on the psychology rather than the technical stuff. I was only asked two technical questions, and since my language of choice was Java the interviewer wanted to see some Java code for the answers. In summary, this interview was perfect. While in all previous interviews, mostly the first and the second, I had some important flaws in my performance, but this one was different. And all this because I was playing in my field. Google at some point asks for a CV. However, the way I see it, Google and other major software companies search always for something unconventional in the candidate's application. You could say of course you know 5 or 10 programming languages, or that you can build an internet spider in 1 minute, however there might be some knowledge you have, that is somewhat rare and hence you should mention. In my case, this is Number Theory. For me, number theory is a passion that has not passed over time. It was love in the first sight, when I became aware of it, maybe at the age of 15 or so, and from that time it was the field mathematics that I was really feeling comfortable with. Anyway, it is not hard to see why it has been named as the "Queen Of Mathematics". First, it is very easy to grasp the basics (primes, divisors etc) since they are inherently tractable by the human brain. After all, every human being starts my learning how to count, which is the first step of the true intelligence, aka understanding that 5 ice creams and 5 cars, share something in common: that they are 5. This helps solving silly cases like, if I ate 5 ice creams and then I ate 1 more, how many did I eat? There is no need to think of ice creams, nor the eating process. All you have to do is to construct the proper model for this situation: use natural numbers and solve 5+1. Another great thing with number theory, is that your 'lab' can be a blank piece of paper. You can argue that 15 is divisible by 3, but all you need is a paper to perform the division. While a physicist might say that in light speeds some hypo-atomic elements, called mambojambions, are created, he still needs a gigantic, CERN-like laboratory to test his theories. Anyway, I myself was raised in a Pythagorean culture(numbers are holy) and so I claimed in my CV to know some number theory stuff. Although I was a little worried if I would be able to defend such claims (after I would be talking to Google), it soon proved to be a wise decision. Both in phone and on site interviews with Google, there was no better time for me than doing number theory. And to much of my surprise, and despite that Google's name is inspired by a natural number (or a unit of measure if you wish), all the 'Googlers' that I spoke and met with, did lack elementary knowledge on the field. This time, (I assume) the interviewer had dug in my profile and wanted to see for himself. Every question and conversation was related to Number Theory. So, the first question was about sets: "Create a function, called powerSet(), that will output the power set of the input set." The power set in Algebra theory is the set of all subsets of a set (no..bull-set!) If a set has N elements then the power set will have 2^N elements. So if a set is denoted by {a,b} with a,b as elements then the power set is { {},{a},{b},{a,b} }. The {} is the empty set. Note that all elements of the power set are sets. Recursion can help for solving this problem. If for example the powerSet function can produce power sets for sets that have at most N elements how should we solve for the N+1 case? If we denote sets with capital letters and the initial set as A, we can use the following algorithm 1. define B set initially empty 2. a = extract one element from A 3. add powerSet(A) to B 4. for every set in B, say X, add a, and then add it to B 5. return B Making the proper checks, this yields a function that can produce the power set of a set. For the Java case you can use the java.util.Set interface to write the code. I was asked to write the Java code but not asked any further questions, like complexity, runtime and so on. So we moved to the next and final question. This was: "Create a function, called findZeros(), that will compute the number of zeros in the decimal representation of n!". Now this is interesting and despite seemingly easy it has subtle points. For example, 5! = 1.2.3.4.5= 120 has one zero and 10! = 1.2.3.4.5.6.7.8.9.10 = 3628800 and has two zeros. Now the obvious answer is to produce this C-style pseudo code: int findZeros(int n) { z<-0; N<- n! while ( N%10==0) { z++; N/=10;} return z; } It seems right but has a terrible flaw: it fails at very 'small' values of n, in our 4-byte world, for n=15. Using some Java code like below, we can verify this case. int n=1,i=2,m=1; while(n>=m) { m=n; n*=i; System.out.println("Previous value "+m+" Current value "+n+" Counter "+i); i++; } System.out.println("OOPS! Overflow!"); So, if our code works only for 14 cases, it is pretty much useless. We should do better than that. For number theory geeks, like myself, this means show time! The equation below is called the Legendre's formula and basically computes the factorization of n!. The exponent in which prime p is 'participating' in the factorization is the sum in the figure. Now, we should use it for our case. 10 is the product 2x5. So, the exponents of 2 and 5 in the factorization of n! defines how many zeros we get. For example, 10! = 1.2.3.4.5.6.7.8.9.10 = (2^8).(3^3).(5^2).7 So 2 is found 8 times and 5 is found 2 times in the factorization, hence if we pair up the 2's and 5's we get two zeros. Now, there are obviously more 2's than 5's in the expansion so finally we have to answer at the question: What is the exponent of 5 in the factorization of n!? Based on the reasoning above this is equal to the number of zeros of n!. Based on Legendre's formula we have to calculate: [n/5]+[n/5^2]+[n/5^3]+... to infinite. This is done for example by the following Java code calculateZeros(int n) { int s=0,r,p=5; while((r=(n/p)) !=0) {s+=r; p*=p;} System.out.println(n+"! has "+s+" zero"+((s==1)?"":"s")); } For example, 25 = 1.2.3....23.24.25 = 15511210043330985984000000. Running the above code will produce the message 25! has 6 zeros. Instead of messing with a number with 26 digits (25!) you only have to deal with the number 25. Why? In the sum S(n) = [n/5]+[n/5^2]+[n/5^3]... the first term, [n/5], computes how many numbers up to n are multiples of 5. For the 25 case there are 5 of them: 5,10,15,20,25. The second computes all multiples of 25, i.e. only one. The third and all others are zero. A number that in its factorization, the prime 5 is in the power of k, e.g. 10 = 2.5 and k=1 or 25 = 5^2 and k=2, participates in the first k terms of the sum by adding one to each term. Hence its overall contribution is k, hence the sum S(n) calculates the power of 5 in the factorization of n!, and therefore the number of zeros in the decimal representation, Q.E.D. That was it! There is no other way to handle such big values and the solution can deal with really gigantic numbers without explicit calculation. The interviewer had elementary number theoretic knowledge but was able to follow the reasoning and we had a very nice conversation after that. He seemed to be fond of such mathematical tricks as the one we dealt with. In summary, I think this was the interview question that booked me the plane ticket to fly to the Google site. I was very satisfied after we hang up and I was impatient for the outcome but deep inside I was sure it was an ideal interview session and that my chances were great. The next morning I received a phone call from Google inviting me for the on site interviews. Mission was accomplished. This post ends a series of posts in which I wrote about my phone interviews with Google along with many interview questions. For the on site interviews I am bound to an NDA so maybe I will post them encrypted! That's all for now about Google interview questions. Until, I come back for the on site experience remember a small tribute to Number Theory: "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Numbers were created by good Lord. Everything else is human's work-Leopold Kronecker)
Tags: , , , | Posted by Admin on 11/11/2008 2:18 PM | Comments (0)
This is the 3rd interview I had with Google. You can find the previous and the questions asked here: * First Google interview * Second interview In the 3rd interview I talked with a woman software engineer from Mountain View. As usually it lasted for about 45 minutes but there was a surprise waiting at the last question..But let's take things from the beginning. The first question was a hard test for my memory: "How do you test your code?" This is a fair one for software engineers. But not for my style. I personally like things that are quick and dirty. For larger projects I use some of my own class libraries that employ some kind of logging, measure method execution time and so on. But saying "Well, I use my own class libraries." I thought would not be a good answer. Nor a professional one. So talking about Java, I made the mistake of mentioning the JUnit framework. I had used for some time (long ago) but the time had passed so I had forgotten even the basics. And of course the interviewer started the questions (How the JUnit handles exception and others) To tell you a secret I had already opened in my browser a JUnit site (some kind of tutorial I guess) but this didn't help at all. So, don't do it. It will only make things worse. Trying to think logically didn't help either. The interviewer kept pushing, until I 'broke' and admitted that I couldn't answer. That was it. We moved to the next question. All next questions were really typical, the kind you find in tech interview sites: * "What is a Unix kernel?" * "What is the difference between interfaces and abstractt classes?" * "What is the difference between threads and processes?" * "What is inheritance, polymorphism and encapsulation?" * "What is overriding and what is overloading?" I think there is no need to elaborate further on that. You most probably have come across these concepts and have your own mind. Which brings us to the last question. Actually it was a puzzle including programming with handicaps, i.e. with small processor, low memory etc. The puzzle was this: "You have 1000 integers. All are less than 1000 and greater or equal to 1. Among them, 999 are distinct and there is one that is found twice. How can you find the duplicate?" To this I gave an answer I think is optimal. The idea is simple. If you denote the duplicate number by d and the sum of all the integers by S then the following equation holds: S-d= 499500 since S-d is the sum 1+2+3...+999 which is equal to 499500 by applying the formula 1+2+3...+n = n*(n+1)/2 Now the good thing is that we can be able to find the duplicate even we have capacity for one integer, or when reading from a stream and so on. We can optimize even if we apply modulus to the first equation: d = (S-500) (mod 1000) Now if d is equal to a positive number mod1000 then this is the duplicate, otherwise the duplicate is the negative part plus 1000. For example is 1 was the duplicate, then d=1(mod 1000) and the duplicate had to be the 1. If the duplicate was 600, then d=-400(mod 1000) so the duplicate had to be -400+1000=600. This means we do not need to have storage for integer (int type) but only the byte type is enough. While fairly easy to grasp the interviewer had difficulties in understanding how this would work, so she asked for an example when we have 10 integers. I replied this would transform the equation to d =S-45 but then the counter question was disappointing: "How did you compute 45?" It is quite obvious however that I had to compute 1+2...+9 which is equal to 45 when applying the formula that Gauss found when he was 8. But the interviewer started computed 'by hand' the sum, adding the numbers from 1 up to 9, which left me speechless for some seconds. I mentioned that there was a formula for that but she didn't listen, still being concentrating on her computations. I didn't bother elaborating on the modulus idea since obviously would not give me any more credit. After that, the interview had finished. I didn't ask anything, saying something like 'I have many questions but I do not wish to spend any more of your time' and we ended the conversation. In overall the last incident was really awkward. To that time I believed that all Google engineers had a good mathematical background. The engineer that I spoke with, did lack elementary skills. So in my eyes, the myth had been destroyed and it is a good advice to anybody, not bother berating himself more than he should. If you already knew the formula for the sum of consecutive integers, you have a good reason to feel more confident.
Tags: , , , | Posted by Admin on 11/10/2008 2:15 PM | Comments (0)
This continues from my first Google interview described here In overall, the second one was harder in terms of questions and expectations. I was called again from Mountain View sharply at the time we had arranged. The conversation began with an interesting question: "What would you change in the Java programming language?" This has more than one questions embedded and it is educating listening to all possible answers. For example, one of my suggestions was having 'mechanisms' much like the properties fields in C# to ease development (programming get/set methods seems very tiring to me)Since the question was referring to the language and not to the Virtual Machine anything you find tiring or absent in Java is probably a valid answer. We next proceeded to a C programming question. My interviewer knew that I was not a C-guru so he was gentle on that. The question was something like this. What is the output of this C program? main() { char X[500] = "Hello World"; printf("%s",X+5); } I knew it had to do something with memory allocation but I was not succinct on that. I said that the output would be blank and I guess I was right (the interviewers never tell you directly if you are right or wrong) So we said OK and moved on. The 3rd question was about creating random functions. It is the type of questions where given a function randX that provides uniformly numbers from 1 to X, to generate a another randY. The actual question was about making rand8 from rand6. It is easy to establish how to get a rand2 from rand6. Then you can get rand8 from rand2. This was a straightforward case. However, this problem appears very often in such situations and deserves some attention. You may find unlimited nonsense by searching for 'create rand7 from rand5' which is also a frequent question. Trying these forums/blogs etc you will get endless efforts of shifting from one rand to another using common arithmetic functions (addition, mod etc). This is nonsense. You will have to shift to elementary analysis for a while to get some good results. In the general case consider you have to generate randX from randY where Y > X. Now consider that this yields the division: Y = n*X+r So, you can one group of Y elements into X groups of n elements and one more group with r elements. Now number the X groups as 1,2,3..X Then, create a 'machine' that uses the algorithm: m = randY(); IF m belongs to one of the X groups return its number ELSE restart the machine The probability in every run of the algorithm to return one specific value from 1 to X is a =n/Y and the probability that the algorithm restarts is b = r/Y. So, the overall probability that the machine will output one number from 1 to X is : P = a+a*b+a*b*b+a*b*b*b+... = a*(1+b+b*b+...) = a/(1-b). By substitution we get, P = 1/X In other words, we have generated the function randX Now, if we wish to increase the rand range, for example get rand7 from rand5 you can create rand25 from rand5 (two rand5 calls) and then use the above method. Shifting to infinity is inevitable in some cases and all other efforts are in vain. Back to the interviews, the final question had to do with designing and analyzing an algorithm. This had to calculate all representations of an integer as a sum of cubes. You can find many similar examples in algorithms textbooks so presenting this story here is trivial. What is interesting is that, we started a discussion on an incident that was directly related to the problem. This is usually called as the 'cab number story'. Back in the days when Ramanujan was in Cambridge and was working with G.H. Hardy, he had frequent health problems. One day, Hardy visited Ramanujan to the hospital and to start a discussion he mentioned the number of the taxi cab that brought him there. He said something like "..The cab number was 1729. I think this number is not interesting at all." A few seconds Ramanujan (which was extremely competent with numbers and calculations) replied: "You are not right Mr.Hardy. 1729 is very interesting. It is the smallest number that can be written as a sum of cubes in two different ways." This was a nice way to close the interview. We didn't have much time left, so we said some relaxing things and then ended the interview conversation. All in all, it went well and my interviewer was a really nice person. Our discussion was interesting and I soon got the news that I was to pass to the next level. Having acquaintance with math and generally science history certainly helps!
Tags: , | Posted by Admin on 11/4/2008 2:15 PM | Comments (0)
First off, I’ll spare you the suspense. I did NOT get offered a job at Google… but I did have a lot of fun! I was first contacted back in December by a Google talent recruiter. Mike had been in the middle of his Google interviews, so it was an exciting time. Was I interested? Definitely! There are few in the software industry that wouldn’t jump at a chance to work for Google - one might call them the Mecca of the software industry (but only if it doesn’t offend anyone; if it does, let’s just call it a pretty neat place to work). I first received an email from the recruiter asking if I was interested, and where I wanted to look for a position. She told me that she thought there was a good fit for me for a Java position in Mountain View, but I asked her about looking for a job in Waterloo. Was it a mistake? Maybe, but she did mention that I could look into a position in Mountain View if the Waterloo position didn’t work out. Over the Christmas holidays, the recruited emailed me to let me know that the Waterloo position was a C++ position, and that perhaps I would have a better chance finding interest in Mountain View, but the next day she emailed me back to let me know that the Waterloo offices were interested. I was excited. One of my goals, new years resolutions if you will, was to step out of my comfort zone with regards to software development. It seems that every script I needed to write was being written in Perl and Bash script and every piece of software I was writing professionally was in Java. I wanted get out of the habbit of relying on Java/Perl/Bash. This seemed like a good opportunity as C++ is one of many languages I wanted to work on this year. Well, I guess what you really want to know is what sorts of things I was asked on my interviews. Well, before that, there are a lot of things that need to be reviewed; first and foremost, asymptotic notation and complexity. The interview questions consisted of asking me to come up with a semi-high level algorithm and then to explain the asymptotic complexity of each part as I went along, and then what the final complexity of the algorithm would be. The next thing that should be reviewed is your basic sorting algorithms and their respective complexities. I made sure to know heap sort, bubble sort, selection sort, binary sort, merge sort, quick sort and insertion sort. Also important, you should know the memory requirements that each algorithm uses to run (in big-O notation). I was asked in my first interview to not only minimize the runtime, but also the memory footprint (ie. insertion sort although is O(n^2) in runtime, it is O(1) with regards to memory). The next thing I reviewed was memory structures. Hash’s, binary trees, n-tier trees, etc and the properties that each one possesses. If the interviewer asks you about a binary tree, make sure you know the properties that make a binary tree special so that you can leverage it in your solution. Now, on to the interviews. The first interview started with a quick introduction from Steve about where he worked within Google (Google NYC) and what he worked on there (Google maps). Then it was right down to business. The first questions (from my memory, so don’t blame me if it isn’t 100% correct) was as follows: Given a binary tree, and two leaves, can you find the lowest common node of those leaves? I won’t give you the answer here. I’ll let you work it out for a bit and perhaps if there is enough discussion in the comments, I’ll leave the answer there. When giving my answer to the interviewer, I think I could have been a lot clearer. I was nervous; very nervous. I really didn’t know what to expect, even though Mike prepared me the night before. The answer I gave was right (as far as a solution and its complexity) however, about 10 minutes after completing my interview, I figured out a way to better leverage the binary tree structure which would have also given a much clearer answer. Also, I was asked to minimize both the runtime and memory usage in my solution. The next interview I had was about 2 weeks later and it was with Chris (also from the Google NYC offices) but he worked for Google’s blog search. This one started a little different; he asked about what I had worked on at my previous companies and more specifically what I felt the coolest project was. I had so many to choose from at Pason, but I went with the biggest and more complex, the DataStream project. After that, he asked me my ideal problem to solve was if I could leverage all that is Google. This really caught me off guard. I should have known it was going to come; I even read about someone who was asked a similar questions. I spent so much time preparing for the technical part of the interview, I forgot about the lighter part. I wish I could have done it over. My answer was a lame scheduling mash-up for Google maps. I really needed to think bigger… hell, my friends and I have talked for years about cool stuff that we could do if only we had a company that was as big as Google. I felt like an idiot, but what can you do. No sense dwelling on that. There were two technical questions that comprised this part of the interview. The first was: If you were designing the Vector class in Java, how would you code the add(Object) method? Deceptive; not hard per se, but there are a few things that need to be worried about when solving this question. The next question was the algorithm question: If you were given an unordered set of plane tickets which represented legs in a trip, can you figure out the order in which to use the tickets? This was a really fun problem to work on, and again, I’ll save the answer for the comments. Remember that they want you to come up with the lowest runtime algorithm that you can. Three days after I completed this interview, I got my letter letting me know that they were not going to be offering me a position. Was I disappointed? Sure. I have to admit that I thought about how neat it would be to work at Google, but it wasn’t all bad. It helped me fulfill another one of my new years resolutions - to get back into studying the “science” of computer science, and although stressful, the whole experience was a lot of fun.
Tags: , | Posted by Admin on 11/3/2008 2:12 PM | Comments (8)
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“. It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough. After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity. For instance, one of Google interview questions says: There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart. Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i]. We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i]. We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]: view plaincopy to clipboardprint? let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs  let rec firstpass product input = match input with | [] -> [] | x::xs -> product :: firstpass (product * x) xs For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual: view plaincopy to clipboardprint? let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr  let secondpass product input arr = let rev_input = List.rev input let rev_arr = List.rev arr let rec rev_secondpass product (input:list<int>) arr = match arr with | [] -> [] | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)] rev_secondpass product rev_input rev_arr Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls. With these functions we can just define an input array and apply them to get the result. The following is the complete F# code: view plaincopy to clipboardprint? #light    let input = [ 4; 3; 2; 1; 2 ]    let answer values =       let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs      let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr      values |> firstpass 1 |> secondpass 1 values 
Tags: , , | Posted by Admin on 10/27/2008 8:59 AM | Comments (0)
I sat in the waiting room with one other applicant. He was older than me by about ten years. Judging by our clothes, it was clear that we were taking different approaches to this once-in-a-lifetime opportunity. He dressed professionally. Black suit, white shirt, striped tie. His dress shoes were polished, and their shine matched well with that of his belt buckle. I dressed casually. Blue jeans. Sneakers. A brown collared sweater that hid the geeky maroon “Computer Wizard” t-shirt that I was using as an undershirt. I was trying to dress the part. I had heard that Google’s dress code was simply “You must wear clothes,” so I wore something I might wear to the office if I got the job. Sitting across from Mr. Business Suit, I started wondering if I made a huge mistake. For whatever reason, Mr. Business Suit hadn’t acknowledged my presence since I arrived. He sat cross-legged with a magazine in his lap, half-heartedly thumbing through it without looking up. He kept this up until the Hiring Manager opened the door to the adjacent office and called his name: “Don?” Don set his magazine down and stood up. “Good luck,” I said hopefully. He nodded at me and followed the Hiring Manager out of the room. I took pleasure noticing that the Hiring Manager wore sneakers and jeans. Now that I was the only applicant left in the room, I started reviewing the materials I brought with me to the interview. In my “Portfolio” (a thin 3-ring binder) I had: Loose copies of my resume How-To Instructions and Screenshots from three of my Open Source Projects Two Letters of Recommendation from previous Employers A Thank You Card that I planned to mail immediately following the interview I imagined that I had at least ten minutes until the Hiring Manager asked for me. I was therefore surprised when a petite woman entered the room and called my name: “Shaun?” “Yes?” “I’m Stacy,” she said, extending her arm. I stood up, tucked the Portfolio under my arm, and shook her hand. “Shaun Boyd. How do you do?” “Just fine, thanks. I have good news for you.” “Oh? What’s that?” “Your application has been fast-tracked. I’ll be giving you a quick tour of our facility, and then I’ll introduce you to the team that’s interested in your background.” “Oh my, that is good news,” I said through a huge smile. “How exciting!” “Definitely. Follow me.” As I followed her through the double doors and down the corridor, Stacy filled me in on what being “fast-tracked” meant. She explained that I still needed to be interviewed, but because my application was unanimously selected by an existing project team I was exempt from the first-tier “initial screening” interview. I would start at the second-tier interview, which would be conducted by current members of the team I might be working with. Stacy, a Senior Hiring Manager, would sit in during this interview to see how I interacted with the team members, and to answer any HR questions I might have about the position. Stacy led me into her office and told me to have a seat. She typed an instant message onto her screen, sent it, and then proceeded to copy and paste the same message to four or five other people. She toggled through the responses for a few minutes before speaking to me again. “We have almost 30 minutes until the entire team will be available to meet with you. Would you like to join me for some Free Lunch in the cafeteria?” “Absolutely,” I said. The cafeteria was intimidating. Nearly every station had at least half-a-dozen Google employees in line for their Free Lunch. Since they were already familiar with the selection and ordering process, they moved around the cafeteria with ease while I stood in place holding an empty tray. Stacy pointed to the different stations, told me the type of cuisine that was served there, and encouraged me to not be shy. “Everything is always free, tasty, and nutritious,” she said, more or less reciting everything I had heard about Google’s cafeteria verbatim. I got into the line for Chinese cuisine. I asked for a helping of General Tso’s Chicken over white rice. The chef asked me if I’d like some orange slices to go with my entree, and I said “Yes please!” I joined Stacy at a round table in the center of the cafeteria. She introduced me to Tom and Anu, two of the team members who would be interviewing me once we finished our lunch. She then busted my chops a little by telling them how I chose to get Free Lunch instead of a tour of the facility, but they said I made the right choice. Anu scolded me for not taking advantage of the Slurpee machine. Tom asked about the Portfolio I was carrying. I paged through it briefly, and explained that it was basically a detailed addendum to my application. I said that I’d like to show it to the entire team during the interview, if they’d be interested. He gave me the impression that they would be. Once we finished lunch, we returned our trays and left the cafeteria. The four of us rode the elevator up together and got off on the floor where the meeting with the entire team would take place. I followed Stacy around a corner and through a large wooden door. I stepped onto the boat and felt disoriented. I suddenly found myself on a sailboat with my father, in the middle of the Atlantic Ocean, rocking violently in a complete mess of a thunderstorm. My dad was signaling for me to grab the lines near the bow, but before I could grab a hold of them a giant wave crashed into the broad side of the boat and knocked me overboard. Right before I hit the surface of the water, I woke up. … I’m jobless in Michigan. For the past month, I’ve been relentlessly applying to and interviewing for various local jobs with little to no success. As of last night, the job hunting process has permeated my subconscious mind to the point where I’m literally dreaming about it. What I experienced in my dream was so vivid that I felt compelled to share it above. No, it never happened. No, it’s not an accurate representation of the application and interview process at Google. It is, however, more interesting than my recent experiences in the real world. If I misled you, I’m sorry. I just wanted to take a break from writing cover letters to write something enjoyable. I hope some readers will enjoy reading it as much as I enjoyed writing it. Original story
Tags: | Posted by Admin on 10/19/2008 10:28 AM | Comments (6)
So the economy is really bad and your job might be on the line, Google is always looking for new talent. Here are 2 questions that they asked a friend of mine. What would you answer? 1. You have been shrunk down to the size of a nickel and tossed into a blender. You are told that the blender blades will start in 60 seconds.What would you do to save your life? 2. Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests.These are the particulars. * You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) * The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. * You can use only custom written applications or available free open-source software. So what do you think, could you answer these questions? And don’t forget, if you have any tech questions then don’t hesitate to ask in our forums Original story
Tags: | Posted by Admin on 9/2/2008 2:06 PM | Comments (6)
Sudoku Write an algorithm for Soduku puzzle Dictionary Lookup What method would you use to look up a name in a dictionary? Stack Growth How would you find out if a machine's stack grows up or down in memory? Random Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7. DFS Describe the algorithm for a depth-first graph traversal. Card Game Design a class library for writing card games. Phone Numner You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? Special Debugging You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? Next Prime Given a number, describe an algorithm to find the next number which is prime. Order functions Order the functions in order of their asymptotic performance * 2^n * n^Googol ( 10^100) * n! * n^n BST what is the best and worst performance time for a hash tree and binary search tree? String What is the best and worst time for the operation 'equals' How do you spedup the 'equals' operation Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place!! E.g.: "This is a sample" --> "sample a is This" Multi Threading Trade offs between a multi threaded and single threaded implementation ? N threads .. n resources .. what protocol do you use to ensure no deadlocks occur? N N-1 There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers. Sorting Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort,Shell,Radix,Heap If you had a million integers how would you sort them and how much memeory would that consume? Check for Square Describe an alogrithm to find out if an integer is a square? Adwords How would you determine if adwords was up and running and serving contextual content ? NXN Matrix Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. Division Implement division (without using the divide operator, obviously). Infinite Queries You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Trees Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. Minimum of List You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Google Home Server Design a web server that serves the Google homepage. a) What are the requirements. b) Design a multi threaded web server that uses shared memory instead of disk access. c) Design a work load balancer for their data centers. d) Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP. SnS Link Amazon Interview Questions Puzzles and Algorithms
Tags: , | Posted by Admin on 9/2/2008 1:53 PM | Comments (0)
Dream of landing a coding job at an A-list tech company? It might be a good idea to prep for your interviews by pondering how many golf balls can fit inside a school bus. Or how much you would charge for washing all the windows in Seattle. Or why, exactly, manhole covers are round and not, say, square. Seemingly random questions like these have become commonplace in Silicon Valley and other tech outposts, where companies aren't as interested in the correct answer to a tough question as they are in how a prospective employee might try to solve it. Since businesses today have to be able to react quickly to shifting market dynamics, they want more than engineers with high IQs and good college transcripts. They want people who can think on their feet. Microsoft (Charts, Fortune 500) often gets credit for bringing so-called open-ended logic-problem screening tools into vogue in the late 1980s, when Redmond interviewers peppered job candidates with offbeat questions like How much does a 747 weigh? "We want to gauge people's creativity," says Warren Ashton, recruiting manager at Microsoft. The manhole cover problem is Ashton's personal favorite. Google: No. 1 best company to work for The most common answer, he says, is that a square manhole cover, tipped at an angle, could fall through the hole. "But some people recognize that you can roll a round manhole cover from site to site. Others figure that you save money by making it round because of tooling requirements. You want to see people taking their conclusions as far as possible." Such questions are more relevant to a high-tech job interview than you might think. "Employers want to see if you can make an estimate in the ballpark, within an order of magnitude," says Mark Jen, a former Google (Charts, Fortune 500) employee who is now a program manager at Tagged. Coders are constantly making educated guesses rather than calculating exact answers, so a good interview should probe how well a candidate handles such estimates. That's why Amazon.com (Charts, Fortune 500) interviewers, for example, have been known to ask job candidates to guess how many gas stations there are in the United States or to ballpark that bill for washing all of Seattle's windows. But today's interviews go beyond seat-of-the-pants estimation. Author, design consultant, and veteran coder Bruce Eckel likes to have job candidates describe a chicken using a programming language. eBay (Charts, Fortune 500) often hits candidates with a word problem that goes like this: You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) Can you pass the Google test? But no company has taken brainteaser recruiting quite as far as Google, which famously reeled in engineers three years ago by posting complex math problems on a billboard along Highway 101 in Silicon Valley. Passing motorists were invited to submit their solutions to an undisclosed website. (The site's URL was hidden in the answer.) If you got to the site, you were asked a second, more difficult question. If you answered that one correctly, you were invited to submit your resume. Once you got to the Googleplex for an interview, a favorite question was this: You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? It's not just employees who have to adjust to the new screening processes. Employers are also prepping for interviews in ways they never did before. When LinkedIn founder Reid Hoffman was searching for a new CEO earlier this year, he took an unusual approach to checking references. Having set his sights on a particular candidate, he used the LinkedIn network to find what he calls "off-balance references": 23 former associates who were not preapproved by the candidate. Some were friends of friends - two degrees removed, in LinkedIn parlance. Some had no idea who Hoffman was or why he was calling. Life inside Google The unscripted references helped to prepare the team that interviewed Hoffman's final choice. Equally important, Hoffman got unfiltered information about a potential top-tier employee, minimizing the likelihood of getting duped. "Normally it's a low bar for someone to give you two or three people who'll say nice things about them," Hoffman says. "Our way of doing it requires a bit of detective work, and you need to put a story together. But you quickly sense if a person is good or a sham." Getting a handle on a candidate's people skills can be just as important - and just as tricky. At aQuantive, a digital marketing company, job applicants go through an extensive interview loop and in most cases must win the approval of everyone who met them before getting an offer. "We jokingly liken it to organ rejection," says Kem Day, director of recruiting. "But by reaching a better decision up front, we make sure that whoever we hire will get support from within the company." Clearly, technical skills alone are not going to cut it in today's high-tech environment. "It used to be that if you could spell 'engineer,' you got a shot," says Beverly Principal, assistant director of Stanford University's Career Development Center. "Now there is much more concern about employees being able to work with the company and grow to the next level." That, and being able to survive when shrunk to the size of a nickel. How many golf balls can fit in a school bus? About 500,000, assuming the bus is 50 balls high, 50 balls wide, and 200 balls long You're shrunk and trapped in a blender that will turn on in 60 seconds. What do you do? Some options: 1. Use the measurement marks to climb out 2. Try to unscrew the glass 3. Risk riding out the air current How much should you charge to wash all the windows in Seattle? Assuming 10,000 city blocks, 600 windows per block, five minutes per window, and a rate of $20 per hour, about $10 million. Original story
Tags: , | Posted by Admin on 8/31/2008 1:33 PM | Comments (8)
Given a number, describe an algorithm to find the next number which is prime. There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find out the heaviest stone ? Answer: Divide the stones into sets like (3,3,2). Use pan to weigh (3,3). If the pan is remains balanced, the heavier is in the remaining (2). use pan again to find which is heavy from (2). (Total pan use 2) If the pan does not remain balanced when weighing (3,3), pick the set of stones that outweigh other. Divide it into (1,1,1). use pan to weigh first two. It it remains balanced, the remaining stone is the heavier, otherwise the one outweighing other is heavier(total pan use 2) [These questions from 'Taher'] Order the functions in order of their asymptotic performance * 2^n * n^Googol ( 10^100) * n! * n^n Answer: n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n what is the best and worst performance time for a hash tree and binary search tree? Answer: Best is O(c), worst is O(log n) Questions regarding a string Class * What do you need when you instantiate a string ( i said a byte array and possibly the length) ? * What is the best and worst time for the operation 'equals' * How do you spedup the 'equals' operation (i said used hash MD5 for example) This still has some problem ( a hash can be the same for unequal strings) -> Use Boyer–Moore string search algorithm => O(n) Trade offs between a multi threaded and single threaded implementation ? N threads .. n resources .. what protocol do you use to ensure no deadlocks occur? There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers. For example, let consider (6, 3, 1, 2). We need to find these products : 6 * 3 * 1 = 18 6 * 3 * 2 = 36 3 * 1 * 2 = 6 6 * 1 * 2 = 12 last one is simple int mul = 1; for i = 1 to N mul *=a[i]; for i= 1 to N a[i] = mul/a[i]; (I got this question, your answer is not correct) First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this. Here's the dynamic programming solution: You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output for (int i = 1; i <= n; i++) { if (i == 1) print x[2,n]; else if (i == n) print x[1,n-1]; else print x[1,i-1] * x[i+1,n]; } To build the table, start along the diagonal (x[i,i] = ni). Then do successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k+1]). 1. Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort 2. If you had a million integers how would you sort them and how much memeory would that consume? Binary tree - requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB Insertion sort - can be done in under 4 MB 3.Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn't a) simple answer - start at 2 and divide the integer by each successive value. If it divides evenly before you reach half way then it is. b) complex answer after much leading - Do the bitwise AND of n and (n-1). If it is zero then it is a square (I think this is wrong. This actually tests whether n is a power of 2). No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 C) i=2; while(!NO) { if((i*i)==Number) { NO; return True;} if((i*i)>Number) { NO; return false;} i++; } 4. How would you determine if adwords was up and running and serving contextual content ? 5428907816463810488188 Here are some questions I got on my first interview with Google (slightly altered for NDA reasons). 1 Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. 2 Write some code to reverse a string. 3 Implement division (without using the divide operator, obviously). 4 Write some code to find all permutations of the letters in a particular string. 5 You have to get from point A to point B. You don’t know if you can get there. What would you do? 6 What method would you use to look up a word in a dictionary? 7 Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? 8 You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? Phone interview 1. Describe the data structure that is used to manage memory. (stack) 2. whats the difference between local and global variables? 3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this) 4. In Java, what is the difference between static, final, and const. (if you dont know java they will ask something similar for C or C++). 5. Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms). In person interview 1. In Java, what is the difference between final, finally, and finalize? 2. What is multithreaded programming? What is a deadlock? 3. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..). 4. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. 5. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. 6. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/Google_Interview_Questions" Here is a bunch more: How many golf balls can fit in a school bus? This is a Fermi question. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? How much should you charge to wash all the windows in Seattle? How would you find out if a machine’s stack grows up or down in memory? Explain a database in three sentences to your eight-year-old nephew. How many times a day does a clock’s hands overlap? You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager? How many piano tuners are there in the entire world? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
Tags: | Posted by Admin on 8/31/2008 12:55 PM | Comments (52)
I gathered some of the important and top interview questions of Google from different people interviews. I hope This post helps those who are preparing for the Google Interview. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n). Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game? So your data structure should consider this condition also. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed. How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note :: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better? How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ? Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ? Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ? Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree Hint: Some kind of pointer handling with In Order Traversal - anybody in for writing some code You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one? Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge? Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change. Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? Write a function to find the middle node of a single link list. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Implement put/get methods of a fixed size cache with LRU replacement algorithm. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity Classic - Egg Problem You are given 2 eggs.You have access to a 100-storey building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
Tags: , , , | Posted by Admin on 7/29/2008 12:59 AM | Comments (0)
1. Reverse a singly linked list // // iterative version // Node* ReverseList( Node ** List ) { Node *temp1 = *List; Node * temp2 = NULL; Node * temp3 = NULL; while ( temp1 ) { *List = temp1; //set the head to last node temp2= temp1->pNext; // save the next ptr in temp2 temp1->pNext = temp3; // change next to privous temp3 = temp1; temp1 = temp2; } return *List; } 2. Delete a node in double linked list void deleteNode(node *n) { node *np = n->prev; node *nn = n->next; np->next = n->next; nn->prev = n->prev; delete n; } 3. Sort a linked list //sorting in descending order struct node { int value; node* NEXT; } //Assume HEAD pointer denotes the first element in the //linked list // only change the values…don’t have to change the //pointers Sort( Node *Head) { node* first,second,temp; first= Head; while(first!=null) { second=first->NEXT; while(second!=null) { if(first->value < second->value) { temp = new node(); temp->value=first->value; first->value=second->value; second->value=temp->value; delete temp; } second=second->NEXT; } first=first->NEXT; } } 4. Reverse a string void ReverseString (char *String) { char *Begin = String; char *End = String + strlen(String) - 1; char TempChar = '\0'; while (Begin < End) { TempChar = *Begin; *Begin = *End; *End = TempChar; Begin++; End--; } } 5. Insert a node a sorted linked list void sortedInsert(Node * head, Node* newNode) { Node *current = head; // traverse the list until you find item bigger the // new node value // while (current!= NULL && current->data < newNode->data) { current = current->next); } // // insert the new node before the big item // newNode->next = current->next; current = newNode; } 6. Covert a string to upper case void ToUpper(char * S) { while (*S!=0) { *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S; S++; } } 7. Multiple a number by 7 without using * and + operator. NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8 NewNum = NewNum - Num; // 8 – 1 = 7 8. Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value. #include int strtoint(char *s) { int index = 0, flag = 0; while( *(s+index) != '\0') { if( (*(s + index) >= '0') && *(s + index) <= '9') { flag = 1; index++; } else { flag = 0; break; } } if( flag == 1 ) return atoi(s); else return 0; } main() { printf("%d",strtoint("0123")); printf("\n%d",strtoint("0123ii")); } 9. Print a data from a binary tree – In-order(ascending) // // recursive version // Void PrintTree ( struct * node node ) { if ( node == NULL ) return; PrintTree(node->left ); Printf(“%d”, node->data); PrintTree(node->right ); } 10. print integer using only putchar // // recursive version // void PrintNum ( int Num ) { if ( Num == 0 ) return; PrintNum ( Num / 10 ); Puthcar ( ‘0’+ Num % 10 ); } 11. Find the factorial of number // // recursive version // int Factorial( int Num ) { If ( num > 0 ) return Num * Factorial ( Num –1 ); else return 1; } // // iterative version // int Factorial( int Num ) { int I int result = 1; for ( I= Num; I > 0; I-- ) { result = result * I; } return result; } 12. Generate Fib numbers: int fib( n ) // recursive version { if ( n < 2 ) return 1; else return fib ( n –1 ) + fib ( n –2 ); } int fib( n ) //iterative version { int f1 =1, f2 = 1; if ( n < 2 ) return 1; for ( i = 1; i < N; i++) { f = f1 + f2; f1= f2; f = f1; } return f; } 13. Write a function that finds the last instance of a character in a string char *lastchar(char *String, char ch) { char *pStr = NULL; // traverse the entire string while( * String ++ != NULL ) { if( *String == ch ) pStr = String; } return pStr; } 14. Return Nth the node from the end of the linked list in one pass. Node * GetNthNode ( Node* Head , int NthNode ) { Node * pNthNode = NULL; Node * pTempNode = NULL; int nCurrentElement = 0; for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext ) { nCurrentElement++; if ( nCurrentElement - NthNode == 0 ) { pNthNode = Head; } else if ( nCurrentElement - NthNode > 0) { pNthNode = pNthNode ->pNext; } } if (pNthNode ) { return pNthNode; } else return NULL; } 15. Counting set bits in a number. First version: int CoutSetBits(int Num) { for(int count=0; Num; Num >>= 1) { if (Num & 1) count++; } return count; } Optimized version: int CoutSetBits(int Num) { for(int count =0; Num; count++) { Num &= Num -1; } }
Tags: , | Posted by Admin on 6/10/2008 1:25 PM | Comments (0)
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“. It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough. After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity. For instance, one of Google interview questions says: There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart. Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i]. We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i]. We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]: let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs  let rec firstpass product input = match input with | [] -> [] | x::xs -> product :: firstpass (product * x) xs For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual: let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr  let secondpass product input arr = let rev_input = List.rev input let rev_arr = List.rev arr let rec rev_secondpass product (input:list<int>) arr = match arr with | [] -> [] | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)] rev_secondpass product rev_input rev_arr Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls. With these functions we can just define an input array and apply them to get the result. The following is the complete F# code: let input = [ 4; 3; 2; 1; 2 ]    let answer values =       let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs      let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr      values |> firstpass 1 |> secondpass 1 values  Original story
Tags: , | Posted by Admin on 9/12/2007 1:16 PM | Comments (0)
I thought it might be useful to collect some of the questions I or my friends have been asked over the years. I've had a number of jobs in the computer industry with the side effect that I've been to a lot of interviews. Obviously these are all centered around Linux System Administration since that's my profession. So to dive right in, here are some questions I remember: Name the three packets exchanged in the setup of a TCP connection. Followup: name the three packets exchanged when a client closes a TCP connection. Answer: SYN, SYN/ACK, SYN Followup: FIN, ACK, FIN, ACK Three times are kept for every unix file. What are they? Answer: atime, ctime, and mtime. The atime is the access time, i.e. the last time the file was read. ctime seems like it should be the creation time, but it isn't. In fact, there is no way to determine when a file was created in Unix. ctime stands for change time, and it is a record of the last time the file's inode was changed. This happens for example when the permissions or ownership on the file are modified. Finally, the mtime is the time the file was modified, i.e. when the actual file was written to. How many computers can you put on a /17 network? Interviewers love these sorts of questions. I personally hate them, but maybe that's just me. The answer to this particular question is 32766. The quick formula is (2^(32-17))-2, i.e. subtract the cidr # from 32, raise 2 to that power, and subtract 2. Why subtract 2? Because all 0s and all 1s are not valid system addresses. All 1s is the broadcast address. All 0s is technically a valid address, but for historical reasons you can't use it. Thus for any address range you always have to subtract 2 entries to get the number of usable addresses. A followup question is what is the netmask? Answer: 255.255.128.0. To calculate, observe that in binary a /17 cidr can be written as: 11111111 11111111 10000000 00000000 the first two octets are 255 (all ones). The last is 0 (all zeros). Thus the only one you need to convert to decimal is 10000000. To do this, dust off your binary knowledge: 10000000 = (0x2^0) + (0x2^1) + (0x2^2) + (0X2^3) + (0x2^4) + (0x2^5) + (0x2^6) + (1x2^7) 2^7 is 128, so it's 0+0+0+0+0+0+0+128 = 128. The netmask is therefore 255.255.128.0. I suspect there's an easier way to do that. What's an inode? Followup: what key piece of information about a file is not stored in the inode? An inode is the on-disk data structure that describes a file and contains key information such as owner and permission. The answer to the followup is the filename - that is stored in the directory. Followup to followup: this also explains the difference between ctime and mtime. What's the first startup script executed on a Fedora system? Answer: /etc/rc.d/rc.sysinit Put the following operations in order from slowest to fastest: read cpu register, disk seek, read from main memory, write to pci bus. Answer: disk seek, write to pci bus, read from main memory, read cpu register Compare the output of two processes using diff. Don't use temporary files. Answer: use NamedPipesInBash, i.e.: # diff <(process one) <(process two) (this one is kind of extra credit) What does the sticky bit do when applied to a file? A directory? Describe RAID levels 0,1,5, and 0+1. What's the difference between 0+1 and 1+0? What's the difference between my and local in perl? Give examples of usage of both. Write a script that takes an input word and a corpus of text, and finds all anagrams of the input word in the text. A pretty good way to do this in perl is to read the input line by line. Then break each line into words by word boundary (\b). Alphabetize the letters of the imput word and each word in the line. If they are a match, you've found an anagram. What are the three fundamental data types in Perl? array, hash, scalar Define a zombie process. Followup: when and why does init become the parent of a process? A process becomes a zombie when it's parent exits without calling wait(). If parent dies before child, init (PID 1) becomes parent of such child. This is necessary to reclaim process state after child exits. In bash, what variable contains the exit status of the last executed process? $?