A technical recruiter found my resume on my website, contacted me, and set up a phone screen.

The phone screen lasted one hour and consisted of three algorithm questions, with difficulty levels gradually increasing.

Then I did two on-site interviews.

The first on-site interview round consisted of six 1:1 interviews (five technical interviews and one technical-recruiter interview), each lasting about 45 minutes.

The second on-site interview round consisted of 3 technical interviews. Following the technical interviews on that day, I was made an offer.

For all the on-site technical interview questions:

• About 80% were algorithms/data structures (some interviewers gave a series of questions and asked me to code some of the algorithms I proposed; some interviewers gave one complex problem and asked me to design the algorithm and code).
• About 10% were OOP principles (e.g., when to use an interface and when to use an abstract class) and CS domain knowledge (e.g., how insertion in a B+ tree works).
• The rest were probability analysis and brain teasers.

I was also asked to give suggestions to improve the functionalities of the TripAdvisor website.

Technical-recruiter interviews were more like happy chats, letting me know more about the company, rather than asking me to answer questions.

The people I interviewed with were intelligent and energetic. The work environment is great: a spacious workspace, huge computer displays, free lunch, and a snack bar.

There are a chessboard, a rock band setup, a Wii, and a PS3 in the entertainment area.

They have shuttle buses to connect between the company and the Newton Highlands T station.

Given an array of coin value types and an amount N, write code to find the minimum number of coins which sum up to N.

You have a fixed list of words. Construct a data structure to achieve efficient (O(1) time complexity) prefix lookup. Write code to implement the lookup.

For example, the result of looking up "app" is {apple, applications, ...}.

You have a fixed file. The format of each line is: city name, ip address range. Construct a data structure and design an algorithm to achieve efficient mapping from an ip address to a city name.

You have one billion numbers. Implement getRandom() which returns a random number from them.

Constraints:

1. No duplicate returning values.
2. getRandom() will at most be invoked 100 million times.

Then optimize for space.

Implement the LRU algorithm. Write code to implement a general Binary Search Tree.