Design Online Coding Platform CODING BLOX (Design Leetcode LLD)

Design Online Coding Platform CODING BLOX (Design Leetcode LLD)

• Coding Blox is an Online Coding Platform that allows a user to Sign Up, Create Contests and participate in Contests hosted by Others.
• Each contest can have a level (LOW, MEDIUM, HIGH) and will contain a set of questions.
• Each question will have different levels of difficulty(LOW, MEDIUM, HIGH) and score.
• Based on the contest level, the question set is going to be decided. Contest level with LOW difficulty will have questions with LOW difficulty level.
• Final score will be decided based on the difficulty LEVEL chosen for a contest
• Users solve problems and get points based on the difficulty of the problems and after the contests scores of the users are updated.

Functionalities/Requirements:

1. CreateUser <user_name>
2. CreateQuestion <difficulty_level>
3. ListQuestion <difficulty_level>
4. CreateContest <contest_name> <contest_level> <contest_creator_user_name>
5. ListContest <difficulty_level>
6. AttendContest <contest_id> <user_name>
7. RunContest <contest_id> <contest_creator_user_name>
8. LeaderBoard <sorting order asc/desc>
9. ContestHistory <contest_id>
10. WithdrawContest <contest_id>

full problem statement & solution (Time given 90min) : http://bit.ly/leetcode-low-level-design

---

Simply I follow these steps for any LLD.

1. Find out entities
2. Find out the relationship between entities
3. Write entities CRUD (use hashmap or JPA)
4. Start implementing requirements

Step 1,2 and 3 => approx 30min
Step 4 => +1hr

Step 1, 2: Domain layer
Step 3: Database/dao layer
Step 4: Service layer

(Use this hashmap template to quick start: http://bit.ly/lld-hashmap-as-db-template )

---

Step 0: Understand the problem statement and requirements

Step 1: List down important entities/model/domain

In the above question list of entities are -> User, Contest, and Question

Step 2: List down the relationship between entities.
e.g.
User can register for multiple contests

User:
	List<Contest> contests

The contest can have multiple Questions

Contest:
	List<Question> questions

Now Add other fields of entities

User:
	username
	score
	List<Contest> contests -- (A)

Contest:
	name
	level
	status
	List<Question> questions

Question:
	question
	level
	score

Step 3: Store entities and write entities CRUD methods (Use Method 1)
Method 1: Use hashMap to store entities,

Map<Long, User> userDb
Map<Long, Question> questionDb
Map<Long, Contest> contestDb

Write CRUD method for each entity (HashMap sample example)

Method 2: Use H2 in memory using JPA, (simple to use but need to practice more)
Create 3 DAO class, internally with the help of the JPA class we can get all CRUD methods so no need to create any methods (JPA sample example)

Step 4: Create a service class for each entity and start implementing the requirement (service classes)

UserService:
	createUser(username)
	attendContest(contest id or contest object, username)
	leaderBoard()
	withdrawContest(contest id or contest object, username)

QuestionService:
	createQuestion(question)
	listAllQuestion()

ContestService:
	createContest(contestId or contest object, username)
	listAllContest()
	runContest(contestid or contest object, username)
	contestHistory()

add logic for above methods plus entity validation

Step 5: Refactor code : extract class to an Interface, Abstract class, add enum, add exceptions, add constant, read from config
List<Contest> contests --(A) become --> Map<Long, List<Long>> userContestQuestions = new HashMap<>(); KEY : Contest Id, Value: list of question ids

---

If we do Step-1 and Step-2 correctly then finally we can see entities tables (these tables are only visible in case of JPA but this entity relationships are also valid if we are using HashMap)

Contest entity

Question entity

User entity

design elevator using event driven programming

 We can divide into three main components:

1. User

   • User presses the floor button (can be up or down direction) to summon the elevator.
   • User presses the elevator button to go to the destination floor.

2. Button

   • An elevator has buttons (ElevatorButton) inside allowing user to choose the destination floor.
   • Each floor has two buttons (FloorButton) to summon the elevator to go up or down from that floor.
   • When the user presses the button, it illuminates.
   • When the elevator reaches the desired floor, the button stops illuminating.
   • Calls placeRequest() to insert into the ElevatorRequest queue when button is pressed.

3. Elevator

   • Open or close door.
   • Moves up/down.
   • Stores states such as direction (up/down), speed, currentFloor.

We need a queue to store all request, this can all be encapsulated in an ElevatorRequests class. When a user presses a button, this request has to be served and is added to the processing queue. Elevator requests can be scheduled using different scheduling algorithms. ElevatorController controls the elevator by giving it instructions such as move up/down, or start/shutdown. The elevator controller reads the next elevator request and serves it.

This diagram may help :)

