Connie Benton

As a beginner in programming, you may be able to work on your projects confidently. However, proving your worth in an interview by showcasing impeccable programming skills may be challenging.

Apart from the pressure that you must feel when your employment depends on a 45-minute talk, there’s one more thing that makes beginner programmers uneasy. You can’t look for answers like you’d typically do if you’re at loss when solving a programming problem.

While you can think your way through a difficult code implementation question, when it comes to data structures, the only thing that’s going to save you is knowledge. Here are the 6 most popular data structures that will help you ace your next coding interview.

Arrays

An array is one of the most basic data structures. Heaps, linked lists, and others are formed based on arrays. Hence, knowing everything you can about arrays is crucial to let your employers know you’re good at data management.

Most interviews would start by asking basic questions. You may need to explain how arrays work and how implementing arrays would work in different languages. You may also need to provide a couple of examples of languages with zero and 1-based indexing. Most popular languages today are zero-based, while some like Cobol and Fortran are 1-based.

Now, when you’re done with the basic questions, you’ll have to answer something more advanced. Typically, you’ll need to provide an answer to a practical problem and write some code to execute your solution.

A good example of this would be finding the second largest number in the array or deleting duplicate entries.

Apart from the duplicate entry questions, there’s another one that often appears on data structure interviews. This type of question heavily relies on maths, like finding the longest consecutive sequence of numbers in an array or a subarray with the largest sum. You’ll need to work on your math skills to answer any of these.

Stacks and queues

Both stack and queue are linear data structures, but the major difference between them is that stack uses the Last In, First Out method while queue uses the First In, First Out method. Essentially, a stack is a data structure where new elements are put on top and are normally retrieved from the top of the list, and a queue is a structure where new elements are placed in the bottom and are retrieved from the top as well.

Apart from talking about the implementation of these two data structures in practice, you will have to answer questions about implementing one as the other. That is, the interviewer may ask how you would implement a queue using a stack or vice versa.

Linked list

Linked lists are the basis for implementing queues and stacks, and are quite crucial for creating graphs. In this structure, elements of the array are interlinked instead of being indexed as in an array. This means you do not need to re-declare memory if an array grows too big as it doesn’t have to be close to each other to work.

This data structure is a great solution when you need to delete or insert items into the list constantly, and you aren’t strained in terms of memory usage. Apart from explaining these differences from the arrays, there’s one question that most interviews that bring up linked lists will mention—the loops.

When you insert or delete an element from the list, you need to rearrange pointers, as there may be a loop in there that breaks the code. Hence, finding and eliminating one is one of the most common linked list questions.

You may also have to find solutions to problems like finding and/or deleting certain nodes of the linked list, flattening and sorting lists, and merging sorting lists. Explaining why merge sort is better than quicksort for linked lists may also appear on the list of questions.

Hash table

Hash tables use a hashing algorithm to assign keys to index values, making an array effectively a two-column table where you can’t choose the value of the first column but can map it with a function itself. The easiest way to imagine a hash table is to assign an index number from 0 to 25 to all letters of the alphabet and then analyze how many times each letter appears in a certain word.

But that’s an easy example. Let’s say a hash table has to present data on response times of your VPN servers in Australia in each Australian town. With so many values to go through the hash function, you’re definitely going to have values that yield identical keys. That’s called hash collision, and it’s one of the major questions on interviews that deal with data structures.

There’s more than one way of solving this problem, and you need to know at least a couple of them and how they would differ. Separate chaining, for instance, is easier to implement than open addressing, but open addressing doesn’t take up as much memory in the end.

Apart from that, you will have to answer some basic hash table questions like finding missing elements and solve maths-related problems like finding a pair with a given sum. Also, expect to hear a question or two about the perfect hash function.

Trees

Probably the biggest set of questions you’ll have to answer when it comes to trees is about typology. While a tree data structure is a rather simple structure with a parent node linking to zero or more child nodes, there are so many subtypes that you can spend half an hour just talking about them.

While there are plenty of tree-like structures, you will be mostly talking about binary trees, BSTs, N-ary trees, AVL trees, as well as some other self-balancing trees and Heap structures.

