This is the first article in my series on improving your technical skills to perform better at technical interviews. The other articles can be found here:
- Data Structures (you are here)
- Algorithms
- Interview questions (in progress)
- Mobile app interviews (in progress)
- Memory management (TBD)
Why should you learn Data Structures?
Solving engineering challenges efficiently require knowing your data needs, how to store, query and update your datasets. This could mean the trustworthy Array, Set or Hash Table/Dictionary are not the right tools for the job. Luckily, there are other data structures available to you which can solve the problem in a simpler or more efficient way.
It’s quite common to get interview questions on how to implement these data structures so let’s dive into them and understand how they work and when they should be applied.
Popular Data Structures
How a Hash Table works
Before we jump into the more complicated data structures I want to visit one of the most common ones.
Depending on your language of choice the Hash Table might be called a Dictionary or Associative Array; and although there is more than one way to implement them, they solve the same problem, and work similarly.
var myHashTable: [String] = []
myHashTable["hello"] = "world"
print(myHashTable["hello"])) // -> world
Because of how memory allocation works, hash tables store their data in what looks like arrays! They hash (compute) an array index from the hash key (hello above) and use that to decide where in the array to store the data. This typically means that hash tables are not very memory efficient since they allocate a range of memory for the storage array.
It’s really fun to learn how hash tables are implemented as it’s something we use every day in our work, and it’s quite simple!
Learn more:
What Linked List are good for
Linked lists are sequences of data, they sound a lot like arrays but work very differently. Linked lists, unlike arrays, are stored as separate objects with pointers to each other where arrays are stored in a linear way. This allows linked lists to grow and shrink easily but adds some memory complexity due to the use of pointers and not storing objects in a contiguous manner, like an array. Also unlike an array, it’s harder to jump to the N-th item since you need to traverse the linked objects to find the one you’re looking for. Linked lists are often used to implement Stacks and Queues which we’ll cover next. They can also be used to implement sorted lists, like a music playlist.
Learn more:
Stacks and Queues for data processing
Stacks and queues are two similar data structures commonly used for collecting and processing data in a specific order. A stack is a Last-In-First-Out (LIFO) collection: last object to go in is the first object pulled out. A queue is as the name suggests, First-In-First-Out (FIFO). Stacks and Queues can be implemented on top of arrays, but I suggest you learn how to build them with both arrays and linked lists. These are great for processing work or requests in a certain order.
Learn more about Stacks:
Learn more about Queues:
Trees are good at relational data
Trees are used to represent hierarchical relationships between objects. Trees are built up by nodes and each node typically has a parent node and multiple child nodes. Unlike trees in nature, the root node, which has no parent node, is represented at the top. Tree structures can save a lot of time, which we’ll cover in the questions and quizzes article. Tree’s are great for graph data, where data has relationships to each other, for example an auto-complete feature.
Learn more:
Honorary mention, the Binary Search Tree (BST)
It’s not unheard of that companies ask you questions about BST but I’ve not personally come across them. A binary search tree is a type of tree where each node has at most two children, and insertions and deletions are always performed in such a way that the tree is sorted. This data structure is very complex, and from what I hear, it’s one of the harder things you learn in an algorithms class. I recommend knowing what they do and how they work, but I don’t expect these to be common interview questions, unless perhaps you’re interviewing for very senior engineering roles.
Learn more:
Make sure to subscribe to the newsletter below to stay up-to-date when I rease new articles.
Read the next article in this series on Algorithms.