Getting Started with Competitive Programming

It’s been around a year since I started with competitive programming. When you’re a newbie, the online resources can be puzzling and intimidating. I’ve tried to incorporate the vital resources and how one can opt to proceed through this journey.

Choosing a language:

C++ makes life easier. It is the most popular language of choice for competitive programmers as it is usually faster than Java and Python, and most of the resources are available in C++ (Eg. STL).

If you’re entirely new to it, it would be better to get a hold the basic syntax of C++. Tutorialspoint is an excellent way to go about learning it.

The next thing one ought to learn is about time and space complexities. The videos in this InterviewBit link should be enough. Learning a few sorting and searching algorithms help in getting a good hold of these concepts. The main sorting algorithms one should know about are Selection, Bubble, Insertion, Quick, Merge and Bucket( though reading about Heap and Pigeonhole won’t do any harm).

For different data structures, GeeksforGeeks articles are beneficial. I have tried to cover the essential data structures:-

1. Arrays
2. Vectors
3. Stacks
4. Queues
5. Deque
6. Linked list
7. Doubly linked list
8. Trees
9. Graphs
10. Trie (hardly ever used it)
11. Ordered_maps/maps
12. Unordered_maps/hashmaps/dictionary
13. Ordered set/set
14. Unordered set/hashset
15. Priority_queue/heaps (min/max)

Next thing should be to get a hold of programming in C++. HackerRank is an excellent platform to do so. The interface is friendly, and solving fundamental problems will give you a gist of what comes next.

After programming on HackerRank for a week or so, one should get started with topic wise questions from either LeetCode or InterviewBit. The interface of either site is fantastic. InterviewBit gives more of a structured approach for practice, while the LeetCode community is incredible. Even after solving a problem, one should look at the most liked solutions in the comment section of LeetCode and see how others may have used a more optimised approach. One can opt to solve the LeetCode’s top interview questions if the interviews are not so far away.

Some resources for specific topics:

Dynamic Programming:

1. https://www.geeksforgeeks.org/top-20-dynamic-programming-interview-questions/ The videos are beneficial for these set of problems, and this ought to help you to get a good hold of Dynamic Programming.
2. https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns This link provides a pretty good overview of the different patterns in the Dynamic Programming problems; definitely worth a read.

Graphs: A few algorithms which come in handy:

1. Prim’s Algorithm for Minimum Spanning Tree
2. Kruskal’s Algorithm for Minimum Spanning Tree
3. Depth-First Search
4. Breadth-First Search
5. Detect Cycle in a Directed Graph
6. Kosaraju’s Algorithm for Strongly Connected Components
7. Dijkstra’s Algorithm for finding the Shortest Path
8. Bellman-Ford
9. Topological Sort for Directed Acyclic Graph
10. Floyd Warshall Algorithm for all pair Shortest Path
11. Finding bridges in a graph: https://www.geeksforgeeks.org/bridge-in-a-graph/

Revising for upcoming interviews:

1. When the interviews are only a month away (would recommend revising from here): https://docs.google.com/document/u/1/d/1SM92efk8oDl8nyVw8NHPnbGexTS9W-1gmTEYfEurLWQ/mobilebasic
2. Going through the problems on GeeksforGeeks Archives is a must. By doing this, one gets a pretty good idea which type of questions to expect and what topic to revise further. Also, I have observed that questions often (couldn’t emphasise more) repeat and you’re in luck if you already know the approach/solution. :P
3. Going through Codeforces Div. 1 A/B and Div. 2 C/D as a lot of organizations directly pick the problem statements from here, or present problem statements very very similar to these.
4. If you still feel like further practise or temperament building is required, one should go for the contests on CodeChef/Codeforces/LeetCode. It definitely helps one to work on his/her speed and accuracy. After all, practice makes perfect. :)

Originally published at https://github.com.