DEV Community

Cover image for Six Data Structures To Help You Ace Your Technical Interview
Emma Bostian ✨ for Ladybug Podcast

Posted on • Edited on

Six Data Structures To Help You Ace Your Technical Interview

It's a new year which means many of us are searching for our next role. It's no secret technical interviews are hard, so we've compiled (hehe) a list of six data structures you should be comfortable with in 2020.

If you're going through a technical interview, these are must-knows.

We chatted about data structures & algorithms on this week's Ladybug Podcast so I recommend checking that out if you haven't already! We'll cover a lot more than the six data structures here!

Since these data structures have been written about until the cows come home, here are some of our favorite resources for learning them!

Good luck, devs!

🐞 Arrays

Array
Arrays are the bread and butter of data structures. They are list-like data structures which allow you to keep track of elements. These elements can be reference types, like objects or other arrays, or primitives, like numbers or strings.

The length of an array in JavaScript is not fixed, meaning you can add values to the array easily.

🐞 Linked Lists

Linked list

Linked lists are a data structure which isn't built-in to JavaScript, but can be created out of other JavaScript data structures.

A linked list represents a series of nodes where each node points to the next node in the list.

There are also doubly-linked lists where each node also points to the previous node in the list.

This structure uses the LIFO, or last-in-first-out, method where nodes are added to and deleted from the same end.

🐞 Stacks

A stack is not a built-in JavaScript data structure but can be built using arrays.

Stack

