Answered Questions

Write a function that outputs an integer in ASCII format.

char c;

int ascii = (int) c;

(string class) What is the best and worst time for the operation ‘equals’?

Best = O(1), worst=O(length)

(string class) How do you spe.ed up the ‘equals’ operation?

(I said use a hash, MD5 for example)

This still has some problem (a hash can be the same for unequal strings)

-> Use Boyer–Moore string search algorithm => O(n)

To beat O(length), the hash must be computed faster than that.

If you have the lengths available, compare those first.

If you know something about the strings you have, then structure the compare to take advantage of it.

Possibly start comparing at the end of the string, for instance, if you know they likely have common prefixes.

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 ?

suffix tree can be used to index all suffixes in the long string

in order to carry out searches for the small strings

information and algo can be found in Wikipedia

A solution I found in some other site, by “goit”:

1 – Create a hashtable/hashmap data structure and put the L small strings in it using the string as a key and

value as count (initially 0) -> O(L)

2 – Traverse the string of length N and for each traversal take the next substring of length L from the current

char position. Check the substring in the hashtable (lookup hashtable is O(1) or constant time) and if it

exists increment the count/value. -> O(N-M) why N-M because we need M length substring.

3 – Traverse the hashtable and print those keys/strings whose value is greater than 0. -> O(L)

Therefore, the overall time growth of this approach is 2*O(L) + O(N-M), which is a linear growth in O(n)

Write some code to reverse a string.

void StrRev( char* str) {

char* strEnd = str + strlen(str) – 1;

while ( str < strEnd )

{

char tmp = *str;

*str     = *strEnd;

*strEnd  = tmp;

str++;

strEnd–;

}

}

Describe an algorithm to find out if an integer is a square? (e.g. 16 is, 15 isn’t)

a) simple answer – start at 2 and divide the integer by each successive value.

If it divides evenly before you reach half way then it is.

b) complex answer after much leading – Do the bitwise AND of n and (n-1).

If it is zero then it is a square (I think this is wrong. This actually tests whether n is a power of 2).

No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2.

More info: ~seander bithacks.html#DetermineIfPowerOf2 (graphics.standford edu)

C)

i=2;

while(1)

{

if((i*i)==Number)

{return True;}

if((i*i)>Number)

{return false;}

i++;

}

Here is some code to find out if a number is a square. For even numbers this is a simple recursive function. For odd numbers it is slightly more complex.

1. Submitted by: Anand

2. Find out if an integer is a square

import math

def is_member(n):

# Return if number n is a member

# of the series defined by

# P(n) = n*(n+1)

for x in range(n/2, 2, -1):

N = x*(x-1)

if N==n: return True

elif N<n: return False

def is_square(N):

# An even number is like 2*p so

# its square is 4*p*p. So if N is an

# even number and a square it will be

# divisible by four and the answer

# also have to be a square. So calling

# this recursively have to finally yield

# 0…

# Trivial cases,

if (N==1): return True

if N %2 == 0:

if N % 4 == 0:

N = N/4

return is_square(N)

else:

return False

# For odd numbers (2*p + 1), the square

# is 4p2 + 4p + 1, which means that N-1

# should be a multiple of four. Since

# N-1 = 4p2 + 4, (N-1)/4 is p*(p+1)

# which has to be an even number. Also

# this even number should be of part

# of the series defined by P(n) = n*(n+1)

else:

# Only numbers ending in 1,5 and 9 can

# be squares…

rem = N % 10

if rem not in (1,5,9): return False

M = N -1

if M % 4 == 0:

q = M/4

# If this is an odd number, return False

if q % 2 != 0: return False

# This number has to be of the form

# p*(p+1)

if q == 2: return True

else: return is_member(q)

else:

return False

Here is an efficient solution in C:

int squareTest(int number)

