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.

Table of Contents

  • Introduction
  • Data Structures
    • Array
    • Linked List
    • 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. Major Advantages
    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).
  2. Major Disadvantages
    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).

Linked List 

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. Major Advantages
    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.)
  2. Major Disadvantages
    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. Major Advantages 
    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).
  2. Major Disadvantage
    1. Can’t efficiently access elements in the stack at random. Insertion and deletion are performed only at the top.

Queue

  1. Major Advantages
    1. Constant time insertion at the end of the queue.
    2. Constant time deletion from the beginning of the queue.
    3. Constant time access to the front of the queue.
  2. Major Disadvantages
    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
  2. Major Disadvantages
    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. Major Advantages
    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.
  2. Major Disadvantages
    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. Major Advantages
    1. Finding maximum from already inserted elements is O(1).
  2. Major Disadvantages
    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. Major Advantages
    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.
  2. Major Disadvantages
    1. If the amount of data is less, a trie may actually consume more memory than storing strings in some other data structures.

Summary

In this quick post, we briefly discussed the key properties of the major data structure. If you haven’t already, I strongly encourage implementing your own version of all the above data structures and common operations on them. Implementing them yourself will help you make your understanding stronger. If you ever have to use some data structure in a unique way, you will precisely know what changes to make. for example, you want to support an efficient search operation in a heap, so you might have to implement your own version of a heap which also maintains a map or a set.

Also, don’t forget to like, share the post, and subscribe to my blog. Should you need more explanation about any data structure, let me know in the comments below. I would also be interested in knowing your thoughts about the post and what would you like me to write next, put that in the comments too.

Happy Interviewing!


Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s