The original link
Swiss computer scientist Niklaus Wirth wrote a book in 1976 called Algorithms + Data Structures = Programming.
More than 40 years later, this equation remains a truism. This is why the software engineer’s understanding of data structures should be examined during the interview process.
Almost all of the questions require a deep understanding of data structures. Whether you’re just starting out in the workforce (fresh out of college or a programming class) or a veteran with decades of experience.
Some interview questions explicitly mention some kind of data structure, for example, “Given a binary tree.” Others are implicit in interview questions, such as, “We would like to record the number of books related to each author.”
Even for very basic work, learning data structures is a must. So, let’s start with some basic concepts.
What is a data structure?
Simply put, a data structure is a container that stores data in a particular layout. This “layout” determines that data structures are efficient for some operations and inefficient for others. First of all, we need to understand various data structures, so that we can choose the most appropriate data structure when dealing with practical problems.
Why do we need data structures?
Data is the most critical entity in computer science, and data structures can store data in some organizational form, so the value of data structures is self-evident.
No matter how you solve any problem, you need to deal with data — whether it involves employee salaries, stock prices, shopping lists, or even a simple phone book problem.
Data needs to be stored in specific formats according to different scenarios. There are many data structures that can accommodate the need to store data in different formats.
Common data structures
We’ll start by listing some of the most common data structures:
An array of
The stack
The queue
The list
The tree
figure
Dictionary tree (this is an efficient tree structure, but worth noting separately)
Hash table
An array of
Arrays are the simplest and most widely used data structures. Stacks, queues and other data structures have evolved from arrays. Here is a simple array of elements (1,2,3, and 4) of length 4.
Each data element is associated with a positive value, called an index, which indicates the location of each element in the array. Most languages define the initial index as zero. Follow the Wechat official account of Java Technology Stack and reply to “Interview” to get more interview questions carefully organized by bloggers.
Here are two types of arrays:
One-dimensional arrays (as shown above)
Multidimensional arrays (arrays of arrays)
Basic operations on arrays
Insert — Inserts an element at the specified index position
Get – Returns the element at the specified index position
Delete — Deletes the element at the specified index position
Size – Gets the number of all elements in the array
Common interview questions about arrays
Find the second smallest element in the array
Find the first non-repeating integer in the array
Merges two ordered arrays
Rearrange the positive and negative values in the array
The stack
Famous undo operations can be found in almost any application. But have you ever thought about how it works? The idea is to store the historical working state in memory in the order that the last state comes first (of course, it is limited to a certain number). You can’t do that with arrays. But with the stack, it becomes very convenient.
Think of a stack as a row of books stacked vertically. To get to the middle book, you need to remove all the books placed on it. This is how LIFO (Last in first Out) works.
Here is a stack containing three data elements (1,2 and 3), with the top 3 being removed first:
Basic stack operations
Push – Inserts an element at the top
Pop — Returns and removes the top element of the stack
IsEmpty – returns true if the stack isEmpty
Top — Returns the Top element but does not remove it
Common interview questions about stacks
Evaluate postfix expressions using stacks
Sort the elements of the stack
Determines whether the expression is bracketed balanced
The queue
Similar to a stack, a queue is another linear data structure that stores elements sequentially. The biggest difference between stacks and queues is that stacks are LIFO (last in, first out) while queues are FIFO (first in, first out).
A perfect real-life example of a queue: the ticket booth line. If a newcomer joins, he goes to the back of the line, not the front — the person at the front of the line gets the ticket first and then leaves.
Here is a queue with four elements (1, 2, 3, and 4), of which the 1 at the top will be removed first:
Removes the first element and inserts new elements
Basic operations on queues
Enqueue() — Inserts elements at the end of the queue
Dequeue() — Removes the element at the head of the queue
IsEmpty () — returns true if the queue isEmpty
Top() – returns the first element in the queue
Common interview questions about queues
Use queues to represent stacks
Invert the first k elements of the queue
Use queues to generate binary numbers from 1 to n
The list
Linked lists are another important linear data structure that may look a bit like an array at first glance, but differ in memory allocation, internal structure, and the basic operations of data insertion and deletion. Follow the Wechat official account of Java Technology Stack and reply to “Interview” to get more interview questions carefully organized by bloggers.
A linked list is like a chain of nodes, where each node contains data and Pointers to subsequent nodes. The list also contains a header pointer that points to the first element of the list, but when the list is empty, it points to null or nothing concrete.
Linked lists are commonly used to implement file systems, hash tables, and adjacency lists.
Here’s a look at the internal structure of the linked list:
Linked lists include the following types:
Single linked list (one way)
Bidirectional linked list (bidirectional)
The basic operations of linked lists:
InsertAtEnd – Inserts the specified element at the end of the list
InsertAtHead – Inserts the specified element at the beginning/head of the list of links
Delete – Removes the specified element from the link list
DeleteAtHead – Removes the first element of the link list
Search – Returns the specified element from the linked list
IsEmpty – returns true if the list isEmpty
Frequently asked interview questions about linked lists
Reverse a linked list
Detect loops in linked lists
Returns the NTH penultimate node of the list
Delete duplicates in the linked list
figure
A graph is a set of nodes connected to each other as a network. Nodes are also called vertices. A pair of nodes (x, y) are called edges, indicating that vertex X is connected to vertex Y. Edges can contain weights/costs that show the cost of going from vertex X to y.
The type of figure
Undirected graph
Directed graph
In a programming language, a graph can be represented in two forms:
Adjacency matrix
Adjacency list
Common graph traversal calculation method
Breadth-first search
Depth-first search
Common interview questions about pictures
Implement breadth and depth first search
Check whether the graph is a tree
Calculate the number of edges of the graph
Find the shortest path between two vertices
The tree
A tree structure is a hierarchical data structure consisting of vertices (nodes) and edges connecting them. Trees are similar to graphs, but the important feature that distinguishes them from graphs is the absence of loops in the tree.
Tree structure is widely used in artificial intelligence and complex algorithms, which can provide an effective storage mechanism to solve problems.
Here is a schematic of a simple tree and the basic terminology used in tree data structures:
Root – Indicates the Root node
Parent – Parent node
Child – Child node
Leaf – A Leaf node
Sibling – Sibling node
Here are the main types of tree structures:
N yuan tree
Balanced tree
Binary tree
Binary search tree
AVL tree
Red and black tree
2-3 tree
Among them, binary tree and binary search tree are the most common trees.
Common interview questions about tree structure:
Find the height of the binary tree
Find the KTH maximum value in the binary search tree
Find the node k away from the root node
Finds the ancestor node of a given node in a binary tree
Dictionary Tree (Trie)
Dictionary trees, also known as “prefix trees,” are special tree-like data structures that are very effective for solving string-related problems. It provides fast retrieval, is mainly used to search for words in dictionaries, automatically makes suggestions in search engines, and is even used for IP routing.
Here is an example of storing three words “top”, “so” and “their” in a dictionary tree:
The words are stored top to bottom, with the green nodes “P”, “s” and “r” representing the bottom of “top”, “thus” and “theirs” respectively.
Common interview questions about dictionary trees
Count the total number of words in the dictionary tree
Prints all the words stored in the dictionary tree
Sort the elements of an array using a dictionary tree
Form words from a dictionary using a dictionary tree
Build T9 dictionary (dictionary tree + DFS)
Hash table
Hashing is a process used to uniquely identify objects and store each object in some pre-computed unique index, called a “key.” Thus, objects are stored as key-value pairs, and collections of these key-value pairs are called dictionaries. You can search each object using a key. There are many different data structures based on hash, but the most common data structure is the hash table.
Hash tables are usually implemented using arrays.
The performance of a hashed data structure depends on three factors:
The hash function
Size of the hash table
Collision handling method
The following illustration shows how to map hash key-value pairs in an array. The index of the array is computed using a hash function.
Common interview questions about hash structures:
Find symmetric key-value pairs in an array
Trace the full path of the traversal
Find if an array is a subset of another array
Checks whether the given array is disjoint
These are eight data structures you should know before your programming interview.
The original link