Machine Coding Round has become very popular interview round in most Product and startup companies like Flipkart, Cleartrip, navi and Udaan,the way the round is structured is the candidate will be provided with a Problem statement and the minimum set of features which needs to implemented within the 90 min window period, we as a candidate need to identity the data models, the service interfaces which will be consumed by the clients and other set of functions and classes, we should be able to present the same to the panel with are design choices / design patterns being made / used and the complete working code.
During my recent Preparation, found out that there was no single resources where we get a collections of all the questions and the corresponding Answers, so currently updating the repo with all the materials I found out from the web and the Questions which has been asked during my interview. feel free to contribute any questions you have got during your recent interview.There other useful YT channel and Git repo which are attached in the resources section.
If you are currently targeting/looking out for any SDE - I,II opportunities. It totally depends on the company you interviewing with, you can check with the HR if they evaluate via machine coding round, but certain companies do ask a object oriented design round where they focus only on one particular feature and DB design as well, so its good get practiced with few problems beforehand.
Below are the list of LLD problem which are asked during my machine coding rounds from tech companies and the resources I collected.
Note : page is under construction, you can click on the individual packages to view all the questions and solutions.
| Low Level Design Question
| Question Link to PDF / Drive
| Company Asked
| Credits to author
| Cricket Match Dashboard | Leetcode | Udaan Assignment | |
| Event Calendar | PDF link | Flipkart LLD Question | |
| FoodKart or food ordering System | Doc link | Flipkart LLD Question | |
| Stock Exchange | Problem Link | Navi LLD Question | |
| PropertyHunt or property Listing site | Question image | ClearTrip LLD Question | |
| ledger company | Question Link | Navi LLD Question | Github code |
| Leetcode Like platform LLD | PDF link | Flipkart LLD Question | Github code |
If you found this resource helpful, give it a 🌟 otherwise contribute to it and give it a .
Learn low level design of system at scale. prepare for the low level design (LLD) / Machine Coding round interviews.
Learning low level design of scalable systems will help you become better engineer.
This repo is an organized collection of resources to help you learn low level design of systesm's.
- Low level Design Questions
- Low level Design Solutions
Low Level Design Resources #TODO
Add new questions
Improve new questions
add new solutions
Add new sections
Interested in adding a section or helping complete one in-progress? Contribute!
- how to guide and study material along with various resources.
- add more questions and improve exisiting questions.
- add solutions for the problems along with their detailed explaination (maybe video)
Credits and sources are provided throughout this repo.
Special thanks to:
- Donne Martin
- System Design Primer
- Cracking the Coding Interview
- G Balasubramanian
- Udit Agarwal ## Contact Info Feel free to contact me to discuss any issues, questions, or comments.
My contact info can be found on my Github Page
This repository aims at providing collated content at a single place to prepare for Software Engineering interviews.
- Coding/DS, Algo
- Top DSA interview questions - Companywise
- Object Oriented Design/Low Level Design
- System Design/High Level Design
- CS Fundamentals
- Low level design questions - Company Wise
- Top interview questions - Company Wise
- How to ace Behavioural interview rounds
- Mock interview platforms
- Resume building
Feel free to submit pull requests to help with:
- Add new questions/topics
- Improve new questions/topics
- Fix errors
- Improve sections
- Add new sections
Feel free to contact me to discuss any issues, questions, or comments.
I am providing code and resources in this repository to you under an open source license. Because this is my personal repository, the license you receive to my code and resources is from me and not my employer (Microsoft).
Copyright 2017 Karan Garg Creative Commons Attribution 4.0 International License (CC BY 4.0) http://creativecommons.org/licenses/by/4.0/
Repository for low level system design of a cache
- Implement checkmate feature.
- Write more unit tests.
- Support special move of pawn where it can go diagonal when it kills.
- At many places, we are evaluating conditions like:
- OR Operation : We are allowed to do something if any condition out of given conditions fulfill.
- And Operation : We are allowed to do something if all conditions fulfill. Try to improve the design for this.
- Add history of moves for each player.
- Add support for casteling move.
- Can we remove putting currentCell in Piece? How about introducing something like position?
- A piece will have a position and you can always get the cell back from board using this position.
- A system is a loosely used term for an architecture or collection of software or technology that communicate with each other or interact with each other in order to serve a certain set of users with a certain set of requirements.
- A system can be defined and built keeping these three factors in mind:
- The user of the systems
- The requirements of those users, and
- The components that are chosen in order to build that system to serve those users and their requirements.
- Design is a process of understanding the user requirements and selecting the components, modules, and software technologies how they are going to be intertwined and communicating with each other to actually serve the need of the system.
- Components are the basic building blocks of system components.
- It could be divided into two parts:
- Logical entities:
- Message Queues
- Communication Protocol
- Requests (API, RPC, etc.)
- Tangible entities:
- Text, images, videos..
- MongoDB, MySQL, Cassandra..
- Java, Golang, Python, React..
- Redis, MemeCache..
- Kafka, RabbitMQ..
- AWS, GCP, Azure..
- APIs, RPCs, Messages..
- Client-server architecture is a computing model in which the server hosts, delivers and manages most ofthe resources and services to be consumed by the client.
- Client: a piece ofsoftware or application that takes the input and sends request to the servers.
- Server: a piece ofsoftware that receives and processes requestsfrom clients.
- Load balancer: responsible for distributing incoming network traffic across a group of backend servers to optimize resource usage.
- Client requests data from server
- Load balancer routes the request to the appropriate server
- Server processes the request client
- Server queries appropriate database for some data
- Database returns the queried data back to the server
- The server processes the data and sends the data back to the client
- This process repeats
- #### Types of Architecture:
- Thin client:
- A thin client is designed to be especially small so that the bulk of the data processing occurs on the server.
- Example: Ecommerce, streaming applications.
- Thick client:
- A thick client (fat client) is one that will perform the bulk of the processing in client/server applications. With thick clients, there is no need for continuous server communications as it is mainly communicating archival storage information to the server.
- It is the simplest one as it is equivalent to running the application on the personal computer.
- It is like Client-Server architecture, where communication takes place between client and server.
- The 3-tier architecture has three different layers.
- Presentation layer
- Business Logic layer
- Database layer
- The 3-tier architecture has three different layers.
- An N-Tier Application program is one that is distributed among three or more separate computers in a distributed network.
- Proxy is an intermediary server between client and the internet.
- Proxy servers allow to hide, conceal and make your network id anonymous by hiding your IP address.
- Proxy servers offers the following basic functionalities:
- Firewall and network data filtering.
- Network connection sharing
- Data caching
- Forward Proxy
- In this the client requests its internal network server to forward to the internet.
- Reverse Proxy
- In this the requests are forwarded to one or more proxy servers and the response from the proxy server is retrieved as if it came directly from the original server.
- In Business Layer:
- Texts, Videos, Images, etc.
- In Application Layer:
- In Data Stores:
- Databases, Tables, Indexes, Cache, Queues, etc.
- Network Layer:
- Hardware Layer:
- Internal Data (System populates on their own).
- Type of data
- Authorization System
- Streaming System
- Transactional System
- Heavy Compute System
- If we consider data as people, in terms of buildings, then the way those buildings house people can be said as databases.
- Some common types of databases are:
- File type
- Network, etc.
- Applications or services performs certain tasks, and at different layers they have different responsibility.
- Tech stack:
- All the codes in applications are written in some languages using some frameworks.
- Any application can be written solely with the use of language. But frameworks do most of the bootstrapping so we can use this feature to make an application on the top of the framework.
- Client app:
- Render UI.
- Handle interactions.
- Collect data.
- Communicate with backend (API) to fetch and store data.
- Render static data/informations.
- Backend app:
- Expose API endpoints.
- House business logics.
- Handle data modelling/transformation.
- Interact with data stores.
- Interact with other services.
- Elements/factors of application development:
- Feature requirements.
- Tech Stack.
- Code structure/design pattern.
- Data store interactions.
- Operational excellence/reliability.
- An API is a set of defined rules that explain how computers or applications communicate with one another.
- Platform agnostic.
- Private APIs: The hidden APIs. Not accessible to everyone.
- Public APIs: Available to public. (Ex: Google maps api)
- Web APIs: Superset of public and private APIs.
- SDK/Library APIs
- Factors to consider:
- API contracts
- Data format
- Stands for REpresentational State Transfer.
- Client Server.
- Uniform Interface.
- Code on demand.
- A hardware or software component which helps in serving the data which is either frequently requested or it is expensive to compute on, so cache stores the computed response and saves the cost of computing.
- Cache hit: If a response for a request is available in cache memory, it is called a cache hit.
- Cache miss: If a response for a request is not available in cache memory, it is called a cache miss.
- Invalidation and eviction:
- The data that is kept in cache is not there for forever, it is volatile.
- The data is going to change at some point of time, hence we need to update the cache as well.
- The process of updating the data in cache by replacing the old value with new value is called data invalidation.
- Methods to invalidate:
- Cache expiry (TTL: Time to live).
- Remove the cache. (When a new request come, cache miss will happen, and data will be fetched.)
- Update the cache.
- A cache eviction algorithm is a way of deciding which element to evict when the cache is full.
- Catch eviction methods:
Where can be keep cache?
- Throughput is the number of actions executed or results produced in a certain amount of time.
- In system design, throughput comes into picutre when we need to understand how many API calls are being served in a particular amount of time.
- Bandwidth is the maximum amount of data that can travel through a 'channel'.
- Latency is the time required to perform some action or to produce some result.
- Response time is the time between a client sending a request and receiving a response. It is the sum of round trip latency and service time.
- Water Analogy:
- Latency is the amount of time it takes to travel through the tube.
- Bandwidth is how wide the tube is.
- The amount of water flow will be your throughput
- Vehicle Analogy:
- Vehicle travel time from source to destination is latency.
- Types of Roadways are bandwidth.
- Number of Vehicles traveling is throughput.
- API Response Time
- Throughput of APIs
- Error occurences
- Bug/defect in the code
- Time taken by various database queries
- Number of queries executed per unit time(or throughput)
- Latency of writing to cache
- Number of cache eviction and invalidation
- Memory of cache instance
- Rate of production and consumption
- Fraction of stale or unprocessed messages
- Number of consumers affects bandwidth and throughput
- Time taken for job completion
- Resources used in processing
- Fault is the cause, failure is the effect.
- The ability to handle more request by buying more machines/bigger machines.
- Key features:
- Able to handle the increased load.
- Not complex to implement and maintain.
- Performance shouldn' takr a hit or rather performance should increase.
- When we increase the capacity of existing resource it is vertical scaling.
- When we increase the number of resources it is horizontal scaling.
| Horizontal | Vertical | |------------|----------| |Need load balancers.|Load balancers not needed.| |Resilient.|Single point of failure.| |Slow remote procedure calls.|Fast inter process communication.| |Data inconsistency.|Data consistent.| |Scales well as uses increases.| Hardware limit.|
- Replication: To have a copy.
- Having exact copy of data present in other databases in other machines.
- The database that has main source of writes/updates becomes the primary db. (Master)
- The database which has the copies from the primary db's is called the secondary database. (Slave)
- Why do we need replication?
- Having replicas helps in tolerating faults.
- Having replicas helps in reducing latency.
- Replica databases can be used for read queries, whereas the primary one can be used for write queries. (Gain application performance)
- Replication lag:
- The time it takes for the value to be copied from the primary to secondary database.
- If replication lag is huge, then it becomes a problem.
- Replicas will give inconsistent data.
- To overcome this there are several consistenct models:
- Synchronous replication:
- All replicas have to be updated before host is acknowledged.
- No lag.
- Data is always consistent.
- Performance might take a hit, because every write will have to wait for all replicas to get updated as well as acknowledge. (High latency)
- If any replica goes down, and couldn't give any acknowledgement, write will fail.
- Asynchronous replication:
- Host is acknowledged after primary database is updated. Replicas update asynchronously.
- Write opeartion becomes faster.
- If any replica fails, system will be in a inconsistent state.
- Semi-synchronous replication:
- Whenever a new write is issued, the primary database will update the value to all the replicas, and will wait for one of the replicas to acknowledge.
- In a consistent system, once a client writes a value to any server and gets a response, it expects to get that value (or a fresher value) back from any server it reads from.
- In an available system, if the client sends a request to a server and the server has not crashed, then the server must eventually respond to the client. The server is not allowed to ignore the client's requests.
- The system continues to function and upholds its consistency guarantees in spite of network partitions.
- If we can tolerate the partition, and even though if partition happens and system can still be available and consistent is called partition tolerance.
- Any network shared system wants to have these three properties.
- In such a system, having all three properties is nearly impossible.
- We need to sacrifice one of them.
- Partition tolerance happens due to network failures, and we do not have complete control over network failures.
- Hence, partition tolerance becomes a mandatory property to support.
- This repo is just a collection of Low-level Design resources available on the Internet and these resources are created by their respective owners.