{

int n, m, p;

if (number <= 0) return 0;

// shift off half of the bits

n=m=number;

for(m=m>>1; m; m=m>>2) n=n>>1;

// n is our first estimate for the binary search:

n = (n + number/n) / 2;

do {

p = n;

n = (n + number/n) / 2;

} while (p-n>1 || n-p>1);

// if n!=p, it isn’t square either

return (n*n == number);

}

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?

Hash it. Take every shirt, and put it in a different drawer depending on

the color of the shirt. Whenever you want a shirt, all you have to do is

simply open the drawer with the corresponding color.

More at: http://alien.dowling.edu/~rohit/wiki/index.php?title=Google_Interview_Questions

Some time back I interviewed with Google, and a number of other well known software development companies. I’ve written up a number of questions very similar to the ones I was asked, changing them enough so that I’m not breaking my NDA.

Q: Why are manhole covers round?

Q: A man pushed his car to a hotel and lost his fortune. What happened?

Q: Explain the significance of “dead beef”.

Q: Write a C program which measures the the speed of a context switch on a UNIX/Linux system.

Q: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Q: Describe the algorithm for a depth-first graph traversal.

Q: Design a class library for writing card games.

Q: You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Q: How are cookies passed in the HTTP protocol?

Q: What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {
        char a;
        char* b;
};

Q: Design the SQL database tables for a car rental database.

Q: Write a regular expression which matches a email address.

Q: Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

Q: You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

Q: Explain how congestion control works in the TCP protocol.

