Tags: , , , | Posted by Admin on 4/9/2009 1:14 AM | Comments (0)
Google telephonic Interview 1. Asked about my project. Prepare well to answer any type of questions that may arise in your project.They will just ask to explain about any one of the projects listed in your resume. 2. In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)… (xn,yn). Now given these n points.Find the maximum number of collinear points. Solution: The duality algorithm would work. Find the point of intersection with maximum no of lines incident on it in the dual plane. It works in O(n^2). 3. Write the code for finding the min of n number. for(i=0;i{ if( a[i] { min = a[i] —- eq(i) } } Given that n numbers are from random sampling how many times (probability) does the line (i) be executed Solution: min=a[0]; for(i=1;i{ if( a[i]{ min = a[i]; ——-eq(i) } } Once the variable min is initialized,the probability of a[i] =k) { count+=n/k; k*=5; } return count; } this count is the number of o’s in n!. Google Interview Round 3 : 1. Write C++ class for the game Connect Four. [Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping discs into a seven column grid with the objective of getting four of one's own discs in a line.] 2. Given a stack and an input string of 1234.At any point you can do anyone of the follow i. take the next input symbol and Enque. ii. you can pop as many as you can. When ever you pop an element it will be printed (you cannot pop from an empty stack) How many such permutations are possible on an input of size N? Solution: It is Nth catalan number.For a detailed solution look at question5 of Stacks and Queues 3. Give an example of one permutation that this data structure cannot generate. For Example: 1234 is input. First push all 1,2,3,4 on to stack and pop all. output will be 4321. It means that this data structure can generate 4321. Solution: 3124 for a detailed solution please look at question7 of the post Stacks and Queues 4. Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque. Input: 12345 Data Structure: Deque ( Doubly Que ) Note: Deque is a data structure into which you can do enque and deque from both sides.Some thing like this __________________________________ enque —> <—-enque dequeue dequeue __________________________________ Solution: It is N!. Guess why?(no constraints).Convince yourself by proving that every permutation can be generated by a set of valid operations.This prove can be using the principle of strong mathematical induction.So for this specific input the answer is 120. 5. Classic Egg Puzzle Problem You are given 2 eggs.You have access to a 100-store building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-store building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process. Solution: Let “d” be the number of drops required to find out the max floor.we need to get the value of d. let’s say if we drop from height d then if it breaks then we have d-1 floors to check for the second egg . so max of “d” drops, so first we will drop it from height “d” if it doesn’t break at a height “d” then we are left with “d-1″ drops,so lets drop it from d + ‘d-2′ + 1 height suppose if it break there then you are left with ‘d-2′ drops. and so on until that sum is less than 100, it’s like a linear search, in equations, (1+(d-1))+ (1+(d-2)) + …. >= 100 here we need to find out d from the above equation d(d + 1)/2 >= 100 from above d is 14 Google Interview Round 4 : 1. Given n non overlapping intervals and an element. Find the interval into which this element falls. Solution: we can extend binary search to intervals.(Assuming the intervals are sorted) consider interval [a,b]. if (a-x)(b-x) a element can be present only in the intervals to its right. so select the middle interval among them to it’s right and repeat the procedure. else element can be present only in the intervals to its left. so select the middle interval among them to it’s left and repeat the procedure. The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals. 2. Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n). So please give a solution that will do better than O(n). 3. Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..) Solution: If the above intervals are overlapping ,then they can be merged in O(N) and then the exact intervals can be resolved later.Otherwise ,we can identify one correct interval and then linear search on its left and right neighbourhood to find the other solutions. 4. Write code for Random Sort? Algorithm is explained: Given an input array of size n. Random sort is sampling a new array from the given array and check whether the sampled array is sorted or not. If sorted return else sample again. The stress was on the code. Google Interview Round 5: This is Manager Round 1. Tell me an achievement that you have done in your non academics 2. Tell me about one of your project 3. Take a feature of C++ and tell me how you have implemented it in one of your project 4. By taking one of your project as example tell me how you have taken care of software engineering where you would have handled more data 5. There is a routine already written to find the subtraction of two sets ( set A - set B) . Write test cases for testing it.Tell me how do you test the test cases you have written? 6. There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have? Solution: Well people,this is too simple a question ..so do give it a try..(no malice,too simple).Any queries then do shoot a comment.
Tags: , , , | Posted by Admin on 3/14/2009 2:46 PM | Comments (0)
Phone Interviews The first two phone interviews were back-to-back and lasted 45 minutes each with a 15 minute break in-between. Both interviews had a mix of questions pertaining to programming, algorithm design, work term experiences, school projects and fundamental programming and computing concepts. The interviews were well-rounded and had good breadth and depth in terms of coverage. The third interview was solely to test my coding skills. It was a 45-minute phone interview as well. I was given two problems and I had to talk through my solutions and provide detailed pseudocode over the phone. Then, I was instructed to submit actual code files to the interviewer’s email address within an 1-2 hours after the interview. I was given freedom to use whatever programming language I saw fit. I made sure my code compiled and I put comments for better readability. I also cleaned up my code for any redundant or unnecessary variables. After a week or so, I was told that there were no more positions available in the smaller offices but that they had an opening for the Software Engineer in Test position at the Mountain View campus, if I was interested. Of course, I said yes. So, I got flown down to Mountain View to interview with the Test team. It was a nice 3-day reprieve from winter chills. On-site Interviews I was scheduled to meet my recruiter at 10am. She gave me a good tour around the Googleplex and talked about Google as a company and some of the employee perks. Then, she brought me to the interview room. There was a Google bag with other Google goodies that was for me to take home after the interview. Technical Interviews I had three technical interviews. The first 2 interviews were held before lunch, and the third one after lunch. Each interview lasted around 45 minutes and had an average of 3 problems each . All the technical interviews were held inside the same room. Although there is a whiteboard in the room, I was only asked to write on it during my third interview. For the other interviews, I mostly wrote on a pad paper. For some reason, I was allowed to write using pseudocode but I think it is still better to write real code. Most of the problems I was asked were just common coding problems or algorithms and to give ways to test them. Two problems I was given were search-related and for one of them, I was asked to scale the solution to a distributed file system that comprised of thousands of servers. I’ve compiled a list of technical interview tips and guidelines, as well as a list of helpful interview resources. Lunch Interview I was introduced to another member of the team and he brought me to the biggest cafeteria in the Googleplex. As everyone probably knows by now, one of the best Google perks is free food and tons of it. There was a wide variety of food and drinks. I decided to get food from the Japanese station. The sashimi was really fresh and sumptuous. Anyway, on to the casual interview. Most of the questions during lunch were just about which aspects of software or computer engineering I liked the most. I also talked about some of the projects I worked on in university as well as in my work terms. There was no technical question at all. I think they just wanted to see whether my interests and expertise are a good match for their team. Original story
Tags: , , | Posted by Admin on 12/27/2008 10:32 AM | Comments (0)
Dec 1st, 4:00 pm. I had a paper that morning, on 'Object Oriented Modeling'. Didn't sleep last night preparing for the paper. So, my condition wasn't its best for the interview. They called at ten past four in the evening. The interviewer wanted to start off with the interview (coding questions) right away. So did I. He asked me what my favorite language was (C++, C#). He then gave me a problem - 'You are given a string of characters. You are required to calculate the frequencies of each distinct character in the string.' The solution is quite simple. I proposed 2 solutions. 'There are 2 sorted lists of integers. You need to merge the 2 lists into a third larger list which should also be sorted.' Solution to this problem is also quite simple. I gave him an array-based solution, O(m+n). He asked me to write the solution using linked lists. I did that too. 'Now suppose there are k lists, all sorted, instead of 2. And you want to merge all of those lists into a single large list which should also be sorted. How will you do that?' I began to think over. Within 30 secs, he dropped a hint and i picked it up instantly. Using his hint, i gave him a solution of O(k*n). He asked me if i could do it better. I tried and proposed a couple of other algorithms, some better than others, but none as good as O(k*n). The interviewer was actually testing as to whether i can think of alternative solutions. He told me that your first solution was optimal. I just wanted to check if you can give other solutions. I was happy i could think of 3-4 alternatives to the same problem. Like other interviewers, he too asked me if i had questions. I asked him about the 'procedure of the interview process at Google', since this third phone screen was unexpected. He said, "This is your 3rd phone screen right? So according to my feedback, they will be inviting you onsite very soon. You will have 2-4 rounds of interviews at Google office." and i was like... :D Yet, this time too, i was not satisfied with my performance. I wished i get another chance to do the same interview and i would do better.. End of this (final) phone screen. Read on, Onsite Interview @ Google, Hyderabad. ..signing off Original story...
Tags: , , | Posted by Admin on 12/27/2008 10:31 AM | Comments (0)
Nov 12th, 5:00 pm. This one was interesting. Not the interview itself, but some of the events related to it. I had put up a status message on my orkut profile - "Nov 12th - Big Day.." Since i thought this interview was final phone screen and would decide on my onsite chances, i considered it big. A friend of mine, thought all the while that the day is big for me, since its her birthday. :-P Another funny thing was with my cell phone. It couldn't take calls. I could make outgoing calls, but incoming calls were rejected on the caller's side. I spoke to the customer care. He said it would take atleast 24 hours to repair the 'technical problem'. I informed about this problem to my recruiter by sending out a mail to her at 12:30pm. Requested her to make arrangements for the interview call to be made at another number. They didn't reply at all. Until 5:00pm, i didnt know if i was going to be interviewed that evening, at all. Well, finally the phone rang (at my friend's phone). I was quite confident this time compared to the last phone screen. The interviewer asked me if i was comfortable and if it was a good time to start with the interview. We got started. He asked me which programming language i was comfortable with. I told C++ & C#. Then he asked me to rate myself in C on a scale of 10. I rated myself 8. Cool, he wanted me to implement atoi() in C. But first, i was supposed to say what atoi() is. And i gave a very naive answer to that (after having myself rated 8!). All i knew was atoi() parsed the input string/array of numeric characters and returned the corresponding integer based on the radix (also passed as an argument to the function). He humbly explained me what the function is "generally" expected to do. :-) Oh, i forgot to mention. In the beginning of the interview, he asked me to have my laptop in front of me, with an internet connection. He shared a google doc with me, where i was supposed to write codes so that he could see them in real time. I wrote a pretty good code for the atoi() implementation. I am sure he liked it! In the middle of discussion on my solution for his first problem, he asked a couple of other simple questions. After this, he gave me a puzzle. I did what i could do worst for this. 'You have a transparent jar of marbles. You can determine the number of marbles in the jar at any time. You and your friend play a game. In each turn, a player draws one or two marbles from the jar. The player who draws the last marble, wins the game. Is it possible to play with a strategy such that you can win the game? Is it possible to determine who will win/lose the game?' As soon as he asked, i told him that i have heard of a similar puzzle earlier. He told me to answer to it anyway. I tried a couple of paths down to solution, but all were wrong. Strange thing is, i have had this puzzle solved twice earlier. I really screwed big time. Solution is quite simple. Readers are welcome to post comments on it. With that, my second phone screen ended. A good code, and a bad puzzle. I wished i had just one more chance to do this interview again. I would do much, much better. They took long time to respond. My hopes were fading. On Nov 26th, i got a mail finally informing about my 3rd phone screen scheduled on the 1st of Dec, 2008. My final semester exams were already on.. Too long post, huh. Read on, Third Phone Screen with Google.
Tags: , , | Posted by Admin on 12/27/2008 10:29 AM | Comments (0)
Nov 3rd, 5:00 pm. I was a little nervous. As for pre-interview preps, i took all my important papers (projects, semester mark sheets, etc) and placed them on my table. I had also some of my codes opened on my laptop screen for quick reference, if needed. Though, none of such preps ever was of any use. Finally the phone rang. It was a female interviewer. "Hi, is this Rajat?".. and the interview began. First question she asked was about my recent academic projects. I talked about one or two projects of mine. She then asked me what programming activities i involve myself in, other than college courses'. I mentioned TopCoder, GCJ, SPOJ and other such contests. She showed some interest in my standings in these contests. Next, she asked a problem and wanted me to code on that. 'Given a set of integers, how would you find out the 2nd maximum element?' I gave two solutions to this question, the second one being optimal. But i wont talk about it here right now, since it will kill readers' imagination. I wrote a code for the same and dictated it back to her. The code had a small bug. It wouldn't run for a corner case. I dont know if she noticed that bug. Next question was, 'There is a town with N people numbered 0 to N-1. Some people of this town knows some other people. The relation between them is not necessarily symmetric. i.e. If a knows b, doesn't mean b knows a. This town needs a mayor. The requisite for being a mayor is that he should be famous and impartial. Being famous means that he should be known to everyone in the town. Being impartial means that he should not know anyone in the town. Consider a function knows(i, j) that return true if i knows j or false otherwise. Write a program to return the list of people who are eligible for the mayor's post.' In google interviews, for every question, we are supposed to first propose the logic/algorithm to solve the question, and then write code for it. So was the case for this question too. I proposed an algorithm to solve this problem. She guided me through indirect hints(by asking questions that would lead me to her hint) to arrive at an almost optimal solution. I say 'almost' because even at the end of the interview, she kept on saying that there's a small bug in the code (and never revealed what it was), which i had not been able to figure out yet! Guess, it was one of the Google's interview pattern - say there is a bug even if there isn't any, to confuse the interviewee. The interivew lasted for around 1hr 5 mins. She asked me if i had any questions. I asked about work culture at Google. Quite expected. She wished me best and advised to continue with coding at Topcoder and GCJ, and solving puzzles. She also said that the HR people will get back to me soon. With that it ended.. I was expecting a 'Thank you' call from Google, given the kind of average perfomance i had shown at the interview. Really wished i had a chance to give this interview once more and i would give my best this time. To my surprise, i got a call for my second phone interivew on 7th Nov. :-) Read on, Second Phone Screen with Google. Original story...
Tags: , , | Posted by Admin on 10/30/2008 9:53 AM | Comments (0)
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.
Tags: | Posted by Admin on 10/29/2008 9:51 AM | Comments (0)
I had a phone interview with Google this morning. Overall it was a pleasant and slightly fun experience. I do not think I botched it up too badly, but I definitely do not think I had a slam dunk either. Here are the questions the Google engineer asked me in the interview: Describe pluggable abstract domains to me. This one related directly to my research. It impressed me for two reasons: the interviewer had read and understood my resume and the thing he asked about wasn't RAM compression (which is what everybody else asked about. He had some follow up questions about mathematical functors (which he had studied in school), interval analysis (which he had done before) and dynamic typing (other potential application). He followed up the type theory question by using Lisp as an example. Simulate a seven-sided die using only five-sided dice. The tricky part of this is generating a uniform distribution between one and seven. Just rolling seven of the five-sided dice does not work because the totals in the middle have higher probability. The solution I eventually arrived at (with a little poke in the right direction by my interviewer) is to change each five-sided die into a binary digit (1-2 are zero, 3-4 are 1, five is a re-roll) and then roll three of them. Interpret the number as binary, with zero being a re-roll. Come up with an algorithm to count number pairs which add to a certain sum in a list. The "obvious" way to do this is to check the first one with all the others, then the second ones with all the others minus the first one, and so on. The problem is that this is O(n2). The better solution is to sort the list first and then go through and look for the missing half of a pair. In other words, if the first number is one and you want to add to six, look for a five in the list. The complexity of this depends on the sorting methodology. If a bin-sort is able to be used (number of possible values is small) then it is O(n). This is because look up and counting is easy with the bin-sort structure as well. If we can't use bin-sort we have to use another sorting method, plus the lookups are more expensive as well. This results in O(n log n). The interviewer always asked me about the complexity of my algorithm (makes sense, since this is Google). Of course, I will never see these questions again, and you probably won't either. However, just thinking about them is probably good practice for future interviews. I collect the technical questions I am asked in interviews: Interview questions Below are some of the technical questions I have been asked in an interview. If you are having a technical interview in Computer Science, use these to warm up: Do a deletion on a linked list Reverse the bits in an int Implement a string search and replace Create aligned versions of malloc and free Count the color clusters of three or more in a binary tree Object-oriented design of an alarm clock Return the "Hello" string in C without allocation What does printf("abcdef\n"+1); print? Store all the words in a book Emulate a 7-sided die with 5-sided dice Count pairs which add to certain sum in a list How do you make a function reentrant? What does the stack frame look like during a function call? What are the different types of variables? local, global, static, register, pointer Write some code to determine the endian-ness of a machine Design a file system for a scratchpad memory  
Tags: , | Posted by Admin on 9/8/2008 1:09 PM | Comments (0)
Before the interview Your objectives To obtain information about the company/position to see if you would like to continue with the interview process To successfully answer the interview questions and prove that you are worthy of a face-to-face interview To appropriately “close” the interview (express your interest and thank the interviewer) Inquire about the rest of the interview process (timeline) Have ready Pen and paper, a computer(with fast internet :) ), your calendar. The job description and the resume and cover letter which you submitted. A list of your accomplishments which relate to the job you are discussing. Research you have done on the company, a short list of questions about the job. Prepare three to five key statements about your strengths and successes (also a few statements on your limitations and difficult situations you’ve encountered).Make sure you have a space set aside that is free of distractions. If you are taking the call on a cell phone, make sure you have strong reception. Know your comfort zone. Plan where you are going to sit (at a desk, table or couch). Prepare responses to typical interview questions Tell me about yourself. Why do you want to work for our company? What are your leadership skills? Give an example. What are your strengths and weaknesses? Tell about a time where you and a group were given a task and successfully completed it. What was your role? What was the result? Describe a time where you were faced with a high pressure or stressful situation. How did you handle it? Describe one work related mistake that you’ve made and what would you do differently? Are you willing to relocate? Travel? What would you like to know about us? During the Interview Who calls who? If you have been asked to call at a specific time, call precisely at that time. Too early makes you appear overly eager. Too late shows lack of interest - excuses won't be tolerated. If you can't get through (manager busy), leave a message with the receptionist to show that you called at the right time. If you have been told that the hiring manager will call you - do not expect the same rules to apply. They will call you when they can. Call objectives If the call is a straightforward screening call, the caller will likely ask about your experience, availability and related skills. Your strategy is to provide facts that support your resume, with some context about your performance. Make every effort to sound professional but also personable. Your goal is to secure an in-person interview with the person who has the authority to hire. Approach the call with that attitude. Things to remember: • When you answer the phone say: “Good Morning, Ms. X”. • Sound interested, energetic and enthusiastic. Speak slowly and enunciate clearly. • Enforce a dress code. Dressing in at least business casual attire will positively impact your ability to focus on the interview. If you wear earrings, remove them before the call. • Relax and be ready. Be sure to take the time to prepare for the interview. • Smile. Smiling will project a positive image to the listener and will change the tone of your voice. • Don't use slang, jargon and don't swear. • Avoid uh, er, um and like. This habit is especially noticeable on the telephone. It’s okay to pause and take time to think - it’s better than saying empty “filler” words. • Avoid simple yes or no answers. • If you need time to think, say so. • Focus on what you have to offer and can do. Be factual in your answers. Be prepared to give a positive two minute summary of your professional career Rehearse this! Employers hire people for what they can do for them. • Be a good listener, don’t interrupt. • Be careful of small talk. • Take notes on long questions. This will help you remember all aspects you need to touch on in your answer. • Be comfortable with silence. The interviewer might be writing as you are speaking. • After the interview, write down key words or interesting questions This will help you prepare for the face-to-face interview Ending the Interview Closing the interview Thank the interviewer (using their name) for their time and tell them that you are interested in the position (assuming that you are). Say you hope to be considered further and meet them in person. Ask about the next steps in the interview process as well as the hiring timetable. Follow up with a thank you note or email as soon as possible (for sure within one week). If you are offered a face-to-face interview Thank the interviewer and express your enthusiasm, and ask for details: When? Where? How to get there? (Are you responsible or will they pay for it?) With whom? What will the process be like?
Tags: , | Posted by Admin on 7/27/2008 2:48 PM | Comments (0)
I’ve been making an attempt to be environmentally-friendly/green/eco-responsible recently, whatever you call it. I’ve been driving better, exercising and studying in my free time. The self improvement isn’t due to increased social responsibility, self esteem or motivation. Its not peer opinion and isn’t even financially driven. It’s because Google is watching me. Don’t get me wrong, I’m not a big polluter - quite the opposite really. But when you try to evaluate whether its worth flushing a urinal that’s already leaking, or if watching the tv or using the computer is a bigger expenditure of electricity, especially when your laptop was charged on the other side of the country where electricity is produced through fossil fuels. Similarly, is driving safer on the left, behind another car or on the empty right lane, despite signs that say “Keep left when not overtaking”. It all started, ironically, when I applied for a job at Chevron. I got through the extensive screening process down to the round where they show you where they work and put you through those psychological screeners and in a room with 10 other potential candidates in a “group discussion” where they look for leadership abilities. This later evaluation, if you ask me, is purely designed to initiate confrontation - a “Jerry Springer” of the recruitment world. Never-the-less I persisted and was very positive about the prospects for my new job as an IT Analyst in Chevron. Why wouldn’t I be? Of the other candidates I was the only one with any significant experience, a double degree and I was locally based. I don’t even think I interviewed that badly - quite the opposite, I saw some raised eyebrows and smiles at my answers. So it was a big surprise when I got rejected. Huge. I was distraught actually, I kept racking my brain as to why - eventually it dawned on me: the perks. Talk about naive graduate, but the though of a company that evaluates your workstation (I’m talking about computer, hardware, software, desk, chair, footrest, couch and any other office furniture) on a quarterly basis for ergonomics, aesthetics, fit and just plain if you liked it or not.  This was in addition to the massages, bonuses and safety bonuses. Having never worked in a big company before, it was evident that economies of scale are very beneficial when it comes to employee perks. What then? I promptly applied to Google. It was my personal “up yours” at Chevron. That’s not a perk, mate….. This is a perk. - Crocodile Dundee (or something like that). At first it was a joke. No, really, I’ve heard how difficult it is to get into Google. Just look here. They hire the best (?) and they hire quickly. The company is 9 years old and doubling in size on a yearly basis. If ever there was proof that There no such thing as a free lunch. its Google. I was contacted a few days later by the Google Australia HR lady by email to organise a time for a phone interview. I didn’t really give it much thought, but had I known the statistics, I probably would’ve thought about preparing for a bit more. I’m no people person, but I know how to talk about myself well, so usually when I get talking to someone I’m not surprised when things proceed from there. In the first phone interview I felt everything going according to that old recruiting rhythm. Its easy to be positive about your degree and your experience when everything you’ve done is stuff you really enjoy and are passionate about. It was allllll good. Right up until she told me that we were about to arrive at the technical component of the phone screen. I panicked. It’s been a long time since I did Java, C++ is not my strongest suit. I was asked questions such as: “What’s the order of a function that iterates through an array?” and “Whats the difference between a class and object?” and “What’s the difference between final and finally?” and “What does the static keyword do?” - and few others. I answered in plain gibberish. One of my own responses I struggled to gauge. She only corrected me twice, which I interpreted to mean that she was only telling me the answers which weren’t blatantly wrong. Her opinion of me must have been positive enough to warrant scheduling the actual technical interview though. I asked her to delay it to the following week. After exams finished, I hit the books like crazy - I prep-ed for the Google technical phone interview like another exam. I started googling for interview questions and I hit a pack of brainteasers. Which ever moron put the title Google Interview questions on those brainteasers wasted me a lot of time, cause I never, ever, came across any of those in the whole interview process. I’m quite certain that the whole “Google Interview Questions” title was just appended to some computery type puzzles in an attempt to make light how difficult the process was going to be. They were pretty fun though. I studied for 2 weeks on the concepts that were fuzzy to me, using Steve Yegges posts as a guide. The HR lady had kindly sent these to me and they did nothing to boost my initial opinion that if I got to that stage that I would just “wing it”. The fact of the matter was that Google was the cheese, I was the mouse and the interview process was a maze, no - a gauntlet. Ok start again, Google was the virgin princess, I was the black knight - I figured out what my answers to the initial phone screen’s interview questions ment in real world terms (gibberish) and calculated how lucky I must have been to get by that day. Then I figured out what the answers should have actually been, what hash tables were and when I learned what they do, I went back and relearned Java. I studied data structures and Java to kingdom come. I roughly figured out Big-O analysis and I even took a quick peak at regular expressions, graph theory. My old lecture notes would’ve come in handy if they weren’t in ashes due to my annual note-burning festival. I found copies of my lectures online, read through them all. Then I started coding again. And had to relearn all the concepts again of-course. I started from the basics. Everything came back quickly enough, I love that I had paid enough attention in lectures to understand what was going on. I’d have been screwed otherwise.By the day of the big phone interview I’d gotten to a level where I could comfortably code things. Probably the level I should have gotten up to before my initial phone screen - or the level I should’ve started studying at. I imagined the recruiter writing notes to the interviewer: “Just scraped in… show no mercy.” or “He’s funny when he talks about Big-O, ask him those questions - it’ll make your day.” or “We had to include him to show you exactly how low the base line goes”. The interview started - he was a different guy from who the recruiter told me I should expect. I told him so. Then I backtracked thinking that he might think that I didn’t want to talk to him, or worse, that the other guy and I conspired to get me into Google by asking me easy questions. After that was resolved I noticed he has a heavy Scottish accent, thankfully he was aware of it too -told me to ask him to repeat things if I didn’t understand. I have a feeling that a lot of Google employees in Sydney work on Google Maps. He was initially from Mountain View and a very interesting guy - I asked him a fair few questions, not because I had  to but I was just genuinely interested in what he did. He asked me what ideas I had for Google. I told him about an interesting idea I had and it really seemed to capture him. Then he asked me how I’d go about implementing it. This particular problem involved figuring out if an author of a particular article was male or female. This was my answer - I kid you not: We’d just search thought the text, building probabilities as we go. We’d look for authors name, look it up in a table or male female names, we’d look at gender identifying establishments (eg. a private boys school)  and occupations (eg oil rig worker) multiplied by the gender distribution in these occupations, we could look at the colour usage on the text (pinks and lighter colours for females), we’d look for references to partners and multiply it by the probability that someone was heterosexual or homosexual. At this point I stopped. I had said the word homosexual in a technical phone interview. There was a silence, but not too long - I mean, there really wasn’t anything to worry about, I knew that, did he, of course he did, didn’t he? - were both professionals, it was a professional answer… For the record I don’t swing that way, neither did he. Google is an equal opportunity employer. Of course he did. The interview continued. We went through an implementation algorithm for a picture collage maker - top level design. Hashtable usage (where pictures were indexed by the predominant colour on them) was important to achieve the speed constraints. Short answer: Hashtables. We covered a similar question to the gender identification regarding fraud detection. Top level design again, used hash tables and probabilities. Then it was over, he thanked me I thanked him, I said I thought it would be harder. He laughed and said he could forward on the message to my next interview. I told him that I really didn’t think that would be necessary. We said goodbyes. I was not really sure what to take away from that interview  - he was obviously positive enough about it to suggest that I would get a second. Was this for real? Two days later, I got an email requesting a suitable time to go to Sydney. This had really gone too far. Original story Continue Part II
Tags: | Posted by Admin on 3/12/2008 3:21 AM | Comments (2)
I had my first Phone Interview for Internship with Google yesterday. I was shortlisted for the Interview by Google, based on my CV and aggregate percentage. I was pleasantly surprised 4 days back when I received a call from Google Bangalore Office informing me of the Interview. So I started preparing for the Technical Phone Interview by revising the fundas of Data Structures, Algorithms and Language subtleties. I came across a very good resource for coding and programming practice: TopCoder which helped me a lot in getting the fundas right practically. Finally yesterday evening the phone came, and I was a hell lot nervous. The interviewer was checking my Resume and exclaimed about my Internship Project at NEC HCL (last summer). He asked me about the details of the project, like what enhancements I did and how it helped, which I could very happily explain..... Then to programming stuff, I was given a problem where I had a large Integer Array and a given sum 'k'. I had to determine whether any two numbers from the Array would add up to k. He gave me various scenarios like the Array is sorted, unsorted and lot of extra storage space or not etc. I used Hash Table for the extra storage space case. I tried using Binary Search method for the In-Place case but could not optimize it for sorted Array, so I asked a teeny weeny bit of Hint and then the "Two Pointers Method" struck. He seemed satisfied with the responses. I had to write all the above stuff in terms of code and read it out to him, which was pretty exciting :) Next came another Question, I had a Binary Search Tree, given two nodes, I had to find the Nearest Common Ancestor. It seemed easy and I came up with the solution in just a Minute. He then Twisted the question a bit and generalized the Tree to a General Binary Tree. I asked for availability of parent pointer and he gave me choice. I came up with a recursive O((lg N)^2) algorithm if parent pointer was available. (Just after the Interview, when I was discussing with my Friend, I just got a better optimum O(lg N) algo (See Comments); I better hope these divine thought come during Interviews). Then as it was obvious, he asked for the general case of no parent pointer. Just few minutes of thinking and a recursive solution was there. (Which I again had to code and read out to him :) ) After his call for optimization, I just applied some Dynamic Programming ideas and Voila!! So, this was my 1 Hour 13 mins. long Interview which I enjoyed every bit of. Hoping for Selection into Round 2!!! Now my Mid Sems are just 2 days away and I have not even read a word....So, I better go and start with some DataBases...... Á la procháine, Au Revoir! Original story
Tags: , | Posted by Admin on 3/7/2008 4:35 PM | Comments (4)
Late in December 2007, I received an email from a recruiter at Google interested in discussing some software engineering positions at the company. Despite being fairly happily employed, I decided to follow up because, well, it’s Google! I forwarded an updated resume and scheduled a phone interview for a few days later in which the recruiter inquired further about my background, current job, and development skills. He also asked about my research assistantship and my publication from the lab. After I spoke for five or ten minutes, the guy gave me an overview of the interview process (one or two technical phone interviews followed by several on-site interviews) and explained that the questions ahead would be very technical and difficult. To this end, he inquired about my experience in theoretical computer science, particularly algorithms, data structures, and distributed systems. I answered honestly, stating that I did not major in computer science in college, but that I had a solid foundation from high school, and that I accrued plenty of relevant experience in the mean time. He seemed satisfied and suggested I brush up on big-O notation and other comp sci basics. I think I went to B&N one night and skimmed a few chapters of Programming Pearls. Technical Phone Intervew For the technical phone interview, an engineer from Google called me exactly at the scheduled time, and conducted an interview for exactly 45 minutes. I was surprised at how punctual he was. For the first half of the interview, he asked me about various items on my resume, honing in on the applications I developed at the research lab, and also my experience in video game development. He allowed the interview to flow naturally, which was nice. E.g., at some point I mentioned Flash, and he followed up by asking my opinion of Flash versus JavaScript, which sparked a tangential conversation in web usability. A few times he asked questions like “How would you do that better?” or “Do you have any improvements on that idea?” I just tried to keep fluid throughout the conversation, and it went very well. The second half of the phone interview revolved around a programming problem. He started off by asking some easy questions about linear versus binary search algorithms, and then presented a more difficult problem concerning a variably shifted sorted array. To get the ball rolling, I rattled off the obvious but inefficient solution, stating why it was inefficient and seguing into the solution the interviewer was after. I whipped out a pencil and paper and started drawing up a solution, making sure to provide frequent updates to the interviewer about what I was thinking or writing. In retrospect, the problem was not too hard, but having to do it over the phone added a level of distraction. I had a rough solution after a few minutes, at which point I recited the pseudo-code line by line. When I finished he said “Good” and asked if I saw any problems with the algorithm. I did a once over and identified two mistakes in my code and corrected them verbally. In the last few minutes of the phone interview, the interviewer gave me a chance to ask him some questions. I quickly asked about his role at Google, the typical development process, and jokingly about the food and if they have sleeping rooms for engineers like Yahoo. He said he works on Google Finance, and that projects are purposely kept small and agile. He laughed at my joke questions, confessing that the food is excellent and that Google does not have any sleeping rooms. On-site Interviews Shortly after the technical phone interview, I received a friendly email from a different recruiter asking to schedule a day of on-site interviews at the NY office. I was again reminded about the “caliber” of the upcoming questions, and scheduled a date a few weeks down the line. At this point they sent me a few forms including an NDA to fill out and bring along to the interview. In preparation, I practiced developing algorithms and writing code on paper without a computer, did a few rounds at TopCoder, and skimmed some academic papers published by Googlers (specifically, the original Google paper, MapReduce, Google File System). Unluckily I came down with some illness right before the interview so I ended up postponing it for another couple of weeks. Originally I was really torn about postponing the interview, but when I called my recruiter she told me it was absolutely no problem and that I did the right thing. I felt a lot better. A few days before the second date, as if the universe was playing a trick on me, I started feeling under the weather AGAIN, but I wasn’t about to postpone twice so I committed. On the morning of the interview, I did have a bit of a scratchy throat, but once the adrenaline kicked in I felt okay. [Travel accommodations expunged to preserve anonymity.] I arrived way too early, so I decided to “people watch” at the entrance for a bit. I got a cup of green tea from a street vendor nearby, took a sip—disgusting—but continued using it as a hand warmer for several minutes. It was very easy to identify which people entering the building were Google employees; they were the young-looking ones in jeans and hoodies. Finally I made my descent into the building, signed in at the lobby, and took an elevator up to the main Google floor. The elevators doors opened to a wide open lobby area. Behind the front desk was a giant Google Earth display animating from point to point on the globe. There was also an animation of search phrases projected on the floor. (In the few seconds I was spectating, I saw the term “yahoo.com” twice. Who does that?!) The receptionist instructed me to sign in and wait for 15 minutes or so, as I was still very early at this point. She asked for my interview contact, which I provided, but she wasn’t able to find him in the computer. Apparently the original recruiter I was in touch with wasn’t working at Google anymore. I gave her another name I remembered from correspondence and she straightened it out. I sat down, opened up my laptop, and hopped on Google’s free wireless network. I IM’ed some people and took some deep breaths. I was pretty nervous. A few minutes ticked by and before I knew it, my recruiter was there to greet me. The New York Google office is huge. It spans an entire city avenue. We walked for a minute or so to my interview room, passing all sorts of fun areas: offices, conference rooms, kitchens, play rooms, giant blue bouncy balls, all very “open air” style, very welcoming. The interview room itself had two glass walls, which were considerably friendlier than the usual closed-doored interview rooms everyone is accustomed to. The recruiter gave me a prospective overview of the day—2 or 3 interviews, lunch, and then X additional interviews—claiming that they didn’t know the schedule for the second half of the day just yet. In actuality I think this was just their way of saying, “We may decide you suck after 2 or 3 interviews, at which point we’ll quit wasting our time on you and kick you out.” The recruiter told me to help myself at the kitchen nearby and to ring him if an interviewer didn’t show up within a few minutes. He left the room, and I did a set of push-ups to blow off some steam. In a few minutes, my first interviewer showed up. The NDA prohibits that I talk about the guts of the interview, but each interview followed the same format as the original phone screen: 5 or 10 minutes of resume-centric discussion and then a programming problem. I had 2 interviews in the morning, then lunch accompanied by an engineer, then 4 additional interviews after lunch. For the last interview, two interviewers were present. Compared to the phone screen question, the programming problems for the on-site interviews were much more difficult, but manageable. In many of the questions, I stated the obvious “brute force” solution, but quickly set off on the “smart” solution. The interviewers wanted you to employ clever data & CPU optimizations, recursion tricks, and heuristics. A few of the interviewers concentrated at least briefly on non-programming questions (class design, system design, usability, asymptotic analysis), and one of them focused on obscure JavaScript (which I nailed, WOO!). I gave myself an A or B+ for most of the interviews, but I did need some prompting at two or three points throughout the day. Overall, the questions were on the level with what I anticipated, and I was happy with my performance. The Google interview process lasted all day and was very exhausting, and I felt an awesome wave of relief when it was over. They also gave me a cool Google T-shirt before I left. Unfortunately it’s way too big for me, but it’s a great memento. No dice A few weeks later, I got a vague email from the recruiter asking for a convenient time to “talk.” Immediately I got a bad vibe from this and braced myself for rejection. Sure enough, when the recruiter called, he informed me that I did very well, but that the hiring committee was not going to move forward at this point. He told me that the bar has been incredibly high for engineers lately, and that they are only accepting candidates who received enthusiastic reviews across the board (hinting that one or two of the interviewers gave me a less-than-stellar review). He apologized for not being able to provide more detailed feedback, and encouraged me to apply in a year or so when I felt motivated. Bummer. After all that stress, it’s downright frustrating to not have any clear feedback. Looking back, I can only think of one instance where I didn’t get the answer, and maybe two or three instances where I needed a slight “push” from the interviewer. I can only assume it was one of those guys who gave me the negative review. I definitely remember more instances of “nailing it” than struggling, but, like the recruiter said, they are looking for aces. Even though I didn’t get an offer, I’m proud of myself just for making it to the end of the process. I think I would have been a good fit at Google, but for now it’s behind me. Original story
Tags: , , , | Posted by Admin on 11/13/2007 1:08 PM | Comments (7)
Google telephonic Interview Asked about my project. Prepare well to answer any type of questions that may arise in your project.They will just ask to explain about any one of the projects listed in your resume. In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now given these n points.Find the maximum number of collinear points. Solution: The duality algorithm would work. Find the point of intersection with maximum no of lines incident on it in the dual plane. It works in O(n^2). Write the code for finding the min of n number. I gave: for(i=0;i<n;i++) { if( a[i]<min ) { min = a[i] ---- eq(i) } } Given that n numbers are from random sampling how many times (probability) does the line (i) be executed Solution: min=a[0]; for(i=1;i<n;i++) { if( a[i]<min ) { min = a[i]; -------eq(i) } } Once the variable min is initialized,the probability of a[i] < min is 1/2. So the expected number of occurances of equation i is (n-1)/2 . Google Interview Round 2: What is Bottom up parsing and what is top down parsing? Solution: Bottom-up parsing is a strategy for analyzing unknown data relationships that attempts to identify the most fundamental units first, and then to infer higher-order structures from them. It attempts to build trees upward toward the start symbol. It occurs in the analysis of both natural languages and computer languages. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural languages and computer languages. Please refer to these links for much better information. http://en.wikipedia.org/wiki/Bottom-up_parsing http://en.wikipedia.org/wiki/Top-down_parsing What is a symbol table? Solution: In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its type, scope level and sometimes its location. Check out http://en.wikipedia.org/wiki/Symbol_table There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situation to make sure that the user gets the response quickly. Solution: Every row has a primary key. Suppose the primary key for this particular database is the name of the user then we can sort the names based on alphabets and do secondary indexing based on the starting alphabet . If the data is uniformly distributed we can go for multilevel indexing or hashing.Similarly if we have a registration number as the primary key then we can sort the table based on registration number and then do indexing either secondary level or multilevel or apply hashing techniques based on the distribution of data. Many efficient algorithms are available for indexing and hashing. There are 8 identical balls. One of them is defective. It could be either heavier of lighter. Given a common balance how do you find the defective ball in least number of weighings. Solution: Weigh 3 balls against 3 others. Case A: If, on the first weighing, the balls balance, then the defective is among the 2 remaining balls and can be determined using 2 weighings making it a total of 3. Case B: Step1: If, on the first weighing, the balls don't balance. If the balls do not balance on the first weighing, we know that the odd ball is one of the 6 balls that was weighed. We also know that the group of 2 unweighed balls are normal, and that one of the sides, let's say Side A, is heavier than the other (although we don't know whether the odd ball is heavy or light). Step 2 : Take 2 balls from the unweighed group and use them to replace 2 balls on Side A (the heavy side). Take the 2 balls from Side A and use them to replace 2 balls on Side B (which are removed from the scale). I. If the scale balances, we know that one of the 2 balls removed from the scale was the odd one. In this case, we know that the ball is also light. We can proceed with the third weighing amd determine the lighter of the 2 balls ,hance the defective. II. If the scale tilts to the other side, so that Side B is now the heavy side, we know that one of the three balls moved from Side A to Side B is the odd ball, and that it is heavy. We proceed with the third weighing and determine the heavier one ,the defective. III. If the scale remains the same, we know that one of the two balls on the scale that was not shifted in our second weighing is the odd ball. We also know that the unmoved ball from Side A is heavier than the unmoved ball on Side B (though we don't know whether the odd ball is heavy or light). Step 3 (for Case B): Weigh the ball from Side A against a normal ball. If the scale balances, the ball from Side B is the odd one, and is light. If the scale does not balance, the ball from Side A is the odd one, and is heavy. You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why? Solution: Dozens of different data structures have been proposed for implementing dictionaries including hash tables, skip lists, and balanced/unbalanced binary search trees -- so choosing the right one can be tricky. Depending on the application, it is also a decision that can significantly impact performance. In practice, it is more important to avoid using a bad data structure than to identify the single best option available.As the frequency of look ups for a word is also important,weighted binary search tree with weights in proportion to the frequency of lookups and determining the depth, can be effective. Asked me about all the details of hash table and heaps. Write code for finding number of zeros in n! Solution: A zero in n! typically occurs when a multiple of 5 gets multiplied to an even number.We use this simple yet effective information to solve this problem.In the first n natural numbers,those divisible by 5 are always less than the no of even numbers.So it all boils down to the power of 5 in the prime factorization of n! . This simple formula works for finding it floor(n/5)+floor(n/25)+floor(n/125)+...... function zeros(int n) { int count=0,k=5; while(n>=k) { count+=n/k; k*=5; } return count; } this count is the number of o's in n!. Google Interview Round 3 : Write C++ class for the game Connect Four. [Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping discs into a seven column grid with the objective of getting four of one's own discs in a line.] Given a stack and an input string of 1234.At any point you can do anyone of the follow i. take the next input symbol and Enque. ii. you can pop as many as you can. When ever you pop an element it will be printed (you cannot pop from an empty stack) How many such permutations are possible on an input of size N? Solution: It is Nth catalan number.For a detailed solution look at question5 of Stacks and Queues Give an example of one permutation that this data structure cannot generate. For Example: 1234 is input. First push all 1,2,3,4 on to stack and pop all. output will be 4321. It means that this data structure can generate 4321. Solution: 3124 for a detailed solution please look at question7 of the post Stacks and Queues Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque. Input: 12345 Data Structure: Deque ( Doubly Que ) Note: Deque is a data structure into which you can do enque and deque from both sides.Some thing like this __________________________________ enque ---> <----enque dequeue <---- ----->dequeue __________________________________ Solution: It is N!. Guess why?(no constraints).Convince yourself by proving that every permutation can be generated by a set of valid operations.This prove can be using the principle of strong mathematical induction.So for this specific input the answer is 120. Classic Egg Puzzle Problem You are given 2 eggs.You have access to a 100-store building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-store building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process. Solution: Let "d" be the number of drops required to find out the max floor.we need to get the value of d. let's say if we drop from height d then if it breaks then we have d-1 floors to check for the second egg . so max of "d" drops, so first we will drop it from height "d" if it doesn't break at a height "d" then we are left with "d-1" drops,so lets drop it from d + 'd-2' + 1 height suppose if it break there then you are left with 'd-2' drops. and so on until that sum is less than 100, it's like a linear search, in equations, (1+(d-1))+ (1+(d-2)) + .... >= 100 here we need to find out d from the above equation d(d + 1)/2 >= 100 from above d is 14 Google Interview Round 4 : Given n non overlapping intervals and an element. Find the interval into which this element falls. Solution: we can extend binary search to intervals.(Assuming the intervals are sorted) consider interval [a,b]. if (a-x)(b-x) <=0 then x belongs to [a,b]. else if x>a element can be present only in the intervals to its right. so select the middle interval among them to it's right and repeat the procedure. else element can be present only in the intervals to its left. so select the middle interval among them to it's left and repeat the procedure. The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals. Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n). So please give a solution that will do better than O(n). Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..) Solution: If the above intervals are overlapping ,then they can be merged in O(N) and then the exact intervals can be resolved later.Otherwise ,we can identify one correct interval and then linear search on its left and right neighbourhood to find the other solutions. Write code for Random Sort? Algorithm is explained: Given an input array of size n. Random sort is sampling a new array from the given array and check whether the sampled array is sorted or not. If sorted return else sample again. The stress was on the code. Google Interview Round 5: This is Manager Round Tell me an achievement that you have done in your non academics Tell me about one of your project Take a feature of C++ and tell me how you have implemented it in one of your project By taking one of your project as example tell me how you have taken care of software engineering where you would have handled more data There is a routine already written to find the subtraction of two sets ( set A - set B) . Write test cases for testing it.Tell me how do you test the test cases you have written? There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have? Solution: Well people,this is too simple a question ..so do give it a try..(no malice,too simple).Any queries then do shoot a comment.
Tags: | Posted by Admin on 5/17/2007 11:39 AM | Comments (0)
It’s been over a month since I had my first phone interview with Google, but I’ve finally got a second one set up for Monday the 19th. It took more than a few emails to prompt the recruiter to do this, but I’m glad that it’s finally happening. Most companies are wrapping up their intern hiring by this time, so I wanted to make sure that I had a backup plan in case Google didn’t come through. I interviewed for a few positions at IBM over break and got two job offers that sound interesting and challenging. Both want a response by this Friday. I’m not willing to let those go in order to chase a Google internship that may not happen, so I’ve let the Google recruiter know that I’m on a tight time schedule in hopes that she can find me a group within the week. I’m not sure how the intern hiring process works at Google. The recruiter mentioned that it can take anywhere from “one week to two months” to find an appropriate match, and that matches are made based on “intern experience, skills, and interview feedback.” The emails that she sends make it sound like they want to hire me, but they’ve really let the ball drop these past few weeks. I think that they must be busy trying to hire people to fill full-time positions. I also wonder if maybe this process would have gone faster if I had applied for an internship out in California, where they have more of their workforce. Either way, I’ve got another week until I have to make a decision. Both options have their merits. If I work at IBM, I can live at home for free and hang out with all of my friends. I would give all that up, though, to have the chance to live in New York City and meet a whole new set of people. I think I’ll be happy no matter which way it goes, but I’ll be keeping my fingers crossed anyway… Update: The second interview went alright. There were more abstract math questions this time, more emphasis on algorithms rather than data structures, although there were a few questions about trees and lists at the beginning. Once again, the interviewer was really interested in hearing my thought process, so I tried to think out loud as I was solving the problems.
Tags: | Posted by Admin on 2/27/2007 1:16 AM | Comments (11)
2/27/07 1000: I decided to send Google another request today in case my first one wasn’t clear enough: This is my second attempt to contact you. I am the CIO of an organization with 11,000 users. Can someone contact me about the feasibility of migrating from our existing Exchange 5.5 platform. 2/27/07 1030: I received this email from Google after my second contact: We did receive your inquiry… thank you for your interest. Blair Reuling s your point of contact given the size of your organization. Blair is in he field and often traveling, and might be delayed in responding. Please eel free to contact Blair at… 2/28/2007: I phoned the Google enterpise dude 6 or 7 times today and could not reach him in his office or on his mobile phone. I left him a voicemail with a request to contact me so I can give him a bunch of cash. No contact yet. He has n are code in the Chicago suburbs. Maybe we will become best friends and go to White Sox games together - I have opening day tickets. Come on Google, answer my calls. 3/6/2007: Today I had my second conversation with Google - this was a WebEx (yes, Google uses WebEx).  I will create a new post when I have something to report.  But, I can confirm that they answered the phone and they have kept my interest enough for a 3rd meeting.   Of course the thing about meeting with Google is that you know they are going to Google your name.  When they did, this little post popped up.  But, they seemed to take it in stride by accepting my baseball offer below.  Hi Blair. Original post This month, for the first time since 1996, I started believing that there may be alternatives to Microsoft Exchange. Recently, Google announced their enterprise offering: Google Apps Premiere Edition for Enterprises. Since we are the verge of beginning a project to rebuild or email system, I quickly jumped into the Google web site completed a web form telling them that I am the CIO for a $1B+ organization with 11,000 users and I wanted to buy their service. Of course there are no phone numbers posted, which indicates to me that Google has not created an infrastructure for supporting enterprises. They are treating their enterprise customers like their freeloading search and gmail users - here is the offering, don’t call us - ever. That is a good strategy for Aunt Agnes who cant figure out ho to open an attachment from her knitting club, it doesn’t work when you hope to close multi-million dollar deals. While I waited for a response I started checking out the information Google had posted online. In general, I wanted to know if this would be an enterprise class service. I got mixed feelings from reading the promotional material. On the one hand they have developed APIs for directory integration, user provisioning and onsite backup (good, good and good). But the information was not very deep and there was not of service to support an enterprise offering. Migrating to an email system would be a massive undertaking and there would have to be a ton of resources to assist us with the planning and testing. While I applaud Google for including a service level agreement, it really isn’t enterprise class. 99.9% uptime for email is not acceptable in today’s world. Even the pricing isn’t geared toward the true enterprise user either. $50 per user per year is great for a small company. But it really doesn’t scale to a large organization. At 11,000 users we would be forking over $550,000 a year. I am not sure how much we spend on messaging now, but I suspect it is less than half a million annually. Google’s service does give our users access to documents and spreadsheets, but most users that need Office already have it. This would be the case in most enterprises. It is 4 days after begging Google to take my half million dollars, and I still have not heard from anyone. Apparently they are processing a backlog of CIOs willing to risk their job on such a venture. I am thinking this is more evidence that there is not a lot of enterprise support and their offering may be more suited to small businesses. Still, I am very intrigued. I really feel that I have been overcharged by Microsoft for years because they could. So, I am primed for a change. Also, a managed service has a lot of appeal. In the mean time I have downloaded the latest version of OpenOffice on my home PC. The improvement over the earlier versions that I have tried is remarkable. I can’t imagine why anyone would buy Office for their home when this works exactly the same. Folks, it is a free download (via bittorrent). Maybe Microsoft’s iron grip is loosening. Maybe Google can get a grip. I will keep you updated.
Tags: | Posted by Admin on 2/21/2007 3:15 AM | Comments (0)
This will be another short update--it's not the weekend, so not the time for my usual update. However, I know people will ask how my phone interview with Google went--so rather than dealing with those as they come up, I figured I'd beat people to the punch and just post a short entry about it. Unfortunately I haven't goaded them into revealing their "rumored" plans for Google mobile phones (a counter for Apple's iPhone), but I do have some notes about my experience to share. Since they don't tell you over the phone (or at least they didn't tell me over the phone--and I've never had anything but an on site interview where they tell me whether or not I've advanced to the next round) how the interview went, this is all just pure conjecture. My thought was that I did considerably better on it then other phone interviews I've had in the past--the lack of technical questions, in terms of programming, (I don't care about big O notation) and the fact that I was chained down to a corded phone (so I couldn't pace) probably helped a lot with that. As for the interview itself, it started out about as I'd expect--finding out about my familiarity with Google and Google products, why I want to work there, the fairly routine questions (warm-ups). After that, the majority of the interview was about me discussing my audio game project and most of the questions regarding that were ones I was prepared for--mostly things regarding my methods for the user study, why the first phase was done with sighted subjects (and what I need to keep in mind in relation to doing the study the visually impaired and blind from birth groups--I consider these questions fairly routine, since we went over our decisions quite a bit before finalizing on a user study plan; plus it's a question that comes up from almost everybody when I discuss the project). One item did, admittedly, trip me up though--the interviewer kept asking me about my use of the "think aloud protocol" for the study; which to me meant that there was clearly a potential problem with it that I hadn't thought of. I knew there was a potential problem in using it while doing the mapping of the levels, as a pilot subject had mentioned it made it difficult for her to remember the level--but I stated that we took that into account and asked subjects not to use that method for the mapping levels. I also mentioned how it could potentially be a problem where the audio from the user talking might distract them from the game's audio; however, none of the pilot (nor primary) subjects mentioned that as a distraction. When it came up again, I finally figured out the problem that was being implied--the "think aloud" method distracts from the primary task and since I was also recording the completion time of the levels, I ran a risk of skewing the timing results (particularly those of the audio only subjects). However, we only used the traditional "think aloud" method (where the user talks about all objects they encounter--what they think they are, where they think they are, etc.) during the training phase, which wasn't timed, and then used a modified version of it (where the subject only talks when they get stuck--such as being at a wall that's too high for them to jump over)--plus, we also implemented a pause feature that not only stops the game, but also stops the timing. She mentioned that it might have been better to run two groups--one for qualitative data collection where we focus on "think aloud" and one where we focus on collecting the quantitative data of the timing. In an ideal situation, we would have liked to do that, however, since the number of people with visual impairments we have access to is limited (and this is more or less an unfunded project) I mentioned how we felt running the two groups would be impractical since it would shrink our number of subjects too much--especially the birth blind subjects (which we'll already be lucky if we get enough of those for the study). She seemed pretty satisfied with my answers, so hopefully my blunder in not grasping the potential problem was faster won't count against me too much. So, in general, I think it went fairly well and I'm really hoping I get invited to the next round of interviews as I really would like the opportunity to work at Google for an internship (it's hard to find a company that does a lot of usability studies and even harder to find one that's as dedicated to user experience research as Google--other companies I've interviewed/have worked at have made doing proper user experience work a chore since you normally have to convince management that testing is in their best interest, and sometimes you have to convince the programmers/engineers...) Hopefully it will all work out. I'll let everybody know what happens when I either get invited for the next interview or get a polite rejection letter (hopefully I get the invite...)
Tags: | Posted by Admin on 10/4/2006 1:05 AM | Comments (0)
My hands are still shaking while I announce that I just got a phone call from Google Ireland Ltd. The lady, a Recruitment Coordinator of Google Ireland, told me that I had passed a test that I had submitted two days ago. I had expected an e-mail as response, so I was shocked to get a phone call, and so swiftly. There will be a real job interview with another recruitment officer on Tuesday October 10, 2006. Cross your fingers for me between 12:30 and 13:00 Central European Time! This will be my 5th job interview since I reported myself to the dole in 1999, and the third such interview since summer 2005. Apparently, this will be the third phase of application for the job as Google Online Sales and Operations Coordinator at the EU Headquarters. Phase one was the letter of application which I filled in on-line in September 2006. Second one was the worksheet test submitted in the early morning hours of Monday October 2. Looking back at the worksheet, I keep noticing all kinds of mistyping, but I presume that I did prove my knowledge about the matters — advertising, dealing with customers according to company internal policy, writing skills, and technical questions. If I have luck, I will be employed in Google Ireland to deal with European operations as Online Sales and Operations Coordinator. Google in Ireland has 700 employees. I am looking forwards to twist my tongue into the Irish variety of English. And to add Irish as the first member of the Celtic group to my fond of languages. The very internet extension of Ireland is .ie and is a clear reminder to any linguist of the importance of Irish to Indo-European linguistics. We all know the abbreviation *ie. for the reconstructed ancient Indo-European proto-language. Google was founded in 1998 by Larry Page and Sergey Brin. It has over 5,000 employees worldwide. Its chief product is its free on-line search machine that can carry out queries on the Internet in an instant. The searches are famous for their relevance, speed, and reliability. There are even courses offered in Denmark for corporate advertisers on how to optimise Google search results. Like most other search providers, Google also offers advertising — AdWords and AdSense — which usually appears as discrete textual highlights on the web pages. The name Google is derived from googol, is the mathematical term for a 1 followed by 100 zeros (i.e., 10100). The term was coined by Milton Sirotta, nephew of American mathematician Edward Kasner, and was popularized in the book, Mathematics and the Imagination by Kasner and James Newman. Google's play on the term reflects the company's mission to organize the immense amount of information available on the web (q.f. 1 followed by 100 zeros.) Original story
Tags: | Posted by Admin on 8/11/2006 11:50 PM | Comments (0)
Few things inspire as much dread and anxiety as the interview process. This screening process, which precedes any job in our industry, is of debatable value. It’s the worst kind of test: subjective, non-repeatable, and entirely qualitative. If the interview was a computer program, it’d be a thousand lines of spaghetti code held together by string, ducktape, prayer, the phase of the moon, and the color of your tie. Each cycle of the IT industry highlights a new company as having the most hideous, awe inspiring, and mind gnashing interview experience. In the first dot-com boom, it was Microsoft. With their two day long process, as many as 8 or 9 hour long interviews a day (including lunch), and mind bogglingly open-ended questions (Implement malloc.) the interviewee was left haggard, drained, and desperately in need of a bathroom after too much caffeine and stress. All things change, however; this cycle, Google’s got the prize. Trying to catch them all, Pokemon style, Google has swiftly gained a reputation for trying to pull in every top notch developer they can lay their hands on who survives the interview. Stealing a page from Microsoft’s book, Google interviews are renowned for placing intractable problems before interviewees with the panache of a sommelier. For your delectation, here are the questions in order for my recent Google phone screen. Not quite the full grilling I expect I’ll get when I go there in person, but a good representative sample of what you might expect. Q. Why does C++ have Virtual Functions? A. I replied that usually the question was “how”, with discussion on thunking and such, but that the primary answer was to enable polymorphism of behaviors in objects — thus answering two questions for the price of one! Q. What is the complexity of a search in a binary tree? A. O(logn) — I’m really glad I covered this material during my review sessions! Q. What is the complexity of a search in a hash table? A. I initially screwed this one up (for some reason my brain had bounced to heaps) but backtracked and caught myself, and got out that calculating the hash was constant time to index into the bucket. Q. When you form a connection with TCP/IP, what happens? A. I guessed where he was going on this one, with the TCP handshaking procedure, so mentioning the SYN, SYNACK, ACK three packet handshake was the answer he was looking for. Q. When you type in, say, “www.google.com” and press enter in your webbrowser, what happens? A. This is one of those wonderful questions where you’re supposed to trace out every single bloody step of the process without running out of breath. Starting with the keyboard interrupt for the enter key, continuing to the windows event handling, and then onwards to the URL parsing, the structure of the DNS resolution, the request itself, and finishing the rendering of the page about summed it up. During this question, I made a point of stopping regularly and making sure things were still on track. This is a good technique I’ve learned to avoid wandering off too far from where the interviewer is looking to go; the feedback also serves to give the interviewer an opportunity to guide the discussion. Q. If you have a phonebook, say of 3 million entries, and you want to provide searches through it as the user types in the name (think Microsoft Help Index’s, where the number of topics displayed gets pruned based on the user input), how would you do this? A. I immediately answered “By using a real database, such as PostgreSQL”. Which was, of course, the real-world “right” answer, but not the particular detail the interviewer wanted discussed (though it did give me points for practicality, which is important). I scrambled for a bit here, fortunately mostly mentally, but came up with a datastructure involving indexs based on each character (i.e. “A’ starts at entry 0, B’ starts at entry two thousand and thirty nine, C’ starts … etc. etc.), and that at a certain point you would just do an iterative search as the bucket got smaller, perhaps a Fibonacci search or some such. The important parts, the interviewer said, were the practicality of the real database approach, the keyed list access, and the concept that at a certain level, it makes sense to switch algorithms and use a linear search approach. All this took about a half-hour to go through, after which the interviewer and I talked a bit about the company, what it’s like to work for Google, the various products he was involved in, and so forth. For all of you out there who will be interviewing with Google in the future, I hope this helps your phone interviews go well! Original story
Tags: | Posted by Admin on 8/2/2005 3:13 AM | Comments (0)
I had a phone interview with Google today. I took notes; some of the questions they asked were interesting. We were allowed to ask questions. The interviewer didn't ask many questions in response to my answers, except to occasionally say "interesting". There's almost certainly more than one answer to each of these, and a few are probably wrong answers or could be improved in some way; I only include my answers for comparison. Any intermediate questions that I asked for clarification or otherwise have been omitted. Without further ado, a few of the more interesting ones: Q: "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?" (my answer): Take off all my clothes, wedge them between the blades and the floor to prevent it from turning. Back up against the edge of the blender until the electric motor overheats and burns out. Using the notches etched in the side for measuring, climb out. If there are no such notches or they're too far apart, retrieve clothes and make a rope to hurl myself out. Q: "How would you find out if a machine's stack grows up or down in memory?" (my answer): 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. (If they're the same, you did something wrong!) Q: "Explain a database in three sentences to your eight-year-old nephew." (my answer): A database is a way of organizing information. It's like a genie who knows where every toy in your room is. Instead of hunting for certain toys yourself and searching the whole room, you can ask the genie to find all your toy soldiers, or only X-Men action figures, or only race cars -- anything you want. Q: "How many gas stations would you say there are in the United States?" (my answer): A business doesn't stick around for long unless it makes a profit. Let's assume that all gas stations in the US are making at least some profit over the long run. Assume that the number of people who own more than one car is negligibly small relative to the total American population. Figure that 20% of people are too young to drive a car, another 10% can't drive because of disability or old age, 5% of people use public transportation or carpool, another 5% choose not to drive, and another 5% of the cars are inventory sitting in lots or warehouses that a dealership owns but which no one drives. There's about 280 million people in the US; subtracting 50%, that means there's about 140 million automobiles and 140 million drivers for them. The busiest city or interstate gas stations probably get a customer pulling in about twice a minute, or about 120 customers per hour; a slower gas station out in an agrarian area probably sees a customer once every 10 or 15 minutes, or about 4 customers per hour. Let's take a weighted average and suppose there's about one customer every 90 seconds, or about 40 customers an hour. Figuring a fourteen-hour business day (staying open from 7 AM to 9 PM), that's about 560 customers a day. If the average gas station services 560 customers a day, then there are 250,000 gas stations in the US. This number slightly overstates the true number of gas stations because some people are serviced by more than one gas station. [Actual number in 2003, according to the Journal of Petroleum Marketing: 237,284, an error of about 5%.] P.S. Apparently, if you make it to the next stage, you can't even tell people you're interviewing, because you sign a 6-page NDA. I haven't had to sign anything yet, though.
Tags: , | Posted by Admin on 2/2/2005 12:46 PM | Comments (8)
1. No phone screening interview with HR staff. 2. Direct phone interview with interviewers, mainly existing Product Managers 3. Questions include -Why do you want to join Google? -What do you know about Google's product and technology -If you are Product Manager for Google's Adwords, how do you plan to market this? -What would you say during product seminar of Adwords or Adsense? -Who are Google competitors, and how Google compete with them? -Have you ever used Google's products? such as Gmail? -Wha's creative way you may think of to market Google's brand name and product? -If you are Product Manager for Google's Gmail product, how do you plan to market it so as to achieve target customer of 100M in 6 months? 4. Almost no questions related to your past work experience. It seems that they are more interested in what you are able to do in future rather than you have done in your previous company. 5. If all phone screen intervews go well, you would be arranged for several on-site interviews.