Google interview questions
1. Write a C program which measures the the speed of a context switch on a UNIX/Linux system?
2. Describe the algorithm for a depth-first graph traversal?
3. Design a class library for writing card games?<a href=”http://localhost/wordpress/wp-content/uploads/2012/10/file0001786983143.jpg”><img src=”http://localhost/wordpress/wp-content/uploads/2012/10/file0001786983143-225×300.jpg” alt=”” title=”file0001786983143″ width=”225″ height=”300″ class=”alignnone size-medium wp-image-59″ /></a>
4. How are cookies passed in the HTTP protocol?
5. Design the SQL database tables for a car rental database?
6. Write a regular expression which matches a email address?
7. 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?
8. 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?
9. Explain how congestion control works in the TCP protocol?
10. 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)?
11. 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.?
12. You can use only custom written applications or available free open-source software?
13. How would you find out if a machine’s stack grows up or down in memory?
14. Explain a database in three sentences to your eight-year-old nephew?
15. 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?
16. Write some code to reverse a string?
17. Implement division (without using the divide operator, obviously)?
18. Write some code to find all permutations of the letters in a particular string?
19. 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..)?
20. 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?
21. 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?
22. How do you convey the meaning of database in three sentences to a child?
23. What does Google do when you enter keywords and hit the return key?
24. How exactly does garbage collection work? Explain about three processes on three different platforms?
25. Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time?
26. Given a circularly sorted array, describe the fastest way to locate the largest element?
27. 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?
28. Given an arbitrarily connected graph, explain how to ascertain the reach ability of a given node?
29. If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?
30. Describe an API for a cache, with all of the associated function signatures. Provide pseudo code for the simple one?
31. 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?
32. 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?
33. 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?
34. Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?
Google interview questions