### Key to Solving Every Problem in a Coding Interview – Choose the right tool

You are free to make whatever choice you want, but you are not free from the consequences of the choice.

• Introduction
• Data Structures
• Array
• Stack
• Queue
• Tree
• Graph
• Hash-Set
• Tree-Set
• Hash-Map
• Tree-Map
• Heap
• Trie
• Summary

## Introduction

Data structures are fundamental building blocks of a software application and hence it is crucial to choose the right ones for the task at hand. As they are so important for the success of the application, testing your data structures skills in software engineering interviews is common. I have written other posts where I discuss how you should intuitively choose the data structure looking at the problem, another where I discuss a real-world scenario and apply different data structures for different situations. This post is a bit different where I discuss the strengths and weaknesses of each data structure without going into details about when to use them. Strength and weaknesses of the data structures can be measured based on time complexity and space complexity of common operations and that is what you will learn in this post.

In a way, this post is a summary of your data structures analysis class. There are mainly 7-8 data structures that are very common in the coding interviews. In reality, there can be an infinite number of data structures because data structures are just a way to store the data and you can create your own ways of storing data. From the point of view of the coding interview, you are going to get tested on standard data structures and hence you should focus on them. Although I will discuss each data structure in detail in separate posts, you can use this post as a time & space complexity cheatsheet, or as a checklist of different data-structures to study for your interview.

## Data Structures

### Array

This is almost the first data structure we learn in any book, any course, any language.

1. Constant time lookup of an element based on the index.
2. Because lookup based on the index is O(1), update based on the index is also O(1).
1. Insertion or deletion of an element is linear time O(n). (An exception is when the array is sorted. If the array is sorted, a binary search can be used instead of the linear search. Time complexity, in that case, is O(logn).
2. Finding an element is O(n).

The linked list is generally the first dynamic size data structure that you study which builds the foundation for learning tree, graph, etc. data structures.

1. Constant time insertion if you have the pointer to where you want to insert.
2. Constant time deletion if you have the pointer to what you want to delete. (Precisely – pointer to the previous node.)
1. Can’t look up an element based on an index. Searching an element is O(n).
2. Because search is O(n), the update is also O(n).

### Stack

1. Constant time insertion at the top of the stack.
2. Constant time deletion of the top element of the stack.
3. Constant time access to the last inserted element (top of the stack).
1. Can’t efficiently access elements in the stack at random. Insertion and deletion are performed only at the top.

### Queue

1. Constant time insertion at the end of the queue.
2. Constant time deletion from the beginning of the queue.
1. Can’t efficiently access elements in the queue at random. Insertion and deletion are performed only at the end and the beginning respectively.

### Tree

A tree is the best way to represent parent-child relationships which also helps in representing sibling relationships or ancestor relationships naturally. Whenever there is a hierarchical structure, a tree is a natural choice.

1. Time complexities
1. Inorder, preorder, postorder traversals are all O(n).

### Graph

A graph is a natural way of representing networks which can be a social network, a network of nodes (routers, modems, etc.) or transportation networks.

1. Time complexities  (n is #nodes and m is #edges)
1. Depth First and Breadth-First traversals
1. Adjacency list representation – O(n+m)
2. Adjacency matrix representation – O(n^2)
2. Check if there is a direct edge between two nodes
1. Adjacency list representation – O(n)
2. Adjacency matrix representation – O(1)
2. Space Complexities (n is #nodes and m is #edges)
1. Adjacency list representation – O(n+m)
2. Adjacency matrix representation – O(n^2)

### Hash-Set

Sets are used to store keys. Hash set places keys into appropriate buckets after finding the hash value of the key.

1. Major Advantages (The following time complexities are not guaranteed but they are amortized. For the interview purposes, you can use them as they are. In reality, they can be a bit worse than that because of collisions i.e. hash function returning the same bucket number for multiple keys.)
1. O(1) Insert
2. O(1) Delete
3. O(1) Lookup based on the key
1. The worst-case time complexity for all operations is O(n), but in reality, they are as good as O(1) and hence can be assumed to be O(1).
2. Unlike Tree-Set, can’t iterate over the hash set in a specific order.

### Tree-Set

Sets are used to store keys. Tree set stores keys in a balanced binary search tree.

1. Guaranteed O(logn) Search
2. Guaranteed O(logn) Insert
3. Guaranteed O(logn) Delete
4. Can iterate over the tree-set in sorted order of the keys.
1. Like Hash-set, time complexities are not O(1).

### Hash-Map

Same as Hash-set except that values are associated with keys and hence they are also stored in addition to keys.

### Tree-Map

Same as Tree-set except that values are associated with keys and hence they are also stored in addition to keys.

### Heap

Heap is a bit tricky structure. It is generally stored in a binary tree layout but inside an array. (Assuming Max-heap, below are the advantages and disadvantages).

1. Finding maximum from already inserted elements is O(1).
1. Insertion takes O(logn).
2. Only the maximum element can be deleted and takes O(logn)
3. The update is not supported (naturally).
4. Can’t access any element other than the maximum.

### Trie

Trie is very useful in storing a lot of strings in compact space, think dictionary. Although they can be used for other use cases too, the most common use case is to store strings.

1. Can store a large number of strings in compact space (less memory).
2. O(1) search, insert, delete assuming a length of the string to be a small constant number.