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: algorithm, questions, puzzle, software engineer, tech leader, |
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?
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: interview process, interview process, |
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: c++ questions, algorithm, |
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: interview process, |
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?)
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.

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.

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: san francisco, interview, |
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: interview process, |
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’….
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: dress code, management, interview process, |
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: interview process, |
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: iq, interview process, |
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.
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?

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

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?

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: interview process, tips, |
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: interview process, resume, tips, |
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: interview process, first interview, phone interview, |
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.
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: interview process, |
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: questions, phone interview, |
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: questions, phone interview, |
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: questions, phone interview, |
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: interview process, |
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...
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??

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.

- Next posts
- 1
- 2
- Previous posts