If you are preparing for Software Developer / Engineer jobs, you have to be prepared to go through rigorous technical interviews. All these interviews require good programming skills.
Apart from impressive side projects and relevant experience, knowledge of Data Structures (DS) and Algorithm Design & Analysis (ADA) with good problem-solving skills are the most important things you’ll need to ace the interview.
So how can you be a pro at both of these things?
The answer is Competitive Programming! So what’s competitive programming?
Competitive programming is a mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications. Contestants are referred to as sport programmers. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google and Facebook — Wikipedia
Here’s how it works: On the programming websites, during a practice session, you’ll be given a programming problem which you have to solve.
You can write your solution in any programming language you’re comfortable with. Your solutions will be judged by online judges. Additionally, your solution should work under certain time and space limits.
It should pass all the test cases (given and hidden) to get accepted. In a live coding competition, everything is same, except there will be a time limit for submitting solutions as well.
As mentioned, a lot of big tech companies like Facebook and Google hire through Competitive programming contests.
Another reason for diving in (if you need one) is, it will really help you improve your problem-solving skills, something that is required in every field including software development.
In addition to this, competitive programming (or algorithmic programming) helps you understand the complexity and performance of programming problems and thus gives you a better idea of implementation of projects.
While working on any aspect of development, you’ll always have to make choices regarding the solution of the problem in hand.
Competitive programming will make you better at making such decisions.
How to get started?
Step 1: Choose a programming language
Choose a programming language you’re most comfortable with. It can be a high-level language like Python or a middle-level language like C.
Choose something you have at least have 3–4 months of experience with. I personally prefer C++ as I have years of experience coding with it.
If you’re a newbie to programming, I’ll recommend Python, given its easy syntax and predefined library functions. Check Python tutorials available here.
Step 2: Learn about Time and Space complexity
Most of the times, there is more than one solution to a problem. How do
we rank which one is the optimal solution?
Online judges rank them with respect to their performance.
Performance is measured through:
Time complexity refers to the execution time of all the operations in a program. All operations of a computer take constant time. Execution time also depends on external factors like hardware but these factors are ignored by online judges.
The execution time is considered in three scenarios:
- Best case
- Average case
- Worst case
Worst case is considered as the execution time for judging the performance of code most of the times.
Let’s look at this with a simple example:
int sum = 0;
for (int i = 0; i < n; i++){
sum += i;
}
What is the time complexity of this code snippet?
In this case, the execution time will be the time taken by the for loop to complete. If the other operations take a constant time c.
Then the execution time will be dependent on the variable ’n’, the total execution time will be:
(c + n*c)
If n increases, the total execution time also increases.
We judge time complexity in Big-O (O) terms.
For the above snippet, the complexity will be O(n) as it completely depends on the size of n.
Space complexity, similar to time complexity, is also used to judge the performance of the running program.
It is a measure of the amount of working storage (or memory) an algorithm needs. While choosing a data structure for a particular problem, space complexity plays a big role.
As with time complexity, we’re mostly concerned with how the space needs grow, in Big-O terms, as the size n of the input problem grows.
int sum(int a[], int n) {
int r = 0;
for (int i = 0; i < n; ++i) {
r +=a[i];
}
return r;
}
This code snippet requires n units of space for array a and 1 unit of space of r, that is O(n + 1) which is equivalent to O(n)
Check out this article for learning more about space complexity.
Step 3: Learn the basic Data Structures and Algorithm concepts
Nearly every coding problem will require the usage of a specific data structure or algorithm for an optimal solution.
Knowing basic data structures and algorithmic techniques before you start is a must. As listed in the Data Structures for Interviews presentation, here is a list of data structures to learn.
I’ll be briefly covering the following:
Array
An array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
int[] array = {1, 3, 5, 2, 6, 9};
- Index: 0 1 2 3 4 5
- Value: 1 3 5 2 6 9
The simplest type of data structure is a linear array, also called a one-dimensional array. The array elements can be int or long or any other datatype depending on the initialization.
Linked list
A Linked list is a data structure consisting of nodes linked together. The nodes are not stored adjacently in memory. Rather, each node points to the next.
Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.
Many variations of linked lists like doubly linked list and circular linked lists are used in different problems.
Stack
A stack is a linear data structure that follows the LIFO (Last in First out) principle.
A Stack has two principle operations:
Push — Add an element to Stack
Pull — Remove an element from Stack
Queue
Like a queue in real life, the queue data structure also follows the FIFO (First in First out) principle. Front refers to the starting of the queue and Rear refers to the ending of the queue.
The process of adding an element in the Rear is called Enqueue and the and process of removing an element from the Front is called Dequeue.
Depending on the problem, different implementations of the queue (other than the linear unidirectional queue) like a circular queue, doubly ended queue and priority queue are also used.
Tree
A Tree is a data structure that starts at the root node and then multiplies recursively into child nodes with no child pointing towards the root node.
The Tree can be directional or non directional, weighted or unweighted and similarly, have many other variations.
For programming competitions the most used tree variations are Binary tree, Binary Search Tree, N-ary Tree, Segment Tree, Red Black Tree and Heaps.
Binary Tree will be used in a lot of problems. Learn more about them here.
Trie
A Trie (or a radix tree) is a efficient tree variation for retrieving data. Using it, the time complexity of search operations can be brought to O(n) where n is the length of the string. Learn more about a Trie here.
Graph
Graph consists of nodes interconnected (partially or completely) to each other. The connections between these nodes are called Edges or Arcs.
Graph can be weighted, unweighted, non directional, directional and can take many other forms. Tree is also a kind of Graph.
It’s implemented through an adjacency list of Adjacency matrix. Learn more about a Graph here.
There are many other Advanced Data Structures. Check out the complete list here.
Some important Algorithmic approaches:
We’ll be covering a few important algorithmic approaches below:
Sorting — Sorting algorithms are used for sorting elements of linear data structures. There are a lot of sorting algorithms based on different time and space complexities. Bubble sort, quick sort, merge sort being the most famous ones.
Dynamic Programming (DP) — Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
Dynamic programming checks the all the options exhaustively before finding the best one. It’s a very popular algorithmic technique and is used for solving a lot of problems like:
It’s a favorite of Job interviewers as well, asked in companies such as Adobe, Google, and Amazon. Check this tutorial for more.
Greedy Approach — Greedy is an algorithmic paradigm that chooses a locally optimal choice at every stage instead of going through all the options at choosing in the end (unlike Dynamic Programming).
It may not give the best solution in all the cases. Djikstra’s algorithm is a popular example of the greedy technique.
Recursion — Recursion occurs when a thing is defined in terms of itself or of its type. The Fibonacci sequence is a classic example of recursion where the function calls itself till the base condition of n<2 is met.
Divide and Conquer (D&C) — A Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
The solutions to the sub-problems are then combined to give a solution to the original problem.
It’s similar to dynamic programming with one difference:
Divide and conquer exhaustively checks all the options (even recomputing values which were earlier computed)
Dynamic programming stores the solutions of sub-problems to avoid recomputing. Merge sort is one example of D&C.
This is just a rough list to get you started. You will learn more along the way.
Step 4: Taking part in online coding challenges
These are some of the most popular online judges you can use to practice your programming skills:
Hackerrank
It’s a programming challenge website where you can also apply for jobs as well as compete for them in hiring contests by solving challenges.
The platform supports a variety of programming languages including Java, C++, PHP, and Python. Furthermore, it also has practice domains other than data structures and algorithms like Regex and SQL.
Project Euler
Project Euler focusses on the mathematical concepts important for programming and solving problems. It helps in developing computational skills required for high-level programming competitions.
The problems varies from basic to hard. It’s really good for learning new concepts in a fun way.
LeetCode
Leetcode is a top competitive programming platform which supports many programming languages (more than 32!).
Other than its coding competitions, it’s also famous for its tutorials which cover a variety of topics. It is the most used platform among experienced developers as well. You'll find questions tagged topic and company wise. I highly recommend using this.
CodeChef
Codechef is a well known competitive coding platform of Directi group.
It’s program such as Go for Gold are very famous for motivating coders to do well at the ACM International Collegiate Programming Contest, an annual multi-tiered competitive programming competition.
Additionally, it’s brilliant programming tutorials and intensive contests make it a favorite of coders.
SPOJ
Sphere Online Judge (SPOJ) is a little different from other coding platforms. The questions on this platform are stated in simple and direct language (and hence my favorite) which makes it a good spot for beginners.
Tasks are prepared by its community of problem setters or are taken from previous programming contests.
Another important factor for choosing SPOJ over others is that it also offers content in Polish, Portuguese and Vietnamese languages other than English.
Topcoder
One of the most famous (and best!) programming websites in the world, Topcoder hosts some of the best and toughest competitive programming competitions in the world.
It attracts famous coders from all over including the popular algorithmic coder Petr Mitrichev. Topcoder tutorials are another good reason to spend time on this platform.
Step 5: Practice, practice, and practice!
Practice day and night. Participate in competitions. Learn from experienced coders.
The more you code, the more you’ll be able to find the suitable data structure and/or algorithm for a specific problem (this is a very important skill for a software development).
TIP: When not participating in competitions, practice solutions and different approaches on a whiteboard while thinking out loud. This will help you in job interviews.
After some months of practice, you’ll be able to ace programming interviews of most companies and land your dream job.
Oldest comments (0)