Monday 15 July 2019

What road map do you suggest for a beginner in programming to learn algorithms and data structures to usable level for competitive programming?

First, some motivation.
How will Competitive Programming benefit you in your Career?
  1. You can very well use your ratings [achieved on various competitive programming platforms] on your resume to show how you outstand amongst your colleagues! (Believe it or not, recruiters do get impressed by seeing your performance on online platforms).
  2. You will learn how to approach a problem with the best of the best possible ways, you will learn how to analytically think and solve a problem and analyze it’s space and time complexity.
  3. Every large MNC or Product-based company prefers to have initial filtering round which consists of Competitive Programming problems.
  4. You will get to learn a programming language end to end.
  5. The adrenaline rush that you will get after seeing the green tick and your name on the leaderboard - there’s nothing compared to that.
Step 1: Learn a well-known programming language
You can do competitive programming in any programming language but it is highly recommended that you choose one of C/C++ or Java. The reason being that the time of execution is a key factor in Competitive Programming and so, choosing a language whose time of execution is fast is surely going to give you a benefit. C/C++ and Java are relatively faster, particularly when compared to languages like Python.
It’s better to use C++ because it’s among the fastest in terms of execution time and it provides a lot of inbuilt functionalities, is most widely used and has support for various data structures through STL (Standard template library), however, Java is also a good choice as it supports BigInteger (the ability to store large numbers without the overflow problems).
If you are a total beginner to programming, it is highly recommended that you learn a programming language. Head to this link for the same.
Step 2: Starting with Competitive Programming
Before you jump into the world of competitions it would be better to get familiar with I/O style and the way coding is done on the online platforms, for that we would suggest you to:
  1. Start practicing on Hackerrank, it has a great IDE and a wonderful beginners program which will help you in getting started. Hackerrank has a great set of problems whose difficulty increases gradually and hence you will not face a sudden rise or fall of difficulty and it also lets you view the test case on which you code failed which will help you greatly in making test cases as well as learning how to debug the code for the case on which it failed. As a total beginner, it is important that you are able to see the test case which failed so that you can learn how to target such corner cases.
  2. Once you are familiar with Hackerrank it would be good to dive a little bit more into a little harder problems for which you can go for SPOJ. SPOJ is not a competitive programming site but it consists of a lot of variety of questions which will help you in learning the implementation of a lot of new data structures and algorithms. If you will solve the first 20 problems on SPOJ you will cover topics like arrays, strings, sorting, searching. If you will solve the first 50 problems you will cover topics like bit manipulation, recursion, backtracking, Graph. If you will solve the first 100 problems you will have covered advanced topics like Dynamic Programming, Heaps, Hashing, Tries, and segment trees.
As mentioned above, try to start with Hackerrank and solve at least the first 20 problems to get an idea as to how Competitive Programming works.
After you’re done with Hackerrank’s first 20 problems you should move to SPOJ and try to solve a few problems here also.
As a side note, we would like to suggest that while you are solving these problems, you shouldn’t really wait for completing them first. Rather, in parallel, you should start participating right away as soon as you get an idea as to how the I/O works because participating in competitions and competing with others are the best part of Competitive Programming.
Note: For those of you who have a little bit Idea of Data Structure and Algorithms, you may want to practice only those parts of Step 3 and 4 below, which you are not familiar with.
Step 3: Get Familiar with Data Structures
Again, Please keep in mind our motive is not to make you memorize these Data Structures or Algorithms in the next step but to show you how can you implement these in real life problems.
We have also added some questions along with each topic so that you can get hands-on experience as to how to apply which data structure in which problem.
Arrays and Vector: A collection of similar data types is called an Array. Vectors are also like arrays but when combined with STL functions they prove to be far more useful than an array in Competitive Programming. Here are some great resources to understand the basics of Arrays and Vectors in C++. If you are going ahead with Java as the programming language, you can do a quick Google Search to find the equivalent Java resources as well.
Basic Maths: Problems from basic mathematics and implementation are fairly common in contests as well as in interviews. Therefore, it is recommended that you should have an idea of the fundamental mathematics concepts.
Strings: They are collections of multiple characters and can be referred to as an array of characters. String problems are quite common in various programming contests and in fact string problems are among the favorite problems for tech interviewers.
Stack: Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). Stack follows LIFO.
Queue: A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
Map: Map is by far one of the most useful Data Structures. It can be used to find, iterate, add, delete numbers, and is also one of the most widely used Data Structures.
Step 4: Get Familiar with Algorithms
Algorithms are logics that are implemented on various Data Structures to achieve the desired output.
Time/Space Complexity: Every Algorithm has a Time and Space complexity which refers to the maximum amount of time an Algorithm will take and the maximum amount of memory an algorithm will require. While doing Competitive Programming these two will play a key role in determining the verdict of your solution.
Always try to think of the most optimal solution, that is, one which runs with least time complexity and occupies minimum space.
Sorting: You must have heard of a number of sorting techniques to sort but while doing Competitive Programming most of those techniques prove to be time-consuming hence the STL library comes to rescue, it offers a function sort() which sorts the array in the most optimal way.
Step 5: Starting with actual online competitions
Once you are familiar with time complexities, I/O operations of online IDE’s and penalties you can start with actual competitions, for which the following sites provide the best environment for competing with others:
  1. Codechef: Codechef offers three monthly contests in which you can participate and test your skills:
    1. Codechef Long: This is a 10-day long contest and is one of the best contest to start Competitive Programming with as it does not have any wrong answer penalty and gives you a lot of time to think and implement your solution for a particular problem.
    2. Cook-Off: This is a much shorter contest that lasts for 2.5 hours and features 5 problems of varying difficulty, this contest will teach you how to think and implement a solution within a given time constraint,
    3. Lunchtime: This is a 3-hour contest meant for school students. A Lunchtime usually features 4 problems. If you think that the problems in this one are gonna be easy, you are in for big surprise.
  2. Codeforces: Codeforces segregates users into three categories: Div 1, Div 2, Div 3.
Start by solving Div 3 problems at first. Codeforces offers multiple contests in a month and you can even try to start a virtual contest if you like. Don’t get demotivated if you find it difficult to solve more than 2,3 problems or even a single problem during a contest when the contest ends look at the tutorials for the problem that you couldn’t solve and then upsolve it.
Codeforces is also good for beginners as it also helps you in looking at the test cases for which your solution which failed which again, in turn, helps you in debugging as well as learning to make your own test cases for further future problems.
Upsolving is the key aspect of improving yourself, also look at the codes of other programmers as it will help you in improving your own coding style.
As a beginner, you should never care about rating because that is your biggest barrier in trying harder and trying problems out of your comfort zone during a competition. Even if your rating is going down, it doesn't mean you aren't improving; rating is relative to others and isn't a sole grader of what you can do.
Solve as many as possible, but don’t get discouraged if you can’t solve a problem after the contest ends, watch the tutorial and also read the code of other participants to learn the coding style and pattern of others.
Step 6: Practice Practice Practice
People say that practice makes man perfect but in the world of Competitive Programming, no one has ever achieved that mark yet no matter how much you practice you will always miss something but that’s the glorious part of Competitive Programming that you never get done with it.
Don’t lose hope and keep trying and submitting until you get that green tick, because trust me when I say this seeing that green tick is one of the best feelings in this world.
Also read about the world championships that are organized by various prestigious organizations like ACM, Google, Facebook, Vk cup, SnackDown and one of the best ways to secure a job interview with companies like these is Competitive Programming and performing well in the competitions organized by them. But first things first, get up from that couch and start enjoying the sport.

No comments:

Post a Comment