How to crack a design interview

I have written about my experience of interviewing for the SDE position of Amazon previously with focus on cracking the programming interview. Apart from the programming interview they give a lot of stress on designing systems.

I had little practice with designing systems so I followed a few basic principles to attempt the problems. Before talking about the principles let me start with a simple example on designing the game of chess.

If you start thinking about how you are going to model the movement of pieces on the board using some matrix then you are already on the wrong track. Forget about how you need to implement it, forget about the minor details and problems you might face in implementation. Design begins with getting the exact set of requirements. Keep asking questions before starting with the design. The conversation would go something like this…

• Is it an offline application or online application? Let’s say online
• Do we need to provide option to play with a bot? Not required right now
• Will a simple website without authentication, player profiles be alright? Yes, we can deal with it later
• Do you need a rating system? Yes, but not right now

So now we know that we need to make a website without any AI which would connect 2 human players and start a game of chess. Next step is to work on the flow of activities.

• Someone would open the website and host a game
• Wait for someone else to join the game
• As the game starts, black and white needs to be assigned
• Board needs to be populated with pieces
• White should be allowed to move first
• Pieces should be allowed to move on the board
• Turn should alternate
• Captured pieces should get removed from the board
• Checkmate position should be identified to end the game
• Special cases like castling, initial two step for pawn needs to be handled

Based on the above flow we can come up with a minimal set of modules to manage Game, Players, Pieces and Board. That’s our high level design. Creating classes out of each will give us the low level design. So there needs to be an entity “game” which will consist of entities “player” and “board”. “board” will contain multiple entities representing each of the pieces and also their positions on the board.

Adding functions in each of these entities to handle multiple gaming instances, movement of pieces and evaluating check-mate position will complete the implementation. All this can be summarised in the below principles.

1. Gather Requirements: Give some time towards understanding the problem. Cross-check with the interviewer to make sure your understanding is correct. If you are asked to design a well known system for example chess you can skip this step. For other systems where you aren’t sure about the functionality you need to thoroughly ask questions. Ask about the minimum features needed, any constraints, exceptional cases and scale of operation
2. High Level Design — Assign responsibilities: Once you have understood the requirements think of architecture. Divide the requirements into an exclusive and exhaustive set of tasks and assign a module for performing each of these tasks. Database discussion may or may not be needed at this stage.
3. Low Level Design — Deep Dive: After assigning functionalities to modules deep dive to create class diagrams followed by functions. Each module will have a bunch of classes. Think about the functions each class will need to implement and then iterate backwards towards defining the attributes
4. Implementation: This is the step where you programming and data structure knowledge will come into play. Decisions like using a linked-list or a simple array or a hashmap needs to be dealt with here. Note that it is the last step of the discussion. Architecture is the focus of this discussion and not implementation.

These principles will help you to solve basic design questions. To understand how to design highly-scalable systems for example twitter or facebook I would recommend reading Head First Design Patterns. This is the best book on the subject that I have read so far.