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.) http://savenseek.com/page/Microsoft_Google_Algorithm_Interview_Questions__brainDead 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.