Weird, Smart and Simple Google interview questions

Weird, Smart, Simple and most frequently asked Google interview questions

1. What happens when you type www.google.com in your browser?
2. Write a short program to print all nodes in a tree, level by level.
3. Write a program to do a binary search in a sorted list, but the list is circularly shifted by an unknown amount.
4. Design a system that can generate order numbers with fault tolerant aspects included.
5. More questions on virtual functions in Java, inheritance, multi-threading, etc.; constant pointers in C++, etc.
6. Implement a hash table for concurrent programming
7. Delete an element from a binary search tree
8. Given a word, mutate it to convert it to a palindrome in linear time
9. Coin Change problem
10. Sometimes as simple an algorithm as Matrix multiplication
11. Explain a database in 3 sentences to your 7 year old nephew
12. How many golf balls could you fit into a classic American school bus?
13. How many petrol stations are there in the USA
14. Algorithm based questions
15. What is your favorite Google product and why
16. What are all the possible outputs of this code/ report error if any
17. How many golf balls can fit in a school bus?
18. You are shrunk to the size of a nickel and thrown into a blender with a moving blade. How do you get out?
19. How many times a day does a clock’s hands overlap?
20.  You need to check that your friend, Bob, has your correct phone number but you cannot ask him directly. You must write the question on a card 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?
21. "How many bottles of wine are sold in Dublin?" 
22. Do you blog?" (I don't.) "Why not?"
23. "What is your favorite website?"
24. Given is number N. Create a function that calculates N−−√N.
25. Given is array containing N numbers, A[0], A[1], ... A[N-1]. Compute the array B of length N, such that B[i] = A[0]*A[1]*...A[i-1]*A[i+1]...*A[N-1]. Algorithm should work in time O(N) and can't use division.
26. Given is sequence of numbers: 1, 11, 21, 1211, 111221, ... Find out how the sequence works and create the function to compute the next element.
27. Given is array A containing N numbers. Find three different indexes i,j,k, such that A[i]+A[j]+A[k] == 0. Algorithm should work in time O(N^2).
28. Given is matrix M of size X*Y, filled with integers. Rows and columns of the matrix are sorted in ascending order. Find the number of zeros in the matrix in time O(X+Y).
29. You will be given N numbers, one at a time. Each time you are given a number, write out the median of numbers you already have. Total time of algorithm should be O(N*log(N)). You should also argue why it cannot be O(N).
30. There are unknown number of objects given to you, one at a time. At each moment you can decide either to keep the new object and throw away the one you already have, or throw away the new object and keep the one that you already have (i.e. you can only use constant memory). Pick up the random object with uniform probability.
31. You have a short string A and a long string B. Count the number of occurrences of A in B. Describe possible algorithms that can achieve this task in fast time. What if you had more short strings, A1, A2,...AN?
32. Then there are many questions testing just implementation skills that require only backtrack to solve them:
33. A person writes a query into a search box. He can of course mistype some of the letters. You are give the list of possible typos, e.g. doubling some letter (typo vs. typpo), not doubling some letter (written vs. writen), etc. You are also given the dictionary of valid words. Generate all the possible words, that the person could have wanted to write.
34. You have thousands of computers that process some tasks. To store the results of the tasks, each task has to be identified by unique ID. Design a fast and reliable system to distribute these IDs to computers.
35. For a member function of some object: const int * Object::f(const int const * v) const                                                                                {...}explain what each const means 
36. Explain how do virtual functions work

Source: Quora