After you’re done explaining the differences between these types of data structures, you’ll be mostly down to questions that deal with either navigating trees or implementing them in real-life situations.

Examples of the first type of questions would be calculating the height of a tree, transforming binary trees to perfect binary trees, or truncating a given tree to remove that lie on a certain path.

Graphs

A graph is a data structure where a set of nodes is connected with edges. As simple as this sounds, graphs are used everywhere, from GPS-based applications to Facebook. As graphs have a multi-faceted use potential, you may encounter a lot of questions about this data structure during an interview.

One of the easiest questions about graphs you can encounter is detecting and dealing with cycles. Another one deals with the minimum number of steps needed to perform a transformation or an operation.

A huge deal of graph questions is going to be about navigating the network of nodes and edges. You’ll need to explain what topological sorting is to your interviewer and find solutions to problems like finding the shortest path from one node to another in a given graph. You may also need to find the longest path in a DAG, clone a DAG, or calculate the maximum number of edges you can add to one for it to remain acyclic.

Some of the harder problems you may encounter during the interview include the traveling salesman problem, the vertex cover problem, or problems related to the Erdos Renyl model or clustering coefficient.

However, these are higher-tier questions and you may not need to ace them to pass an interview as a beginner in programming.

Excel at your next interview

Learning every possible question about data structures for the interview may be frustrating if you’re just cramming the information. If you want to succeed at interviews consistently, you need to practice and improve your data structure skills.

Work on pet projects to not just learn the typology of data structures but understand how they are used and what are the benefits of one or another structure. If that’s not an option for you, find common data science problems that you can solve and practice that way.

However, that’s going to prepare you for working with data. The only way you can prepare yourself for a data structure interview is by going through many interviews. Take part in mock interviews to polish your skills and excel at the next real interview you schedule.

System design can be a huge leap forward in your career both in terms of money and satisfaction you get from your job. But if your previous job was focused on working closely on one of the components of a system, it can be hard to switch to high-level thinking

Imagine switching from roofing to architectural design. Instead of knowing the ins and outs of making one component, you need to develop a system of components that work well together. This is why so many people fail in system design interviews. They don’t understand what the interviewer wants to hear from them.

What are interviewers looking for?

You walk into an interview, ready to discuss the pros and cons of using NoSQL, fine details of implementing map-reduce, and the possibilities of using the newest node library. What do they ask you? Design Netflix from scratch.

This leaves many interviewees puzzled, and they do two crucial mistakes. The first mistake is focusing too much on the service that already exists. The interviewer doesn’t want to know how Netflix or Twitter is actually made. Rather, they want to see your thought process that goes into creating a similar system.

The second mistake is focusing too much on details. That’s not what you need to do, at least not at first. The technical knowledge and the ability to solve bottlenecks is great, but your main goal for such interviews should be understanding the type of system you need to develop and figuring out the optimal way of solving user problems.

How to ace a system design interview: A step by step guide

Now that you know the direction, let’s go through the interview, step by step.

Step 0: Get good

Preparing for the interview starts months before you arrive at the office. You need to work on gaining knowledge and acquiring skills to be sure that you have what it takes to crack it.

This includes a lot of reading. Start with following high scalability and getting yourself a copy of Martin Klepmann’s Designing Data-Intensive Applications. It’s a great place to start if you have limited experience with system designs.

If you have the knowledge but struggle to apply it to real-world problems, try hosting brainstorming sessions with your pals. After all, trying to design Twitter from scratch can be fun when your employment doesn’t rely on it.

You can go even further and attend a hackathon to try implementing your system design knowledge in practice and get expert advice on it. When you feel confident about your skills, start polishing them before the interview. For instance, you can focus your practice on the typical cases interviewers offer.

In most cases, the interviewer will ask you to design one of the following services:

• URL shortener
• Social network
• Messenger
• Video streaming
• File storage
• Search engine

If you know a bit about each of these services, you’re already on the right track. To gain even more confidence before the actual interview, attend a mock one. You can do it online, and instead of “we’ll call you back”, you’ll receive an expert opinion on your performance.

Step 1: Define the key assumptions about the system

Now, let’s say you’ve made it to the interview. Given the number of applications big tech companies receive, it’s already an achievement. You feel good about yourself, and when the interviewer asks you to develop something like Facebook, you start talking about peculiarities of data storage and what is the best way to create a dynamic feed.

