How did I prepare for Amazon Onsite Interview

Note: This post is not about the interview questions I was asked at Amazon. Its about how I approached the interview preparation. There are many blogs out there talking about their Amazon interview experience and the questions they were asked.

Fortunately, Amazon got interest in my profile and scheduled telephonic interview for SDE position. Couple of days before the interview, I was wondering what could Amazon (or anyone) ask me to code in 30min on phone? After thinking for a while, I came to a conclusion that they can't ask me to code problems that are long. At the same time they can't ask me silly questions like factorial! So I figured problems that have recursive solutions or problems on arrays and strings are a good fit. I was inclined more towards recursion because I like recursion!!! Well, anyone who has done fair bit of functional programming always thinks recursively! Imagine writing code without loops... Many problems on trees are fundamentally recursive an complex problems in trees can be solved recursively easily in short code. Turning them to iterative using stacks is interesting but hard to do over phone. I practised writing code for some tree problems recursively. I was always taking more than 30min which is not a good sign. I was worried about it. I also looked at Java collections and C++ STL data structures. Finally my first telephonic interview went successfully given that my basics in OS, algorithms, networking is good.

At this point I was thinking whether they are going to schedule 2nd phone interview or fly me to their office but not about being rejected! I was contacted in 2 days and scheduled 2nd round. This time I did solve some problems I found on the web. I was expecting some dynamic programming or graph questions but to my luck they asked simple question. But I never thought I could present 4 solutions to this problem. Presented theoretical analysis and covered edge cases well. I step back and say problems with my previous approach and why it occurs, how to correct it. After this round, I was sure they are going to fly me!

As expected, they asked me to visit their office for onsite interview. I have not prepared everything that I wanted. Under any circumstance, I didn't want to lose this opportunity. I wanted this job. So I planned for a week preparation (well 5 days only!). Here is my preparation for 5 days.

All the 5 days I practised solving and writing complete code. learnt that I'm making some mistakes. Writing one or 2 problems a day on the board and timing!.

Day 1:
+ Revise c++ and java languages.
+ C++
+ I/O, overloading <<, >> etc
+ String manipulation, bit manipulation.
+ Code using STL without reference.
+ Design and code OOP way. (virtual?) inheritance, polymorphism
+ operator overloading, functors, templates, exceptions,
+ exceptions, thread-safe, mutexes, locks, iterators,
+ internationalization wchar_t???, reference?, pointer?
+ friends, smart pointers, auto_ptr?, RAII?, casts?
+ new, delete[] implementation?, nothrow new, placement new?
+ stack unwinding, assert?, assignment op, copy constructor
+ custom memory allocators for containers like list, vector (Well, I didn't study this. just planned)
+ Java
+ I/O, String manipulation
+ Using collections java.util without reference.
+ OOP support. inheritance, static, access modifiers?
+ Threads, abstract classes, synchronization, exceptions
+ equals(), hash(), deep, shallow copy, type system?
+ know thread-safe, and unsafe classes?
+ design patterns used in collections.
+ aggregation, composition, association, has-a, is-a?
+ anonymous inner classes? comparator, comparable?
+ RTTI, JDBC?, garbage collection?, inner classes, generics,
+ reflections? (didn't revise. no time!)
+ c++ vs java.
Note: also coded standard algorithms that require stack, queue, priority_queue, map and hashtable both in c++ and java.

Day 2:
+ Operating Systems, Concurrency, OOP I
+ Processes
+ Threads, posix threads, mutexes, semaphores?, deadlocks?, livelocks?
+ synchronization primitives implementation, multicore?, barriers?
+ scheduling, scheduling algorithms, priority inversion,
+ classic thread synchronization problems, critical section.
+ virtual memory, demand paging, TLB, address translation, segmentation?
+ caching, page replacement algorithms, thrashing?,
+ file system implementation, inodes, buffer cache, inode cache,
+ block allocation schemes? trade-offs?
+ DMA, disk scheduling etc, interrupts, syscalls, traps? signals?

+ Basics of OOP, class design? UML? relationship? design principles?

Day 3:
+ Object Oriented Design II & Design Patterns.
+ Misc:
+ Basics of compilers
+ AI search, BFS, DFS, Iterative Deepening, UCS, A*,
+ graph coloring, inference?, min-max?
+ functional language? haskell? why? what they offer?
+ different types of languges and what they offer and what not?

Day 4:
+ Relational Databases, SQL, joins?, Regular Expressions in perl
+ Networking: different layers, functionality of each one, design choices?
+ TCP/IP???, routing, packet switched vs circuit switched?
+ DNS, DHCP, MAC, IP, ARP, RARP, ping? tracert? longest prefix match?
+ broadcasting, multicasting, unicasting, congestion control?
+ Revise Algorithms & Data Structures - part I

Day 5:
+ Revise Algorithms & Data Structures - part II
+ Divide & Conquer, Backtracking, Greedy, Dynamic programming
+ Graph Algorithms (yes Flow problems too!), Sorting and Searching,
+ Strings, suffix trees, tries, KMP substring, basic number theory, prime numbers.

.... I know that is long.... but I didn't want to miss this opportunity. At the end it was worth it. I was way confidant than before. Solved all arrays, strings problems on careercup at a rate of more than 1 per minute. Well I couldn't solve some in 5-10min also. Noted them down and solved at the end.

I did well in onsite interviews and hoping to hear good news soon. Few lessons I learnt during onsite interview.

• Solving problems on board didn't allowed me to think through the problem. Some programming errors were not obvious because code is all over the board and I couldn't get complete picture of what is written unless I step back a few times. Usually on computer, I can see full code and a bug easily attracts me.
• I write different parts of programs at different times. for example I dont write recursion termination condition first. I write after combining sub problems which are solved recursively. So writing on board was kind of trouble.

Good part is, interviews didn't last long. In 4 hrs I finished 5 interviews including lunch!. It was good experience, churning out code and design continuously without any delay. I must say people at Amazon are really bright and nice.

Note: I know the list that I presented in 5-day preparation is exhausting. Being aware of this stuff before makes life lot better otherwise I would suggest month time. This is how I prepared. I'm not expecting anyone to prepare all of this.