LeetCode: 1114. Print in Order | Java | Wait and Notify

Prepare for Facebook System Design Interview [Pirate Round]

What is the System Design Interview Round at Facebook?

1. System Design Interview Round is also known as the Pirate Interview round at Facebook.
2. In this round, you will be asked to show off your design skills. The system design questions asked are typically more open-ended and feel more like a discussion.
3. The design interview is 45 minutes long. It rarely involves coding. You will spend most of the time talking and drawing on the whiteboard.
4. The purpose of the interview is to assess the candidate's ability to solve a non-trivial engineering design problem. The interviewer will ask you a very broad design problem and evaluate your solution.

Now let us review the top system design questions which are usually asked at Facebook.

---

Question 1: Design Facebook News Feed

In the Design Facebook News Feed question, design the following key features and their APIs.

1. Facebook users should see the news feed containing posts and statuses from their friends and pages that they have followed.
2. They can post and like statuses that may contain text, images, and videos.
3. They can send friend requests to other users and follow other pages.

Design Goals

1. Minimum latency
2. High Availability
3. Eventual Consistency (Due to CAP Theorem)
4. Read-Heavy Service

Scale Estimations

1. One billion daily active users (DAUs)
2. Ten billion news feed requests daily
3. On average:
   • Each user posts twice a day
   • Each post is liked five times
   • Each user has 200 friends
   • Each user follows 100 pages

---

Question 2: Design Facebook Status Search

Facebook provides a search bar at the top of its page to enable its users to search posts, statuses, videos, and other forms of content posted by their friends and the pages they follow. In this question,

1. Develop a service to enable the users to search the statuses posted on Facebook by their friends and followed pages.
2. Consider that these statuses will only contain text for this particular question.

Design Goals

1. We should ensure that the final system has minimum latency, and users should not experience any significant lag while searching for the statuses.
2. The system should be highly available.
3. Due to the CAP theorem, we will aim for an eventually consistent system.
4. Our system will be read-heavy as more users will be searching on Facebook rather than posting statuses. Thus, the number of read requests will be far greater than write requests.

Scale Estimations

For an efficient system, we will have to consider the following scale estimations.

1. On average, the system will have one billion daily active users
2. Receive around five billion search requests daily
3. About one billion statuses will be generated by the users per day.

---

Question 3: Design Live Commenting

This question is not related to Live Videos. This question is related to the active real-time feed of comments at the bottom of each post. Thus, in this question,

1. Design the backend of a system that can enable real-time commenting on Facebook posts.
2. The users should be able to see the new comments in real-time for the posts visible in front of their screen.

This problem is quite challenging, as users are continuously scrolling the news feed, and thus the posts that are visible in their view can change very frequently.

Scale Estimations

To design an efficient system in the interview, we will have to consider the following scale estimations. These estimations will help us in explaining the scale of the system to the interviewer.

1. Every minute, Facebook serves over 100 million pieces of content that may receive comments.
2. In that same minute, users submit around a million comments that need to get routed to the correct viewers.

---

Question 4: Design Facebook Messenger or WhatsApp

Develop the backend of a messenger system that can,

1. Support 1:1 conversations between two users.
2. Track the online or offline status of the users.

If time remains, discuss more complex features like Group conversations and Push notifications.

---

Question 5: Design Instagram

Design a simpler version of Instagram.

1. Users can upload and share photos.
2. They can follow other users.
3. Like the photos posted on Instagram.
4. Instagram users should get a scrollable feed of photos that are posted by the users they follow.