That’s not what they expect to hear. First, you need to understand what kind of system are you building. What is the intended audience? What problems are they solving with this service? You’ll need to answer those questions before you can go any further.

In many cases, the interviewer won’t know the answer. Why? Here’s a very important thing about system design interviews: it’s not about giving the correct answer to a well-defined problem, but it’s about your ability to define the open-ended problem and solve it creatively.

This means you can pretty much decide on these key assumptions together with the interviewer.

Step 2: Define the key features

Once that is out of the way, your next step is defining what kind of features your hypothetical service must possess. Even though your task is designing an already existing service from scratch, it doesn’t mean they should be identical.

For instance, if you’re tasked with designing Facebook, you can take the features this social media has as the basis and work from that. Think of ways you can combine Messenger and Facebook into one app instead of two or suggest how to make ads more user-friendly.

If you’re tasked with developing a Discord-like chat, you’ll need to include secure chat rooms with stable voice chat features. You can also suggest a streaming option. If you need to develop a digital product marketplace such as Pro Essay Writer, you’ll need to combine features like dynamic display of offers, secure access to database, and several payment options. You can throw in a Ai live chat or a monitoring feature to make sure the freelancer the user has hired is busy working on the project.

This will show the interviewers that you’re not only capable of reverse-engineering a service, but actually thinking about the problems customers face and solving them.

Step 3: Define the scale

While the system you design should be scalable, you need to start somewhere. This is why you need to define the scale of the system at first. Think about the read-to-write ratio, the number of concurrent requests the system should expect, and various data limitations.

Once you define these parameters together with your interviewer, you can think of the best way to make that system work well and be scalable. But before that, there’s one more step.

Step 4: Define the data model

Before you can design the hypothetical system, you need to define how you’re going to process data. Find out the main inputs and outputs, how they’re going to be stored, and how the data will flow.

This doesn’t require you to know every little aspect of implementing MongoDB or the latest MySQL library. If you know what database would serve the purpose better, it’s going to be enough. Remember, you don’t need to go into detail too much at this stage.

Step 5: Design the high-level system

By this time, you should have all the information necessary to design the system your interviewer wants. Ideally, you should be no more than 15-20 minutes into the interview.

Start with the entry-points and work your way up to the database. If the interview room has a whiteboard, it’s a great opportunity to visualize your ideas, but even a sheet of paper will do. Draw the architecture that’s needed to support all user and API interactions and present a decent response time.

Don’t be afraid to change the layout of the system on the go. Interviewers don’t care about you making mistakes. They want to see if you’re able to iterate your ideas and improve as you go along.

Step 6: Look for bottlenecks

Once your version of the system seems more or less final, you can get down to details. Look for possible bottlenecks that can slow down or hinder the functions of the system. It’s also okay to take the interviewer’s advice on this. In many cases, the interviewer is an expert on the topic, so you’ll only show your readiness to learn and improve by this.

Find out the bottlenecks and come up with ways of eliminating them either by redesigning a part of the system, or scaling up the hardware.

Step 7: Go in-depth on the subsystem you know well

This is an optional step, but many interviewers ask you to go through this as well. You’ll have to go low-level and elaborate on a subsystem. If you can, steer the conversation to the one you know best.

There’s no shame in admitting you don’t know much about a certain subsystem. After all, you’re no Renaissance man, and the company you’re applying to has teams of experts working on each subsystem, so you’ll have plenty of opportunities to consult with them.

Show off the knowledge you have, and move to the next step.

Step 8: Acknowledge the trade-offs

No system is ideal, and a good system design engineer knows that well. Let the interviewer understand what trade-offs did you make to let the system work well at this stage.

Stay in touch

With that, your 45-minute interview should be over, and the interviewer would be either impressed or bored with your take on the problem. Regardless, you should try to stay in touch with them to increase your chances of getting hired. At the very least, you may get an expert opinion on what went wrong.

If you’ve failed the interview, don’t stop in your tracks. It’s just an opportunity to learn more and practice more. Join Hackathons and do mock interviews to up your skills, and you’ll get the job you’ve been dreaming about.