You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them. Solution:The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array. Sum of first N natural numbers=N*(N+1)/2 and S=N*(N+1)/2 – K.Now putting this other way around we get K=N*(N+1)/2 -S !! Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y. We solve this problem by solving 2 essential equations. They are X+Y=N*(N+1)/2 -S               (1) X*Y=N!/P             (2) where S and P are the cumulative sum and product of the array entries. You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place. Solution:The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution. Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.Questions on my project please be prepare well about your projectHow do you search for a word in a large database.How do you build address bar in say gmail. i.e. if you press ‘r’ then you get all email starting from ‘r’, and if you press ‘ra’ then you will get emails starting from ‘ra’.  

Question: How to find the Least Common Ancestor for 2 nodes of a binary tree? This sounds like "On finding lowest common ancestors: simplification and parallelization", by Baruch Schieber and Uzi Vishkin, SIAM J. Comput. Vol 17, No 6, December 1988. A google search leads me tohttp://ia700208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf. I actually wrote an implementation of this for fun - it is in a zip file miscellaneous for-fun Java code that you can find off a link from http://www.mcdowella.demon.co.uk/programs.html. (The algorithm needs linear space and time for pre-processing, then runs at O(1) per query).

All the below questions are to be done in O(n) time complexity. 1>Given an array of size n-1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as read-only. 2>Given an array of size n-2 whose entries are integers in the range [1, n], find two integer that are missing. 3>There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. or Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Solution : 1>Let the missing number be M. We know that the sum of first N natural numbers is N*(N+1)/2. Traverse through the array once and calculate the sum. This is the sum of first N natural numbers – M or S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S. 2>Similar approach to the first one. Traverse the array once and calculate its sum and multiplication. Let the sum be S and multiplication be M. Let the missing numbers be P and Q. From above we know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q from these two equations. 3> Lets first see the C++ solution. void solution(vector<int> A) { int N=A.size(),i,j; vector<int> L(N,0); vector<int> R(N,0); vector<int> B(N,0); for (i=0,j=N-1; i=0 ;i++, j–) { L[i] = i==0? 1 : A[i-1] * L[i-1]; R[j] = j==N-1? 1 : R[j+1] * A[j+1]; } for (i=0; i { B[i] = L[i] * R[i]; printf(“%d “,B[i]); } } Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of i-th term. then finally we multiply it to get the result.

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)

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.

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!

Q: What should I expect from a phone interview with Google? I have a phone interview which I never done this kind of interview by phone. What should I expect? Learn? Prepare? Any tip may help. A: First of all, congratulations on having the opportunity to work at a top company... You must have very attractive credentials on paper.  I believe you live in Austria.  I think Google is headquartered in Mountain View, CA with offices all over the world. There are a couple reasons well run corporations conduct telephone interviews. It provides them with a cost-effective way to screen you, without having to pay to fly you to Milan, Zürich, or the US for an in person interview. It offers the HR function the opportunity to gather basic information about you and do a high level corporate fit test. Be sure you are fluent in your strengths and "weaknesses". Make yourself focused about where you want to be in 5 years...whether you are or not. Think of the 2-3 top things that you bring to the table.  Be sure they come out in the Q&A somehow.  And, prepare 3-5 good questions you want answered by them.  You may only get time to ask one. Make it a good one. If you pass this first screen, you will be interviewed by someone in the area/function in which you would be working.  These interviews can sometimes also be done by telephone, especially if the candidate who looks attractive on paper lives far away. Eventually, you will be brought in for face to face meetings, possibly supplemented by videoconference interviews. I don’t know the type of job you are interviewing for--business? engineering? staff? etc.?  But, Google has a reputation for hiring the best and the brightest.  On the phone, they have the ability to evaluate how well you communicate and how you think.  Depending upon how important the latter is, they have the ability to give you "brainteasers" or cases to solve.  Typically, solving the problem is secondary to seeing how you structure your solutions and go about problem solving. Don’t be nervous. It will help you to prepare for the interview.  Show that you have done your research into the company and in particular into the division in which you are hoping to work.  Do what you can to find out specifics about Google’s recruiting process from other Google candidates who have gone through it successfully.  Perhaps there are alumni from your university employed there.  Speak to them. Hals und Beinbruch! (not literally, of course...) Viel Glück! Sources: decades of interviewing experience on both sides of the desk Q: What is the protocol after a phone interview? Do I write a thank you note/email? I know that after a regular job interview, one should write a thank you note. Should a thank you note be written after a phone interview? Also, is it acceptable to send an email thank you note if you do not have the person's work...... A: Definately Speaking from Human Resources experience, something as small as a thank you will make a huge impression.  It's not much effort on your part, and it will help solidify a phone conversation in the minds of the interviewers and company. I myself would never do a formal letter after a phone interview or phone screen, but e-mail is perfect.  Also, keep it short and sweet.  Thank them for the opportunity, not the interview (this keeps it positive).  If by some chance you can put a quick sentance in that personalizes the thank you, do it . If you spoke with the interviewer about something non-interview related, making a light, one sentance comment about it is fine.  Something you would say to your grandmother or pastor/priest/reverend will be the test on appropriateness. EXAMPLE: Mr. Smith -   Thank you for the phone conversation and the opportunity, and looking forward to the next step of the process.  Hope that your Cubs make it past this weekend!   Regards,   Employee X   One last thing:  Stay away from animated e-mails, backgrounds, and use a general font (Arial, Times New Roman, Helvetica, etc.)  Q: Do you care about A ‘Dream’ Come True?: US Approves The First Google Phone! A ‘Dream’ Come True: US Approves The First Google Phone New York Times, United States - Aug 18, 2008 The new phone is an important step in Google’s plans to expand the company’s presence beyond the personal computer and into the mobile...... A: Google seems to be a company that is determined in dominating the technology market. I don't care about their phone, but I can imagine it giving a run for its money to Blackberry and iPhone.

Free cafeteria food, annual ski trips to the Sierras and free laundry are just some of the fringe benefits of working at Google. Getting hired is the trick. Every month, aspiring workers deluge the popular Mountain View, Calif., search engine with up to 150,000 resumes -- equivalent to a stack of paper at least 50 feet high. And the company claims to read each and every one. As one of Silicon Valley's hottest companies, Google has become a beacon for job seekers. In just a few short years, the interest has helped the company amass an arsenal of what is arguably among the world's top technology minds. "I would argue that definitely they have the best talent," said Joe Kraus, a co-founder of the Web portal Excite Inc. who currently leads a start-up, JotSpot, in Palo Alto, Calif. "They invest so much because the more great talent you have, the easier it is to attract even more great talent." Google hires nine new workers a day. In less than two years, the number of employees has more than tripled to 4,989. The growth spurt is being fueled by a gangbusters-like online advertising market and Google's boundless ambition, including new initiatives in everything from wireless Internet access to video downloads. The goal is to keep the production line of new products humming so that users spend more time on the Web site. Getting rich is what drives some of the applicants. Many Google workers became instant millionaires at the time of the company's initial stock offering in 2004. To this day, prospective employees are drawn by the promise of wealth, although their chances of striking gold are a lot lower now that the firm's shares are soaring above $400, making stock options less likely to appreciate by large amounts. Competition for the best and brightest is fierce. Rivals Microsoft Corp. and Yahoo! Inc., plus start-ups, are trying to reel in many of the same job applicants, igniting occasional bidding wars. Hiring is a major challenge Yahoo!, in particular, has recently landed some workers who interviewed at Google, such as Andrei Broder, a former research executive at AltaVista and IBM. He says being at Yahoo!'s research lab is an opportunity to have more impact because it's younger and smaller than those of its competition. Sergey Brin, Google's co-founder, has called hiring one of his firm's biggest challenges. If it's unable to find enough top-notch workers, he says the company's rapid growth could be hamstrung. Google's also hiring superstars. This year, they include Vint Cerf, one of the Internet's founding fathers, as chief Internet evangelist. Kai-Fu Lee, a former Microsoft executive and expert in technology that turns speech into text, now heads operations in China. And Louis Monier, founder of the early search engine AltaVista, has an undisclosed technical role. To lure workers, Google offers perks, including free cafeteria meals, free use of laundry machines, a child-care center, a free annual one-night ski trip (resort destinations vary depending on office location), dog-friendly offices and an on-site doctor. Engineers can devote 20 percent of their time to projects of their choice. What's not mentioned is that much of the largesse is designed to keep workers at their desks longer. In addition to posting job openings in newspapers and online, Google recruits at universities, offers computer science students free pizza, hosts a software programming competition and invites technology clubs to hold their meetings at its headquarters. Last year, the company won attention for publishing a booklet of 21 problems called the Google Labs Aptitude Test. Readers of several technology magazines were asked to mail in their answers and promised that Google would get in touch with them if they scored well. One question asked: "In your opinion, what is the most beautiful math equation ever derived?" The Gaussian integral, a complex mathematical equation used in studying the kinetic molecular theory of gases, among other things, has been suggested as a smart answer by some on the Internet. Another question involved filling a blank rectangle "with something that improves upon emptiness," leaving applicants scratching for a subjective winner. Judy Gilbert, Google's staffing programs director, says the questions weren't really used for hiring. In any case, smart alecks soon posted the answers online so they could be easily found by cheaters. Hundreds of recruiters keep the resumes pouring into Google. Many are contractors, making them easier to dismiss if the company scales back its hiring needs. Jobs available as of last week include someone to negotiate video licensing deals with Hollywood studios, someone to lead user studies for guiding product design and an attorney to manage the firm's real estate. More posts are likely to open in announcements this week, as the company is creating 600 new jobs in Ireland and up to 100 in Pittsburgh. To land all-stars, Google's recruiting machine goes into overdrive. Secrecy is sometimes critical. If tipped off, companies from which Google is trying to poach could start a bidding war or retaliate against a potential defector. The risk can be worth it for a top executive of Lee's caliber. He ultimately accepted a compensation package of more than $10 million, igniting the legal battle between Google and Microsoft. To fill positions lower on the pecking order, Google has created an extensive college-hiring program, among other efforts. Recruiters visited 60 schools this year to show off the firm's technology, hand out T-shirts and interview prospective job candidates. Interviews at Google usually begin on the telephone. If successful, applicants are invited for face-to-face meetings with up to 10 people, a process described as excruciating by people who have gone through them because of the length of time it takes and the mental gymnastics necessary. Recent job candidates described questions as being on topic, whether about software code or business. In many cases, they were asked to brainstorm and role-play to show how they think. For instance, how would they market a product? Those who conduct the interviews frequently challenge applicants. Questions about algorithms, Java software and computer networking are common for applicants seeking technical positions. Google has created its own software system for tracking job candidates that allows employees to share comments on each applicant. Because so many people must sign off on new hires -- Larry Page, one of the firm's famed co-founders, approves each one -- the process can be lengthy, even excessively so, several applicants said. Some were shocked to learn the importance Google gives to college grade-point averages in deciding whom to hire. The emphasis draws complaints from some older candidates, who believe the measure is irrelevant for them because they have been out of school for so long. In general, Gilbert says Google seeks applicants who show they are willing to take risks, are highly motivated by a range of topics and want to be part of something bigger than themselves. The profile is in line with the firm's carefully crafted iconoclastic image. Historically, Google has paid workers less than the industry standard and showered them with stock options. That paid off for approximately 1,000 Google employees in 2004, when the company's high-profile initial stock offering made them instant millionaires. Although the firm's current pay structure is a closely guarded secret, one can assume hundreds, if not thousands, more have become worth seven figures, at least on paper, considering that Google's stock is now hovering above the $400 mark, a nearly fivefold increase from its premiere. After its initial public offering last year, the company has had to offer more money upfront because options aren't as valuable, compensation experts say. Many competing firms claim Google has driven up salaries for software programmers by nearly 50 percent in recent years. According to one source who wanted to remain anonymous, the beginning salary for programmers is now about $45,000. How accurate this is cannot be known, but at least it's a clue. BENEFITS GOOGLE TEST QUESTIONS A test published by Google last year in several magazines was used as a recruiting tool. Questions included: 1) Solve this cryptic equation, realizing of course that value for M and E could be interchanged. No leading zeros are allowed: WWWDOT -- GOOGLE DOTCOM Answers: 777589 -- 188106 589483 or 777589 -- 188103 589486 2) How many different ways can you color an icosahedron with one of three colors on each face? Answer: 58,130,055 3) Which of the following expresses Google's overarching philosophy? a) I'm feeling lucky b) Don't be evil c) Oh, I already fixed that d) You should never be more than 50 feet from food e) All of the above Answer: b   -- San Francisco Chronicle BENEFITS Workers at Google get a range of benefits that surpass those at many other companies. Here's a sample: Free cafeteria meals   On-site dry cleaning   Coin-free laundry room   Free annual ski trip   Dog-friendly offices   On-site doctor and dentist   Free commuter shuttle service to several Bay Area locations   Source: Google Inc.

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

We are providing solutions to the Crazy Questions at Google Job Interview post By Thiomir How many golf balls can fit in a school bus? Solution: The point of the question isn't to see how golf balls you think are in the bus, but to see what your deduction skills are like. Do you just make a random guess or try to cop out by saying a lot, or do you actually try to come up with a legitimate answer by going through a logical series of steps. 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? Solution:You simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people. How much should you charge to wash all the windows in Seattle? Solution:As crazy as it might sound, questions like these demonstrate your ability to think through a complex problem with little or no information. They expect you to take an educated guess. Most of the time you can ask them questions like - how many buildings are there in Seattle. How would you find out if a machine’s stack grows up or down in memory? Solution:Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0. Explain a database in three sentences to your eight-year-old nephew. Solution:A database is like a file cabinet. The files, or data, is stored in it and can be arranged in categories. But unlike an actual file cabinet, you can do a lot more cool stuff with a database like being able to make it accessible through the internet. How many times a day does a clock’s hands overlap? Solution:The Hour hand and Minute hand would be meeting exactly 11 times in 12 hours (Hour hand would have taken 1 clockwise round and Minute hand would have taken 12 clockwise rounds, so 12 - 1 = 11 rounds). result: First time hour and minute hands overlap will be 12 Hours / 11 = 01:05:27.27. So at this time only hour and minute hands would be overlapping and second hand will not be any near to them. Similarly for 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th and 10th overlap of hour and minute hand the Second hand wont be any nearby. So all 3 hands (hour, minute and Second) overlap only 2 times i.e. (0:0:0 and 12:0:0). Also we all know when we get our watches repaired, normally the repairman overlaps all the three hands to 12. If we are considering that the second hand is not present, then the rest two overlaps 22 times in 24 hours. There again is a catch, if we check the angles by which the hour hand and minute hand moves. The second hand moves 6 degree in a second. In that time the minute hand will move 6/60 degrees. and the hour hand will move 6/(60*12) degrees. now taking these things in the considerations. if we check the positions of the hour and minute hand in terms of angle from the marker 12, for our first rendezvous time, i.e. 01:05:27.27 sec. first thing that comes to my mind is that, there is fraction in the seconds. So that time can’t be measured. there will be no exact overlap. now lets calculate the angles: 1 hour 5 mins and 27 seconds = 3600 + 5*60 + 27 = 3927 seconds. angle of hour hand = 3927 * 6/(60*12) = 32.725 degree. angle of minute hand = 3927 * 6/60 = 392.7 degree subtracting 360 degree from it we get - 32.7 degree. So at 01:05:27 both hands don’t overlap. Now for 01:05:28 : Angles : hour hand - 32.73333 minute hand - 32.8 so obviously they dont meet at 01:05:28 either. So they overlap at 12:00 and 24:00 only. So the answer is 2 only. You have to get from point A to point B. You don’t know if you can get there. What would you do? Solution:Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther. Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed. During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements. This is the best chance you have reaching point B if you don’t know if you can get there. 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? Solution:Let’s suppose there are a set of attributes of each shirt you are interested in: e.g. sleeve length, color, buttons (no buttons, fully button, partially buttoned from collar to chest level). Let’s say the closet is a simple wall closet with a single closet rod running the entire length of closet. On the left you put all the short sleeve shirts, and on the right the long sleeve shorts. You separate then long and short sleeve sides with a specially marked coat hanger. Then you separate each group into no buttonoed, partially buttoned, and fully button, using more specially marked hangers. Then each sub group is separated into colored and monochrome sub-sub-groups (specially marked hangers aren’t needed for separators unless you are color blind) Then each colored group is sorted left to right according to the color spectrum: ROYGBIV: red, orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is sorted left to right: white on the left, black on the right, and shades of grey in the middle, the darker greys on the right, the lighter on the left. 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? Solution:1. There is only one cheat husband - If it is so then 99 wives knew it before. So the cheated wife got the idea from queen that her husband is cheating. So she will kill him. Next morning every wife will know there is no cheat husbands anymore. 2. There are more than one cheat husbands - In this case, all of the wives already had the idea prior to queen's information. Its just that the cheated wives knew the count which is one less than what the non-cheated wives' knew - thats all. i.e. if there were 2 cheat husbands then their wives knew the count is 1 and others knew its 2. So the queen just repeated the info saying "at least 1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife kills her husband. 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? Solution:From pure probability,we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1 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)? Solution:If the chance to see the car is 10 percent per minute, the first minute you have 10% chance, the second minute you have 10% of 90% = 9% (so total 19%), the third minute 10% of 81% (= 8,1%, total 27,1 %) ...... As the chance for 30 minutes is 95 percent, the chance for 1 minute is 9.5% and for 10 minute 63.1 %. 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!) Solution:7.5 degrees (the hour hand is 1/4th of the way between 3 and 4, the angle measure of that is 360/12 = 30 degrees between hours / 4 = 7.5 degrees). 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? Solution:1 and 2 cross, taking 2 minutes, 1 goes back carrying the flashlight total=3 minutes. 5 and 10 cross, taking 10 minutes totaltime now= 13 minutes, 2 goes back,total time now = 15 minutes. 1 and 2 cross again, taking 2 minutes making it 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? Solution:No. How many piano tuners are there in the entire world? Solution:1) At first list out all the piano manufacturing companies in the world. 2) Then look into their purchase records and find out the piano purchasers information. 3) i) If the purchase is made by an individual or a house hold then the piano is played at best case by all the people of the house. ii) Else if the piano is purchased for school then list out the students that opted the piano course in their music curriculum. iii) If the piano is purchased by a Church then count the no of major or minor events of the church and count the piano users. sum up all the numbers to get more or less accurate piano users count. 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? Solution:choose 6 balls and weigh 3 against 3 - if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one - if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them: - if they weigh the same, the remaining ball is the heavier one; otherwise you just found the heavier one by weighing the 2 chosen balls. 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.) Solution:The highest ranked pirate gets 98 gold coins ---Two pirates get 1 gold coin each ---The other 2 pirates get nothing.

