Graph, not often tested
definition
Nodes connected to each other in the form of a network
the term
Edge: edge, a pair of nodes
Interview related
Implement breadth and depth first search
Check if the graph is a tree
Count the number of edges in a graph
Find the shortest distance between two vertices
Monotone stack monotone stack is rarely tested
Double-ended queue Deque, rarely tested
Union Find is rarely tested
Line segment trees are rarely tested
Tree array Binary Indexed Tree, BIT, rarely tested
Dictionary tree Trie, rarely tested
definition
Also known as: prefix tree, a special tree-like data structure
use
Very effective in solving string related problems
Search a word in a dictionary
Automatic suggestions in search engines
interview
Count the total number of words in the dictionary tree
Print all words stored in dictionary tree
Sort elements in an array using a dictionary tree
Form words from a dictionary using a dictionary tree
Build T9 dictionary: Dictionary tree DFS
Hash table/Hash Map Hash table, often tested
definition
Store uniquely identified objects in the form of key-value pairs
Dictionary: a collection of key-value pairs
Search object value using key key
HashSet/HashMap in Java, unordered_map in C, dict in Python
Supported operations: O(1) Insert / O(1) Find / O(1) Delete
How hash tables work
<br>Working principle: For set. The key gets an index through the hash function, and then the value is stored in the array. <br>For get, find the index through the key and hash functions and get the value.
Why can’t the time complexity of various operations on hash be simply considered to be O(1)?
The key can be a string, an integer, or something of unknown length. Therefore, it is appropriate to use O(L); in a strict sense, the time complexity of any operation is O(keySize) rather than O(1)<br>
How to implement hash function
How to solve hash collision (Collision)
Collision means that two different keys obtain two identical values after calculation by the hash function. There are two main ways to resolve conflicts:<br>Open Hashing. It means that in the array on which the hash table is based, each position is the head node of a Linked List. In this way, conflicting <key, value> tuples are placed in the same linked list. <br>Closed Hashing. It means that when a conflict occurs, the subsequent elements will go to the next position to find an empty space<br>
How to make the hash table continuously expand?
performance factors
Collision handling method
interview
Find symmetric key-value pairs in an array
Will the hash table be used flexibly to solve the problem?
Are you proficient in the basic principles of hash tables?
Track the complete path for convenience
Find if an array is a subset of another array
Checks whether the given arrays are disjoint
134. LRU cache strategy<br>657. Insert Delete GetRandom O(1)<br>954. Insert Delete GetRandom O(1) - Duplicates allowed<br>209. The first character that appears only once
Data Stream class problems<br>960. First Unique Number in a Stream II<br>138. Sum of subarrays<br>105. Copying a linked list with random pointers<br>171. Out-of-order string<br>124. longest continuous sequence
Data structure definition: A data structure can be thought of as a data storage collection and several operations (functions) defined on this collection.
Test method 1: Ask about the basic principles of a certain data structure and ask for its implementation
Example: Talk about the principle of Hash and implement a Hash table
Test method 2: Use some kind of data structure to complete things
Example: Merge K ordered arrays
Test method 3: Implement a data structure to provide some specific functions
Example: The highest frequency K item problem
time complexity:
Describe the time complexity of multiple interfaces<br>
For example, you need to design a Set data structure
Algorithm 1:O(n) lowerBound O(1) add
Implementation method: use array storage, compare each time, and insert directly into the end of the array
Algorithm 2:O(logn) lowerBound O(logn) add
Implementation method: Use Red-black Tree storage, TreeSet in Java, map in C
Array Array, most commonly tested
type
subarray
Interview questions
41. 42,43, Maximum subarray<br>44. Minimum subarray<br>138. Sum of subarrays
Array interval problem
Interview questions
30. Inserting ranges<br>793. Intersection of multiple arrays<br>156. Merging ranges
external sorting problem
Definition: External Sorting algorithm refers to an algorithm for sorting data stored in one or more large files when there is insufficient memory. <br>
Two basic steps:<br>Cut the large file into several small files, and use memory to sort them respectively<br>Use the K-way merge algorithm (k-way merge) to sort several small files merge into one big file
Interview questions
486. Merge K Sorted Arrays<br>104. Merge K Sorted Lists
Bit operations
Definition: Operations on binary bits
Interview questions
365. How many 1’s are there in binary<br>
Tree arrays are rarely considered
Also known as: Fenwick Tree English name: Binary Indexed Tree Abbreviation: BIT is implemented based on prefix and information<br>
Although the name is Tree, it is stored in an array (Array)<br>BIT is a multi-tree, and the parent-child relationship represents the inclusion relationship<br>Use getPrefixSum(k) to implement getRangeSum(x, y)
time complexity
Log(n) Modify the value at any position<br>Log(n) Query the sum of any interval
Features
For an array with N numbers, the following functions are supported:<br>update(index, val) //Update the value at a position in the array within logN time getPrefixSum(k) //Obtain it within log(K) time The sum of the first K numbers in the array
Interview questions
817. Range matrix element sum-variable<br>249. Count the number of previous numbers smaller than itself
Interview related
Find the second smallest element in an array
Find the first non-repeating integer
Rearrange positive and negative values in an array
65. Median of two sorted arrays, difficult problem<br>
6. Merge Sorted Arrays II<br>64. Merge Sorted Arrays<br>839. Merge two sorted interval lists<br>486. Merge K Sorted Arrays<br>577. Merge K sorted interval lists<br>547 . Intersection of two arrays<br>548. Intersection of two arrays II<br>793. Intersection of multiple arrays<br>654. Sparse matrix multiplication<br>931. Median of K Sorted Arrays<br>149. Buying and selling stocks The best time<br>405. Submatrix whose sum is zero<br>944. Maximum Submatrix<br>943. Range Sum Query - Immutable<br>665. Plane Range Sum-Immutable Matrix<br>840. variable range summation
Stack Stack, not often tested
definition
LIFO. For example, in logistics loading, the goods loaded later are unloaded first.
Supported operations: O(1) Push / O(1) Pop / O(1) Top
application
Used for non-recursive traversal of binary trees, computing reverse Polish expressions, etc.
The main data structure of non-recursive implementation of DFS
In breadth-first search (BFS), the nodes to be expanded are recorded.
Queues can be used to implement message queues to complete asynchronous tasks.
When the speed of message production and consumption is inconsistent, a message queue is needed to temporarily store messages that have been sent but not received.
Implement stack mode
Use a storage structure (commonly used arrays, occasionally linked lists) to store elements
Use one array to implement three stacks?
Implement a stack using two queues? <br>
the difference
Arrays have better performance for random access. <br>Linked lists have better performance for inserting and deleting elements.
Exercises<br>
lintcode: 495. Implement stack
494. Dual queue implementation stack<br>
224. Use an array to implement three stacks<br>
operate
push, insert element at the top
pop returns and removes the top element of the stack
isEmptyThe stack is empty and returns true
top returns the top element without removing it
Java uses java.util.Stack, which extends from the Vector class and supports operations such as push(), pop(), peek(), empty(), and search().
C, just use the stack in <stack>. The method is similar to Java, except that peek() in C is called top(), and when pop(), the return value is empty.
Python, use list directly, use slicing operations like [-1] to view the top of the stack, use list.pop() when popping the top of the stack, and use list.append() when pushing the top of the stack. <br>
Interview related
Using the stack to evaluate postfix expressions
Sort the elements of the stack
Determine whether an expression is parenthetically balanced
QueueQueue, often tested
definition
FIFO first-in first-out sequential storage linear data structure, supermarket checkout
Supported operations: O(1) Push / O(1) Pop / O(1) Top
application
Used as the main data structure for the BFS algorithm
operate
Insert elements at the end of the enqueue queue
dequeue removes the head element of the queue
isEmpty column is empty and returns true
top returns the first element of the queue
Method to realize
Implement queue using linked list?
Implement a queue with two stacks? <br>
Implement queue using circular array?
Exercise: 955. Implement Queue by Circular Array<br>
interview
Use queue to represent stack
Reverse the first k elements of the queue
Use a queue to generate binary numbers from 1 to n
642. Moving Average from Data Stream<br>
955. Implement Queue by Circular Array<br>
Linked List, often tested
definition
Node chain: each node contains data and pointers to subsequent nodes
use
Implement file system, hash table, adjacency list
operate
isEmpty, is empty, returns true
interview
Detect cycles in linked lists
Returns the nth node from the last in the linked list
Remove duplicates from linked list
TreeTree
definition
hierarchical data structure
Made up of vertices and edges
There are no cycles in the tree as shown in the graph
type
Line segment trees are basically not tested, they are universal.
Binary tree, often tested
binary search tree
Definition: The left subtree is smaller than the root node, and the root node is smaller than the right subtree. The effect is: the left side is always smaller than the right side
balanced binary tree
Balanced tree (AVL tree)
definition:
It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and the left and right subtrees are both balanced binary trees.
Implementation
Red-black tree, AVL, scapegoat tree, Treap, spreading tree
heap
Definition: A heap is a balanced binary tree. The parent node is smaller than the child node. The excess child nodes are placed on the left child node as much as possible. There is no size relationship between the left and right child nodes. Can be implemented using arrays<br>
Supported operations: O(log N) Add / O(log N) Remove / O(1) Min or Max
Value characteristics: For the min heap, the parent node is smaller than the child node, and there is no size relationship between the left and right child nodes; for the max type heap, the parent node is larger than the child node, and there is no size relationship between the left and right child nodes;
Structural characteristics: It is a binary tree with a height of logN
Time complexity: delete and pop complexity are all logN, find min, or max complexity O(1)<br>
Insertion method: Always insert from the left, ensuring a balanced binary tree. If the inserted number is small, move it up and the parent node moves down. So the maximum complexity is logN<br>
The deletion method is similar to
Implementation method: Exercise: lintcode 130 heapify<br>
Interview practice questions
104. Merge K Sorted Lists<br>612. K nearest points<br>545. Top K Big Numbers II<br>613. Excellent results<br>486. Merge K Sorted Arrays<br>81. In data flow Number of digits<br>544. Top K large numbers<br>401. The kth number from small to large in the sorting matrix
Segment Tree<br>
Definition: Line segment tree is an advanced data structure and a tree structure, to be precise, it is a binary tree. It can efficiently handle issues such as interval modification queries. <br>
Note: It is basically not tested, but if you can master it, you can solve a lot of problems in one go. The line segment tree is implemented based on the divide and conquer method and can be used as a good practice for the divide and conquer method.
interview
Find the height of a binary tree
Find the kth maximum value in a binary search tree
Find the node that is distance k from the root node
Find the ancestor nodes of a given node in a binary tree
104. Merge K Sorted Lists<br>
3 ways
Method 1: Use PriorityQueue
Method 2: Divide and conquer algorithm similar to merge sort
Method 3: Bottom-up pairwise merging algorithm
The time complexity is O(NlogK)
Combined with: Jiuzhang algorithm
The practice questions are all lintcode questions
Wondershare EdrawMind