Here’s one that someone sent me in email. I’ve outlined a possible solution, but I haven’t thought through the problem very well. Here’s the question:

Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. You are given:

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 are approx. 8 billion search terms per log file (320 GIG / 40 Bytes). Each computer can return it’s top 1 million search terms to a central server at a cost of 48MB each because 40 Bytes * 1 million = 40MB, plus a 8 byte unsigned integer occurrence count for each search term. The combined top 1 million results from each log take only 520 MB, so there is plenty of space on any single computer to merge the 12 million entries together and come up with top 1 million. So, the only missing part at this point is how to efficiently count the search term occurrences on each computer, and return the top 1 million (this same algorithm can be used for merging the 12 top 1 million, too). A hash table may be a bad idea. With this many search terms and only 4GIG of memory, hashing the search terms would cause a lot of collisions. You want to use a tree, not a hash. Order ln(n) should work well for the search term lookups (if it’s good enough for the STL maps, it’s good enough for me, right??!!). Now, we know that we need to produce the top 1 million results, but there are potentially 8 Billion unique search terms per log, and a minimum of 1 unique search term per log (what are the chances you get 8 billion searches for ‘porn’ or ‘sex’ on a single log? Not much, but it is a formal possibility. At the very least, such a case would make a great unit test for your program), either way, you could blow a 32 bit unsigned int trying to count them… So, we do have to use unsigned longs. That increases the size of the search term count to a long-int, 8 bytes instead of 4. With 4 gigs of memory, how many log entries can be counted at a time? 1 unique term will take 40 bytes, + 8 bytes for the count, two pointers for the left/right nodes of the binary tree (+ 8 bytes or + 16 bytes on a 64 bit system). Let’s only assume you can use 3.5GIG of the 4GIG of memory, so that’s 3.5/64 = 0.0546 GIG, or about 54 million. So, here’s the stratagy:
1) go through the log, and count the occurances of search terms found using a binary tree for search term lookups, and a long-int for the counter. Do this unil you have 54 million unique terms in your tree. Write a marker into the log file for each search term used so that further passes know it has been counted.
2) transmit the tree over the network to the next computer and count only the search term occurances which are already in the tree, marking any counted in the logs as such; then transmit the tree to the next and repeat this process until the tree has passed through each computer and ends up at the computer WHERE THE FIRST UNQIUE SEARCH TERM WAS ADDED TO THE TREE(more on this in the next step). Heap-sort the tree by search term occurance number (why not, it’s already in a binary tree — that’s great for heap-sort!). Truncate the tree to 1 million search terms, and write it to disk.
3) Every time a tree of unique search terms has “filled up”, that is, the tree contains 54 million unique search terms, a new unique-search term tree must be built and sent to each computer so that the terms can be counted. A tree might begin near the end of a log on one computer, and be sent to the next computer with less than the 54 million unique search terms. When this is the case, the tree will continue to collect unique search terms from the log on the next computer.
There are two processess occuring in this algorithm which travel in rings around the computer network until they reach the computer at which they began. The first process travels from computer to computer generating these unqiue search term trees (call this process #1). Once a tree fills up with unique terms, it breaks off from this process and is sent around the ring to count the search term occurances for terms which it already contains (call these processes Tn, there can be many). Once process #1 reaches the computer where it started, it quits. Once all the Tn processes have traveled the ring, they quit also after writing their top 1 million search results to disk in sorted order. The search terms in these files are all unique and accurately counted. Just start popping search terms off the top of these logs by the highest occurance count until you have 1 million search terms. That should be it.

From http://www.drizzle.com/~jpaint/google.html

• Given a number, describe an algorithm to find the next number which is prime.
• There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find out the heaviest stone ?

Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If the pan is remains balanced, the heavier is in the remaining (2). use pan again to find which is heavy from (2). (Total pan use 2)

If the pan does not remain balanced when weighing (3,3), pick the set of stones that outweigh other. Divide it into (1,1,1). use pan to weigh first two. It it remains balanced, the remaining stone is the heavier, otherwise the one outweighing other is heavier(total pan use 2)

[These questions from 'Taher']

• Order the functions in order of their asymptotic performance

  * 2^n
  * n^Googol ( 10^100)
  * n!
  * n^n

Answer: n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n

• what is the best and worst performance time for a hash tree and binary search tree?

Answer:
Best is O(c), worst is O(log n)

• Questions regarding a string Class

  * What do you need when you instantiate a string ( i said a byte array and possibly the length) ?
  * What is the best and worst time for the operation 'equals'
  * How do you spedup the 'equals' operation (i said used  hash  MD5 for example)
    This still has some problem ( a hash can be the same for unequal strings)
    -> Use Boyer–Moore string search algorithm => O(n)

• Trade offs between a multi threaded and single threaded implementation ?
• N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
• There are a set of ‘n’ integers. Describe an algorithm to find for each of all its subsets of n-1integers the product of its integers.

For example, let consider (6, 3, 1, 2). We need to find these products :

• • 6 * 3 * 1 = 18
  • 6 * 3 * 2 = 36
  • 3 * 1 * 2 = 6
  • 6 * 1 * 2 = 12

last one is simple

int mul = 1;
for i = 1 to N
mul *=a[i];

for i= 1 to N
a[i] = mul/a[i];

(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this.

Here’s the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output

for (int i = 1; i <= n; i++)
{

  if (i == 1)
       print x[2,n];
  else if (i == n)
       print x[1,n-1];
  else
       print x[1,i-1] * x[i+1,n];

}

To build the table, start along the diagonal (x[i,i] = ni). Then do successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k+1]).

• 1. Describe Sorting algorithms and their complexity – Quick sort, Insertion Sort, Merge Sort
• 2. If you had a million integers how would you sort them and how much memeory would that consume?

Binary tree – requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB
Insertion sort – can be done in under 4 MB

• 3.Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn’t

a) simple answer – start at 2 and divide the integer by each successive value. If it divides evenly before you reach half way then it is.
b) complex answer after much leading – Do the bitwise AND of n and (n-1). If it is zero then it is a square (I think this is wrong. This actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info:http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

C)

i=2;
while(!NO)
  {

       if((i*i)==Number)
          {
          NO;
          return True;}
       if((i*i)>Number)
          {
           NO;
          return false;}
    i++;
 }

• 4. How would you determine if adwords was up and running and serving contextual content ?

5428907816463810488188

