Last installment of the Google Interview Questions Series

This will be the last installment of the Google interview questions series. I think these interview questions are the best in terms of more search engine related. So without much ado, here you go:

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

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

* How would you compare two search engines?

* Write a function that takes a string and converts '%20' sequences to spaces (in place).

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

* How would you determine if adwords was up and running and serving contextual content?

* Describe the data structure that is used to manage memory. (heap / stack)

* Design a web server that serves the Google homepage. a) What are the requirements. b) Design a multi threaded web server that uses shared memory instead of disk access. c) Design a work load balancer for their data centers. d) Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP.

* What is multi-threaded programming? What is a deadlock?

* Describe Sorting algorithms and their complexity: Quick sort, Insertion Sort, Merge Sort.

* Given a list of numbers and a target sum, how would you efficiently determine whether a pair of numbers from the list can add up to the target sum? (list based approach is O(n^2) while hash-table based approach is O(n) )

* 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 the path to goal state.

* Design an algorithm which can find all the dictionary words correspond to a n-digit telephone number, assuming each digit maps to several alphabet letter.

* There are N stars in the sky, how do you find the closest pair?

* Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

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

* What are some trade-offs between a multi-threaded and single-threaded implementation?

* (string class) What do you need when you instantiate a string? (I said a byte array and possibly the length.)

* You have N threads and M resources. What protocol do you use to ensure no deadlocks occur?

* Lets 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?

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

* Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

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

* Explain a database in three sentences to your eight-year-old nephew.

* How many times a day does a clock’s hands overlap?

* 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 is 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 weightings?

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

* Explain a database in three sentences to your eight-year-old nephew.

* Calculate the Resistance in ohm's that a knights move would require on an infinite plane of resistors(forgot the resistance of each resistor, or whatever).

* What is the most beautiful equation you have ever seen? Explain.

* You have 10,000 Apache servers, and 1 day to generate $1,000,000. What do you do?

* Why are manhole covers round?

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

* What is the size of the C structure below on a 32-bit system? On a 64-bit?
struct foo {
char a;
char* b;
};

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

* Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. You are given:
--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)
--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.
--You can use only custom written applications or available free open-source software.