---

Question 6: Design Typeahead Suggestions

Google predicts and suggests a list of autocomplete queries based on the characters that we have already typed in the search box.

1. Suggest the top ten search queries based on the characters already typed by the user in the search box.
2. Assume query's popularity can be determined by the frequency of the query being searched in the past.

---

Question 7: Design Privacy Settings at Facebook

We can set different privacy levels for the Facebook posts we publish to be only visible to a specific set of users like public, friends, friends of friends, etc.

1. Enable a user to specify the different levels of privacy for a post so that it is only visible to a particular set of users.
2. Implement two levels of privacy, Public and Friends.
3. Optional Complex Levels: friends of friends, custom groups

---

Question 8: Design Proximity Server

Proximity servers are used to discover nearby attractions such as places and events, which are then recommended to Facebook users.

1. Users can add, update, and delete places.
2. Given a location expressed as latitude and longitude, users can query all the nearby places within a given distance.
3. Optional Follow-up: Query events near a given place around a particular time. This adds the third dimension of time to the problem.

---

Question 9: Design Top N Songs

This question is very similar to designing the system for Top N Trending topics.

1. Get the top N songs for a user over the past X days.
2. Assume popularity of a song can be determined by the frequency of the song being listened to in the past.

---

Question 10: Design Web Crawler

Web Crawler scans the world wide web to download and index all the web pages to be made available for the search queries submitted by the users.

1. Given a list of seed web pages, it should download all the web pages and index them for future retrieval.
2. The service should handle duplicate web pages so that unique URLs are stored.

Design Goals

1. We should ensure that our service is highly scalable, as it needs to crawl the entire Web and fetch billions of web pages.
2. It should implement the Robot Exclusion protocol, allowing web admins to declare parts of their websites off-limits to crawlers.
3. For the simplicity of the interview, we can consider that we will crawl only HTML pages.

Scale Estimations

1. Our System will be crawling about 25 billion web pages every two weeks.
2. On average, each URL will be 512 bytes in size,
3. And each page will be about 100 KB in size.

Designing Distributed File Storage Systems - Explained with Google File System(GFS)

 A distributed file system(DFS) is a file system that allows you to access files stored in multiple hosts distributed across them.

In contrast to other data stores like MySQL or NoSQL which can also be made distributed, the data is DFS is stored in raw form and as files instead of a table or a fixed-document format.

The use cases where DFS is used are very vast. From storing media content like Youtube videos to Instagram images to blogs like these, anything that can be stored as a file, is big and is not suitable to store in other data stores, DFS is generally a preferred choice for everyone.

Key points to consider while designing a DFS:

Understanding from the perspective of using a distributed file system, there are some characteristics that need to be considered while choosing the data store and tweaked according to the business requirements of the project.