Here are some questions I got on my first interview with Google (slightly altered for NDA reasons).

• 1 Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.

• 2 Write some code to reverse a string.

• 3 Implement division (without using the divide operator, obviously).

• 4 Write some code to find all permutations of the letters in a particular string.

• 5 You have to get from point A to point B. You don’t know if you can get there. What would you do?

• 6 What method would you use to look up a word in a dictionary?

• 7 Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you

do to organize your shirts for easy retrieval?

• 8 You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?

External Links

www.technical-interview. com Google Interview Questions

Phone interview

1. Describe the data structure that is used to manage memory. (stack)

2. whats the difference between local and global variables?

3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)

4. In Java, what is the difference between static, final, and const. (if you dont know java they will ask something similar for C or C++).

5. Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).

In person interview

1. In Java, what is the difference between final, finally, and finalize?

2. What is multithreaded programming? What is a deadlock?

3. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).

4. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.

5. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.

6. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.

I had a phone interview with Google today. I took notes; some of the questions they asked were interesting. We were allowed to ask questions. The interviewer didn’t ask many questions in response to my answers, except to occasionally say “interesting”. There’s almost certainly more than one answer to each of these, and a few are probably wrong answers or could be improved in some way; I only include my answers for comparison. Any intermediate questions that I asked for clarification or otherwise have been omitted.

Without further ado, a few of the more interesting ones:

Q: “You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?”

(my answer): Take off all my clothes, wedge them between the blades and the floor to prevent it from turning. Back up against the edge of the blender until the electric motor overheats and burns out. Using the notches etched in the side for measuring, climb out. If there are no such notches or they’re too far apart, retrieve clothes and make a rope to hurl myself out.

Q: “How would you find out if a machine’s stack grows up or down in memory?”

(my answer): Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function’s local is higher, the stack grows away from address location 0; if the function’s local is lower, the stack grows towards address location 0. (If they’re the same, you did something wrong!)

Q: “Explain a database in three sentences to your eight-year-old nephew.”

(my answer): A database is a way of organizing information. It’s like a genie who knows where every toy in your room is. Instead of hunting for certain toys yourself and searching the whole room, you can ask the genie to find all your toy soldiers, or only X-Men action figures, or only race cars — anything you want.

Q: “How many gas stations would you say there are in the United States?”

(my answer): A business doesn’t stick around for long unless it makes a profit. Let’s assume that all gas stations in the US are making at least some profit over the long run. Assume that the number of people who own more than one car is negligibly small relative to the total American population. Figure that 20% of people are too young to drive a car, another 10% can’t drive because of disability or old age, 5% of people use public transportation or carpool, another 5% choose not to drive, and another 5% of the cars are inventory sitting in lots or warehouses that a dealership owns but which no one drives.

There’s about 280 million people in the US; subtracting 50%, that means there’s about 140 million automobiles and 140 million drivers for them. The busiest city or interstate gas stations probably get a customer pulling in about twice a minute, or about 120 customers per hour; a slower gas station out in an agrarian area probably sees a customer once every 10 or 15 minutes, or about 4 customers per hour. Let’s take a weighted average and suppose there’s about one customer every 90 seconds, or about 40 customers an hour. Figuring a fourteen-hour business day (staying open from 7 AM to 9 PM), that’s about 560 customers a day.

If the average gas station services 560 customers a day, then there are 250,000 gas stations in the US. This number slightly overstates the true number of gas stations because some people are serviced by more than one gas station. [Actual number in 2003, according to the Journal of Petroleum Marketing: 237,284, an error of about 5%.]

P.S. Apparently, if you make it to the next stage, you can’t even tell people you’re interviewing, because you sign a 6-page NDA. I haven’t had to sign anything yet, though.

From http://www.gamedev.net/community/forums/topic.asp?topic_id=299692

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

Tihomir.org

from: http://jhorna.wordpress.com/2007/09/08/google-interview-questions-fun-brain-teasers/

