Chapter 9
Working with Data Structures: Garbage In Means Garbage Out
IN THIS CHAPTER
Learning the basics of data structures from lists to queues
Understanding how to answer questions about data structures
Finding other resources about data structures
You’ve likely used data structures in your job and/or you studied them in your computer science courses in school. Questions about data structures in interviews are as common as data structures themselves. Interviewers will want to know if you understand which data structures are used in particular situations so they know you’re an efficient programmer.
If you need a data structures refresher, then you’ve come to the right chapter. We start by explaining the basics of data structures from lists and arrays to hashes, stacks, and queues.
Once you’ve soaked in everything about data structures, you learn what interviewers will ask you about them so you can show that your knowledge about data structures is, well, structured.
Finally, you learn how to get more in-depth information if you’re still not feeling confident that you can answer interviewers’ data structures questions correctly. These tips not only include refreshing your memory with good college and general market textbooks about the topic, but also where to find online courses so you can learn about data structures at your own pace.
Learning the Basics of Data Structures
A data structure is a particular method for managing, storing, and retrieving data. Data structures are similar in most programming languages. Even if you’ll need to learn (or brush up on) a different programming language for the job, you’ll be working with arrays, linked lists, hashes, stacks, and queues no matter what programming language your prospective employer wants. So, what we talk about in this chapter applies regardless of the language you’re using.
Managing arrays and linked lists
Lists and arrays are the basic building blocks of data structures, but new programmers are often confused by them. All you may remember about them is that you didn’t understand or know much about lists, so you were drawn to arrays instead.
The good and bad of arrays
Arrays differ from lists in several important ways:
- An array is typically created at compile time if you’re using a compiled language.
- An array is of a fixed size.
- Elements in the array are in a specific order. That means you can easily find out where an element in the array is and access that element quickly.
So, what’s the price? (There’s one for everything, isn’t there?) Because the array is of a fixed size and is in a contiguous segment of memory while the program is running, applying any changes you make to the structure of the array, such as inserting or deleting one or more indexes, is a slow process.
Contrasting arrays with linked lists
A linked list is similar to an array in that it’s a set of objects, types, or data that’s arranged in an orderly manner. A list is linked together by a node, which you can think of like a link in a chain. There are two different types of lists: a single-linked list and a double-linked list.
The single-linked list, as you can probably tell from its description, is the simpler of the two list types. A single-linked list has a head node, and this node contains an element and a pointer to the next node in the list. The result is that lists are dynamic; that is, you can add and delete nodes at any point in the list. After you add or remove nodes, the pointers in each node update automatically so all the nodes in your list remain in perfect order.
And here comes the price again: When you want to access an element within a node, the list has to go through each node sequentially until it comes to the node that contains your element. And that process takes more time than you may expect at first.
A linked list can (but doesn’t have to) occupy a contiguous space in memory. Your computer may place the list anywhere in memory. What’s more, your list can be changed on the fly after you compile your program.
A double-linked list is a set of lists linked together. One node at the end of the first list has a link to the second list, and the first node at the beginning of the second list has a link back to the first list. As you remember, any linked list, single or double, holds more memory than an array because a longer list holds more elements.
When do you use an array or a linked list?
The most important thing to know is that an array’s size is fixed, and it doesn’t matter how many indexes are populated within that array. So, the memory is going to be used for the entire size of the array even though not all the indexes are filled. This means you want to use an array when you know three things:
- The size the array needs to be
- How many elements will exist in the array
- How to access elements in that array quickly, which we talk about later in this chapter
When you don’t know how many elements you’re going to need to store ahead of time, and you may need to add more elements over time, then you need to use a linked list.
For example, if you’re entering a stack of résumés and you want to do so in a sequential manner, and you need to add a new résumé when it comes into your office, then you can add each new résumé to your linked list without having to worry about size limits as you would if you used an array.
Wrangling hashes
A hash is a data structure with two parts: a key and its associated value. It is used to map data of any size onto a set of data of a fixed size. It’s useful in computer science to create a hash table or hash map data structure that maps a key to some value. Hashing is the process of doing that mapping through the use of a hashing algorithm.
This can be hard to get your head around, but we have a good example: a dictionary. (We don’t care if it’s the printed or online variety.) A dictionary has a key, which is the word you’re looking up. The associated value, the definition of the word, comes with that key.
Hash crash
Here’s the catch about creating a hashing algorithm: A key doesn’t have to be associated with only one value. You can create two different hashing algorithms that have different values but have the same key. That leads to what is politely called a collision, and then you can’t find the values you’re looking for when you access the hash key without performing a secondary check of each hash key and see which one has the value you’re looking for.
So, it’s important to understand that you should make a hashing algorithm as unique as possible. If you access a hashing algorithm to find the associated value with it, such as a résumé you’re looking for, you’ll be able to find that data much more quickly than you would with a linked list or even an array because you’re just accessing the hash key. That is, you don’t have to wait for the list to go sequentially through each item in the list to find what you need or specify the index of an array.
If an interviewer ever asks you what fields hashing is used in, remember to tell them it’s used widely in encryption to determine the uniqueness of a file. Creators of popular hashing algorithms in the encryption world virtually guarantee that their hashing algorithm has a key with a unique data value — the file. It also means if you find that two files have the same hash, you can be virtually certain that the files are the same. (If that’s not good enough, you can still double-check each file. We won’t judge you.)
Create a hash map
Programmers keep track of how each hash key connects to its associated value (like a file) using a hash map, also called a hash table. Accessing a hash map to find associated values allows your application to get the element(s) it’s looking for quickly.
When you create a hash map, you should create it so you have more keys in it than elements. That way, you can easily add more elements by simply assigning the element to a hash key that isn’t being used.
A good rule of thumb when you want to avoid running out of space in your hash map is to double the size of the number of keys you need in your hash map and then round the number of keys up to the next prime number. For example, if you have 12 keys connected to elements, double the number of keys to 24 and then round up to the next prime number, which is 29. Having 29 keys will give you plenty of space to add elements to new hash keys when you need to.
Hashes are common enough in programming languages including Java, C++, and C# that if you’re interviewing for a job that uses those languages, then you need to be prepared to show how to use a hash — especially a hash map — to store elements efficiently.
Learning about stacks in your kitchen
A stack is a straightforward data structure that holds elements. The order in which elements are removed from the data structure is known by its acronym LIFO: Last In, First Out.
The easiest way to visualize how stacks work is to look at the stack of dinner plates in your kitchen. Before you wash your dirty dishes and put them away, there’s one plate that’s currently at the top of the stack of plates in the cupboard. After you wash your dishes, you place the clean dishes on top of the stack, and the plate that was at the top of the stack is now somewhere in the middle. One of the washed (and dried) plates you added to the stack is now at the top. The next time you need a dinner plate, you grab the one at the top of the stack. That plate was last in, and first out.
When you have a stack of elements, you can write code to get the first element in that stack and do something with it. For example, if you want to spell a word in reverse, you can put all the letters of the word onto the stack starting with the first letter and ending with the last letter. When you take the letters off the stack and display them on the screen, you see the word is spelled in reverse.
You can tell that a stack is a simple and straightforward data structure to implement, so you can expect that an interviewer will ask you how to implement a stack in an application.
Learning about queues
You need to know about stacks so that you understand what queues are. The only difference between a queue and a stack is that you get elements from the queue using FIFO: First In, First Out.
A queue is a synonym for a line, so a queue data structure behaves just like a line to get into a concert to see and hear today’s hottest singer: The first person in line gets in first, and the last person in line passes through the metal detectors and the double doors last.
Queues are useful when you want to process elements in the order in which they were received. For example, when you’re creating a message processing application, you want to process the messages as they come in. When a message comes in, the queue would start up and enqueue that message. Enqueue means the program adds the element (the message) to the queue.
When the message is at the front of the queue and ready to be processed by your handy application, you dequeue the message. That is, you take it from the queue so your application can use it to do something, such as display the message summary on the screen.
If an interviewer asks you about how to use a stack, you can expect to receive a follow-up question about how to use a queue. That question may be about the properties of a queue, how a queue works, and how to implement a queue. In other words, everything we just told you.
Showing You Know Data Structures
So far, we’ve given you an idea of what interviewers may ask you about data structures. You need to be prepared to answer these questions and to do so the right way, and that’s what this section prepares you to do.
If interviewers don’t ask you about using data structures specifically, they may ask you about problems that require data structures to solve. Don’t be shy in talking about the correct data structures you would use to solve the problem. Showing that you have high levels of competence and confidence when it comes to using data structures will further persuade your interviewers that you’re the right person for the job.
Questions companies have asked interviewees
During a phone screen, the interviewer may ask you about using data structures and how you implement them. If not, it’s likely interviewers will ask about using data structures during the actual interview to find out if you know which data structures to use in a particular situation.
Prepare for specific questions
Here’s a list of basic data structure questions interviewers will likely ask:
- What are the differences between a linked list and an array?
- What is a hash and when would you use a hash and a hash map?
- What is the difference between a stack and a queue?
- When would you use a stack?
- When would you use a queue?
- How do you implement a linked list, a stack, or a queue?
One or more interviewers may also ask you about more complex data structures such as what a binary tree is, so if you feel you need to brush up on those sophisticated data structures, you learn how to find resources about them later in this chapter.
Know how to apply data structures
Your interviewers may ask you to write one or more algorithms on a whiteboard in response to questions that ask you to apply data structures. For example, they may ask you to:
- Write an algorithm to traverse a linked list.
- Create a linked list and then insert and remove elements from it.
- Rearrange an array.
- Reverse the order of a linked list or array — or both. If you write an algorithm for both data structures, you need to explain the differences in those algorithms.
- Queue up messages to process them one at a time or process the most urgent messages first.
Typically, the questions that ask you to create algorithms are in the form of a word problem, such as reversing a string, to make you deduce which data structure is the one that will solve the problem.
Answering data structure questions the right way with Big O
As you write your algorithm, talk about what you’re doing and why the data structure you’re using is the correct one to get the result the interviewer wants.
Big O notation is the first concept to have in mind if you want to answer data structure questions correctly. If Big O reminds you of the tire company instead of a programming term, then what you need to know about Big O notation is that it’s a method for measuring how much time it takes and how much space is required to execute an algorithm.
For example, an interviewer may ask what the Big O notation is for traversing a linked list to find an item within that list. Answering this question correctly requires you to understand that this is a linear search, also known as a sequential search, because you have to progress from one element to the next in the list until you find the element you’re looking for.
If the interviewer asks how accessing a linked list differs from an array, the correct answer is that you can use Big O notation to access the exact index and get the element instantly, such as the element in O(4) to get the element within index 4.
As you talk about the data structure you’re using in your algorithm, you need to cover the following talking points:
- What a data structure is and does.
- What the common operations on the specific data structure are.
- Why you’re using use data structure over another.
- The speed of different operations in different types of data structures.
- The data structure’s set of operations that you can perform. For example, in a linked list you can insert and delete elements as well as remove a node from the list. You can also traverse the linked list to determine its length.
If you want to score bonus points with your interview team, tell them about instances in the past when you’ve used data structures at other companies to complete projects. One example is how you used a stack in a particular situation. Showing your interviewers real-world examples is how you put smiles on their faces.
Finding More Detailed Information
If you have a programmer on your mock interview team who is more experienced than you are — or at least has interviewed with the company you’re going to interview with — then you’re already ahead of your competition.
When you prepare your mock interview, which we talk about in Chapter 8, you should encourage each programmer on your mock interview panel to challenge you, though they probably won’t need any persuasion. They may give you questions that you can’t answer right away and you’ll need to find information online or even crack open another book to help you answer those questions and give you an even better understanding of data structures.
So, where do you start? We’d be remiss if we didn’t suggest Programming Interviews Exposed: Coding Your Way Through the Interview, Fourth Edition by John Mongan, Noah Kindler, and Eric Giguere (Wrox). This book has in-depth examples about the data structures we discuss in this chapter and advanced structures including trees and graphs.
If you’re not allergic to opening books and reading text on real paper (and likely you aren’t, if you’re reading this one), you should also check out computer science books at your local library or that you can purchase from Amazon or your local bookstore. You may already have used some computer science books in college courses but don’t have them anymore, and this is a good opportunity to correct that error and have copies of these books near your desk for easy reference.
Books take up too much space, you say? Paper books are bad for the environment? Books aren’t interactive?
Fair enough. Go online and use websites including LeetCode, which we talk about in Chapter 8, and Interview Cake (www.interviewcake.com) to hone your programming skills interactively.
Do you learn better by watching before doing? There are plenty of computer science courses available (for a fee) on a variety of different websites, including LinkedIn, Udemy, Coursera, Khan Academy, and more.
If you’d rather not pay for online computer science courses, there is a bounty of free online courses available from top-tier universities, including Harvard, Stanford, and MIT. The Computer Science Online website (www.computerscienceonline.org) contains links to these universities’ online course websites where you can search for specific topics such as data structures and view a list of courses that match your search terms.
When you add up what you’ve learned in this chapter, where all these other resources are, and mock interviewers eager to lay down the gauntlet, the real interview will be a piece of cake, or easy as pie, or … we see you’re drooling on the book, so go enjoy a tasty snack. You’ve earned it.