Many minds shudder at the thought of sitting in a technical interview. A job interview at a professional firm can be nerve-racking, grueling, and most importantly – demanding.
Quite often, candidates struggle to understand what topics they should and shouldn’t prepare for the interview.
In this article, we will be discussing the top data structures and algorithms that are essential for competitive programming.
Top Data Structures Every Developer Must Know
Data structures are different types of ways to store and organize data in a computer so that you can access and modify it later on.
Ensure that you study the following listed data structures in-depth during your interview preparation:
Arrays in data structures are a collection of data elements. Here, each data element can be identified by at least a single key or array index.
Arrays make it easier for a programmer to detect the location of a particular data element by adding an offset to the base value. The index zero is regarded as the base value and offset is defined as the difference between two indexes.
For example, you can imagine arrays to be a flight of stairs and you have a friend standing on each step. You can easily identify the location of your friends based on the step they’re on.
Interview questions based on arrays are – rearrange the given array in a decreasing order, use the divide and conquer method to find the maximum sum subarray, etc.
Linked Lists are known as a sequence of data structures that are connected to each other via links.
Every link in a linked list stores a data element and it contains a link to the very next link. You can visualize a linked list as a set of nodes wherein each node points to the node that is next in line.
There are three types of linked lists:
- Single linked list: In this linked list, only forward navigation of the item is allowed.
- Doubly linked list: In this linked list, both forward and backward navigation of a data item is allowed.
- Circular linked list: The last item in the linked list contains the link to the first data element as ‘next’ and the first data element has the link to the last data element as ‘previous’.
You can also perform certain basic operations in a linked list such as – insertion, deletion, display, search, and delete.
Common interview questions based on linked lists are – can you reverse the given linked list, can you remove the loop in the given linked list, find out the middle value in the mentioned linked list, etc.
Stacks are a linear data structure that follow the principle of Last-In-First-Out (LIFO).
A classical example of stacks and the LIFO principle could be a stack of plates in a canteen. You’d typically take out the first plate from the top which was the last to go in.
The stack is an abstract data structure that behaves just like a real-life stack of books, plates, etc. It has a pre-defined capacity and can store only a limited number of data elements.
In an interview, you may be asked questions such as how can you implement two stacks into an array.
You might get confused between queues and stacks because they’re both linear data structures with a pre-defined capacity. However, contrary to the stacks, queues are based on the First-In-First-Out principle.
For example: Think of a queue at an amusement park ride. The first person to go in on the ride is the first person to leave as well.
In queues, data elements enter from the back of the queue but leave from its front.
Based on this concept, you may face questions like – use a queue to create binary numbers from one to n or try to reverse the first nth element of a queue.
Other important data structures that you must study are – graphs, hash tables, and binary search trees.
Once you’re clear about data structures, it’s time to move on to the algorithms.
Algorithms Every Software Developer Must Know About
Recursion is a type of algorithm where a function repeatedly calls on itself either directly or indirectly. The recursive function helps break a given problem into smaller parts and simplify any complex problems at hand.
Complex problems like the DFS of graphs, Inorder Tree Traversal, Preorder Tree Traversal, Postorder Tree Traversal, Towers of Hanoi, etc. can be solved easily with recursion.
Interview questions based on recursion can be – differentiate between direct and indirect recursion, what do you understand by tailed and non-tail recursion, etc.
Bubble sort is an algorithm that switches adjacent data elements if they are not arranged in the correct order. It goes through the array multiple times to ensure that all the data elements are arranged in the correct order. The only disadvantage of this algorithm is that it can perform poorly while working with multiple data elements.
The selection sort algorithm splits an array of given data elements into sorted and unsorted data elements. During each revision of the array, the algorithm inspects the smallest data element in the unsorted data group. It then shifts it to the end of the sorted data group. Its only disadvantage is that it is kind of slow.
Insertion sort is a type of sorting algorithm that constructs the final data array by sorting through one data element at a time. It examines every element and then compares it with the sorted data elements on the left side. After this, it inserts the data elements in the correct order.
One of the most efficient algorithms to exist till date is the binary search algorithm. This algorithm compares the middle data element in an array or a linked list to the target data element. If the values of both the elements are found to be the same, the index of the current element is returned. If not, then the linked list or the array will be cut in half.
The list of data structures & algorithms for competitive programming and nailing your coding interview, doesn’t end here. You must go the extra mile and prepare for topics such as heap sort, merge sort, quick sort, tries, dijkstra’s algorithm, etc.
Try to get hands-on practice by solving real-time problems and focus on concept implementation.