A stack is based on the LIFO, or last-in-first-out, concept. A stack is like a pile (or stack) of books where you have to take the top book off before you can get to the bottom book (unless you're a savage).

Stack

Stacks allow for constant time adding and removing of an item but unfortunately they don't provide constant-time access to the nth item in the stack.

🐞 Queues

A queue is similar to a stack, but uses the FIFO, or first-in-first-out, method. You can think of a queue like a line of people waiting to buy a movie ticket. The person who has been in line the longest (first) is the first to be serviced.

Queue

🐞 Binary Trees

BST
Binary trees are a data structure consisting of a series of nodes where each node can have a maximum of two child nodes as well as a value. The root is the top node in the tree structure and doesn't have a parent node.

A binary search tree is another type of binary tree where all node values are distinct, every parent node has a left child whose value is less than it and a right child whose value is greater than it.

🐞 Graphs

Graph

Graphs are a data structure comprised of nodes with edges. If a graph is directed, that means each edge has a direction associated with it (like a one-way street). In contrast, undirected doesn't have associated edge directions.

You might have a graph of people (purple) and movies (green) where each person can have several favorite movies but movies don't have a favorite person.


What are some other resources you like for learning data structures and algorithms?!

Leave yours below! 👇

Top comments (41)

Collapse
 
sergchr profile image
Serhii

Great. What data structures we will need to know in 2021? I want to prepare myself!

Collapse
 
dexygen profile image
George Jempty

The same ones you needed to know in 2020. These "in 2020" posts are nothing but click-bait in my opinion. Surprised to see one working so well in February. Maybe we should start flooding the site again.

Collapse
 
kylefilegriffin profile image
Kyle Griffin

I read this article because Emma knows how to write articles. If it was written by someone else, I may have not.

Thread Thread
 
dexygen profile image
George Jempty • Edited

So you too are judging a book by its cover -- thanks for the validation \s

Collapse
 
yaser profile image
Yaser Al-Najjar

Easy:

  1. Arrays.
  2. Linked Lists.
  3. Stacks.
  4. Queues.
  5. Binary Trees.
  6. Graphs.

Prepare yourself well 😆

Collapse
 
ssimontis profile image
Scott Simontis

I think graphs are incredibly valuable because of the amount of insight they can reveal within datasets. Dictionaries can also be a very powerful tool from my (pretty basic) studies of machine learning, along with hashing functions (although that's technically getting into algorithms). I still don't know what to make of the blockchain and if there is any value in learning it, so I suppose I will learn it and report back!

Collapse
 
emmabostian profile image
Emma Bostian ✨

HAHA I don't know but I like this comment!

Collapse
 
canderson93 profile image
Carl Anderson

It won't be invented until later this year, but "Abstract inverted hash-heaps" and going to become very popular.

Collapse
 
aminmansuri profile image
hidden_dude

I'd say linked lists are overrated. Instead learn about dynamic arrays (aka ArrayLists).

Others to learn are:

  • hash tables
  • priority queues (esp. the heap version)
  • red black trees (esp. leftist 2-3 red black trees)

For extra credit learn about:

  • skip lists (coolest thing since swiss cheese)
Collapse
 
aleksandrhovhannisyan profile image
Aleksandr Hovhannisyan • Edited

I'd say linked lists are overrated

They definitely aren't. Compare the efficiency of removing the head of a linked list to removing the first element of an array/arraylist, and you'll understand why they're used. Linked lists take advantage of pointers to efficiently insert and delete nodes. Arrays don't have that luxury because memory is allocated in consecutive blocks, and thus removing an element requires the remaining elements to be shifted.

Collapse
 
aminmansuri profile image
hidden_dude • Edited

Its interesting you'd say that. But one factor many people seem to forget is cache misses. ArrayLists are cached to the point that huge portions of the array stay in the cache while using it, while LinkedLists can often lead to many cache misses increasing the time to access quite a bit.

Linked lists consume a lot more memory as well since you ALWAYS pay a 2x penalty when creating a node (3x penalty if you have a doubly linked list like in Java).

Some benchmarks have surprisingly shown ArrayList to beat LinkedList even when you'd expect LinkedList to win (like shift scenarios). I think there's a case to use LinkedList if you do heavy removals in the middle of the list often. But that is an extremely rare use case. Usually the benefits of ArrayList far outweigh LinkedList. Namely:

  1. I uses at lot less memory (so less memory pressure)
  2. Is compact and contiguous so it often fits in the cache and results in a lot less cache misses
  3. Allows for indexed random access

Here's a more detailed analysis if you're interested:

slideshare.net/jpaumard/linked-to-...

Here's another:

springframework.guru/java-arraylis...
(and this code tests worst case scenarios and doesn't make use of tricks to force the ArrayList to avoid resizing too much)

ps. the case of adding and removing to the head of a linkedlist can often be reproduced by storing your list backwards in an ArrayList and adding/removing from the end. But even in the shift scenario many times ArrayList may win because caches matter!

Thread Thread
 
aleksandrhovhannisyan profile image
Aleksandr Hovhannisyan

Did not know about those points!

Thread Thread
 
canderson93 profile image
Carl Anderson

A lot of the criticisms of linked lists vs ArrayList are language-specific...

In languages like C and Java, arrays (and the underlying arrays in ArrayLists) have to be created with a fixed size. This memory is allocated in a block. If you need to insert more items than your array has, you have to request a larger block of memory and copy things across. You also have the problem where the array is taking up memory even if it's not actually being used, although with modern tech this is largely irrelevant.

The linked list addresses this problem by allowing you to create a list by storing the items in disparate pieces of memory, and storing references. The memory allocation per item is higher, since you also have to store references, but the list can happily grow to any size and has a constant insertion/deletion cost.

The big tradeoff of Linked Lists is that you lose the ability to randomly access the list. If you want the nth element, you have to traverse the entire chain until you get there. This is actually a perfectly good tradeoff for setups where you need to constantly access the first element of the list, like a queue or stack.

Like all data structures, whether it's correct for you depends heavily on your situation. In languages like JavaScript that have dynamic arrays anyway, it's probably not worth thinking about.

Thread Thread
 
aminmansuri profile image
hidden_dude • Edited

But you're forgetting the cache tradeoff.. the cache tradeoff of linked lists vs dynamic arrays (aka. ArrayLists) is considerable.

It can make a very large performance difference if every time you access a new item in the list you have to suffer a cache miss.

Also I don't think these "criticisms" (I prefer comparison) are language specific. Underlying it all is the concept of a fixed block of memory you allocate for an array or for a node. How you do those allocations and what their dispositions in RAM are is very relevant when figuring out the practical performance behaviors.

It may be that Python or Javascript hides this from you by implementing the dynamic array outright, however, its the very selection of the data structures used in these languages that will dictate their performance characteristics.

I'm using Java as an example. But the underlying notions of how you create lists are the same.

Collapse
 
sidvishnoi profile image
Sid Vishnoi

Conceptually, linked lists are a good first step for learning trees/graphs (and hashmap implementation).
Practically, linked lists are essentially useless unless you're doing interviews or some niche low level programming.

Collapse
 
tamouse profile image
Tamara Temple

reread the first two paragraphs

Collapse
 
aminmansuri profile image
hidden_dude

Also another way to implement "linked lists" is to create two arrays:

values = [5,6,2,4,8]
next = [1,2,3,4, null]

Here the next array basically stores the pointers to the next "node".

My parallel processing professor says this is the "correct way" to do linked lists because it allows much greater levels of concurrency. But really its kind of a hybrid between the array list / dynamic array and the classical disjoint linked list approach. One big advantage is its MUCH better cache behavior and its ability to store the data in a compact form that is better with the cache.

Finally, this approach allows you to have several "next" arrays holding links in different order (which is useful for atomic behavior during parallel or concurrent processing).

Collapse
 
pclundaahl profile image
Patrick Charles-Lundaahl

This is really cool! Thank you for sharing!

Collapse
 
deciduously profile image
Ben Lovy

Tell that to a Lisper.

Collapse
 
aminmansuri profile image
hidden_dude

Does Lisp mandate a LinkedList implementation?

Also I don't think the designers of Lisp were very concerned about performance issues, or cache misses, etc..

Thread Thread
 
tyrrrz profile image
Oleksii Holub

Functional programming languages heavily use linked lists because of immutability. If you need to add an item to the list, you can create a new tail and re-use the existing list. It's extremely good for performance. Also, head/tail pattern matching works really well on linked lists.

Thread Thread
 
aminmansuri profile image
hidden_dude • Edited

True.. immutability is hard to achieve with a growing dynamic array. Link list implementations do that better.

Collapse
 
dexygen profile image
George Jempty

Linked lists are not over-rated, in fact they provide a conceptual foundation for block-chain (as do graphs)

Collapse
 
aminmansuri profile image
hidden_dude

They've also been used in file systems and skip lists (which are super awesome).

But dynamic arrays often got ignored in intro data structures classes. (Maybe not anymore with the advent of Java)

Collapse
 
juanvg profile image
Juan Vela

Regarding the linked list, "This structure uses the LIFO, or last-in-first-out, method where nodes are added to and deleted from the same end." is completely false (specially if it's a sorted one). You can add a new node wherever you want, and the same happens for deletion. You shouldn't mix it with the stack structure

Collapse
 
chriscwz profile image
Chris Chia

Hey there, thanks for the article! But for the sentence: “If a graph is undirected, that means each edge has a direction associated with it (like a one-way street). In contrast, undirected doesn't have associated edge directions.”, don’t you mean “If a graph is directed” instead?

Collapse
 
emmabostian profile image
Emma Bostian ✨

Oops yep thanks

Collapse
 
achargoy profile image
Chargoy

Nice post, congratulations and thanks for sharing.

Just a quick observation, in Queue topic:
A queue is similar to a stack, but uses the FIFO, or first-in-first-out, method. You can think of a stack like a line of people waiting to buy a movie ticket. The person who has been in line the longest (first) is the first to be serviced.
I think is queue instead of stack, isn't it?

Collapse
 
emmabostian profile image
Emma Bostian ✨

YES THANKS

Collapse
 
achargoy profile image
Chargoy

Thanks to you for sharing your knowledge .

Collapse
 
anshulnegitc profile image
Anshul Negi

The article would have been more elegant if you had added real-world problems that can be solved using these data structures.

Collapse
 
waylonwalker profile image
Waylon Walker

I came into data science as a second career without a CS degree. I can say that I have a fairly good understanding of how these are implemented in scripting languages like python and JavaScript. This episode was very interesting to hear just a bit deeper into some of these topics. The supplemental images in this post are also fantastic.

Collapse
 
caiangums profile image
Ilê Caian

Nice work @emmabostian !

Just a small point for all those who want to search about it: Graphs are so freakin more powerful than just a simple Data Structure.

Through my College, I had an entire semester just studying Algorithms specific for Graphs and its properties. In comparison, trees were just one of the parts from my Data Structures course in the previous semester.

Collapse
 
brunotag profile image
Bruno Tagliapietra • Edited

I'd add a seventh one, too important to miss: the hash sets/hash tables/hash maps/dictionaries/maps.. in general, the constant time O(1) data structures that are sooo key to drastically improve performances sooo many times.

By the way, one of the best introductory articles to data structures I've ever seen!

Collapse
 
horaceshmorace profile image
Horace Nelson

Here, I fixed that second paragraph:

“If you're going through a technical interview with interviewers who have zero idea how to qualify a dev (and thus lean on outmoded engineering interview dogma and arrogant “stump the dev” questions), these are must-know-how-to-fake-your-way-throughs.”