A brand new day, and some brand new fun! In the previous post for this series, I presented the basic data structures you NEED to know for any interviews (FAANG or otherwise), if you are a decent software engineer. However, now we'll talk about some data structures that are absolutely essential to solve any of the real interview questions that interviewers will ask you.
Without further adieu.
1. Heaps
What should you practice? It is essential to learn how to create a min/max heap and perform operations on it. If you don't know how to write that code, time to learn that first. Probably here - https://www.geeksforgeeks.org/binary-heap/
Once you go through that, it is time for applying the concept on a leetcode problem here - https://leetcode.com/problems/kth-largest-element-in-an-array/ (Pro tip - There is one other way of solving this. Relates to one type of sorting method. Think about it.)
2. Trie
This is probably the most important data structure you can read up on for an interview. Anything that has strings, or words, or a dictionary of words, you can probably be 90% sure that the question involves a Trie.
What should you practice? You should learn how to construct a trie, and how to add or remove words from it. Removing is usually less important. Go and solve the following leetcode HARD - https://leetcode.com/problems/prefix-and-suffix-search/ (But trust me, it isn't that hard)
From this point on, the complexity of data structures increases, and the frequency of questions you see for them in an interview decreases, so prioritize accordingly.
3. Balanced Binary Search Trees
Level up ! Learn how to implement a Red Black tree (for insertion intensive tasks) or an AVL tree (for lookup intensive tasks). Understand the differences in each, their pros and cons, and probably use it to get brownie points in an interview ! :)
(Pro tip : For those looking for a more advanced implementation that is more practical, go read up on Splay Trees)
4. Binary Indexed Trees
This data structure (that is actually implemented using arrays) is useful to do efficient range operations (for example, range sum). A good question to solve is here - https://leetcode.com/problems/range-sum-query-mutable/
I think I'll stop there, and not mention others like a B-tree, Segment trees, a memory optimized doubly linked list, and so many other data structures ! The ones we have gone over till now are the most used ones, and will give you sufficient knowledge!
Have questions, chat with me anytime !