Total there are five Technical Interviews followed by Management round. So here are the questions. Google Interview Round 1: What is the Space complexity of quick sort algorithm? how do find it? Solution: Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that * in-place partitioning is used. This requires O(1). * After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration. The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space. However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space. What are dangling pointers? Solution: A dangling pointer is a pointer to storage that is no longer allocated. Dangling pointers are nasty bugs because they seldom crash the program until long after they have been created, which makes them hard to find. Programs that create dangling pointers often appear to work on small inputs, but are likely to fail on large or complex inputs. Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step. Solution:The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence. Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance. You are given biased coin. Find unbiased decision out of it? Solution:Throw the biased coin twice.Classify it as true for HT and false for TH.Both of these occur with probability=p*(1-p),hence unbiased. Ignore the other 2 events namely HH and TT. On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps Google Interview Round 2: You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them. Solution: The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array. Sum of first N natural numbers=N*(N+1)/2 and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !! Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y. We solve this problem by solving 2 essential equations. They are X+Y=N*(N+1)/2 -S---------->(1) X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries. You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place. Solution: The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution. Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2. Questions on my project please be prepare well about your project How do you search for a word in a large database. How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'. Google Interview Round 3: You have given an array. Find the maximum and minimum numbers in less number of comparisons. Solution: only 3n/2 comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements. You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n). Solution:All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent. Google Interview Round 4 : Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B. Ex: A="abcd" B="xyz" C="axybczd". answer is yes. Solution: bool test(A,B,C) { i=j=k=0; while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); } The above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing one in to a dilemma whether to accept the character from A or B. Given two sorted arrays A and B. Find the intersection of these arrays A and B. Solution:The intersection can be found by using a variation of merge routine of the merge sort. If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays? Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence. Google Interview Round 5: If you get into Google, which products are you going to work on? What is TCP, UDP. what is reliability, unreliability, give examples of these? Solution: Click Here To Read About TCP Click Here To Read About UDP Click Here To Read About Reliability What is http protocol? Solution: Click Here To Read About HTTP How does Google search engine works? What is indexing, what is the input and output to it. how Google does that? This was the interview i got from one of my friends.

