Top 8 Data Structures for Coding Interviews

I get to know this links and questions from my mentor in Timely Bootcamp.

Reference: https://www.youtube.com/watch?v=uhYq27iSk9s 

 

1. Array

- Array is stored in a contiguous way. In RAM, the array would be stored in a subset of that memory in order.

- If we know the index that we want to access, we can directly figure out what is the value in constant time. 

- However, in terms of inserting and removing element, it may take longer if it is not located at the end of array.

- Time complexity of inserting/removing middle of an array: O(n)

- Time complexity of inserting/removing end of an array: O(1) ; big O of one time.

- We can't just remove an element in the middle, because that will be not contiguous anymore. 

 

2. Linked List

- Stored an ordered list of elements. In RAM, the set of values are not have to be contiguous.

- We don't have to shift everything over like we did with an array.

- Insert/Remove End: O(1)

- Insert/Remove Mid: O(1)

 

3. HashMap

- Single most common data structure. It is actually built on top of arrays. 

- Key + Value (The relationship itself is a matter here).

- Key = not like index of array, it could be any arbitrary everything (e.g., characters, numbers, strings). 

- Value = Could be everything

- Insert/Remove/Search: O(1)

 

4. Queue

- Many cases, they are implemented using linked lists.

- Doubly linked list cues: having two pointers between each node. Typically used to process a set of elements in the same order that they are added.

- Push/Pop Front/Back: O(1)

 

5. Binary Tree

- For every single node, the left subtree of that node is going to be less than it.

- For every single node, the right subtree of that node is going to be larger than it.

- Less efficient versions of hashmaps

- Insert/Remove/Search: O(logn)

 

6. Trie/Prefix Tree

- Each note typically represents a single character and each node can have up to 26 children.

- Usually each node is for one of the characters in the alphabet so if you wanted to insert a new word into this 

- ex. A -> N -> T (e.g., autocomplete in google search)

- Insert/Search: O(n)

 

7. Heap

- either min / max heap according to the node value.

- Every level in the tree will be completely full except for the last level potentially of the tree and while they're visualized as trees

- Insert/Pop: O(logn)

- Min/Max: O(1)

 

8. Graph

- wide range of potential

- Node + Neighbors

 

 

Other useful links:

1. https://towardsdatascience.com/seven-7-essential-data-structures-for-a-coding-interview-and-associated-common-questions-72ceb644290

Seven (7) Essential Data Structures for a Coding Interview and associated common questions

2. https://www.hackerrank.com/

HackerRank

3. https://leetcode.com/tag/hash-table/

Hash Table - LeetCode

4. https://leetcode.com/problems/diameter-of-binary-tree/

Diameter of Binary Tree - LeetCode

5. https://leetcode.com/problems/maximum-width-of-binary-tree/solution/

Maximum Width of Binary Tree - LeetCode

6. https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode