My Amazon job interview experience

I just had an hour-long phone interview with an Amazon.com employee for the position of a Research Scientist. Here is a summary of the interview.

The interview began with a quick chit-chat about my resume and then dived into technical questions.

The first question was: Suppose a rabbit is hopping on a 2-dimensional integer lattice. It can only go left or up by one step at a time. The rabbit starts at (0,0), how many paths are there for it to reach (5, 5)?

I immediately realized the answer lies in a Pascal triangle. Unfortunately I stumbled a bit with the actual calculations and gave a number of wrong answers. With some help from the interview, I ended up using binomial expansion and gave the correct answer. Clearly I need more experience with conducting these interviews.

The second question was: We have developed a new algorithm and have conducted 100 trials of a benchmark test to compare with the original algorithm. The difference between the performances are given as real numbers, say 0.1, 0, -0.1, etc. How do you decide whether to adopt the new algorithm or not?

I was slightly unsure as to exactly what the interview wanted. So I began by pointing out that outliers may affect the mean. The interview clarified and added that the trials are exactly alike. I somewhat timidly replied that we can obtain a confidence interval on the performance difference using mean and standard deviation. The interview asked me how to calculate the mean and standard deviation, which I gave. He asked how to compute a certain custom confidence interval, which I responded with an integral of the appropriate density function. He then followed up with why it is reasonable to assume normal distribution, and I answered that because we are running 100 trials (which is a reasonably large to the outcome to ) and quoted the Central Limit Theorem (unfortunately I blanked out on the name of the theorem).

The third and last question was: Suppose you have n different colored balls in a bag. You blindly pick a ball at random, record its color, and put the ball back in the bag. After repeating this 100 times, how many colors are you going to see on average?

I began by pointing out that this depends on n. If n is much larger than 100, then we are likely to see 100 different colored balls. On the other hand, if we have just 2 balls in the bag, then we are almost guaranteed to see two colors. The interview then made the problem more specific by taking n to be 5. I realized then that he wanted a formula for calculating the expectation of this polynomial trial. I proceeded to calculate the expectation but my brain is no longer functioning at the time, and I blanked out for quite a while.

After some brief moments of silence that felt like an eternity, the interview suggested we solve some simpler cases of the problem to see if we can pick up some clues. So we worked out the case of picking just two balls. This was not much of a problem, but I again stumbled to come up with anything precise when we proceeded to three balls. I was definitely not pleased and pointed out the obvious that I am not in my best form right now. The best I could come up with at the time was that some induction together with conditional probability is going to resolve the problem.

Overall, I enjoyed the interview. The interviewer, who is a recent hire by Amazon, is a mathematician himself. I was more than pleased that there were no questions on computer science or operations research. My main setback coming into this interview is my lack of experience with these job interviews. I found myself scatter-brained at times trying to figure out how to answer the question in away the interviewer wanted. I also wish I was faster at solving the problems.

In any case, the ball is now in the interviewer’s court, and I gained some valuable experience. What else can I ask for?

Added April 11, 2012:

I figured out the answer to the last question last night. It just slowly came to me without much conscious effort. Here it is:

Let be the random variable that gives the number of different colors from selections with replacement from a bag of balls. We have that, for all positive integers and ,

where we set . Now multiply both sides by and sum over , we get

where is the expectation of .

A tedious but simple computation gives the recurrence relation

for and the initial condition . The closed form of is easily seen to be the geometric series:

.

Break through your mental limits

Humans are amazing machines. Today’s bike ride to Burnaby Mountain and Port Moody again confirmed this fact.

Recently I have been debating whether I am training too much and burning too much a hole inside. Workouts began to feel less like fun and more like work. They became a source of stress (mostly due to my lack of improvements, and the unpleasant feelings I began to associate with my workout sessions) and I’ve secretly dreaded workout on numerous occasions. But today’s ride made me realize a lot of these feelings are only mental. I need to believe in myself and my abilities, and break through these mental limits. Only then can I improve.

The ride began at 8:30AM, and I was not feeling quite up to it. In fact, I was feeling quite trashed the day before from a hard week of training. But I have already committed to the long ride, and I know I need to get some quality hard bike rides in for my upcoming races.

We began the official ride at the roundabout in Stanley Park. The group consisted of Brendan, Carl, Chris, Max, Winston, and I. Andrew and Christian also joined up for a bit, and then they headed to climb Mt. Seymour.

The group set a blistering pace once we crossed Lions Gate Bridge. Brendan and Chris led the group and were going at 40kph. I was doing my best to not get dropped too far behind at about 35-37kph. Drafting off Max did help a bit, but soon I began to drift back thanks to my screaming quads. It’s going to be a long day ahead.

Worried that I may get dropped to far behind, I actually thought about turning back; but I am moving into the build phase of my training, and really need to get some zone 4 long rides in. So I hardened up and told myself that at least I won’t die, and kept riding.

Things got a bit better once we got to Burnaby Mountain. Worst comes to worst, the others will wait for me at the top. So I settled into the lowest gear on my Orbea, which is still a challenging 39×23, and ground up the slopes. It was a relatively short climb, but was still a solid sufferfest.

Thanks to constant fueling and a solid base, I began feeling better and better as the ride went along. The way up to the two lakes (Sasamat Lake and Buntzen Lake) in Port Moody was again quite a bit of steep climbing, but I felt strong and kept pushing hard (but still not fast) throughout.

