Tags: , , | Posted by Admin on 2/18/2011 11:04 PM | Comments (0)
Given a sorting order string, sort the input string based on the given sorting order string. Ex sorting order string -> dfbcae Input string -> abcdeeabc output -> dbbccaaee
Tags: , , , , , | Posted by Admin on 1/26/2011 2:16 PM | Comments (0)
Here’s a list of 150 Google interview questions. Don't ask us where we got it from... Product Marketing ManagerWhy do you want to join Google? What do you know about Google’s product and technology? If you are Product Manager for Google’s Adwords, how do you plan to market this? What would you say during an AdWords or AdSense product seminar? Who are Google’s competitors, and how does Google compete with them? Have you ever used Google’s products? Gmail? What’s a creative way of marketing Google’s brand name and product? If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months? How much money you think Google makes daily from Gmail ads? Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product. Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20? Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year. Product ManagerHow would you boost the GMail subscription base? What is the most efficient way to sort a million integers? How would you re-position Google’s offerings to counteract competitive threats from Microsoft? How many golf balls can fit in a school bus? You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? How much should you charge to wash all the windows in Seattle? How would you find out if a machine’s stack grows up or down in memory? Explain a database in three sentences to your eight-year-old nephew. How many times a day does a clock’s hands overlap? You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager? How many piano tuners are there in the entire world? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process. Describe a technical problem you had and how you solved it. How would you design a simple search engine? Design an evacuation plan for San Francisco. There’s a latency problem in South Africa. Diagnose it. What are three long term challenges facing Google? Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it? If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building? How many vacuum’s are made per year in USA? Software EngineerWhy are manhole covers round? What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation? A man pushed his car to a hotel and lost his fortune. What happened? Explain the significance of “dead beef”. Write a C program which measures the the speed of a context switch on a UNIX/Linux system. Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7. Describe the algorithm for a depth-first graph traversal. Design a class library for writing card games. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How are cookies passed in the HTTP protocol? Design the SQL database tables for a car rental database. Write a regular expression which matches a email address. Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N. You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? Explain how congestion control works in the TCP protocol. In Java, what is the difference between final, finally, and finalize? What is multithreaded programming? What is a deadlock? Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..). You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Describe the data structure that is used to manage memory. (stack) What’s the difference between local and global variables? If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this) In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++). Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms). Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. Write some code to reverse a string. Implement division (without using the divide operator, obviously). Write some code to find all permutations of the letters in a particular string. What method would you use to look up a word in a dictionary? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? What is the C-language command for opening a connection with a foreign host over the internet? Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n). Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game? So your data structure should consider this condition also. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed. How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better? How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points? Let’s say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? Given a binary tree, programmatically you need to prove it is a binary search tree. You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one? Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge? Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change. Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? Write a function to find the middle node of a single link list. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Implement put/get methods of a fixed size cache with LRU replacement algorithm. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a solution in O(n) time complexity How does C++ deal with constructors and deconstructors of a class and its child class? Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list. What’s 2 to the power of 64? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How long it would take to sort 1 trillion numbers? Come up with a good estimate. Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it? How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three? Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element. Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists. What’s the difference between a hashtable and a hashmap? If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers? How would you reverse the image on an n by n matrix where each pixel is represented by a bit? Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t). Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space. Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road. What sort would you use if you had a large data set on disk and a small amount of ram to work with? What sort would you use if you required tight max time bounds and wanted highly regular performance. How would you store 1 million phone numbers? Design a 2D dungeon crawling game. It must allow for various items in the maze – walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.) What is the size of the C structure below on a 32-bit system? On a 64-bit? struct foo { char a; char* b; }; Software Engineer in TestEfficiently implement 3 stacks in a single array. Given an array of integers which is circularly sorted, how do you find a given integer. Write a program to find depth of binary search tree without using recursion. Find the maximum rectangle (in terms of area) under a histogram in linear time. Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type. Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python. How would you determine if someone has won a game of tic-tac-toe on a board of any size? Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. Create a cache with fast look up that only stores the N most recently accessed items. How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices? Given two files that has list of words (one per line), write a program to show the intersection. What kind of data structure would you use to index annagrams of words? e.g. if there exists the word “top” in the database, the query for “pot” should list that. Quantitative Compensation AnalystWhat is the yearly standard deviation of a stock given the monthly standard deviation? How many resumes does Google receive each year for software engineering? Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office? What is the probability of breaking a stick into 3 pieces and forming a triangle? Engineering ManagerYou’re the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive? AdWords AssociateHow would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions? How would you deal with an angry or frustrated advertisers on the phone?
Tags: , | Posted by Admin on 12/19/2010 11:37 AM | Comments (0)
Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens? Any answers? :)
Tags: , , | Posted by Admin on 7/21/2010 10:59 AM | Comments (0)
So I’ve now completed the interview process twice with Google (once in 2007 and once in 2010), and while I’m not sure advice from someone not hired after two run-throughs is all that useful, I figured that the more information out there for those undergoing pre-Google-Interview stress, the better, so here’s how it went. In both cases, I was contacted out of the blue by a Google recruiter. The first time I had been considering looking for a new role and pursued it immediately; the second time I hadn’t been and put off the recruitment process for several months, during which the same recruiter contacted me again twice to follow up. If nothing else, that’s a nice ego boost, but a more cynical mind might be considering the shotgun approach to a narrow recruiting filter and commissions First, a quick data point, I was applying for an SRE(SA) position on both occasions – Site Reliability Engineer (System Administration), because in most of my roles to date, I’ve been doing both sysadmin and development work and I’ve never seemed to drift towards one pigeonhole or another. SRE(SA) seemed optimal – interesting sysadmin work on large-scale systems and quite a bit of tool-writing to boot. This was decided on between myself and the recruiter, based on the self-assessment form you are given to fill out. I would love to know how they get around illusory superiority and the Dunning-Kruger effect with those forms, especially given the wierd bias they’d have in the dataset from having so many of the best in their fields working there. Both times, the process proceeded in the same way: the recruiter themselves carried out the initial phone screening, an idiot test of basic knowledge. The questions at this level are more broad than deep, and you really are talking about easy things like basic unix commands and the like. The second phone screen was more demanding technically, and was of the same mould as the famous “why is the sky blue?” physics exam question, with an initial simple answer and then drilling more and more into that answer. In my case, both were focussed on the level where user-level unix meets the underlying systems, the sort of thing you’d encounter in writing any kind of sysadmin tool. If I had to give hints here, it would be to know the underlying systems, their APIs, and the unix philosophy for writing tools to work with them. I’m not sure hints are of much use for Google interviews though – there are many sites saying they have questions used in Google interviews, but I’ve not yet encountered one of those examples after fourteen interviews. Knowing how to tackle Fermi questions (back-of-the-envelope estimates using what seem to be reasonable assumptions, such as “how many golf balls fit in a bus”) is probably a good idea, though I’ve only encountered them in passing; and big O notation has never come up. However, I think that SRE(SA) questions probably lean far more heavily towards the practical workaday stuff than towards application-level design fundamentals. Presumably there’s a different balance for developers. Certainly, practicing fault diagnosis in networked systems would be a good idea, and having your internal process for diagnosing faults well defined in your own head would be an even better one – that’s what the interviews are looking for and if you don’t have it clear for yourself, they can’t spot that. I would also suggest practicing writing code longhand, in one of the Google languages (C++, Python and shell script seemed to be the most popular). And I don’t mean coding on a machine, I mean writing the code longhand into a notebook and then typing it verbatim into a machine to test it. For a nice side effect, this’ll improve your penmanship and that may prove useful because you will be working a lot with a whiteboard. Incidentally, one of the better tips I’ve come across was to bring your own whiteboard markers (thin ones); it effectively gives you more room to work with, and whiteboards are never big enough, no matter how big they are… On both occasions, I then went on to do the on-site interviews. In my case, this was logistically easy as I was very close to the Dublin office, which is currently the second-largest Google office worldwide, so I didn’t have to fly to California or anything so onerous, but all five on-site interviews were held on one day, back-to-back, which is a bit exhausting. And on both occasions, the experience was about the same; initially you notice very Californian decor, with even the temp receptionist surrounded by a dozen or so lava lamps in alternating colours, with everything nice and brightly lit, and with swiss balls everywhere acting as seats and so forth. It does sound very Dr.Seuss, and it is in a way, but it’s a lot nicer than that sounds to be honest (if a bit… young), and there’s definitely an element of creating a culture through a particular physical appearance. The entire office complex is self-contained for the most part, with its own on-site canteen (which, by the way, is quite impressive – any canteen that can cook cous-cous properly for a thousand or so servings, while serving up at least four other lunch menus, is showing off very competent catering skills indeed, even if noone’s noticing most of the time), gyms and so on. In fact, walking around the streets you’d never know how many people are working in the offices from a casual glance. Again, on both occasions, the procedure was the same – I was met in reception after checking in by the recruiter, who’d booked an interview room and who walks you around the office a bit on the way there. Take a look around at this point; it’s an interesting office setup. Once there, the recruiter introduces the first interviewer and leaves you to the interview process and retrieves you at the end of the day to walk you out (after which point, the interviewers write up their reports and the hiring committee makes a decision. Start to finish, it’s been three to four weeks each time from initial contact to final decision). There were five interviews back-to-back each time, and the technical areas covered for me were those you’d expect for such a role: Design and Coding approaches; Unix/Linux sysadmin stuff; Networking; Scripting; Troubleshooting and problem-solving; Disk and storage systems. One google expert in each area, with the brief to start light and then push and push until you’re out of your comfort zone and well into your sweaty, stressed, exploding-head zone. If nothing else, you do wind up learning things from Google interviews, which is reason enough to undergo them to be honest. I didn’t know about isatty() until this round of interviews, for example. I don’t know of any other interview process that could be counted as a continuing professional development activity I’ve read accounts of Google interviewers being uninterested in the interviews they’re carrying out and being borderline rude in some cases; I have to say, I never encountered anything like that in any of the fourteen interviews I did over the two occasions, and never encountered anyone doing an interview who was less than professional about it; and most, if not all, were quite happy people during the interviews. Honestly, I never picked up on any personal or professional issues towards me, there was nothing but buy-in to their way of doing things. Which was quite impressive – I’ve interviewed with companies before where the interview felt more like a test of how much abuse you could tolerate, or where the company was simply wasting my time and theirs (for example, calling me in for an onsite interview that ate half a day, only to announce that they couldn’t pay me more than 60% of the expected salary). There’s not much feedback in the interviews though. That’s about the only real criticism I have of them. I can understand the hyping of the interviews – as much as you try to null it out, it does create mental stress and some think that gives greater insights into your real abilities (although frankly, it’s not the same kind of stress as you get during your daily work, so I don’t think it’s as useful as you’d imagine). I can understand the mythologising of the Google workplace (and given the professional and personal advantages that workplace offers, I can accept it as the cost of doing business). Actually, to digress for a moment on the workplace, I should point out that one of my main concerns while interviewing was how Google and professionals with families get along. Famously, Google is a young work environment, and while an eighty-hour work week, all-nighters and completely obsessive behaviour around your job is something you can manage to do in your early twenties, I don’t think you should do it – I think it’s one of our industry’s worst cases of macho-driven work practices, and a main reason for the high instance of IT project failures. Beside that opinion however, there’s the very real point that by the time you hit your thirties, you have to worry about wives, children, and other family things outside of work; and often you are faced with a choice between being a good employee and being a good person (and yes, I count letting obsession with work take over time that belongs to your family as a character failing; and no, that’s not the same thing as having to work long hours, that’s a different thing entirely). Google, however, seems to have taken this on-board, and everyone I spoke to about it had similar experiences – the mean age of the work force in Google is increasing, and more and more now have young families and work practices and facilities are changing to match the new demands. Childcare is the new free food, being family-friendly is now part of doing no evil. Feedback, however, is still a verboten topic. Interviewers don’t (and one told me they’re not allowed to) give feedback; nor are you given any if the hiring committee decides not to go with you as a candidate (which is what happened in both cases for me). That is rather fustrating – there’s no way to tell if you flunked a particular area, or if it was just that it wasn’t thought that you’d fit in with the Google environment. So you can wind up going through a process taking a few weeks, bringing a lot of stress, go through seven (or more) interviews, and not learn at the end if the problem was your technical proficiency or your popularity. Which is… suboptimal, at least from the interviewee’s point of view. From the interviewing company’s point of view, I suppose it could be said that every minute spent on a candidate after a decision to not hire them is a wasted minute; but the fact that you could be coming back to that person in a year or three does somewhat argue against that view. In short, it’s pretty tough, you will have to study hard for it (well, that’s to be expected), you may find your brain stalls because of the stress on things you fully grok day-to-day (that happened to me several times), and at the end of it all, you might be turned down purely on social reasons without ever being told it was because of workplace fit instead of technical competence. It’s still worth doing though, if only for the experience. Good luck!
Tags: , , | Posted by Admin on 5/16/2010 11:19 PM | Comments (0)
Question Come out with an algorithm for getting the column number provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA… This had to be converted to the column numbers. A will be 1 and AA will 27.. Also the algorithm to find the name provided column number.   Answer #include <string> #include <iostream> using namespace std; int ExcelColNum (char *name) {     int s = 0;     for (int i=strlen(name)-1, e=1; i>=0; –i, e*=26) {         s += e*(name[i]-’A'+1);     }     return s; } string ExcelColName (int num) {     string name;     for ( ; num; num/=26) {         name.insert (name.begin(), ‘A’+(num-1)%26);     }     return name; } int main(void) {     cout << "AAA ==> " << ExcelColNum ("AAA") << endl;     cout << "703 ==> " << ExcelColName (703) << endl;     return 0; }   Results are, AAA ==> 703 703 ==> AAA
Tags: , | Posted by Admin on 5/12/2010 3:25 PM | Comments (0)
Yesterday, word broke that Google is looking for a new "head of social." A couple months back, Google reached out to a source of ours in the industry for the job.  Curious "to see what the famous Google interview process was like," our guy told Google he'd talk to them about the job. In the end, he says the interview process "was not handled well at all." Our source's account: It started with a 2-hour breakfast interview at a fancy restaurant. Then a 1-hour recorded interview for playback to "the committee." Then a phone interview, after which they said they'd probably want to fly me out next. After that, another phone interview (of course weeks are going by in between each of these steps). Then they said great, OK now we definitely want to fly you out. Let's talk dates. We talked on the phone, upon which they said "cool, now let's schedule some video interviews" I was like WTF? "Oh... you mean the whole thing where we said let's fly you out? Well we decided that since you're near a major office, we'd do some video interviews first so that while we schedule your interviews at HQ we can line up the right people to interview you. So let's have an engineer talk with you, and a person from the social group." Surprise, neither of those two people materialized, instead it was a video interview with a different person. These were all very, very smart people, but that process just was not handled well at all. Of course, our source is not the first applicant to be left dumbfounded by Google's interview process. Remember those 15 Google Interview Questions That Will Make You Feel Stupid? (Side thought: If Google really needs a "head of social," maybe it could have skipped its painful hiring process and just done more to hang on to Foursquare founder Dennis Crowley? Or Twitter CEO Ev Williams? Or Facebook ex Paul Buchheit?)
Tags: , , | Posted by Admin on 5/9/2010 10:03 AM | Comments (0)
http://www.youtube.com/watch?v=E2dMmdewRxE&feature=player_embedded Want to apply for a job at Google? Fitz and Ben from Google’s Chicago office share useful tips that might help get your résumé noticed by the hiring managers at Google. One of the key things they stress upon in this video is open-source. If you are a software engineer who’s fresh out of college with no job experience, get yourself involved in some open-source project, contribute code and that may improve your chances of landing a job interview.
Tags: , , | Posted by Admin on 4/30/2010 10:23 AM | Comments (0)
Questions I was asked for Adwords Representative Interview Give me a runthrough of your resume? What do you know about Google? What do you know about Adwords? What do you understand about your job profile? How you fit into that role? Are you willing to give up the role of a team leader and creative writer to be an Adword Representative? How do you think this position can help your job profile? If Adwords was not associated with Google, would you have accepted the position? Yahoo and Microsoft has similar positions, why do you want to join Google only? You say you want a change in your career and use more of your skills, what other job profiles do you think would have suited you? What is your biggest failure in life? Have you been in a position when one of your colleagues did not do his share of work? How did you handle the situation? Suppose there is a project going on in full swing and two of your colleagues just fall sick, how will you handle the position? If you had to sell the job of Adwords Representative to a friend, what would you say to them? Tell me about a situation where just couldn't get along with one of your team members. What did you do? Have you ever faced a situation you didn't like at job? How did you face it? Do you have any questions to ask? Besides what HR sent you, what did you do to research about the position? What Google services you have used till date? Choose one of them and tell what change would you like to make in it? Your company generates revenue through Adsense. What kind of ads show up on your webpage? Why do you think Indian ads do not show up on your website's page? Do you know any of the Google terms and policies regarding Adwords? What did you liked about Google? Do you like the peole here? Which interviewer you liked the best? Why? Google has a flat system with not much vertical hierarchy system. It is based on meritocracy. If a person joins 6 months after you and becomes your mentor in a year, how would you handle the situation? Are you comfortable not having a vertical ladder to move on? At Google, you may have to deal with people who are freshers and ones who are much more qualified than you are. How will you balance out the situation and maintain relationships with all of them? You say you are flexible, adaptable and client-friendly. How? Give examples. What do you mean by people skills? That's all that I can remember for now.
Tags: , | Posted by Admin on 12/3/2009 10:38 AM | Comments (0)
It was hard to follow tech news this week without getting icky lawyer-stuff all over you. AT&T filed suit against Verizon, Intel got sued by New York State, an alleged cable modem hacker got indicted, and EMI sued to stop a tiny music Web site from sharing The Beatles' love. Also: A former high-tech CEO looks for better position in D.C., and Google seeks employees who speak nothing but geek. Do you have the qualifications to ace this week's quiz? Give yourself 10 points and a pat on the back for each correct answer. Now hand over your résumé and begin. 1. The Beatles' music will finally be available in disc-less digital form this December. Where will you soon be able to find the Fab Four? a. On Apple's iTunes Storeb. At BlueBeat.comc. On Verizon phonesd. On an apple-shaped USB drive 2. New York State Attorney General Andrew Cuomo is beating on Intel like a drum, accusing the chip giant of all manner of bad behavior. Which of the following is one of the official charges? a. Misleading advertising b. Strong-arming PC makers using bribery and coercion c. Shipping defective merchandise d. Charging exorbitant early termination fees 3. AT&T is suing Verizon. What's the dispute about? a. Verizon's attempts to wrest the iPhone from AT&T b. AT&T's claim to offer the "fastest 3G network" c. Verizon's exorbitant early termination fees d. Maps 4. Pew Research has conducted a study of the dominant ways people interact. How many days per year, on average, do Americans communicate via cell phone? a. 210 b. 195 c. 125 d. 72 5. Watch your back, Twitter. A new microblog has formed and it's apparently got God on its side. What's this new blessed blog called? a. TweetBabyJesus b. HeavenlyTwits c. ChristianChirp d. ChristianTwerp 6. "The decisions made in Washington impact every family and every business, of any size, in America. Throughout my career, I've brought people together and solved problems, and that is what I plan to do in government: Set aside ego and partisanship and work to develop solutions to our problems." What former high-tech CEO plans to bring the hard-won lessons of business management to Washington, D.C.? a. Jerry Yang b. Carly Fiorina c. Hector Ruiz d. Meg Whitman 7. Alleged cable modem hacker Ryan Harris was indicted this week by federal prosecutors in California. What is Harris's hacker alias? a. DerCable b. DerEngel c. DerSpiegel d. DerWeinerschnitzel 8. Careers coach Lewis Lin has released a list of 140 questions Google asks of prospective employees. Which of the following questions is not on Lin's list? a. How many golf balls can fit in a school bus? b. There's a latency problem in South Africa. Diagnose it. c. Explain the significance of "dead meat." d. Why are manhole covers round? 9. The Doodle -- the six-letter logo that adorns Google's otherwise sparse home page -- changed multiple times in the last week to honor various icons of childhood. Which of the following was not a Google Doodle? a. Wallace and Gromit b. Sesame Street c. Asterix & Obelix d. The Great Pumpkin 10. Take the number of iPhones Apple sold the first weekend it was available in China and multiply by the new early termination fee Verizon plans to charge users of smartphones who bail on their contracts. Add the volume of apps in the iPhone Store, rounded to the nearest large number. Download that to your Windows Mobile phone and pray someone will buy you an iPhone for Christmas. What do you get? a. 1,850,000 b. 185,000 c. 18,500 d. 1,850 Answer key Question 1: The Beatles' music will finally be available in disc-less digital form this December. Where will you soon be able to find the Fab Four? Correct Answer: On an apple-shaped USB drive The digitally remastered tunes will be available from record company EMI on a 16GB key drive shipped in a container made to resemble Apple Corp.'s Granny Smith-style logo. At press time BlueBeat.com, which was selling Beatles tracks for 25 cents each, found itself sued by EMI. The odds of the site surviving until December? Tomorrow never knows. Question 2: New York State Attorney General Andrew Cuomo is beating on Intel like a drum, accusing the chip giant of all manner of bad behavior. Which of the following is one of the official charges? Correct Answer: Strong-arming PC makers using bribery and coercion Cuomo's 83-page complaint echoes what the European Union fined Intel $1.5 billion for, and AMD has been suing Intel over since 2005 -- the company kicked back billions to computer makers who agreed to limit the use of AMD chips in their machines, and threatened those who would not be bribed. Others argue that, with the price of computers plummeting regardless of Intel's bad behavior, the harm to consumers is largely imaginary. Looks like somebody's running for governor. Question 3: AT&T is suing Verizon. What's the dispute about? Correct Answer: Maps More specifically, AT&T is suing Verizon over an ad campaign showing maps of their respective 3G coverage, with Verizon's mostly full and AT&T's nearly empty. AT&T claims the map ad is misleading because it implies AT&T offers no data coverage over much of the United States, when it in fact offers slower 2G service. Thus suggesting a new AT&T ad slogan: Slow service is better than no service. Question 4: Pew Research has conducted a study of the dominant ways people interact. How many days per year, on average, do Americans communicate via cell phone? Correct Answer: 195 According to the Pew Internet & American Life Project, Americans communicate face to face an average of 210 days a year, followed by mobile phones (195 days), texting and landlines (tied at 125), e-mail (72), instant messaging (55), and social networks (39). Their conclusion: Technology is not turning us into hermits. The caveat? Pew did not release data showing how many people talk on their phones, text, or e-mail during face-to-face meetings. Question 5: Watch your back, Twitter. A new microblog has formed and it's apparently got God on its side. What's this new blessed blog called? Correct Answer: ChristianChirp The service was launched by Net entrepreneur James L. Paris after Twitter allegedly shut down his account temporarily for "posting an article in support of Rush Limbaugh." FYI, Paris's other venture, ChristianMoney.com, aims to "help you make the most of God's money." Because, after all, He's got more money than, well, Himself. Question 6: "The decisions made in Washington impact every family and every business, of any size, in America. Throughout my career, I've brought people together and solved problems, and that is what I plan to do in government: Set aside ego and partisanship and work to develop solutions to our problems." What former high-tech CEO plans to bring the hard-won lessons of business management to Washington, D.C.? Correct Answer: Carly Fiorina The former HP chief confirmed long-standing rumors by officially joining the U.S. Senate race in California. She'll be fighting Republican Assemblyman Chuck Devore for the chance to challenge Senator Barbara Boxer a year from now. Considering the shape HP was in when she left, Fiorina might have a better shot running on the Amnesia Party ticket. Question 7: Alleged cable modem hacker Ryan Harris was indicted this week by federal prosecutors in California. What is Harris's hacker alias? Correct Answer: DerEngel Harris, author of "Hacking the Cable Modem," has been charged with conspiracy and fraud for allegedly selling software and modded modems that allowed customers to access cable ISPs and/or boost their bandwidth for free. He's facing up to 20 years in prison and a $250,000 fine. No word yet whether he also plans to run for the Senate in California. Question 8: Careers coach Lewis Lin has released a list of 140 questions Google asks of prospective employees. Which of the following questions is not on Lin's list? Correct Answer: Explain the significance of "dead meat." The actual question is "Explain the significance of 'dead beef'," the answer to which involves hexidecimal code. The other questions on Lin's list are equally baffling to the uninitiated. So unless you bone up before the interview, you are in fact dead meat. So much for those dreams of a comfortable retirement fueled by Google stock options. Question 9: The Doodle -- the six-letter logo that adorns Google's otherwise sparse home page -- changed multiple times in the last week to honor various icons of childhood. Which of the following was not a Google Doodle? Correct Answer: The Great Pumpkin However, which Google Doodle you saw depended on where you were sitting. Googlers in the United Kingdom saw Wallace and Gromit (in honor of the animated duo's 20th anniversary). U.S. searchers saw the Doodle visited by the Cookie Monster, Big Bird, and others (Sesame Street turned 40 this week). Ancient Gauls Asterix & Obelix got the Doodle treatment for their 50th anniversary (visible in 43 countries, but not the States). Also in the mix: various Doodles for Halloween and the Day of the Dead (in Mexico). Do you suppose Google has a Chief Doodle Officer, and if so, what kind of questions would you need to answer to get that job? Question 10: Take the number of iPhones Apple sold the first weekend it was available in China and multiply by the new early termination fee Verizon plans to charge users of smartphones who bail on their contracts. Add the volume of apps in the iPhone Store, rounded to the nearest large number. Download that to your Windows Mobile phone and pray someone will buy you an iPhone for Christmas. What do you get? Correct Answer: 1,850,000 China Unicom signed up 5,000 new subscribers, or one iPhone for every 263,000 people. (By contrast, Apple sold 1 million 3GS models over a similar time frame in Europe and the United States.) Verizon plans to ding its customers $350 for weaseling out of their commitments, minus $10 for every month they stayed in contract -- or roughly double what it charged in the past. Apple proudly announced its iPhone Store now serves more than 100,000 apps. So 5K * 350 + 100K = 1,850,000. Subtract the apps related to beer drinking, plastic surgery, or farting, though, and you're down to around 10,000. Come back next week for another gaseous quiz. Original story - www.infoworld.com/node/99198
Tags: , , | Posted by Admin on 12/2/2009 10:34 AM | Comments (0)
Google's recruiters are infamous in the Valley for dismissing Ivy-free applications* and posing highly technical brainteasers** during interviews. But apparently these "past results do not necessarily guarantee future performance," according to none other than Googlers themselves. Tech Chronicles wrote last month about the growing complaints among employees that academic pedigree is rewarded over real life experience and performance. One poster on Glassdoor.com, a Sausalito site that allows workers to anonymously review and rate their companies and managers, lamented:     They hire too many young overachievers -- people who have only ever "shown aptitude for having aptitude," as that one writer said. So it feels like half of everyone is angry about learning what being in the workforce is actually like, and shocked that you don't get promoted for working 12 hours a day and having aptitude and a great GPA. Turns out, the puzzlers don't work out so well in reality either, according to Gawker. Like not at all. Peter Norvig, Google's director of research, told Peter Seibel in an interview for the new book "Coders at Work":     One of the interesting things we've found, when trying to predict how well somebody we've hired is going to perform when we evaluate them a year or two later, is one of the best indicators of success within the company was getting the worst possible score on one of your interviews. We rank people from one to four, and if you got a one on one of your interviews, that was a really good indicator of success. That's a pretty big problem for Google, considering:     Ninety-nine percent of the people who got a one in one of their interviews we didn't hire. But the rest of them, in order for us to hire them somebody else had to be so passionate that they pounded on the table and said, "I have to hire this person because I see something in him..." Update: Google proper disputes these conclusions. "Our hiring process is well known for being pretty rigorous but we've found that, by and large, it goes a long way towards getting us the kind of candidates who will do well at Google and stay for a long time," a Google spokesperson said. "Our hiring process is designed to give both the company and the candidate a complete picture of how they will fit and we think it works exceptionally well." Update #2: Norvig took issue with the way his comments were framed too, saying in a blog post:     What do you know? Valleywag got everything wrong. Google is hiring, not laying off. Also, our interview scores actually correlate very well with on-the-job performance. Peter Seibel asked me if there was anything counterintuitive about the process and I said that people who got one low score but were hired anyway did well on-the-job. To me, that means the interview process is doing very well, not that it is broken. It means that we don't let one bad interview blackball a candidate.         Except, of course, to reiterate, he himself said that: "Ninety-nine percent of the people who got a one in one of their interviews we didn't hire."         If that's not a blackball, it's an awfully dark gray one.         Norvig continued: "We'll keep interviewing, keep hiring, and keep analyzing the results to improve the process."         *A extremely capable and intelligent friend of mine was advised by a Googler not to bother applying because she hadn't attended an Ivy League university or achieved a 4.0 GPA. And that was for a PR gig.         According to "Planet Google: One Company's Audacious Plan to Organize Everything We Know" by Randall Stross:             Google goes after not just the well educated, but the very well educated. Among the company's first hundred engineers, forty were Ph.D.'s. The company's emphasis on Ph.D.'s was not shared universally in the software industry. Microsoft mostly recruited computer science majors who had only a bachelor's degree; the company eschewed those with advanced degrees ("We're huge believers in hiring potential," Kristen Roby, Microsoft's director of recruiting at colleges in the United States, said in 2004). In contrast, Google sought those with the most academic training possible. A typical job listing featured a three-word phrase rarely seen outside of academe: "Ph.D. a plus."         **One question asked, according to an earlier Chronicle story:             "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.         For more purported Google interview questions, which we can't verify the accuracy of, click here.
Tags: , | Posted by Admin on 11/23/2009 10:27 AM | Comments (0)
Google strives to hire “the world’s best engineers,“and has crafted an “interminable” interview process dotted with puzzles and brainteasers to do so.That’s according to Peter Norvig Google’s director of research.What Google interview process also involves is a set of  crazy questions and asking those sorts of questions in a job interview is essentially a way of giving a prospective employee a de facto IQ test. Some of the best known google interview questions are given below. Why do you want to join Google? What would you say during an AdWords or AdSense product seminar? Have you ever used Google’s products? Gmail? What’s a creative way of marketing Google’s brand name and product? If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months? How many golf balls can fit in a school bus? You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? How much should you charge to wash all the windows in Seattle? 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!) How many piano tuners are there in the entire world? How many resumes does Google receive each year for software engineering? Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office? These questions clearly show that apart from from being able to solve puzzles and create complex algorithms, employers also look in for people with a good sense of humour. This clearly explains why google turned down thousands of application because they couldn’t get the “answer” to the question-’ How to design a perfect toaster’….
Tags: , | Posted by Admin on 11/19/2009 2:39 PM | Comments (0)
I just got done reading the Google Interview Questions over at Gizmodo and came to only one conclusion about them, and it is the same problem I have with most “clever” interview questions. Why bother? What does this tell you about the candidate? Can they perform under pressure? Can they think on their feet? Do they already know the answer? Have they heard this one before? I am sure, somewhere, someone found that in the framework of an actual interview these questions have some utility, but mostly I find that they serve only three purposes for the company doing the hiring: To demonstrate how clever the interviewer actually is. Give a poor interviewer a crutch to lean on. Give a lazy interviewer (see point two above) something to ask rather than actually do real work during the interview process. I guess I have been lucky when hiring employees for my company in that they are all people I have had the pleasure of working with in the past at other gigs. I don’t think I have ever asked a “clever” interview question in my entire career. I’d rather the interviewee demonstrate a clear understanding of their chosen profession than their ability to “answer a pop quiz.” I have been asked “clever” questions, and they are mostly unoriginal and something the interviewer looked up on the internet. What the questions are supposed to do is provide insight in to how you think, how you perform under pressure, and so on. The problem is that the lazy interviewer doesn’t give a damn about how you perform, just whether your answer matches up. And the poor interviewer doesn’t have the skills to usefully evaluate your performance so they, again, focus on the answer you gave. Usually if you don’t give the exact right answer they have memorised or have written down in front of them, in their eyes, you failed. On the whole, the interviewer generally isn’t smart enough to actually understand the question themselves, or even come up with something original. What the questions are supposed to do is I’m angry at lazy, poor interviewers the and companies they work for. But I am even angrier still at people who focus so much on these questions, because the questions themselves are self-serving, self-fulfilling prophecies – “Look at how clever we are to ask these kinds of questions!” and so it goes “Gosh darn it, that must be a top-flight company if they ask interview questions only they know the answers to.” Perhaps I am sore because I cannot answer the questions satisfactorily? I answered each and every one, except for #8, to a satisfactory level in under a minute with the CTO of the company I am currently consulting for acting as the “heckling interviewer.” And boy can he heckle. The heckling provided a “realistic interview scenario” to apply a little pressure. The “How many lines can be drawn in a 2D plane” stumped me because I simply didn’t understand the question as stated until I got up and drew it out on the whiteboard. Total time to solve: less than 3 minutes. And question #9 is just plain silly. The answer is obviously 0×10000000000000000. Proof that the interviewer was attempting to be clever but the interviewee was being cleverer. Also, ignores the fact that any competent software engineer knows their powers of two, off by heart, all the way up to 128 bits.
Tags: , , , | Posted by Admin on 11/17/2009 10:42 AM | Comments (0)
How can you go wrong with a jacket and tie, or a nice suit? Be well groomed, look your best, and dont think that its old fashioned and out of style. first impressions are the most lasting ones. you may be the most qualified, but if you show up looking like Smeagle from the Lord of the Rings or one of those orcs, i dont think you are gong to get the job. Cover the tats, get rid of the nose rings, piercings etc. get a nice haircut. Be well groomed and go for it. remember, once you are in your work environment you can take your cue from your fellow workers to see whats appropriate dress. good luck and let me know how it goes. and be a little bit early.! Try to look smart, but be casual at the same time. Don’t look like you’re trying too hard to impress them though!!
Tags: , | Posted by Admin on 11/16/2009 10:41 AM | Comments (0)
OK, I’ve had enough. People, seriously. If you are retarded, then Google doesn’t want you to work for them. Duh. I just read this poor girl’s account of an interview: The Interview Well, they asked her a question (according to her). About how much money AdWords pulls in a day. Hmmm. It’s Google. What do you think, they want a number? Like, oh yeah I think they make $70,000 a day. WTF?! That’s my first response. Apparently, Google thought the same. I also was interviewed by Google. They flew me to Trondheim a while back. Holy. Shit. Not because I thought their interview process was madness. Because it’s not. Actually it is. But compared to everyone else’s idea of an interview process, it’s pretty damn good. I think they could learn a bit from Semco – but that’s a personal bias. My interview was a fail because of something else. I was treated. I do thank Google for this, they put me in front of some really great people – they gave me 4 hours of some top talent’s time to pretty much have my way with. Wow, thanks! But! Fail. Not fail for me. Fail for Google. The 1st guy was, well, junior. He asked some questions about stats (the math kind), and basically didn’t know enough about the subject to hold his own. 2nd guy up asked me some questions about graphics algorithms, which I knew nothing about. But, I wasn’t completely clueless – I was able to come up with the recursive flood fills and other basic crap he was after. All was OK (not great, I had some reservations already, but still was possible…). Then, #3 came out. He had another guy with him, they both EMPHATICALLY denied this 2nd guy’s role in the interview (he was there to review the interviewer…). Before it started, I already knew: I could never, ever, in a million billion years, work at Google. Know why? Because, they have guys like that working there. Fuck those people!!! This guy was droning on about Mars rovers and convergent series and I was like “WTF?!”. No, you don’t understand. Really, I was close to just telling this guy he could take his 1/2 autistic, Mars roving questions and shove them up his ass. BUT. There is something about intelligence that I respect. And this guy wasn’t retarded. He was smart. Really, he’s the kind of guy I would be friends with. But my boss? This guy? I was ANGRY by the time I got into the interview with him, forget a job – I was ready to tell him where to shove it. But, but, this was being paid for by Google. It was a privlege. I set aside whatever differences I felt like I was experiencing and followed through. Next guy up was even worse. Anything about packets – happy face. Anything else, angry face. OK, seriously, there’s more to life than knowing how to thwart a SYN flood. I never let on anything. I played dumb, and I dropped off the Google grid. Well, until maybe now who knows. But really, who is Google? Who are these people? In my experience, the Google mold is one of trees. As in, can’t see the forest for the trees. As in, oblivious. Smart? Sure. But it takes more than smart to forge a decent life. You digg? You have to understand, I flew from South Africa to come to this interview (don’t even bother with the shit I had to go through to get a decent phone connection to Norway from inner Siberia during screening). At the 12-hour layover in Windhoek (I’m pretty sure it was here…) I picked up a viral infection of some sort. That’s right, shitting liquid nastiness, barfing, fever – I wasn’t in top form anyway. However, I was in good enough form to understand rovers and stats. The guy that interviewed me who allegedly would’ve been my boss couldn’t even detect that I was feigning ignorance of the basic maths we were going over. Nor did he know that I was really sick. Not like butterflies sick mind you, like I-caught-a-virus-in-Namibia-and-now-I’m-shitting-my-pants-sick. I should’ve cancelled, but I was pretty damn sure I wasn’t contagious by the time I got to Norway and I didn’t have a lot of time to fuck around there, so I went for it. Granted, this was after the whole Cox Communications thing which put me off of having a proper job ever again. But, really, after this experience there are 2 things that are clear for me: If you are truly good, you don’t belong at Google. If you are truly good, you are smart enough to transcend nations, companies, technologies, languages (human, computer, otherwise…), etc. Hell, if I can then damn near anyone can. Google is a company. Forget the “do no evil” bullshit. Google has agendas, ultimatums, politics, and retardedness like everyone else. For now, their leadership thinks more than just about today’s 1/4 earnings. For now. You don’t need Google. And most importantly, Google doesn’t need you. This poor girl in the article, I’ll bet she’s working for Yahoo…you don’t even want me to get started on their mediocrity. My interview was almost 2 years ago, and I have circled the globe twice since then. Now I am in Novosibirsk, where I study various languages, learn how to cook, ski, have fun at the banya, etc. Forget a dayjob, it’s too much fun to live without one – Google or otherwise!
Tags: , , | Posted by Admin on 10/30/2009 1:22 PM | Comments (0)
Ryan Tate of Silicon Valley Insider quotes Google's director of research Peter Norvig: One of the interesting things we've found, when trying to predict how well somebody we've hired is going to perform when we evaluate them a year or two later, is one of the best indicators of success within the company was getting the worst possible score on one of your interviews. We rank people from one to four [one being the worst], and if you got a one on one of your interviews, that was a really good indicator of success. Tate notes elsewhere in his piece that the Google interview process involves crazy questions. Tate doesn't connect the dots, but asking those sorts of questions in a job interview is essentially a way of giving a prospective employee a de facto IQ test (giving actual IQ tests to prospective employees has been legally problematic since Griggs v. Duke Power). Back to Googler Peter Norvig: Ninety-nine percent of the people who got a one in one of their interviews we didn't hire. But the rest of them, in order for us to hire them somebody else had to be so passionate that they pounded on the table and said, "I have to hire this person because I see something in him..." My guess at what's going on here: creativity probably increases directly with IQ up to a certain point, at which it peaks and then declines. So if you are looking for an employee who's going to come up with the next killer app or new line of business for your company, and you hire only the candidates with the highest IQs, you are probably overshooting the IQ sweet spot where you'd find the smart, creative types.
Tags: , | Posted by Admin on 10/25/2009 8:35 AM | Comments (0)
Google Interview Questions: Product Marketing Manager Why do you want to join Google? What do you know about Google's product and technology? If you are Product Manager for Google's Adwords, how do you plan to market this? What would you say during an AdWords or AdSense product seminar? Who are Google competitors, and how does Google compete with them? Have you ever used Google's products? Gmail? What's a creative way of marketing Google's brand name and product? If you are the product marketing manager for Google's Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months? Google Interview Questions: Product Manager How would you boost the GMail subscription base? What is the most efficient way to sort a million integers? How would you re-position Google's offerings to counteract competitive threats from Microsoft? How many golf balls can fit in a school bus? You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? How much should you charge to wash all the windows in Seattle? How would you find out if a machine’s stack grows up or down in memory? Explain a database in three sentences to your eight-year-old nephew. How many times a day does a clock’s hands overlap? You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it's only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager? How many piano tuners are there in the entire world? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process. Describe a technical problem you had and how you solved it. How would you design a simple search engine? Design an evacuation plan for San Francisco. There's a latency problem in South Africa. Diagnose it. What are three long term challenges facing google? Google Interview Questions: Software Engineer Why are manhole covers round? What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation? A man pushed his car to a hotel and lost his fortune. What happened? Explain the significance of "dead beef". Write a C program which measures the the speed of a context switch on a UNIX/Linux system. Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7. Describe the algorithm for a depth-first graph traversal. Design a class library for writing card games. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How are cookies passed in the HTTP protocol? Design the SQL database tables for a car rental database. Write a regular expression which matches a email address. Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N. You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? Explain how congestion control works in the TCP protocol. In Java, what is the difference between final, finally, and finalize? What is multithreaded programming? What is a deadlock? Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..). You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Describe the data structure that is used to manage memory. (stack) What's the difference between local and global variables? If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this) In Java, what is the difference between static, final, and const. (if you don't know Java they will ask something similar for C or C++). Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms). Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. Write some code to reverse a string. Implement division (without using the divide operator, obviously). Write some code to find all permutations of the letters in a particular string. What method would you use to look up a word in a dictionary? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? What is the C-language command for opening a connection with a foreign host over the internet? Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n). Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed. How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better? How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points? Let's say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? Given a binary tree, programmatically you need to prove it is a binary search tree. You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one? Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge? Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change. Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? Write a function to find the middle node of a single link list. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Implement put/get methods of a fixed size cache with LRU replacement algorithm. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity How does C++ deal with constructors and deconstructors of a class and its child class? Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list. What's 2 to the power of 64? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How long it would take to sort 1 trillion numbers? Come up with a good estimate. Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it? How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three? Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element. Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists. What's the difference between a hashtable and a hashmap? If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers? How would you reverse the image on an n by n matrix where each pixel is represented by a bit? Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t). Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space. Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road. What sort would you use if you had a large data set on disk and a small amount of ram to work with? What sort would you use if you required tight max time bounds and wanted highly regular performance. How would you store 1 million phone numbers? Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.) What is the size of the C structure below on a 32-bit system? On a 64-bit? struct foo { char a; char* b; }; Google Interview: Software Engineer in Test Efficiently implement 3 stacks in a single array. Given an array of integers which is circularly sorted, how do you find a given integer. Write a program to find depth of binary search tree without using recursion. Find the maximum rectangle (in terms of area) under a histogram in linear time. Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type. Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python. How would you determine if someone has won a game of tic-tac-toe on a board of any size? Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. Create a cache with fast look up that only stores the N most recently accessed items. How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices? Given two files that has list of words (one per line), write a program to show the intersection. What kind of data structure would you use to index annagrams of words? e.g. if there exists the word "top" in the database, the query for "pot" should list that. Google Interview: Quantitative Compensation Analyst What is the yearly standard deviation of a stock given the monthly standard deviation? How many resumes does Google receive each year for software engineering? Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office? What is the probability of breaking a stick into 3 pieces and forming a triangle? Google Interview: Engineering Manager You're the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive? Google Interview: AdWords Associate How would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions? How would you deal with an angry or frustrated advertisers on the phone?
Tags: , | Posted by Admin on 8/1/2009 10:49 PM | Comments (0)
1. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time. 2. Given a circularly sorted array, describe the fastest way to locate the largest element. 3. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k. 4. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node. 5. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers? 6. Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one. 7. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you’d write the next() and hasNext() functions to work with the next negative integer instead of just the next integer. 8. You are making an AI to play Tic-Tac-To. Make a function that takes a board position as an input and returns a good position to play. Describe how you’d represent the board, and how you’d determine where to play next. 9. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible? 10. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?.
Tags: , , | Posted by Admin on 7/28/2009 10:48 PM | Comments (0)
You have to get from point A to point B. You don’t know if you can get there. What would you do? Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? What method would you use to look up a word in a dictionary? Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens? You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings? How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut. How many piano tuners are there in the entire world? What gives you joy? Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can’t use fractions in the answer. Hint: This is a trick question, pay close attention to the condition) How many times a day a clock’s hands overlap? Two MIT math graduates bump into each other. They hadn’t seen each other in over 20 years. The first grad says to the second: “how have you been?” Second: “Great! I got married and I have three daughters now” First: “Really? how old are they?” Second: “Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..” First: “Right, ok.. oh wait.. I still don’t know” second: “Oh sorry, the oldest one just started to play the piano” First: “Wonderful! my oldest is the same age!” Problem: How old are the daughters? If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country? You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?
Tags: , , | Posted by Admin on 7/25/2009 10:43 PM | Comments (0)
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.
Tags: , , | Posted by Admin on 7/21/2009 10:33 PM | Comments (0)
Tomorrow at noon I’ll have my interview with Google. I went through a great deal of effort to be as prepared for this interview as I could be. I poured over my resume, I researched practice questions, I had friends and family run me through mock interviews. Let me share some of the things I learned, and tell you about some of the things I did.   I proofread my resume about a million times. When I printed it, I found that I spelled “laptop” as “laptpo”. Ouch! Whatever, I made it this far into the process with a typo, on my resume. On this plus side I did rig up this resume custom just for Google. Just goes to show that you cannot proofread or double check your work too many times.   I have a long document with all my skills in it, formatted the way I wanted my resume to look. When I want to apply somewhere I copy this document and delete out skills until it fits on one page. This only leaves the skills that the prospective employer cares about most. This is great because I can proofread the big document and benefit from it on all the resume I create later. Each employer I deem worth an hour of my time can get a custom version of my resume. It usually takes me about 15 minutes to snip the chaff, then about 45 minutes to put in company names and copiously proofread. I also made a generic PC Technician and Software Engineer Resume, for businesses that aren’t worth an hour of my time.   When printing my resume I always use some special kind of paper. I have been told that this make it stick out in the pile from other resumes. For this I purchased some 100% cotton 32# paper, it is thick, has a rich color and feels sturdy. Then I just printed it on photo paper. The photo paper is thicker, harder to rip, and this ink/paper combination is completely waterproof. I do not know if this works, but it can’t really hurt. I will post my interviewers reaction to a glossy waterproof resume later.   Next, I wanted to brush up on Linux and PC hardware skills. Not that I have let them lapse in any particular way, but I do not know everything. I started looking into Comptia’s practice tests and their Certification Objectives. I have taken countless A+ tests and passed them all, but judging by my knowledge of the objectives I am a little surprised I scored as well as I did. I studied the best I could in the few short days I had. Despite the objectives list, I feel that my real world experience will pull me through. For some scope on my experience, right now, in my house I have four computers I am fixing for other people. I will diagnose them all successfully, and suggest solutions to all the people who own them. I guess actually fixing computers is the best kind of study I can do.   I also searched for A+ practice tests, even though there are plenty out there I feel I came up empty handed. Most of what is out there is old and not worth studying. I stuck with Comptia as my guide, they had enough to fill my time well.   I asked three other people to ask me technical interview type questions. There where tons of technical questions, and there were Crazy Google interview questions. Many people have told me that an interviewer may throw crazy stuff at you just to see how you react. If this is true I think the worst things you can do is give up or say things like “I don’t know”.   I think the best way to respond to crazy questions is to give the kind of answer they are looking for and a creative answer. If a question relates to real world behavior then it may be wise to point out what could be done better to improve teamwork or leadership or one of those other key skills that all businesses are looking for. For example, on the bridge crossing question couple question from the crazy interview question page: I would start by explaining how I would carry the 10 minute guy because I would be the 2 minute guy or if he refused I would toss him the flashlight once I crossed. Then I would explain the ‘Proper solution’ which involves the fast people ferrying the flashlight back and forth so both the slowpokes can cross together to save time. Then finally. I would state that if the bridge is so unsafe that if a flashlight is mandatory to cross it and our flashlight has exactly the amount of time that we we need it, then it would be safer to wait until morning. My rationale is, if it is too dangerous to cross without the flashlight then it is too dangerous to mount a rescue mission when something goes wrong.   I will follow this up tomorrow with as much as I can say. I am sure that there will be mistakes, highlights and an amazing story about how I got my new job with Google. Original  story
Tags: , , , | Posted by Admin on 7/19/2009 10:28 PM | Comments (0)
If you’ve gotten through the first job interview and you’re moving on toward the second one, the odds of being hired have just gone up. With that in mind, you really want to be prepared for that second job interview. The questions will be tougher and things will be more complex in a second interview. Make sure that you dress appropriately and that you are on time. You probably did that for the first interview, too, but make sure you do it for the second one, since that’s likely going to be where the final decision is made about hiring you or hiring someone else who presented himself or herself better. If you find that you’ll be late for your interview for any reason, call ahead. Let someone know. That’s much more responsible than breezing in the door fifteen minutes after your scheduled appointment time and saying you’re sorry you’re late but traffic was bad, etc. Another thing you should do is make sure you know about the company before you go to that second interview. You can’t know everything, but you can Google the company and read what is said about it. You can visit its Website if it has one. You can also see if it has a Wikipedia entry. If it’s a big company, it probably does - and some smaller companies do, too. While it’s never wise to believe everything you read on the Internet, this kind of information will give you a lot of knowledge about the company overall, and you’ll notice things that don’t match up properly. If you’ve done anything very important in between a first and second interview, such as received an award or completed your degree, be sure to update your resume and bring the new one to your interview. There’s no shame in letting your potential employer know that you’re still moving forward with your goals. It shows your desire to work, and that’s important. Ultimately, relax and be honest at a second interview. Think about what kind of salary you’re really looking for, and know what’s common for that position. You might be asked about it. Honest answers are very important for success. This article was written by Tom Sangers on behalf of Martin Ward Anderson who offer recruitment services for finance jobs Original story
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 1/18/2009 3:39 PM | Comments (0)
Class, here is an organizational issue that we will be discussing this semester. How can economics help explain individual behavior suggest as hiring or resigning. In particular, we will talk about incentives and informational asymmetries. The article is from TechCrunch, one of my favorite tech sites. Given the importance of this topic for class, I have reproduced a good portion of the article below. For the complete article, you must go here. In 2008 Google HR set up a private Google Group to ask former employees why they left the company. We’ve been forwarded what appears to be authentic posts to the thread by a number of ex-Googlers, which we reprint below minus identifying information other than their first names. The thread shows a brutal honesty about what it’s like to work at Google, at least from the point of view of employees who were unhappy enough to resign. Top amongst the complaints is low pay relative to what they could earn elsewhere, and disappearing fringe benefits seemed to elevate the concern. Other popular gripes - too much bureaucracy, poor management, poor mentoring, and a hiring process that took months. A few of the posts are more positive, and frankly there isn’t a whole lot here that you don’t see in other big companies. One message stands out though in most of the posts - employees thought they were entering the promised land when they joined Google, and most of them were disappointed. Some of them wondered if it meant they were somehow lacking. One person sums it all up nicely: Those of us who failed to thrive at Google are faced with some pretty serious questions about ourselves. Just seeing that other people ran into the same issues is a huge relief. Google is supposed to be some kind of Nirvana, so if you can’t be happy there how will you ever be happy? It’s supposed to be the ultimate font of technical resources, so if you can’t be productive there how will you ever be productive? Original post
Tags: , | Posted by Admin on 12/31/2008 9:45 AM | Comments (0)
A couple years ago, there were some HR trolls or maybe some some resume bots that figured out that I went to MIT and that I was a software engineer from my blog (yes, this one). A recruiter from Google emailed me asking me whether I'd be interested in a position at Google. Um yes, isn't that every software developer's dream? That initial contact didn't amount to anything as there was no local office, but they called again recently when an office opened in Cambridge, MA. My initial phone interviews went great where I kibitzed with the HR recruiter. But they sniffed me out as a faker during the technical phone interview. It's not that I don't know how to program, but having no formal education (let's just say MIT's first programming class 6.001 made me swear never to be a SW engineer), I sometimes leave some of the nitty gritty technical details to magic. Since the software application I'm currently developing for work looks great and works beautifully, this is all I need! I have Google for the rest. I had heard many about many interesting recruiting techniques that Google uses to get the best and the brightest. One of them is the billboard for Solve the Equation, Get an Interview. Yup, way over my head too. Another is the Google Labs Aptitude Test which is a half-serious spoof with questions like "In your opinion, what is the most beautiful math equation ever derived?" Geek alert! Most of my technical interview went pretty well as we got along fabulously. The coding sample wasn't too bad, although I was not extremely creative with my answer (reverse the order of the elements of a array in place). Luckily, I dodged questions about pointers since I've only done C# in the last two years and feigned forgetfulness (nothing the feign there, it was never my strong suit). But then I got tougher questions like how would you design a smart pointer interface. Yikes! She seemed happy with my answer, although she corrected me in that the interface must track the number of instances (seems obvious after the fact). I was encouraged when she asked if I could go extra time beyond our allotted hour. The she asked how I would design an assertion class, to which I responded that I use exceptions and not assertions in .NET. I think that was the WRONG answer. I could hear the BZZT! buzzer going off in her head. Since we got along so well, near the end of the interview I confided in her that I have had really tough technical interviews in the past such as with SolidWorks, where they asked questions about vector geometry as well as programming. She responded that at Google, they need people able to solve those kinds problems as well. Oops (reminder to self, never be so chatty and self-deprecating during interviews in an attempt to be funny). Suddenly the interview was rushing to a close and I knew I had flunked. Needless to say, I received the email with "After carefully reviewing your experience and qualifications, we have determined that there is not a fit for a position," a few days later. I kicked myself for weeks afterwards on some of my answers during the interview. The one thing that I did get out of this experience was a glimpse into the life of a Google employee. I had been fascinated by their culture (and gourmet meals) ever since seeing the Time magazine photo essay Life in the Googleplex. My interviewer was a woman who has worked at the Google headquarters in Mountain View, CA for 18 months and previously worked at AOL in Virginia. She was a technical leader and seemed quite ambitious. She lived very close to the office and worked long hours although not everyone is expected to (obviously no kids). The group sizes at Google are small, around 2-3 people, and the reporting structure is very flat. They use Agile, Extreme, Scrum and/or Test-driven processes depending on the group's preference. They test their own programs against the Google framework, which is like NUnit, and release products whenever they are ready. It sounded like a really cool, flexible environment, but I'm not sure how this old fogey would stand up to all the young whipper snappers who can name the first 10 digit prime found in consecutive digits of e. 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 12/27/2008 10:27 AM | Comments (0)
I had a recent opportunity to do an interview with Google India! While preparing for the interview, the one thing that i would constantly look for, on the internet, was blogs on Google Interview Experiences so that i could learn about the pattern of the interview and the questions. Well, now that i have an experience of my own, i suppose its my turn to create a blog on it, too. Before i start with the details, i'd rather mention some dates - Oct 29th, 2008 - Day of 1st intimation from Google Nov 3rd, 2008 - 1st Phone Screen Nov 12th, 2008 - 2nd Phone Screen Dec 1st, 2008 - 3rd Phone Screen Dec 22nd, 2008 - Onsite Interview @ Google, Hyderabad First Intimation from Google! How did I apply? There was an opening for 'Software Engineer New Grad' post at Google Job Site. I added it to my job cart and applied. Additionally, i had got an email address of a Google recruiter from a friend. Few days after applying on the Google Job site, i sent an email to the recruiter too. That was around mid-october or something. Oct 29th, 12:15 pm. Previous day was Diwali. I was sleeping (since an hour only) when i got a call on my cell phone. It was from a Google Recruiter. She said that they had received my resume and got it reviewed with a couple of engineers @ Google. And they think that Google has openings for roles that suit my qualifications. So she wanted to set up a phone interview. It was scheduled to be held on Nov 3rd..   Oct 29th, 2008 - Day of 1st intimation from Google Nov 3rd, 2008 - 1st Phone Screen Nov 12th, 2008 - 2nd Phone Screen Dec 1st, 2008 - 3rd Phone Screen Dec 22nd, 2008 - Onsite Interview @ Google, Hyderabad First Intimation from Google! How did I apply? There was an opening for 'Software Engineer New Grad' post at Google Job Site. I added it to my job cart and applied. Additionally, i had got an email address of a Google recruiter from a friend. Few days after applying on the Google Job site, i sent an email to the recruiter too. That was around mid-october or something. Oct 29th, 12:15 pm. Previous day was Diwali. I was sleeping (since an hour only) when i got a call on my cell phone. It was from a Google Recruiter. She said that they had received my resume and got it reviewed with a couple of engineers @ Google. And they think that Google has openings for roles that suit my qualifications. So she wanted to set up a phone interview. It was scheduled to be held on Nov 3rd.. To be continued... Original story...
Tags: , | Posted by Admin on 12/26/2008 10:04 AM | Comments (0)
Was surfing through some blogs , and found this one interesting. Some of the questions asked by Google Inc. in their interview : 1. How many golf balls can fit in a school bus? 2. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do? 3. How much should you charge to wash all the windows in Seattle? 4. How would you find out if a machine’s stack grows up or down in memory? 5. Explain a database in three sentences to your eight-year-old nephew. 6. How many times a day does a clock’s hands overlap? 7. You have to get from point A to point B. You don’t know if you can get there. What would you do? 8. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? 9. This one is interesting. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? 10. In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop.What is the proportion of boys to girls in the country? 11. If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? 12. If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!) 13. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? 14. You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager? 15. How many piano tuners are there in the entire world? 16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings? 17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on hisplan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) Any answers??
Tags: , | Posted by Admin on 12/21/2008 2:27 AM | Comments (0)
This was originally posted in mathNEWS, a publication put out by students at the University of Waterloo. Pretty interesting stuff, good to read up on if you are going for a high end Google-type job. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time. Given a circularly sorted array, describe the fastest way to locate the largest element. Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k. Given an arbitrarily connected graph, explain how to ascertain the reachability of a given node. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers? Describe an API for a cache, with all of the associated function signatures. Provide pseudocode for the simple one. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you’d write the next() and hasNext() functions to work with the next negative integer instead of just the next integer. You are making an AI to play Tic-Tac-To. Make a function that takes a board position as an input and returns a good position to play. Describe how you’d represent the board, and how you’d determine where to play next. You are given 1001 numbers in an array. There are 1000 unique numbers and 1 duplicate. How do you locate the duplicate as quickly as possible? Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?. I have been in interviews that have asked very technical, industry specific questions. However they always tend to be more strait forward right or wrong questions. Never seen anything this open-ended before.