The Google Interview has some strange questions on it. Here are my answers: 1. How many golf balls can fit in a school bus? 1 trillion (then I draw a Dr. Evil Picture) 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? Plead to be taken back out. 3. How much should you charge to wash all the windows in Seattle? As much as possible. 4. How would you find out if a machine’s stack grows up or down in memory? Ask someone. 5. Explain a database in three sentences to your eight-year-old nephew. Hey. Kid. Google it. 6. How many times a day does a clock’s hands overlap? 24 7. You have to get from point A to point B. You don’t know if you can get there. What would you do? Try. 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? Tell my wife or a maid to do it. 9. 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? They kill the queen - she’s the messenger (they always kill the messenger). 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? ~1:1 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)? About 63% via .95 =(n+n*(1-n))+n(1-(n+n*(1-n))) (actually, I think it has to do with logs and that’s slightly off). 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!) 360/12/4 degrees. 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? 1 goes with 2 = 2 mins 1 returns with the flashlight = 1 min 5 goes with 10 = 10 mins 2 returns = 2 mins 1 + 2 go = 2 mins but really, how the fuck would they know the flashlight has 17 minutes left on it? 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? Maybe . . . but only if i was really shitfaced. 15. How many piano tuners are there in the entire world? What do you mean, an African or European Swallow? 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? weigh balls 1, 2, 3 (set 1) against 4 against 4 and 5 and 6 (set 2) - if not equal, take the heavier set and weigh 1 v 2 (or 4 v 5 if set 2 was heavier) - if not equal the heavier ball is the it - if equal it is the odd ball is heaviest. - if set 1 and 2 are equal weight 7 v 8 and the heavier is the heaviest. 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 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.) Wrong shitbag. You tell a pirate he’s gonna get 1 gold piece out of 100 and he’s gonna vote to kill you. You can reason with him all you want, but he’s gonna vote to fucking kill you. It’s not game theory, it’s human emotions and common sense. 20/20/20/20/20 or something close to it. Hint: They’re fucking Pirates, not Game theory doctorates. If anyone get’s fucked they’re gonna vote to kill the others. I’d vote to kill you if you if you gave me only 1 piece. ARRRRRRGGGGG!

Some time back I interviewed with Google, and a number of other well known software development companies. I've written up a number of questions very similar to the ones I was asked, changing them enough so that I'm not breaking my NDA. Q: Why are manhole covers round? Q: A man pushed his car to a hotel and lost his fortune. What happened? Q: Explain the significance of "dead beef". Q: Write a C program which measures the the speed of a context switch on a UNIX/Linux system. Q: 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. Q: Describe the algorithm for a depth-first graph traversal. Q: Design a class library for writing card games. Q: 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? Q: How are cookies passed in the HTTP protocol? Q: What is the size of the C structure below on a 32-bit system? On a 64-bit? struct foo { char a; char* b; }; Q: Design the SQL database tables for a car rental database. Q: Write a regular expression which matches a email address. Q: 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. Q: 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? Q: Explain how congestion control works in the TCP protocol. Here's one that someone sent me in email. I've outlined a possible solution, but I haven't thought through the problem very well. Here's the question: Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. You are given: 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. There are approx. 8 billion search terms per log file (320 GIG / 40 Bytes). Each computer can return it's top 1 million search terms to a central server at a cost of 48MB each because 40 Bytes * 1 million = 40MB, plus a 8 byte unsigned integer occurrence count for each search term. The combined top 1 million results from each log take only 520 MB, so there is plenty of space on any single computer to merge the 12 million entries together and come up with top 1 million. So, the only missing part at this point is how to efficiently count the search term occurrences on each computer, and return the top 1 million (this same algorithm can be used for merging the 12 top 1 million, too). A hash table may be a bad idea. With this many search terms and only 4GIG of memory, hashing the search terms would cause a lot of collisions. You want to use a tree, not a hash. Order ln(n) should work well for the search term lookups (if it's good enough for the STL maps, it's good enough for me, right??!!). Now, we know that we need to produce the top 1 million results, but there are potentially 8 Billion unique search terms per log, and a minimum of 1 unique search term per log (what are the chances you get 8 billion searches for 'porn' or 'sex' on a single log? Not much, but it is a formal possibility. At the very least, such a case would make a great unit test for your program), either way, you could blow a 32 bit unsigned int trying to count them... So, we do have to use unsigned longs. That increases the size of the search term count to a long-int, 8 bytes instead of 4. With 4 gigs of memory, how many log entries can be counted at a time? 1 unique term will take 40 bytes, + 8 bytes for the count, two pointers for the left/right nodes of the binary tree (+ 8 bytes or + 16 bytes on a 64 bit system). Let's only assume you can use 3.5GIG of the 4GIG of memory, so that's 3.5/64 = 0.0546 GIG, or about 54 million. So, here's the stratagy: 1) go through the log, and count the occurances of search terms found using a binary tree for search term lookups, and a long-int for the counter. Do this unil you have 54 million unique terms in your tree. Write a marker into the log file for each search term used so that further passes know it has been counted. 2) transmit the tree over the network to the next computer and count only the search term occurances which are already in the tree, marking any counted in the logs as such; then transmit the tree to the next and repeat this process until the tree has passed through each computer and ends up at the computer WHERE THE FIRST UNQIUE SEARCH TERM WAS ADDED TO THE TREE(more on this in the next step). Heap-sort the tree by search term occurance number (why not, it's already in a binary tree -- that's great for heap-sort!). Truncate the tree to 1 million search terms, and write it to disk. 3) Every time a tree of unique search terms has "filled up", that is, the tree contains 54 million unique search terms, a new unique-search term tree must be built and sent to each computer so that the terms can be counted. A tree might begin near the end of a log on one computer, and be sent to the next computer with less than the 54 million unique search terms. When this is the case, the tree will continue to collect unique search terms from the log on the next computer. There are two processess occuring in this algorithm which travel in rings around the computer network until they reach the computer at which they began. The first process travels from computer to computer generating these unqiue search term trees (call this process #1). Once a tree fills up with unique terms, it breaks off from this process and is sent around the ring to count the search term occurances for terms which it already contains (call these processes Tn, there can be many). Once process #1 reaches the computer where it started, it quits. Once all the Tn processes have traveled the ring, they quit also after writing their top 1 million search results to disk in sorted order. The search terms in these files are all unique and accurately counted. Just start popping search terms off the top of these logs by the highest occurance count until you have 1 million search terms. That should be it.

1. Reverse a singly linked list // // iterative version // Node* ReverseList( Node ** List ) { Node *temp1 = *List; Node * temp2 = NULL; Node * temp3 = NULL; while ( temp1 ) { *List = temp1; //set the head to last node temp2= temp1->pNext; // save the next ptr in temp2 temp1->pNext = temp3; // change next to privous temp3 = temp1; temp1 = temp2; } return *List; } 2. Delete a node in double linked list void deleteNode(node *n) { node *np = n->prev; node *nn = n->next; np->next = n->next; nn->prev = n->prev; delete n; } 3. Sort a linked list //sorting in descending order struct node { int value; node* NEXT; } //Assume HEAD pointer denotes the first element in the //linked list // only change the values…don’t have to change the //pointers Sort( Node *Head) { node* first,second,temp; first= Head; while(first!=null) { second=first->NEXT; while(second!=null) { if(first->value < second->value) { temp = new node(); temp->value=first->value; first->value=second->value; second->value=temp->value; delete temp; } second=second->NEXT; } first=first->NEXT; } } 4. Reverse a string void ReverseString (char *String) { char *Begin = String; char *End = String + strlen(String) - 1; char TempChar = '\0'; while (Begin < End) { TempChar = *Begin; *Begin = *End; *End = TempChar; Begin++; End--; } } 5. Insert a node a sorted linked list void sortedInsert(Node * head, Node* newNode) { Node *current = head; // traverse the list until you find item bigger the // new node value // while (current!= NULL && current->data < newNode->data) { current = current->next); } // // insert the new node before the big item // newNode->next = current->next; current = newNode; } 6. Covert a string to upper case void ToUpper(char * S) { while (*S!=0) { *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S; S++; } } 7. Multiple a number by 7 without using * and + operator. NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8 NewNum = NewNum - Num; // 8 – 1 = 7 8. Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value. #include int strtoint(char *s) { int index = 0, flag = 0; while( *(s+index) != '\0') { if( (*(s + index) >= '0') && *(s + index) <= '9') { flag = 1; index++; } else { flag = 0; break; } } if( flag == 1 ) return atoi(s); else return 0; } main() { printf("%d",strtoint("0123")); printf("\n%d",strtoint("0123ii")); } 9. Print a data from a binary tree – In-order(ascending) // // recursive version // Void PrintTree ( struct * node node ) { if ( node == NULL ) return; PrintTree(node->left ); Printf(“%d”, node->data); PrintTree(node->right ); } 10. print integer using only putchar // // recursive version // void PrintNum ( int Num ) { if ( Num == 0 ) return; PrintNum ( Num / 10 ); Puthcar ( ‘0’+ Num % 10 ); } 11. Find the factorial of number // // recursive version // int Factorial( int Num ) { If ( num > 0 ) return Num * Factorial ( Num –1 ); else return 1; } // // iterative version // int Factorial( int Num ) { int I int result = 1; for ( I= Num; I > 0; I-- ) { result = result * I; } return result; } 12. Generate Fib numbers: int fib( n ) // recursive version { if ( n < 2 ) return 1; else return fib ( n –1 ) + fib ( n –2 ); } int fib( n ) //iterative version { int f1 =1, f2 = 1; if ( n < 2 ) return 1; for ( i = 1; i < N; i++) { f = f1 + f2; f1= f2; f = f1; } return f; } 13. Write a function that finds the last instance of a character in a string char *lastchar(char *String, char ch) { char *pStr = NULL; // traverse the entire string while( * String ++ != NULL ) { if( *String == ch ) pStr = String; } return pStr; } 14. Return Nth the node from the end of the linked list in one pass. Node * GetNthNode ( Node* Head , int NthNode ) { Node * pNthNode = NULL; Node * pTempNode = NULL; int nCurrentElement = 0; for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext ) { nCurrentElement++; if ( nCurrentElement - NthNode == 0 ) { pNthNode = Head; } else if ( nCurrentElement - NthNode > 0) { pNthNode = pNthNode ->pNext; } } if (pNthNode ) { return pNthNode; } else return NULL; } 15. Counting set bits in a number. First version: int CoutSetBits(int Num) { for(int count=0; Num; Num >>= 1) { if (Num & 1) count++; } return count; } Optimized version: int CoutSetBits(int Num) { for(int count =0; Num; count++) { Num &= Num -1; } }

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