Google’s mission: Organize the world’s information and make it universally accessible and useful.
From: http://labs.google.com/why-google.html

Google is an engineering company. The Google web site is powered by some amazing technology, most of it developed in-house. Yet people often ask us what we do here at Google Engineering. “What are you working on? Isn’t search a solved problem?”

Glad you asked.

We’re working on lots of interesting stuff and one of the main reasons is that search is far from a solved problem.

Perhaps you’re interested in Norse mythology and search for information about “Thor”. The results page shows “Results 1-10″ out of millions of links. That seems like a lot of information, but look at the results. Mixed in with information about the god of thunder there may be links to sites about medical equipment companies, bus builders, comic superheroes, even a movie. To someone looking for those other Thors, the Norse god is less interesting; to you, though, it’s the other way around. Google prides itself on its algorithm for choosing the most relevant pages, but search has context, which is just one of the considerations in choosing the right results. Plus, the top pages listed are all in English; surely there are some interesting web pages in Norwegian (or even Old Norse) that we could translate for you, and chances are at least some of them deserve high ranking. And whether we’re asking about the god, the superhero, the equipment, or the movie, there should be images, maybe movies or animations, and other rich content available; how do we find that? Plus there are many other sources of information about Thor (the god) that the web doesn’t reach: ancient sagas, oral histories; who knows? So yes, Google is very good at searching the web for relevant pages for the query you type, but the web isn’t enough and `relevant’ is a relative term. The search problem remains far from solved. Read the rest of this entry »

A friend of mine had an interview a couple weeks ago with Google Inc. He provided me a list of just some of the questions he was asked. I’ve added a few more from others I have talked to who had interviews with the internet giant, Google, as well. See if you can answer them. Many are open ended with several right answers, therefore I did not provide the answers.

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

Do you still think you have what it takes to work for Google?

http://tihomir.org/crazy-questions-at-google-job-interview/

I didn’t expect the story of My Interview With Google to be a two-parter, but it turns out the story didn’t end where I expected.

Not too long after I made the post, it was submitted to Reddit.com where it enjoyed front-page status for two days. During that time, I got a lot of visitors and a lot of comments, some even from Google engineers.

I also got a private e-mail. It was from someone at Google. He explained that my post had been circulating around the Google office and when it got to him, it piqued his interest.

Essentially, he wanted me to come work for him in Mountain View. He was looking for Java folks for his team, and he thought I’d be a good fit. I jumped out of my chair when I read this, amazed some additional life had been breathed into my foray into the world of Google. The more I considered the e-mail, however, the more a part of me wanted to say no. Why? Read the rest of this entry »

Update: Apparently this site (talking about the ways in which people blew their Google interviews) links to me, and also used my picture. It kind of sucks that an article titled “How I Blew My Google Interview” has my face on it, but that’s what happens when you put a picture on the internet, I guess. More disconcerting to me is that the portion of the article below that was highlighted was my discussion of my interview with the guy with the thick accent. The implication of the linked article is that I blew the interview by not understanding him. I’d like to clarify, that part of the experience was just a relevant part of the story, which is why I shared it. I blew the Google Interview not for that reason, but because my algorithm skills simply were not up to snuff at the time. Blaming the rejection on having a hard time with accents would be petty and silly. I was rejected because I wasn’t good enough, plain and simple. Read the rest of this entry »

With Google positioning itself to be “the new Microsoft” – to be understood as gaining a place in the mind of the SEC, the media, the developer community, the business student, rivals, and prospective employees as the most popular/dominant/challenged/feared/innovative software company in all the land – it’s no far reach to say that a heckuva lot of people are going to want to work there (myself included), and that opportunities will abound.  One thing I remember about interviewing with Microsoft a few times was how legendary & intellectually rigorous the interview process was, all by design.  I’d thus like to know in contrast how difficult Google makes it for justifying one’s qualifications for varying positions. Read the rest of this entry »