29-Jan-2019 • 3 min read
Data structures are the main focus in a coding interview, since they form the fundamental building blocks of any software system ever built. With right set of data structures, you could solve impossible to solve problems so easily. Your choice and knowledge of data structures will help in writing excellent software which performs well in terms of speed and data management.
So, let's find out what are some data structures that are essential from interview point of view.
Arrays are the basic data structures that are generally built into any language. Most problems can be solved just by using arrays. Some modern programming languages like Python, Ruby etc. provide ways to use them as stacks and queues in efficient ways.
Strings are everywhere. You won't find a software system which doesn't manipulate text, which is basically a collection of strings. It is therefore essential that you understand strings completely and get adept at dealing with strings in your programs.
Linked lists are memory efficient in terms that they don't need space on stack. They are stored in heaps, in contiguous memory locations by the help of associations called as pointers to nodes. Arrays have a downside of needing to reserve memory in advance(not in modern programming languages though), but linked lists can grow as per your need.
Stacks and queues are used very often in many software systems. It is essential that you know how to use them in the programming language of your choice. Many programming problems can be solved optimally with the use of stacks and queues. These are also used in graph traversal algorithms which form the basic operations in e-commerce, mapping applications.
Trees are widely used in many software systems since they are apt in representing natural hierarchies. Trees are similar to linked lists in terms of implementation in connecting different nodes. They are also efficient algorithmically since they support efficient traversal, retrieval, deletion and addition of nodes. There are different variations of trees including binary trees, binary search trees, binary indexed trees etc.
Binary search trees as the name suggest, they help in search. In this, the data is stored in such a format that retrieval is efficient. In-order traversal of nodes will give you the sorted data. You should definitely prepare various operations that can be performed on Binary search tree including retrieval, insertion, deletion, addition, balancing etc.
Hash tables help in achieving O(1) time complexity for lookup operations if you have implemented the hashing function properly. It is due to this efficiency they are used regularly. No slack on this data structure. You should definitely master this data structure.
How do you think language dictionaries are able to give you results as you type? Because they use a data structure called Trie, which stores the data in such a way that it is efficient to retrieve with just a prefix. Hence, the name Trie which is comes from reTRIEval.
Heaps are the data structures similar to trees but they hold the data in a particular fashion. Heaps are generally of two types - min-heaps and max-heaps. Min-heap is a heap which has a root node with smallest element. And Max-heap vice-versa.
Priority queues are basically queues with an additional constraint of letting some elements leave the queue with priority than others. This data structure is used in implementing a variety of algorithms.
This list is not an exhaustive one. It is an attempt to focus on the more important ones. You should understand the usage and implementation of above algorithms so as to understand many algorithms and paradigms.