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

I've been meaning to write up some tips on interviewing at Google for a good long time now. I keep putting it off, though, because it's going to make you mad. Probably. For some statistical definition of "you", it's very likely to upset you. Why? Because... well, here, I wrote a little ditty about it: Hey man, I don't know that stuff Stevey's talking aboooooout If my boss thinks it's important I'm gonna get fiiiiiiiiiired Oooh yeah baaaby baaaay-beeeeee.... I didn't realize this was such a typical reaction back when I first started writing about interviewing, way back at other companies. Boy-o-howdy did I find out in a hurry. See, it goes like this: Me: blah blah blah, I like asking question X in interviews, blah blah blah... You: Question X? Oh man, I haven't heard about X since college! I've never needed it for my job! He asks that in interviews? But that means someone out there thinks it's important to know, and, and... I don't know it! If they detect my ignorance, not only will I be summarily fired for incompetence without so much as a thank-you, I will also be unemployable by people who ask question X! If people listen to Stevey, that will be everyone! I will become homeless and destitute! For not knowing something I've never needed before! This is horrible! I would attack X itself, except that I do not want to pick up a book and figure enough out about it to discredit it. Clearly I must yell a lot about how stupid Stevey is so that nobody will listen to him! Me: So in conclusion, blah blah... huh? Did you say "fired"? "Destitute?" What are you talking about? You: Aaaaaaauuuggh!!! *stab* *stab* *stab* Me: That's it. I'm never talking about interviewing again. It doesn't matter what X is, either. It's arbitrary. I could say: "I really enjoy asking the candidate (their name) in interviews", and people would still freak out, on account of insecurity about either interviewing in general or their knowledge of their own name, hopefully the former. But THEN, time passes, and interview candidates come and go, and we always wind up saying: "Gosh, we sure wish that obviously smart person had prepared a little better for his or her interviews. Is there any way we can help future candidates out with some tips?" And then nobody actually does anything, because we're all afraid of getting stabbed violently by People Who Don't Know X. I considered giving out a set of tips in which I actually use variable names like X, rather than real subjects, but decided that in the resultant vacuum, everyone would get upset. Otherwise that approach seemed pretty good, as long as I published under a pseudonym. In the end, people really need the tips, regardless of how many feelings get hurt along the way. So rather than skirt around the issues, I'm going to give you a few mandatory substitutions for X along with a fair amount of general interview-prep information. Caveats and Disclaimers This blog is not endorsed by Google. Google doesn't know I'm publishing these tips. It's just between you and me, OK? Don't tell them I prepped you. Just go kick ass on your interviews and we'll be square. I'm only talking about general software engineering positions, and interviews for those positions. These tips are actually generic; there's nothing specific to Google vs. any other software company. I could have been writing these tips about my first software job 20 years ago. That implies that these tips are also timeless, at least for the span of our careers. These tips obviously won't get you a job on their own. My hope is that by following them you will perform your very best during the interviews. Oh, and um, why Google? Oho! Why Google, you ask? Well let's just have that dialog right up front, shall we? You: Should I work at Google? Is it all they say it is, and more? Will I be serenely happy there? Should I apply immediately? Me: Yes. You: To which ques... wait, what do you mean by "Yes?" I didn't even say who I am! Me: Dude, the answer is Yes. (You may be a woman, but I'm still calling you Dude.) You: But... but... I am paralyzed by inertia! And I feel a certain comfort level at my current company, or at least I have become relatively inured to the discomfort. I know people here and nobody at Google! I would have to learn Google's build system and technology and stuff! I have no credibility, no reputation there – I would have to start over virtually from scratch! I waited too long, there's no upside! I'm afraaaaaaid! Me: DUDE. The answer is Yes already, OK? It's an invariant. Everyone else who came to Google was in the exact same position as you are, modulo a handful of famous people with beards that put Gandalf's to shame, but they're a very tiny minority. Everyone who applied had the same reasons for not applying as you do. And everyone here says: "GOSH, I SURE AM HAPPY I CAME HERE!" So just apply already. But prep first. You: But what if I get a mistrial? I might be smart and qualified, but for some random reason I may do poorly in the interviews and not get an offer! That would be a huge blow to my ego! I would rather pass up the opportunity altogether than have a chance of failure! Me: Yeah, that's at least partly true. Heck, I kinda didn't make it in on my first attempt, but I begged like a street dog until they gave me a second round of interviews. I caught them in a weak moment. And the second time around, I prepared, and did much better. The thing is, Google has a well-known false negative rate, which means we sometimes turn away qualified people, because that's considered better than sometimes hiring unqualified people. This is actually an industry-wide thing, but the dial gets turned differently at different companies. At Google the false-negative rate is pretty high. I don't know what it is, but I do know a lot of smart, qualified people who've not made it through our interviews. It's a bummer. But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all! As far as anyone I know can tell, false negatives are completely random, and are unrelated to your skills or qualifications. They can happen from a variety of factors, including but not limited to: you're having an off day one or more of your interviewers is having an off day there were communication issues invisible to you and/or one or more of the interviewers you got unlucky and got an Interview Anti-Loop Oh no, not the Interview Anti-Loop! Yes, I'm afraid you have to worry about this. What is it, you ask? Well, back when I was at Amazon, we did (and they undoubtedly still do) a LOT of soul-searching about this exact problem. We eventually concluded that every single employee E at Amazon has at least one "Interview Anti-Loop": a set of other employees S who would not hire E. The root cause is important for you to understand when you're going into interviews, so I'll tell you a little about what I've found over the years. First, you can't tell interviewers what's important. Not at any company. Not unless they're specifically asking you for advice. You have a very narrow window of perhaps one year after an engineer graduates from college to inculcate them in the art of interviewing, after which the window closes and they believe they are a "good interviewer" and they don't need to change their questions, their question styles, their interviewing style, or their feedback style, ever again. It's a problem. But I've had my hand bitten enough times that I just don't try anymore. Second problem: every "experienced" interviewer has a set of pet subjects and possibly specific questions that he or she feels is an accurate gauge of a candidate's abilities. The question sets for any two interviewers can be widely different and even entirely non-overlapping. A classic example found everywhere is: Interviewer A always asks about C++ trivia, filesystems, network protocols and discrete math. Interviewer B always asks about Java trivia, design patterns, unit testing, web frameworks, and software project management. For any given candidate with both A and B on the interview loop, A and B are likely to give very different votes. A and B would probably not even hire each other, given a chance, but they both happened to go through interviewer C, who asked them both about data structures, unix utilities, and processes versus threads, and A and B both happened to squeak by. That's almost always what happens when you get an offer from a tech company. You just happened to squeak by. Because of the inherently flawed nature of the interviewing process, it's highly likely that someone on the loop will be unimpressed with you, even if you are Alan Turing. Especially if you're Alan Turing, in fact, since it means you obviously don't know C++. The bottom line is, if you go to an interview at any software company, you should plan for the contingency that you might get genuinely unlucky, and wind up with one or more people from your Interview Anti-Loop on your interview loop. If this happens, you will struggle, then be told that you were not a fit at this time, and then you will feel bad. Just as long as you don't feel meta-bad, everything is OK. You should feel good that you feel bad after this happens, because hey, it means you're human. And then you should wait 6-12 months and re-apply. That's pretty much the best solution we (or anyone else I know of) could come up with for the false-negative problem. We wipe the slate clean and start over again. There are lots of people here who got in on their second or third attempt, and they're kicking butt. You can too. OK, I feel better about potentially not getting hired Good! So let's get on to those tips, then. If you've been following along very closely, you'll have realized that I'm interviewer D. Meaning that my personal set of pet questions and topics is just my own, and it's no better or worse than anyone else's. So I can't tell you what it is, no matter how much I'd like to, because I'll offend interviewers A through X who have slightly different working sets. Instead, I want to prep you for some general topics that I believe are shared by the majority of tech interviewers at Google-like companies. Roughly speaking, this means the company builds a lot of their own software and does a lot of distributed computing. There are other tech-company footprints, the opposite end of the spectrum being companies that outsource everything to consultants and try to use as much third-party software as possible. My tips will be useful only to the extent that the company resembles Google. So you might as well make it Google, eh? First, let's talk about non-technical prep. The Warm-Up Nobody goes into a boxing match cold. Lesson: you should bring your boxing gloves to the interview. No, wait, sorry, I mean: warm up beforehand! How do you warm up? Basically there is short-term and long-term warming up, and you should do both. Long-term warming up means: study and practice for a week or two before the interview. You want your mind to be in the general "mode" of problem solving on whiteboards. If you can do it on a whiteboard, every other medium (laptop, shared network document, whatever) is a cakewalk. So plan for the whiteboard. Short-term warming up means: get lots of rest the night before, and then do intense, fast-paced warm-ups the morning of the interview. The two best long-term warm-ups I know of are: 1) Study a data-structures and algorithms book. Why? Because it is the most likely to help you beef up on problem identification. Many interviewers are happy when you understand the broad class of question they're asking without explanation. For instance, if they ask you about coloring U.S. states in different colors, you get major bonus points if you recognize it as a graph-coloring problem, even if you don't actually remember exactly how graph-coloring works. And if you do remember how it works, then you can probably whip through the answer pretty quickly. So your best bet, interview-prep wise, is to practice the art of recognizing that certain problem classes are best solved with certain algorithms and data structures. My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types. Other interviewers I know recommend Introduction to Algorithms. It's a true classic and an invaluable resource, but it will probably take you more than 2 weeks to get through it. But if you want to come into your interviews prepped, then consider deferring your application until you've made your way through that book. 2) Have a friend interview you. The friend should ask you a random interview question, and you should go write it on the board. You should keep going until it is complete, no matter how tired or lazy you feel. Do this as much as you can possibly tolerate. I didn't do these two types of preparation before my first Google interview, and I was absolutely shocked at how bad at whiteboard coding I had become since I had last interviewed seven years prior. It's hard! And I also had forgotten a bunch of algorithms and data structures that I used to know, or at least had heard of. Going through these exercises for a week prepped me mightily for my second round of Google interviews, and I did way, way better. It made all the difference. As for short-term preparation, all you can really do is make sure you are as alert and warmed up as possible. Don't go in cold. Solve a few problems and read through your study books. Drink some coffee: it actually helps you think faster, believe it or not. Make sure you spend at least an hour practicing immediately before you walk into the interview. Treat it like a sports game or a music recital, or heck, an exam: if you go in warmed up you'll give your best performance. Mental Prep So! You're a hotshot programmer with a long list of accomplishments. Time to forget about all that and focus on interview survival. You should go in humble, open-minded, and focused. If you come across as arrogant, then people will question whether they want to work with you. The best way to appear arrogant is to question the validity of the interviewer's question – it really ticks them off, as I pointed out earlier on. Remember how I said you can't tell an interviewer how to interview? Well, that's especially true if you're a candidate. So don't ask: "gosh, are algorithms really all that important? do you ever need to do that kind of thing in real life? I've never had to do that kind of stuff." You'll just get rejected, so don't say that kind of thing. Treat every question as legitimate, even if you are frustrated that you don't know the answer. Feel free to ask for help or hints if you're stuck. Some interviewers take points off for that, but occasionally it will get you past some hurdle and give you a good performance on what would have otherwise been a horrible stony half-hour silence. Don't say "choo choo choo" when you're "thinking". Don't try to change the subject and answer a different question. Don't try to divert the interviewer from asking you a question by telling war stories. Don't try to bluff your interviewer. You should focus on each problem they're giving you and make your best effort to answer it fully. Some interviewers will not ask you to write code, but they will expect you to start writing code on the whiteboard at some point during your answer. They will give you hints but won't necessarily come right out and say: "I want you to write some code on the board now." If in doubt, you should ask them if they would like to see code. Interviewers have vastly different expectations about code. I personally don't care about syntax (unless you write something that could obviously never work in any programming language, at which point I will dive in and verify that you are not, in fact, a circus clown and that it was an honest mistake). But some interviewers are really picky about syntax, and some will even silently mark you down for missing a semicolon or a curly brace, without telling you. I think of these interviewers as – well, it's a technical term that rhymes with "bass soles", but they think of themselves as brilliant technical evaluators, and there's no way to tell them otherwise. So ask. Ask if they care about syntax, and if they do, try to get it right. Look over your code carefully from different angles and distances. Pretend it's someone else's code and you're tasked with finding bugs in it. You'd be amazed at what you can miss when you're standing 2 feet from a whiteboard with an interviewer staring at your shoulder blades. It's OK (and highly encouraged) to ask a few clarifying questions, and occasionally verify with the interviewer that you're on the track they want you to be on. Some interviewers will mark you down if you just jump up and start coding, even if you get the code right. They'll say you didn't think carefully first, and you're one of those "let's not do any design" type cowboys. So even if you think you know the answer to the problem, ask some questions and talk about the approach you'll take a little before diving in. On the flip side, don't take too long before actually solving the problem, or some interviewers will give you a delay-of-game penalty. Try to move (and write) quickly, since often interviewers want to get through more than one question during the interview, and if you solve the first one too slowly then they'll be out of time. They'll mark you down because they couldn't get a full picture of your skills. The benefit of the doubt is rarely given in interviewing. One last non-technical tip: bring your own whiteboard dry-erase markers. They sell pencil-thin ones at office supply stores, whereas most companies (including Google) tend to stock the fat kind. The thin ones turn your whiteboard from a 480i standard-definition tube into a 58-inch 1080p HD plasma screen. You need all the help you can get, and free whiteboard space is a real blessing. You should also practice whiteboard space-management skills, such as not starting on the right and coding down into the lower-right corner in Teeny Unreadable Font. Your interviewer will not be impressed. Amusingly, although it always irks me when people do this, I did it during my interviews, too. Just be aware of it! Oh, and don't let the marker dry out while you're standing there waving it. I'm tellin' ya: you want minimal distractions during the interview, and that one is surprisingly common. OK, that should be good for non-tech tips. On to X, for some value of X! Don't stab me! Tech Prep Tips The best tip is: go get a computer science degree. The more computer science you have, the better. You don't have to have a CS degree, but it helps. It doesn't have to be an advanced degree, but that helps too. However, you're probably thinking of applying to Google a little sooner than 2 to 8 years from now, so here are some shorter-term tips for you. Algorithm Complexity: you need to know Big-O. It's a must. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. It's, like, one chapter in the beginning of one theory of computation book, so just go read it. You can do it. Sorting: know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it. For God's sake, don't try sorting a linked list during the interview. Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview. Trees: you should know about trees. I'm tellin' ya: this is basic stuff, and it's embarrassing to bring it up, but some of you out there don't know basic tree construction, traversal and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises. You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree. You should actually know how it's implemented. You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder. You might not use trees much day-to-day, but if so, it's because you're avoiding tree problems. You won't need to do that anymore once you know how they work. Study up! Graphs Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think. There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. You should know their computational complexity, their tradeoffs, and how to implement them in real code. You should try to study up on fancier algorithms, such as Dijkstra and A*, if you get a chance. They're really great for just about anything, from game programming to distributed computing to you name it. You should know them. Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important! Other data structures You should study up on as many other data structures and algorithms as you can fit in that big noggin of yours. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. You should find out what NP-complete means. Basically, hit that data structures book hard, and try to retain as much of it as you can, and you can't go wrong. Math Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other places I've been, and I consider it a Good Thing, even though I'm not particularly good at discrete math. We're surrounded by counting problems, probability problems, and other Discrete Math 101 situations, and those innumerate among us blithely hack around them without knowing what we're doing. Don't get mad if the interviewer asks math questions. Do your best. Your best will be a heck of a lot better if you spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better. I know, I know, you're short on time. But this tip can really help make the difference between a "we're not sure" and a "let's hire her". And it's actually not all that bad – discrete math doesn't use much of the high-school math you studied and forgot. It starts back with elementary-school math and builds up from there, so you can probably pick up what you need for interviews in a couple of days of intense study. Sadly, I don't have a good recommendation for a Discrete Math book, so if you do, please mention it in the comments. Thanks. Operating Systems This is just a plug, from me, for you to know about processes, threads and concurrency issues. A lot of interviewers ask about that stuff, and it's pretty fundamental, so you should know it. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, and you'll be a dinosaur in a real hurry if you don't understand the fundamentals of "modern" (which is to say, "kinda broken") concurrency constructs. The best, most practical book I've ever personally read on the subject is Doug Lea's Concurrent Programming in Java. It got me the most bang per page. There are obviously lots of other books on concurrency. I'd avoid the academic ones and focus on the practical stuff, since it's most likely to get asked in interviews. Coding You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language. Other Stuff Because of the rules I outlined above, it's still possible that you'll get Interviewer A, and none of the stuff you've studied from these tips will be directly useful (except being warmed up.) If so, just do your best. Worst case, you can always come back in 6-12 months, right? Might seem like a long time, but I assure you it will go by in a flash. The stuff I've covered is actually mostly red-flags: stuff that really worries people if you don't know it. The discrete math is potentially optional, but somewhat risky if you don't know the first thing about it. Everything else I've mentioned you should know cold, and then you'll at least be prepped for the baseline interview level. It could be a lot harder than that, depending on the interviewer, or it could be easy. It just depends on how lucky you are. Are you feeling lucky? Then give it a try! Send me your resume I'll probably batch up any resume submissions people send me and submit them weekly. In the meantime, study up! You have a lot of warming up to do. Real-world work makes you rusty. I hope this was helpful. Let the flames begin, etc. Yawn. Original story