Google Software Engineer interview questions

* Write iterator class encapsulating in-order traversal of a binary tree. What is a time complexity? What is a worst case? * You have a collection of html documents grouped by a source web site . You need to count frequencies of bi-grams across all documents and present it in a sorted order (may be return top N frequent bi-grams). How would you approach it? How to filter out non-significant bi-grams? How to distribute and merge? What data structures to use to keep counters? * OOP. Write classes representing expression tree for a simple calculator. You care only about constants and basic binary operators. Write function evaluating expressions. * N clients - M servers. Each server can handle limited number of queries/sec. How to improve availability and performance ? * Write code to shift a string with rotation [a, b, c << 2 = 2 c, a, b] * How to count frequencies of characters in a string. What if the string is too huge? When is it reasonable to distribute across machines? How to find the most frequent character in the distributed scenario with a minimum data exchange between machines? * You are given a huge stream of geo coordinates. Unordered. Return list of objects in a specified radius from some point X.