Key data structures you should know about your programming interview.

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

After more than 40 years, this identity remains in force. That is why applicants who wish to become programmers must demonstrate that they know the data structures and know how to use them.
')
In almost all tasks, the candidate is required to have a deep understanding of data structures. It is not so important whether you graduate (have graduated from a university or programming courses), or you have decades of experience behind you.

Sometimes in interview questions this or that data structure is explicitly mentioned, for example, “given a binary tree”. In other cases, the task is formulated more covertly, for example, “we need to track how many books we have from each author”.

The study of data structures is an irreplaceable thing, even if you just try to professionally improve yourself in your current job. Let's start with the basics.

Transferred to Alconost

What is a data structure?

In short, the data structure is a container, the information in which 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 task 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 does not matter which task you are solving, one way or another you will have to deal with the data, be it 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.

The most common data structures

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

1. Arrays
2. Stacks
3. Queues
4. Linked lists
5. Trees
6. Counts
7. Bora (in essence, these are also trees, but it is advisable to consider them 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 element is assigned a positive numeric value, called an index, and corresponding to the position of this element in the array. In most programming languages, elements in an array are numbered from 0.

There are two types of arrays:

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

Simple array operations

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

Array Questions Frequently Asked at Interviews

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

Stacks

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

Stack can be compared with a high stack of books. If you need some book lying near the center of the stack, you first have to remove all the books lying above. This is how the principle of LIFO works (the last to come, the first to come out)

This is a stack containing three items of data (1, 2 and 3), where 3 is on top - so it will be removed first:

The simplest stack operations are:

• Push - Inserts an item onto the stack at the top.
• Pop - Returns the top item after removing it from the stack.
• isEmpty - Returns true if the stack is empty.
• Top - Returns the top item without removing it from the stack.

Stack frequently asked questions on interviews

• Calculate postfix expression using the stack
• Sort values ​​on the stack
• Check balanced brackets in expression

Queues

A queue, like a stack, is a linear data structure whose 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 principle of FIFO works (first came, first came out).

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

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.

Queuing Questions Frequently Asked at Interviews

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

Linked list

The linked list is another important linear data structure that at first glance resembles an array. However, a coherent list differs from an array in terms of memory allocation, internal structure, and how basic insertion and deletion operations are performed in it.

The 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 item in the linked list, and if the list is empty, then it is directed simply to null (nothing).

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

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


There are such types of linked lists:

• Singly linked list (unidirectional)
• Doubly linked list (bidirectional)

The simplest operations with linked lists:

• InsertAtEnd - Inserts the specified item at the end of a linked list.
• InsertAtHead - Inserts the specified item at the beginning (from the head) of the linked list
• Delete - Removes 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.

Linked questions frequently asked at interviews:

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

Counts

A graph is a set of nodes connected to each other as 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 describes how costly 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:

• Search wide
• Depth search

Frequently asked questions about interviews:

• Implement wide and deep search
• Check whether the graph is a tree or not
• Count the number of edges in the 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 like 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 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 trees of the following types:

• N-ary tree
• Balanced tree
• Binary tree
• Binary search tree
• AVL tree
• Red and black wood
• 2-3 tree

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

Trees frequently asked for interviews:

Find the height of the binary tree
Find the kth maximum value in the binary search tree
Find the nodes located at a distance of "k" from the root
Find the ancestors of a given node in the binary tree

Boron

Boron, also referred to as “prefix tree”, is a tree data structure that is especially effective for solving problems on strings. It provides fast data retrieval and is most often used for searching words in a dictionary, auto-completion in a search engine, and even for IP routing.

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


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

Questions about bobs, often asked at interviews:

• Count the total number of words stored in the forest
  
• Display all words saved in the forest
  
• Sort the array elements with boron
  
• Build words from the dictionary using boron
  
• Create a T9 dictionary
  

Hash table

Hashing is a process used to uniquely identify objects and save each object by a pre-computed index called its “key”. Thus, the object is stored in the form of “key-value”, and the collection of such objects is called a “dictionary”. Each object can be searched by its key. There are various 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 the hashing data structure depends on the following three factors:

• Hash function
• Hash table size
• Collision handling method

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

Hash questions frequently asked at interviews:

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

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

Good luck and interesting learning! :)

About the translator

The article is translated in Alconost.

Alconost is engaged in the localization of games , applications and sites in 68 languages. Language translators, linguistic testing, cloud platform with API, continuous localization, 24/7 project managers, any formats of string resources.

We also make advertising and training videos - for websites selling, image, advertising, training, teasers, expliners, trailers for Google Play and the App Store.

Read more