Knowing Data Structures is crucial for any software interview and almost all the coding questions asked during an interview are based on Data Structures, thus every candidate should brush up on their Data Structures and be ready to solve questions related to them.
Before we begin, let’s understand the importance of Data Structures for candidate selection?
First it is a great way to challenge a candidate during an interview as these questions require thinking and problem solving skills. Also in reality, Data Structures are very important for Performance and/or Memory dependent software where selecting a correct Data Structure over another makes a huge difference and sometimes is the only one that works.
That said it is also valid to say that a lot of the software written out there are not highly dependent on Performance or Memory and thus carefully selecting a Data structure is not as important.
In this article I will briefly go over the most common Data Structures and explain how to select one over another when solving an interview coding question.
i.e. Linked List over Array?
i.e. Binary Search Tree over Hash table?
The Data Structures covered here are:
Array, Linked List, Binary Search Tree, Hash Table, Stack, Queue and Set.
The goal here is not to explain them in detail as there are many resources (i.e. YouTube videos) explaining them thoroughly.
The best way to answer the above question is to think about the advantages and disadvantages of each Data Structure, and once we know them it will be very easy to make a good decision!
Advantages & Disadvantages:
Array:
Array is the most used Data Structure. It is easy to create and is very fast to index (point to) an element (i.e. A[3] points to the forth element in the collection)
One downside of Array though is Insertion and Deletion of elements. This is due to the fact that all other elements in the collection have to be shifted when these operations are performed. For that reason Array is not suitable for Insertion and Deletion operations. Also Array is a not good candidate for Sorting and Searching elements.
Advantages:
Disadvantages:
Linked List:
Linked List as oppose to Array is excellent for Insertion and Deletion operations. This is due to the fact that elements use pointers to point to each other, thus shifting is not required. Because of pointers, Linked List is also great for iterating through the elements in a collection.
One disadvantage of Linked List over Array is that it cannot be used for direct indexing of an element and likewise Array, Linked List is not suitable for Sorting and Searching.
Advantages:
Disadvantages:
Now given the information above, if your solution requires modifying the collection by adding or removing elements consider using Linked List over Array. Likewise if you are indexing an element (i.e. accessing the forth element in the collection) use Array.
Hash Table:
Hash Table is a Data Structure that is often used in the solution of many coding exercises. It is used to access elements using Key Value pairs. An example of a Key Value pair is: Color Name to Hex Color Code (i.e. Black, #000000). Hash Table is excellent for Insertion and Deletion operations.
However, Hash table should not be used when ordering of elements in the collection is important.
Advantages:
Disadvantages:
Binary Search Tree:
Binary Search Tree has similar advantages as Hash table with the difference that it keeps the elements in the collection in sorted order and so is great when ordering of elements in the collection is important.
Advantages:
Stack:
Stack should only be used when elements are inserted and removed according to LIFO (Last-In First-Out).
Advantages:
Disadvantages:
Queue:
Queue should only be used when elements are inserted and removed according to FIFO (First-In First-Out).
Advantages:
Disadvantages:
Check if the solution requires LIFO or FIFO behaviours. For example: A Question asking to check if a given string has matching parentheses (i.e. open close parentheses). The solution is to add an element to the head of the collection when an open parenthesis is seen and remove it from the head of the collection when a close parenthesis is seen afterwards. This is dictating a Last-In First-Out behaviour and therefore should be implemented using a Stack.
Set:
Set is ideal for checking if an element exists in a collection. It can also be used for avoiding duplicate elements in a solution.
Advantages:
Disadvantages: