The Most Important Data Structures You Should Know About Your Programming Interview

Nicklaus Wirth, a Swiss computer scientist, wrote a book in 1976 entitled Algorithms + Data Structures = Programs .

After more than 40 years, this identity remains valid. This is why job seekers who want to become programmers must demonstrate that they know the data structures and are able to apply them.

In almost all tasks, a candidate needs a deep understanding of data structures. At the same time, it is not so important whether you are a graduate (graduated from a university or programming courses), or you have tens of years of experience behind you.

Sometimes in interview questions one or another data structure is directly mentioned, for example, “given a binary tree”. In other cases, the task is formulated in a more veiled manner, for example, "you need to track how many books we have from each author."

Studying data structures is an indispensable business, even if you are just trying to improve professionally at your current job. Let's start with the basics.

Translated to Alconost

What is a data structure?

In short, a data structure is a container in which information is arranged in a characteristic way. Thanks to this “layout”, the data structure will be effective in some operations and inefficient in others. Our goal is to understand the data structures in such a way that you can choose from them the most suitable for solving the specific problem you are facing.

Why do we need data structures?

Since data structures are used to store information in an orderly manner, and data is the most important phenomenon in computer science, the true value of data structures is obvious.

It doesn’t matter what kind of task you are solving, one way or another you will have to deal with the data, whether it’s an employee’s salary, stock quotes, a list of products for going to the store or a regular telephone directory.

Depending on the specific scenario, the data must be stored in a suitable format. We have at our disposal a number of data structures that provide us with such various formats.

Common Data Structures

First, let's list the most common data structures, and then parse each one in turn:

1. Arrays
2. Stacks
3. Queues
4. Linked Lists
5. Trees
6. Counts
7. Burs (in essence, these are also trees, but they should be considered separately).
8. Hash tables

Arrays

An array is the simplest and most common data structure. Other data structures, such as stacks and queues, are derived from arrays.

Shown here is a simple array of size 4 containing elements (1, 2, 3, and 4).

Each data item is assigned a positive numeric value called an index and corresponding to the position of this item in the array. In most programming languages, elements in an array are numbered from 0.

There are arrays of two types:

• One-dimensional (such as shown above)
• Multidimensional (arrays in which other arrays are embedded)

The simplest array operations

• Insert - insert an element at a position with a given index
• Get - return an element occupying a position with a given index
• Delete - delete the item with the specified index
• Size - Get the total number of elements in the array

Interview Frequently Asked Questions

• Find the second minimum array element
• Find non-repeating integers in an array
• Merge two sorted arrays
• Reorder positive and negative values ​​in an array

Stacks

Everyone knows the famous “Cancel” option, which is provided in almost all applications. Ever wondered how it works? The meaning is this: the previous state of your work is saved in the program (the number of saved states is limited), and they are located in memory in this order: the last saved element goes first. Arrays alone cannot solve this problem. This is where the stack comes in handy.

The stack can be compared to a high stack of books. If you need a book lying near the center of the stack, you will first have to remove all the books above. This is how the LIFO principle works (Last come, first go).

It looks like a stack containing three data elements (1, 2 and 3), where 3 is on top - therefore it will be removed first:

Simplest operations with the stack:

• Push - Pushes an item onto the stack on top
• Pop - Returns the top item after it removes it from the stack
• isEmpty - Returns true if the stack is empty
• Top - Returns the top item without removing it from the stack

Interview Frequently Asked Questions about the Stack

• Calculate postfix expression using stack
• Sort Values ​​on Stack
• Check balanced parentheses in expression

Queues

A queue, like a stack, is a linear data structure in which elements are stored in sequential order. The only significant difference between the stack and the queue is that in the queue, instead of LIFO, the FIFO principle applies (First come, first go).

An ideal realistic example of a queue - this is the queue of customers at the ticket office. A new buyer is at the very tail of the line, not at the beginning. The one who is in the queue first will be the first to purchase a ticket and leave it first.

Here is an image of a queue with four data elements (1, 2, 3, and 4), where 1 goes first and leaves the queue first:

Simple queue operations

• Enqueue () - Adds an item to the end of the queue
• Dequeue () - Removes an item from the front of the queue
• isEmpty () - Returns true if the queue is empty
• Top () - Returns the first item in the queue

Interview Frequently Asked Questions

• Implement a stack using a queue
• Pay the first k items in the queue
• Generate binary numbers from 1 to n using a queue

Linked list

