Binary search

Concept of search interval:

If it is a left closed and right closed space, the condition for jumping out of the loop is that the search interval is empty, and it returns only when left>right

 

The following are basic binary search, left boundary binary search and right boundary binary search

 

How to quickly find an ip address from all the ip addresses

How to find the square root of a number

recursion

non-recursive

Sorting algorithm

Their respective properties, even optimization, hand tearing, quick arrangement, merging, etc

https://blog.csdn.net/SHAOYEZUIZUISHAUI/article/details/102233729

Quick platoon:

https://blog.csdn.net/SHAOYEZUIZUISHAUI/article/details/100667691

Bubbling:

https://blog.csdn.net/SHAOYEZUIZUISHAUI/article/details/102408256

Merge:

https://blog.csdn.net/SHAOYEZUIZUISHAUI/article/details/100545517

Bucket sort

void BucketSort(vector<int>& vec)
{
	int max = vec[0];
	int min = vec[0];
	// Determine the maximum value of an element
	for (auto it : vec)
	{
		if (it > max)	max = it;
		if (it < min)	min = it;
	}
 
	// Barrels: (max - min) / array The result of length is a multiple of the array size (maximum multiple), and the multiple is used as the number of buckets
	// [Note 1] when the sequence size is vec Size () is small, but the element values are large and scattered (max - min is large), which will cause many "empty buckets" and increase the system overhead
	// For example (0, 13, 19892) - > many "empty barrels"
	// [Note 2]: when the number of elements in the sequence to be sorted is very large (vec.size() is very large), but each element is very small, there is only one bucket, which is time-consuming
	int bucketNum = (max - min) / vec.size() + 1;
 
	// Initialization bucket can be implemented by array or vector. Here, vector is selected for the following reasons
	// int** buckets = new int*[bucketNum]; 	//  Array implementation bucket requires two-dimensional array
	vector<vector<int> > vecBucket;	// The vector container implements a bucket, similar to a two-dimensional array
	// Bucket initialization
	for (size_t i = 0; i < bucketNum; i++)
	{
		vector<int> vecTmp;
		vecBucket.push_back(vecTmp);
	}
	// Implementing bucket initialization with array
	// for (size_t i = 0; i < bucketNum; i++)
	// {
	// 	buckets[i] = new int[vec.size()]; 		//  Each barrel can store VEC at most Size () elements
	// }
 
	// Put the elements to be sorted into the corresponding bucket one by one
	for (size_t i = 0; i < vec.size(); i++)
	{
		// In combination with the above [note], if there is only one barrel, it should be treated separately
		if (bucketNum == 1)
		{
			vecBucket[0].push_back(vec[i]);
		}
		else
		{
			int bucketIndex = (vec[i] - min) / bucketNum;	// Determine which barrel to store			
			bucketIndex = bucketIndex >= bucketNum ? bucketNum - 1 : bucketIndex;
			vecBucket[bucketIndex].push_back(vec[i]);	// This is the advantage of using vector to implement buckets, which can be directly "connected" and automatically expanded later. The array implementation also needs code processing
		}
	}
 
	vec.clear();
	// Traverse "bucket combinations" and sort the elements in each bucket
	// When the elements of each bucket are in order, the whole "bucket combination" traverses from the bucket with "small number" to the bucket with "large number", which is the overall ordered sequence
	for (vector<vector<int> >::iterator iter = vecBucket.begin(); iter != vecBucket.end(); iter++)
	{
		vector<int> vecTmp = *iter;		// *iter is also a vector, which stores the elements in the bucket
		if (vecTmp.size() <= 0)
		{
			continue;
		}
 
		// Sort each bucket. Here, select sorting is used
		// When n is small and stability is not required, selective sorting should be used
		//SelectSort(vecTmp);
		sort(vecTmp.begin(),vecTmp.end());
		for (auto it : vecTmp)
		{
			// After the elements in each bucket are in order, assign a value to vec again. At this time, vec is in order.
			vec.push_back(it);
		}
	}
}

Linked list

Search, location, inversion and connection of linked list

How to judge whether two linked lists have rings

Speed pointer:

First, create two pointers 1 and 2 (two object references in java) and point to the header node of the linked list. Then start a large loop. In the loop body, let pointer 1 move down one node at a time and pointer 2 move down two nodes at a time. Then compare whether the nodes pointed to by the two pointers are the same. If it is the same, it is judged that there are links in the linked list. If it is different, it will continue the next cycle.

For example, in the linked list a->b->c->d->b->c->d, the two pointers initially point to node A and enter the first cycle. Pointer 1 moves to node B and pointer 2 moves to C. In the second cycle, pointer 1 moves to node C and pointer 2 moves to node B. In the third cycle, pointer 1 moves to node D and pointer 2 moves to node D. at this time, the two pointers point to the same node. It is judged that the linked list has a ring

Queues and stacks

Let the interviewer use the queue to write a producer and consumer program under multithreading, and comprehensively investigate the resource synchronization and race state of multithreading

Function call implementation to ask. That is, how to implement the function, including several common call methods of function call, the order of parameters entering the stack, the expansion of memory stack from high to low, the position of stack frame pointer and stack top pointer, the memory distribution of local variables in the function in the stack, who and how to clean up the stack after the function call, etc.

tree

Binary search tree

avl tree

Red black tree

The concept of red black tree, the way of left-hand and right-hand rotation, the average algorithm complexity of finding and inserting and the algorithm complexity of the best and worst cases

Hash table, hash function, hash conflict

Class B tree

Implementation principle of MySQL index

chart

Depth first and breadth first issues