If you are a competitive programmer you don't need an introduction to coding judge.Most of us use coding platforms like Hackerank,Hackerearth,leetCode,CodeChef for practicing coding or to take part in various contests.Ever wondered how it works?Food for mind, think how your code get's executed and judged accordingly after plagiarism check.
What is an online coding judge?
Online coding judge evaluates the algorithmic source code submitted by the platform users and tests it against various test cases, constraints and plagiarism. It hosts Competitive Programming Contests as well.
In this article at OPENGENUS, you will get the complete idea of System Design of an Online Coding Judge.
For example, let's consider the most commonly used platform for coding i.e HackerRank. There are than 11 million developers who code. On an average there are more than 100k code submissions per day all around the globe and these much of submissions happen within hours at the time of contest!
Important factors should be taken into considerations in the design
- Security - The source code of users has to be secure to maintain the integrity of contest or participation.
- Time constraint - The program should be constrained to be executed in limited time.Usually this is in milliseconds and varies with respect to programming languages.
- System Capacity - A robust system that is not prone to hackers.
- Solution code should be evaluated in a coherent and reliable server infrastructure.
Different types of judges
There are four types of judges. They are:
- Systems that do not support any compilers because they only assess the results obtained by algorithms executed by the user using her infrastructure.
- Systems that support a single specific programming language
- Systems that support several of the most popular languages such as C++, Java, Python, C#
- Systems that support a broad range of compilers
Which database to use?SQL or NoSQL
Why do we need database in coding judges?
- Store information of users(including admins and contest creators) and problem statements.
- Online judge Database helps the graders/contest creators to view the submissions and attempts.
Which database to use?
DB has a huge compiler which supports multiple programming languages.
So, as SQL can handle GB's of data effectively SQL is preferred and sufficient. Also, SQL can handle relations effectively in this case. Although,using NoSql seems to be efficient but turns out to be costly for this and there's no need for it in case of online coding judge.
Caching is needed to reduce the query times. Like in the cases:
- Sort Problem statements according to the filter(difficulty level ,topic ,solved/unsolved ,company)
- View leaderboad
- Get score of previous challenges etc.
To achieve this Redis load balancing environment can be used.
Distributing set of tasks among the set of resources is necessary which in turn makes the overall process efficient.
Load will be high during contests and we need to take this account while deciding on load balancing algorithm. We can keep a simple and cost effective algorithms for regular use and change it at the time of contests to handle extra load.There are several load balancing approaches like round robin,least connection,resource based etc. Round robin is the simplest of all and most used.In this coding judge we have client,application server and database server. We can round robin approach to distribute the requests equally among the servers.
Load balancing algorithm can be changed the time of contests. You may use Weighted roung robin, because it takes into the account of the differing application server characteristics.
Should a different design be enabled during a contest and for other times?
According to me it's a YES. Because the traffic of submission is more at the period of competition and it's more prone to plagiarism. Secondly, the constraints like time limit and memory limit varies according the contest.
- Sophisticated and robust system handles request.
- Fair judgement as it uses plagiarism check tool
- The candidate who writes the most efficient get's the reward.
- Better interface for participants
Rate limiting for such a system (to avoid bots? or same code multiple times)
Rate limiting is definitely needed to avoid bots and also prevent the overuse of API and other resources(which are free).Sometimes the competitor may also submit the same code multiple times, which is essentially not the best practice.
We can apply rate limiting algorithms like token bucket,leaky bucket,fixed window,sliding window etc.We can also use API Rate limiting here.
To know more about Rate Limiting Systems and Algorithms used in it click here
Behavior of load systems
It's usual that the requests/submissions are high at the period of contests where's it's comparatively less on other days. The robust load handling system which estimates the usage according to the contests can be implemented to handle this scenario.
Some Complications while using coding judge
- Time Limit Exceeded: Program should run in fixed time.
- Memory Limit Exceeded: Fixed memory should be used.
- Stack Overflow/Runtime Error: If the program doesn't run successfully this error is raised.
How to avoid malicious code?
User is allowed to write any code with wide range of languages support. The code could be malicious too, which can result into attacks and information leak. To avoid that we can use Code-Sand Boxing.Code-Sand boxing simply offers an isolated environment where the users can write their code and execute them without affecting the system.
Case Study - CodeForces
Codeforces is a famous website that hosts competitive programming contests.
Established Year - 2013
Led By - Mikhail Mirzayanov
Database Used - MySql
Pros of CodeForces -
- Codeforces have a super fast rating system
- Quicker response from discussion forums
- more number of competitions
- Editorials being better and being on time
How does CodeForces/online judge determines whether the solution is correct?
It's impossible for humans to check the code of millions of problems.To evaluate the code,it is tested by a code-checker automatically, not by a human being, and accordingly code has to be written.
For each problem statement, there will be one or more input files which are defined beforehand. Each according to the specifications mentioned in the problem statement, and corresponding correct output files.The bridge between them is the code that is being written and submitted to the online judge. The program is run on each of the input files to check for code versatility and boundary conditions, which is done by redirecting the standard input stream to an input file, and the standard output stream to another file. The output generated by the written program must match the correct output exactly in order to be judged correct.
Time to Think!
What are the concepts you need to know to build an Online Coding Judge
Finally,to put it simple online judges are systems used to assess the algorithms source code written in various languages submitted by the user.They are becoming very popular with wide range of applications.
Hope you had a good time reading the article at OPENGENUS. Keep learning!