The next item on the agenda is lunch at Pajo’s. We all ordered fish and chips and stuffed ourselves good. The weather then took a turn for the worse and began to rain. We were not phased by the rain but we were concerned about how cold it is getting. Who knew? I thought it was going to be sunny all day.

Bracing ourselves for a cold ride back, we got on our bikes again. Shortly after we got on Barnet Hwy, the weather turned really ugly. The rain began to drop like a sprinkler and then hail began to pounding down on us. The quarter-sized icy patches mercilessly chipped at our beaten bodies and carbon-fiber bikes. Worried again about getting dropped, I hustled up and tried to keep in zone 4 as much as I could. But the fish and chips are not setting well with this hard effort. I felt slightly light-headed and uncomfortable. Yet I cannot stop laughing how ridiculous this is. I really broke through my mental limits today.

I have to admit that I am quite pleased with today’s ride. It was by far the hardest training ride I’ve done this year yet; in fact, it’s probably the hardest workout this year yet.

Equipment:

• Orbea Opal

Nutrition:

• 4 Scoops of Hammer HEED (Lemon)
• Hammer Gel in Flask (Chocolate, equal to 3 gels)
• 1 Clif Shot (Vanilla)
• 2 Pamela’s Whenever Bars (Oat Raisin Walnut Spice)
• 1 Mini Larabar (Peanut Butter Cookie)
• 1 Mini Clif Bar (Crunchy Peanut Butter)
• Small Fish & Chips at Pajo’s.

What does the term “satisfying career” mean to me?

I just came back from a career workshop put on by the UBC Postdoctoral Fellows Office. I saw it as an opportunity for me to get some affirmation about my career decisions and bounce some ideas off other people. Of course, it is also a semi-social event for me to share my experiences and ideas in this time of transition. The workshop was facilitated by Sally Halliday, and she did a fantastic job!

My main take away from the workshop is that I should not limit myself to a job title or a set of concrete skills, which may become obsolete; instead, it is better to identify myself with a set of abstract qualities and values, and pursue career options that best exemplify these values.

For future reference, I recorded below some of my discoveries from the workshop:

Who are you?

I am a learner and a doer. I am inquisitive and adventurous.

What three words best describe you?

Excellence, competitive, and

What do you want?

Live my life to the fullest. Experience all the wonders of life.

What do you have to offer?

Brains and sweat.

What does the term “satisfying career” mean to you?

• means doing work that brings out the best in me (challenging, engaging, and rewarding)
• lets me work with people who are optimistic and who seek excellence in all aspects of life
• lets me use my natural ability to solve real-world problems and discovery new things
• is done in an environment that is open, harmonious, and exciting
• doesn’t require me to work like a slave
• rewards me for quality work and strong results
• gives me opportunities to experience the wonders of life and live to my potential

Becoming a operations research scientist, step 0

Objective: My career goal for the next five years is to become an expert in applied probability, statistical analysis, and operations research.

The bucket list: Instead of pinning down a detailed plan, it seems more prudent to begin with a bucket list of what I believe (based on information available) to be the essential components toward achieving my goal.

• Programming skills: C++, Java, Python, R, SAS, Visual Basic, Excel, shell scripting, SQL, and Matlab
• Computer science theory: algorithms, database, OOP, programming project management
• Mathematics: probability, stochastic calculus, statistics
• Operations research: mathematical modeling, forecasting, game theory, optimization
• Personal qualities: consistency, focus, discipline, balance, passion

The next steps:

• Work through “Introduction to Computer Science and Programming” on MIT’s OpenCourseWare.
• Work through “Statistical Thinking and Data Analysis” on MIT’s OpenCourseWare.
• Work through Bruce Eckel’s “Thinking in C++: Volume 1”.

Some harsh but important advice I wish I knew before graduate school

My postdoc fellowship is scheduled to terminate by the end of July this year, and I am busy applying for a permanent job. Today I finally mailed out my application for the Directorate Post Doctoral Program at the NSA. A wrinkle in this application is the status of a recommendation letter from my doctoral thesis adviser. I have asked him for a letter about a month ago and still do not know whether he is going to write the letter or not.

Before you scoff at my naivety and imprudence, let me point out this is quite typical of him. Almost all the letters I asked of him are written “covertly” without any assurance or closure.

To be fair, my adviser is a great person and a superb mathematician, and has provided critical support when it really mattered; but working with him could be very frustrating since at times it feels that he is none existent. He rarely responds to my emails (then and now), and this can be quite unsettling–I am chronically worried that I may have accidentally offended or perhaps disappointed him somehow. (This is one of the reason behind my decision to not apply for any more academic jobs.)

I have gotten used to this slightly dysfunctional relationship, though. I felt neglected for a major part of my graduate education and have babbled a bit too much about my troubled relationship with my adviser. Even though I have had my Ph.D. for close to two years now, the moments of dissatisfaction with

With the status of his rec letter in limbo. I sought for some group assurance and moral support from the hive mind by googling “why professors don’t care”. Some very candid and sound advice from Professor Stephen C. Stearns from Yale University showed up and is very reflective my experience in graduate school:

http://www.eeb.yale.edu/stearns/advice.htm