1. Consistency - Strong consistency for a user means the system should behave as if the user is talking to a single server in spite of behind the scene they are in 1000s. If a user chooses to build a distributed system that is also consistent in nature, performance should be traded off for this, which is mostly the write performance. The general case is a write is acknowledged successful if and only if the writes to all the replicas are done, and the write performance takes a hit with this. Most of the systems are made eventual consistent due to this reason if it can be afforded for the busses use case. If we want strong consistency, it will trade-off performance, as it cannot send an acknowledgment until all replicas are updated.
2. Parallel performance(through sharding and replication) - As most of the data is independent, we can split up the data(shard) to store in multiple machines to scale horizontally with an increased amount of data as well as traffic load. This will surely increase the query and maintenance complexity of storing data, as we have to manage the metadata at the application layer as well, but a good way to store if the data is very huge, like for a typical file data store. We can achieve increase query performance as most of the queries can be done parallelly, even for the same file if we split the file as well(we'll talk about chunking)
3. Fault-tolerant (through replication) - As we want the system to be highly available, i.e. even if a few servers fail, it should continue working without any change for the end-user. This can be achieved with replication, i.e. duplicating and storing the same data across multiple machines. Though replication can be very tricky to achieve, and we have to trade off consistency to achieve this, this can certainly be very useful if losing a file, even a chunk of it can be very costly for the business. Ex: if we are trusting google drive to keep all our data for a lifetime, we don't want them to lose any of it, and losing even a little data can be very harmful for their reputation.
4. Automatic failure recovery - As we will be dealing with 1000s of servers storing and maintaining the data, any failure if fixed manually can take some amount of time and human hours, which also cost the company. And if the servers are in 1000s, the chances of any kind of failure is very high. We can achieve this by persisting some metadata so that after any failure or restart, the node can backup the state from where it was before the failure.

Architecture

Metadata service(servers)

Metadata service(servers) is responsible for keeping track of all the metadata like where a file is stored, how it is chunked, how it is replicated, update pattern(versions).

Considering the above points, we will be using a master-slave architecture means there will be a single node that will take care of the update to files and there will be replicas that will be used for reading the files, and in the case of the master failure, coordinate between them to select a new master among them.

Responsibilities of the master node:

• master keeps mapping from filename to chunks
• we query the master to ask for servers where the file is stored
• the master contains two main tables
• map of the file name to an array of chunk ids or chunks handles
• maps chunk handle to 
• a list of chunk servers
• the version number of the chunk
• which chunk servers are primary
• all the tabular data should be kept in memory in master for faster reads and writes
• periodically syncs all data to non-volatile memory(disks) in case of failure, the newly elected master will load these data from disk

Responsibilities of slave node(s):

• keep all data in sync with the master
• in case of failure, elect a new master among the remaining nodes to act as the primary server for redirection

Chunking service(servers)

The chunking service(servers) is responsible for chunking the file and storing it on disk(non-volatile). Files are chunked in smaller parts, as the files can be very big, and to update, we may not require the whole file to be loaded again and again. It will also be easier to replicate and synchronize small files across secondary servers and clients if multiple clients are connected at the same time.

How reads and writes happen?

Both metadata service and chunking service are involved in any kind of reads or write.

Reads:

• API: read(file_name, offset)
• file_name: will be a unique identifier for the file
• offset: will be the starting point in the whole file, from where it will start reading
• the read request from the client will first go to metadata service, which will return
• chunk handle for the file and offset
• list of chunk servers, including the primary and secondary(replicas) servers
• the above information will also be cached, as the same call will be very frequent
• then the read request will go to the chunk server as read(chunk_handle, offset) where chunk_handle will have the information about the chunk version
• this will return the chunk of the file from one of the secondary chunk servers

Writes:

• API: write(data, file_name)
• data: is the data that will be appended to the end of the file
• file_name: will be a unique identifier of file to be written
• the request will go to metadata service, which will create a new chunk identifier for new data and
• will store chunk handle, version
• find up to data replicas(chunk servers)
• elect one of them to be primary, others to be secondary
• master of metadata server will increment the version number and writes it to disk
• sends primary and secondary a message for the updated version number, elected primary server, and list of secondary servers for the given chunk handle
• the primary server picks and sets the offset for the data
• send all replicas a request to write at the offset
• if all replicas respond with "success", returns "success" to the client
• if any secondary server responds with "fail" or doesn't respond within a given time, returns "failed" to the client

WHAT IF the metadata service thinks the primary chunk server is dead?

This may be due to various scenarios such as network failure, packet loss, etc due to which the metadata service thinks the primary chunk server is dead, so it will elect and assign a new primary server and update its database.

But if in actuality, it's not dead, it can be the case that the primary server is even responding to the client and to other secondary servers as well, but disconnected from metadata service.

In this case, it will elect a new primary server, and we will be having two primary servers, which is a big problem.

This problem is called a "split-brain" problem which mainly occurs due to network partition.

To solve this, the master can assign a TTL to primary, i.e. for how much time it will be primary, and stop taking any requests after the TTL ends.

After TTL ends, it will check for available nodes and chooses one of them to be primary for a given lease again making the remaining secondary, and updates its database accordingly.

The value of TTL can be chosen as per the consistency and availability requirements, as it will not be updating it's primary even if the primary dies until the TTL ends.