A linked list is another important linear data structure that at first glance resembles an array. However, a linked list differs from an array in memory allocation, internal structure, and how basic insert and delete operations are performed in it.

A linked list resembles a chain of nodes, each of which contains information: for example, data and a pointer to the next node in the chain. There is a head pointer corresponding to the first element in a linked list, and if the list is empty, then it is directed simply to null (nothing).

Using linked lists, file systems, hash tables, and adjacency lists are implemented.

This is how you can visualize the internal structure of a linked list:


There are such types of linked lists:

• Single Link List (Unidirectional)
• Doubly linked list (bidirectional)

The simplest operations with linked lists are:

• InsertAtEnd - Inserts the specified item at the end of the linked list.
• InsertAtHead - Inserts the specified element at the beginning (from the head) of the linked list
• Delete - Deletes the specified item from the linked list.
• DeleteAtHead - Deletes the first item in a linked list.
• Search - Returns the specified item from the linked list.
• isEmpty - Returns true if the linked list is empty

Interview Frequently Asked Questions:

• Pay a linked list
• Find the loop in the linked list
• Return the Nth node from the top of the linked list
• Remove duplicate values ​​from the linked list

Counts

A graph is a set of nodes connected to each other in the form of a network. Nodes are also called vertices. The pair (x, y) is called an edge, which means that the vertex x is connected to the vertex y . An edge can have weight / cost - an indicator that characterizes how expensive the transition from vertex x to vertex y is.


Types of graphs:

• Undirected graph
• Oriented Graph

In a programming language, graphs can be of two types:

• Adjacency matrix
• Adjacency list

Common graph traversal algorithms:

• Wide search
• Depth Search

Interview Frequently Asked Questions:

• Implement breadth and depth searches
• Check if the graph is a tree or not
• Count the number of edges in a graph
• Find the shortest path between two peaks

Trees

A tree is a hierarchical data structure consisting of vertices (nodes) and edges that connect them. Trees are similar to graphs, however, the key difference between a tree and a graph is this: there are no cycles in a tree.

Trees are widely used in the field of artificial intelligence and in complex algorithms, acting as an effective repository of information in solving problems.

Here is a simple tree diagram and basic terminology associated with this data structure:


There are the following types of trees:

• N-tree
• Balanced tree
• Binary tree
• Binary search tree
• AVL tree
• Red ebony
• 2-3 tree

Of the above trees, the binary tree and the binary search tree are most often used.

Frequently asked interview questions about trees:

Find the height of the binary tree
Find the k-th maximum value in the binary search tree
Find the nodes located at a distance of “k” from the root
Find the ancestors of the given node in the binary tree

Boron

Boron, also referred to as the "prefix tree", is a tree-like data structure that is especially effective in solving string problems. It provides fast data retrieval and is most often used to search for words in a dictionary, autocomplete in a search engine, and even for IP routing.

This is how the three words “top” (top), “thus” (hence), and “their” (them) are stored in the forest:


The words are arranged in the direction from top to bottom, and the green nodes are “p”, “s” and “r” the words "top", "thus" and "their" complete, respectively.

Frequently asked interview questions about burs:

• Count the total number of words stored in the pine forest
  
• Display all words stored in the forest.
  
• Sort array elements using boron
  
• Build vocabulary words using boron
  
• Create T9 Dictionary
  

Hash table

Hashing is a process used to uniquely identify objects and store each object by a pre-computed index called its “key”. Thus, the object is stored as a key-value, and a collection of such objects is called a dictionary. Each object can be searched by its key. There are different data structures built on the principle of hashing, but most often a hash table is used from such structures .

As a rule, hash tables are implemented using arrays.

The performance of a hashed data structure depends on the following three factors:

• Hash function
• Hash Table Size
• Collision Processing Method

The following shows how a hash maps to an array. The index of this array is calculated using a hash function.

Interview Frequently Asked Hash Questions:

• Find symmetric pairs in an array
• Track the full path
• Find if an array is a subset of another array
• Check if arrays are disjoint

The above describes the eight most important data structures that you definitely need to know before you go to a programming interview.

Good luck and interesting learning! :)

About the translator.

Translation of the article was done in Alconost.

Alconost localizes games , applications and sites in 68 languages. Native translators, linguistic testing, cloud platform with API, continuous localization, project managers 24/7, any format of string resources.

We also make advertising and training videos - for sites that sell, image, advertising, training, teasers, expliner, trailers for Google Play and the App Store.

More details