# Advanced data structures for coding interview preparation

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 !