** What are good ways to answer interview design questions? **
** Cited from Quora **
https://www.quora.com/What-are-good-ways-to-answer-interview-design-questions
There are 2 sorts of design interviews:
- System design. Eg: Design a twitter like system, which should let users post some sentences and these then be published to other users.
- Class design. Eg: Design how you'd represent a Football tournament.
Let's see how you should walk through each of these types of questions:
-- It's clear the system supports "users". Clarify what else the system should let a user do - can he find friends / follow people / etc. What are some limits on how quickly a post by one user appears in someone else's feed?
-- Come up with high level components for this system.
--There needs to be a data store (DB or key-value store) that stores user data, people he follows etc. Each of these relationships might be in the same table or be broken into multiple tables. The relationship might have attributes and those need to be put in somewhere too. Basically I'm looking for some db design skills here and need the interviewee to come up with a good table design.
--There needs to be a front-end for the user to view/login etc. and a backend that talks to this data store (or it could be a 2 level system with the front end directly talking to the datastore). I expect the candidate to talk about the pros/cons of the two approaches --What is a good mechanism to send posts from a user to others? A queue? Or can it be modeled using the same datastore? Is it advantageous to use a queue so that it can be extended to publish to third party people at some time in the future?
-- Is a cache needed? What would it store, what is its eviction policy etc.
-- What about security of this system. I'd expect the candidate to atleast come up with some validation at the entry points of each of these components. -- And so on. Notice how the discussion revolves around a very high level design of different components and usually involves discussing data storage and scalability.
For 2, here's what I'd expect:
-- Clarify how the tournament is going to proceed. Find out the major "entities" that you need - each of these will mostly end up being a class of its own. It will typically have league matches, quarterfinals, semis leading upto the finals. There were will be different types of participants - teams, players, coaches, referees, cheerleaders, presenters and so on. Matches will have venues, competing teams, a referee, result, statistics, list of players with red cards etc. and so on.
-- You'll end up with a bunch of classes with some relationship between them (base and child classes or composite ones - isA or hasA relationship)
-- Now that you have a set of classes, start with the major ones and figure out what methods /operations make sense of each of them and write down a method signature. The interviewer will mostly restrict the discussion to a few major classes and just the major methods on each of these classes. - Eg: Tournament.createSchedule(), Tournament.getStatsForMatch(), Match.calculateStats() etc.-- Next, think about the best data structures to be used inside each of these classes so that the methods can work efficiently. Notice that here, we discuss about OO concepts, polymorphism, implementation details inside a class etc. There's more focus on extensibility of a class and correct representation of concepts, rather than a focus on scale.Hope this helps!
As mentioned earlier in one of the posts that a design question can be of either a high-level system design for e.g. design a chat application, or the low-level classes and methods.
For a high level system design some things that should be handled well are Speed, Reusability, Scalability, Availability and Security.
Reusability comes from the software architecture, design patterns, classes and data structures. How modular your class methods are ? Usage of proper abstraction (abstract classes and interfaces) ? Correct visibility of classes and methods (private, public, protected wherever necessary) ? Handled class and package dependencies properly ? Any framework used MVC etc. ? and so on...
Scalability comes from handling of large amount of data and handling large number of requests effectively. Multiple web servers serving requests ? How is database designed and managed ? Proper indexing of database tables ? Caching of requests handled properly or technologies used for caching ? Master-slave configuration ? Multiple nodes ? Usage of NoSQL to avoid joining tables ? Hadoop or MapReduce design patterns for models ? Knowledge of what is persistent data and what should be kept in memory ? How to read persistent data effectively ? and so on...
Speed comes with improving application performance, views loading faster. Lowering of server latency using Memcache, Redis etc. ? UI components handling for web page requests (separate css, js files, CDN serving images, lazy loading of images) ? Avoiding costly database queries and using Session variables and cookies wherever necessary ? Caching of web pages on browsers ? and so on...
Availability comes from how fast you can recover from failures. Multiple servers ? Backup databases ? Round robin server request handling ? Proper logging mechanisms ? Efficient log file reading ? Log rotation ? Proper "downtime" messages for users and so on ...
Security comes with strong authentication and encryption maintained. HTTPS ? Prevention of XSS and MySQL injection attacks ? Two step verification of user input data ? Proper cleansing of user input data (is it what is only required) ? Captcha ? Securing api's using HMAC and nonces ? Strong passwords only ? Proper access rules for files defined in .htaccess ? Proper permissions of the code base ? and so on..
Now for the design of classes and methods, one should properly identify the entities in the problem. Define the entities in their appropriate classes. Create abstract classes and interfaces wherever the entity is an abstraction and can be reusable by overriding. Classes used as data structures should be efficient i.e. possibly lowest runtime complexity for methods. Usage of polymorphic methods to handle flexible requests. Encapsulation of algorithms in separate methods and classes. Define a method such that it does only what it is supposed to do. Handling thread safety. Where static classes and methods were used and why ? Final and Immutability for required variables. What design patterns used if any ? (e.g. Factory pattern) and so on..
In a nutshell, I'd suggest people first make the problem more well-defined. Twitter is a huge product and we should clarify the scope of discussion. For instance, we can set the goal to design only core features of Twitter - follow relationship and browse feed.
Secondly, high-level idea is preferable. Don't try to dive into all those details. Instead, try to provide high-level ideas about how to solve the problem. You may explain how to model the user relationship and how to store/serve feeds.
Lastly, we can discuss in depth about specific issue. While discussing, interviewers might be interested in particular detail and the discussion will go deeper to that topic. I covered few examples in the post as well.
It's worth to note that for system design interview, specific techniques like whether to use EC2 or Heroku, whether to use AngularJS or ReactJS, which backend framework to choose etc. are not important at all. What really matters is the more general and basic ideas about how to design the whole system.
Key concept
Thread-safe (with respect to a piece of code)
A piece of code is thread-safe if it only manipulates shared data structures in a manner that guarantees safe execution by multiple threads at the same time. There are various strategies for making thread-safe data structures.[1]
[2]
A program may execute code in several threads simultaneously in a shared address space where each of those threads has access to virtually all of the memory of every other thread. Thread safety is a property that allows code to run in multi-threaded environments by re-establishing some of the correspondences between the actual flow of control and the text of the program, by means of synchronization.
Implementation approaches(wiki)
- The first class of approaches focuses on avoiding shared state, and includes
- The second class of approaches are synchronization-related, and are used in situations where shared state cannot be avoided
synchronization
In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data.Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action. Data synchronization refers to the idea of keeping multiple copies of a dataset in coherence with one another, or to maintain data integrity. Process synchronization primitives are commonly used to implement data synchronization.
Thread synchronization is defined as a mechanism which ensures that two or more concurrent processes orthreads do not simultaneously execute some particular program segment known as critical section. When one thread starts executing the critical section (serialized segment of the program) the other thread should wait until the first thread finishes. If proper synchronization techniques[1]
are not applied, it may cause a race condition where, the values of variables may be unpredictable and vary depending on the timings of context switches of the processes or threads.
v
