1. The prefix tree
1.1 illustrates
The prefix tree has something to do with the greedy algorithm, let’s not say what it is.
A prefix tree, also known as a Trie, word lookup tree, etc., is a tree-like structure used to store a large number of strings.
Its characteristic is that it is space for time, using the common prefix of string to reduce the cost of query time to achieve the purpose of improving efficiency.
1.2 Classic prefix tree
The characters of a classical prefix tree are stored on the path, and each node has no data.
1.3 Code Definition
1.3.1 Node Structure
To implement certain functions with Trie, data items are actually added to the nodes.
public class Node {
// How many times the node has been reached when building the prefix tree
int pass;
// Is this the end node of a string, and if so, how many end nodes of a string
int end;
// The path of each character
Node[] nexts; // HashMap<Char, Node> -- TreeMap<Char, Node>
public Node(a) {
this.pass = 0;
this.end = 0;
// If 'a'-'z' is in the dictionary, then next[26], corresponding to subscripts 0-25
// Check whether there is a path by checking whether there are nodes at the lower level
// nexts[0]==null indicates that the child has no path for storing 'a'
// nexts[0]! = NULL indicates that the parent has a path that stores 'a'
nexts = new Node[26]; }}Copy the codeNote:
In the prefix tree, the downward path of each node is achieved by mounting the subordinate nodes. In the implementation of the code is the use of the array of subscript, to mount the number of the subordinate nodes, so that you can use the subscript and the character of one to one to achieve each edge “carry” different character information.
If you need to store strings that contain many types of characters, then using arrays to store mount nodes is not appropriate. For example, Java supports more than 60,000 characters. You can’t start with an array of 60,000 characters. So if you have a lot of characters, you can replace the array with a hash table to store the mount nodes, and the key of the hash table can also correspond to the characters one by one.
When you replace the array with the hash table, the algorithm as a whole does not change, but the Coding details change.
However, with hash table storage, paths are unordered from path to path. If you want the paths to be organized in order like array storage, you can use ordered table storage instead of hash table storage.
Store the string again with the node where the data item was added:
By adding nodes with data items, we can easily solve many problems, such as:
-
How do I know if the string “BCK” is stored in the Trie?
A: Starting at the root node, is there a path to ‘b’? A; Is there a path to ‘C’? A; And then is there a way to ‘K’? A; Then check the end of the node at the end of the ‘k’ path, if end! If end = 0, “BCK” is stored. If end = 0, “BCK” is not stored.
-
How do I know how many strings are prefixed with “ab” out of all the strings stored in Trie?
A: Starting at the root node, is there a path to ‘a’? A; Is there a way to ‘B’? A; Then look at the pass of the node at the end of the ‘b’ path. The value of pass is the number of strings prefixed with “ab”.
-
How do I know how many strings are stored in the Trie?
A: Check the pass of the root node.
-
How do I know how many empty strings are stored in the Trie?
A: Check the end of the root node.
Through the above problems, we can find that, with the data item information of node species, we can query each string stored in Trie very conveniently, and the cost of query string is very low, only need to traverse the number of characters in the string to be queried.
1.3.2 tree structure
public class Trie {
/ / the root node
private Node root;
public Trie(a) {
this.root = new Node();
}
// Related operations. }Copy the code1.4 Basic Operations
1.4.1 Adding a String
From the root node, pass increases by 1, and end increases by 1 at the end of the string.
Code:
public void insert(String word) {
if (word == null) {
return ;
}
char[] charSequence = word.toCharArray();
// The starting node of the string is the root node
Node cur = this.root;
cur.pass ++;
for (int i = 0; i < charSequence.length; i ++) {
int index = charSequence[i] - 'a';
// Mount the node corresponding to this character if it is not mounted
if (cur.nexts[index] == null) {
cur.nexts[index] = new Node();
}
// Go down
cur = cur.nexts[index];
cur.pass ++;
}
// Record the end of string node
cur.end ++;
}
Copy the codeNote: Each string is added from the root, which means that each string is prefixed with an empty string.
1.4.2 Deleting a String
If the string exists, start at the root node and decrement the pass of nodes along the string by 1, and the end of the string decrement by 1.
Code:
public void delete(String word) {
// Determine whether to store the word
if (word == null || search(word) == 0) {
return ;
}
char[] charSequence = word.toCharArray();
Node cur = this.root;
cur.pass --;
for (int i = 0; i < charSequence.length; i ++) {
int index = charSequence[i] - 'a';
// The current node's children pass 0 after updating the data, meaning that no strings have passed through the node
if (-- cur.nexts[index].pass == 0) {
// Release all nodes of the sub-path
cur.nexts[index] = null;
return ;
}
cur = cur.nexts[index];
}
cur.end --;
}
Copy the codeNote: If only one of the target strings is stored in the Trie, then after modifying the node data, you need to release all the extra nodes. In Java, we have automatic garbage collection, so the first time we walk through a node with a pass of 0, we can just set it to null, and all the children of that node will also be automatically collected. If implemented in C++, you would iterate to the end, calling the destructor to manually release the nodes when you backtracked.
1.4.3 Query character string
Query the end of the string if it exists.
Code:
// Query the number of times the word has been stored
public int search(String word) {
if (word == null) {
return 0;
}
char[] charSequence = word.toCharArray();
Node cur = this.root;
// Only iterate over the Trie without updating the data
for (int i = 0; i < charSequence.length; i ++) {
int index = charSequence[i] - 'a';
// If no node is mounted, the string is not stored
if (cur.nexts[index] == null) {
return 0;
}
cur = cur.nexts[index];
}
// Return the end of the node at the end of the string
return cur.end;
}
Copy the code1.4.4 Querying prefixes
Query the pass of the node at the end of the prefix string if it exists.
Code:
// Trie stores the number of strings prefixed by pre
public int preFixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] charSequence = pre.toCharArray();
Node cur = this.root;
// Only iterate over the Trie without updating the data
for (int i = 0; i < charSequence.length; i ++) {
int index = charSequence[i] - 'a';
// If no node is mounted, no string is prefixed with this substring
if (cur.nexts[index] == null) {
return 0;
}
cur = cur.nexts[index];
}
// Return the pass of the node at the end of the pre substring
return cur.pass;
}
Copy the code2. Greedy algorithms
2.1 concept
Under a certain standard, the first sample that meets the standard is considered, and the last sample that does not meet the standard is considered, and the algorithm that finally gets an answer is called the greedy algorithm.
In other words, instead of thinking in terms of global optimality, what you get is a locally optimal solution in some sense.
2.2 illustrates
The greedy algorithm is actually the most commonly used algorithm, and the code implementation is very short.
Many greedy algorithms only want to find a good solution, not an optimal solution. That is to say, most everyday greedy algorithms, the process from local optimum to global optimum can’t be proved, or it can’t be proved, because sometimes greed is very subjective. But we daily contact with the greedy algorithm problems are deterministic, is able to find the global optimal solution, then the investigation of the greedy algorithm needs to have a proof from the local optimal to the global optimal.
This article will not show the proof process, because for each problem, it is different how the local optimal strategy leads to the global optimal proof. There won’t be enough time during the interview if every greedy algorithm question proves it. Here’s a very useful technique that requires you to prepare a lot of templates, but only once. And then when you do the greedy algorithm problem later on, the answer will be faster and more accurate, much faster than the proof.
2.3 Conference Problems
Topic:
Some projects take up a conference room for presentations, and the conference room cannot accommodate two presentations at the same time. Given the start time and end time of all projects and each project, you arrange the presentation schedule, and request the most presentations to take place in the conference room. Returns the maximum number of lectures.
Analysis:
Greedy Strategy A: The earlier the project starts, the earlier it starts.
The global optimal solution cannot be obtained, as shown below:
Greedy strategy B: Schedule shorter projects first.
The global optimal solution cannot be obtained, as shown below:
Greedy strategy C: Schedule projects that end earlier.
We can get the global optimal solution.
Counterexample of Strategy A:
Counterexample of strategy B:
Code:
public class Solution {
static class Program {
// Start time of project
public int begin;
// Project end time
public int end;
public Program(int begin, int end) {
this.begin = begin;
this.end = end; }}// Define a Program comparator to compare the end time of the Program
static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program program1, Program program2) {
returnprogram1.end - program2.end; }}public int arrangeProgram(Program[] programs, int currentTime) {
if (programs == null || programs.length == 0) {
return 0;
}
// The number of fields can be arranged for the project
int number = 0;
// Sort the Program array by the end time
Arrays.sort(programs, new ProgramComparator());
for (int i = 0; i < programs.length; i ++) {
// If the current time has not reached the meeting start time, schedule the meeting
if (currentTime < programs[i].begin) {
number ++;
}
// The current time comes to the end of the meeting
currentTime = programs[i].end;
}
returnnumber; }}Copy the code2.4 Problem solving routines
If you look at 2.3, you have to wonder, why is greedy strategy C the optimal solution? Let’s not worry about why greedy strategy C is the right strategy, but it’s the deception, the skillful deception.
In problems related to greedy algorithms, you always have a number of greedy strategies, and it’s good to be able to use counterexamples to overturn a number of greedy strategies. But if there are a few greedy strategies that seem to work for you, but you can’t come up with any counterexamples, do you need to prove them mathematically? You can do it in private, but never in an interview!
The mathematical proof of greedy strategy is different from problem to problem, because each problem has its own business, and the way to prove it is bizarre and a test of mathematical ability.
What’s the best way to see if your greedy strategy is correct? The logarithmic detector.
Problem solving routine:
- To achieve a solution X that does not rely on greedy strategies, the most violent attempt can be made.
- Imagine greedy strategy A, greedy strategy B, greedy strategy C…
- The solution X and logarithmic device are used to verify each greedy strategy, and the correct greedy strategy is learned experimentally.
- Don’t worry about the proof of the greedy strategy.
Preparation:
- Prepare violent attempts or fully aligned code templates.
- Prepare the logger code template.
2.5 Interview Status
The questions of greedy algorithm are inflexible, and the proportion of them in the interview is relatively low, about five questions at most one question.
First, greedy algorithm problems do not test Coding skills, because the code is extremely simple.
Second, the problem of greedy algorithm does not distinguish, as long as the greedy strategy to find the right, to do the same, only 0 and 1 difference.
3. The logarithmic
3.1 illustrates
Logers are very useful and can help you solve a lot of problems.
Suppose we want to test method A, but there are many different strategies for the same problem. If I do not consider the complexity of the event, I can write a violent attempt to solve the problem (such as listing all the percombinations), we do not pursue the advantages and disadvantages of time complexity, but it is good to think and easy to write method B. Why measure method A? Because maybe method A is harder to think about or the time complexity is lower.
Before, did you need to rely on online OJ for every test? If you rely on OJ for every question, do you have to go to OJ for a new question? Can’t find it? You’re not gonna practice it? Secondly, the online test data is also thought by a person, so when he prepares the test case, will he not make your code run error, but not let you pass? You may have passed, but can you guarantee that your code is correct? Not necessarily. That’s where you need the logist method, which is foolproof.
3.2 implementation
Implement a random sample generator, can control the sample size, can control the number of tests, and can generate random data. Run the generated data once in method A to get res1 and again in method B to get res2. Compare res1 and RES2 to see if they are consistent. You measure it tens of thousands of groups, and then change the size of the sample, when you find that Res1 and Res2 are not consistent, then method A is wrong, or method B is wrong, or all wrong.
Random numbers in Java:
// return a double for all decimals in [0,1] with equal probability
random = Math.random();
// return a double for all decimals in [0,N] with equal probability
random = N * Math.random();
// All integers on [0, n-1], equal probability return one, type int
random = (int) (N * Math.random());
Copy the codeBy generating random numbers, you can make any part of the test sample random, such as sample size, test times, test data.
The business logic of each topic is different, and the realization of the logger is also different, which needs to be realized according to the actual situation.
4. Interview questions
4.1 Finding the median
Topic:
The user uses a structure to store N digits one by one, and is required to find the median of all digits currently stored in the structure at any time.
The median of an odd number is the middle number, and the median of an even number is the average of the two middle numbers.
Analysis:
This problem has nothing to do with the greedy algorithm, is a classic investigation of heap application.
Because the greedy algorithm will use a lot of heap, so you can get familiar with the heap operation through this problem.
The time complexity of this algorithm is low because all operations on the heap are O(logN).
The process is:
- Prepare a large root heap and a small root heap.
- The first number goes into the big root heap.
- Enter the fixed iteration process:
- Current input number cur whether <= big root heap top number, if so, cur into big root heap; If not, cur into the small root heap.
- Look at the size of the big root heap and the small root heap. If the big one has two more than the small one, the top of the big one pops into the other.
- Stop iterating when all numbers are stored.
- The smaller N/2 numbers are in the larger root pile, the larger N/2 numbers are in the smaller root pile, and you can figure out the median by looking at the top number of the two piles.
Code:
public class Solution {
// Large root heap comparator
static class BigComparator implements Comparator<Integer> {
@Override
public int compare(Integer num1, Integer num2) {
returnnum2 - num1; }}public static int findMedian(int[] input) {
if (input == null || input.length == 0) {
return 0;
}
PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>(new BigComparator());
PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>();
// Put the first number into the big root heap first
bigRootHeap.add(input[0]);
for (int i = 1; i < input.length; i ++) {
if (input[i] <= bigRootHeap.peek()) {
bigRootHeap.add(input[i]);
} else {
smallRootHeap.add(input[i]);
}
if (Math.abs(bigRootHeap.size() - smallRootHeap.size()) == 2) {
if (bigRootHeap.size() > smallRootHeap.size()) {
smallRootHeap.add(bigRootHeap.poll());
} else{ bigRootHeap.add(smallRootHeap.poll()); }}}// Determine whether the input number is odd or even
if (input.length % 2! =0) {
return smallRootHeap.peek();
}
return (bigRootHeap.peek() + smallRootHeap.peek()) / 2; }}Copy the code4.2 Gold bar problem
Topic:
It takes the same amount of copper to cut a gold bar in half. For example, a 20 length bar, no matter how long it is cut in half, will cost 20 coppers.
A group of people want to divide the whole piece of gold bar, how to divide the most copper?
For example, given an array [10, 20, 30], representing a total of three people, the bar is 10 + 20 + 30 = 60. Gold bars are divided into 10,20,30 parts. If you split the 60 bars into 10 and 50 first, it costs 60; If you divide the 50 bars into 20 and 30, it costs 50; The total cost is 110 coppers.
But if you split the 60 bars into 30 and 30, it costs 60; Divide the length of 30 bars into 10 and 20, and it costs 30; The total cost is 90 coppers.
Enter an array and return the minimum cost of partitioning.
Analysis:
This problem is the classic Huffman coding problem.
The process is:
- Put all elements of the array into the root heap
- Iterative fixed process:
- The Huffman tree is constructed by popping two nodes from the top of the small root heap and combining them into new nodes.
- The new node is put back into the root heap.
- Stop iterating until the small root heap has only one node.
Code:
public int leastMoney(int[] parts) {
PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>();
// The minimum amount of money to spend
int money = 0;
// Put all nodes into the root heap
for (int i = 0; i < parts.length; i ++) {
smallRootHeap.add(parts[i]);
}
// Stop until there is only one node in the heap
while(smallRootHeap.size() ! =1) {
// Add two projectiles per stack
int cur = smallRootHeap.poll() + smallRootHeap.poll();
money += cur;
// Add the sum of the new nodes into the heap
smallRootHeap.add(cur);
}
return money;
}
Copy the code4.3 Project Planning
Topic:
Your team has received some projects, and each project will have casts and profits. Since you have a small team, you can only work on projects sequentially. Given that your team has M available funds and can only do K projects at most, what is the maximum amount of final available funds?
Casts [I], profits[I], casts[I], casts[I]
Analysis:
The process is:
- Build a small root heap and a large root heap. The sorting criterion for small root heap is cost, and the sorting criterion for large root heap is profit.
- Put all items into the root heap.
- Enter the fixed iteration process:
- The small root heap pops all items that cost less than or equal to M into the large root heap.
- The big root heap pops the most profitable items to do.
- M plus the profit from the project you just finished.
- Stop the iteration until the number of projects done is K.
Code:
public class Solution {
static class Project {
int cost;
int profit;
public Project(int cost, int profit) {
this.cost = cost;
this.profit = profit; }}static class minCostComparator implements Comparator<Project> {
@Override
public int compare(Project p1, Project p2) {
returnp1.cost - p2.cost; }}static class maxProfitComparator implements Comparator<Project> {
@Override
public int compare(Project p1, Project p2) {
returnp2.profit - p1.profit; }}public static int findMaximumFund(int M, int K, int[] costs, int[] profits) {
if (M == 0 || K == 0) {
return 0;
}
// Build a small root heap by spending
PriorityQueue<Project> costSmallRootHeap = new PriorityQueue<>(new minCostComparator());
// Build a large root heap from profits
PriorityQueue<Project> profitBigRootHeap = new PriorityQueue<>(new maxProfitComparator());
// Put all items into the root heap
for (int i = 0; i < costs.length; i ++) {
costSmallRootHeap.add(new Project(costs[i], profits[i]));
}
// Only K projects can be done
for (int i = 0; i < K; i ++) {
// Put the items currently available in the small root heap into the large root heap
while(! costSmallRootHeap.isEmpty() && costSmallRootHeap.peek().cost <= M) { profitBigRootHeap.add(costSmallRootHeap.poll()); }// No projects to work on
if (profitBigRootHeap.isEmpty()) {
return M;
}
// Select the most profitable one from the big root heap
Project cur = profitBigRootHeap.poll();
M += cur.profit;
}
returnM; }}Copy the code4.4 N Queen problem
Topic:
The N queen problem means that there are N queens on an N*N chessboard, requiring that any two queens are not in the same line, in different columns, or on the same slash.
Given an integer n, return how many pendulum methods n queen has.
Such as:
If n=1, return 1.
If n=2 or 3, return 0. (2 queens and 3 queens problem no matter how to put)
N =8, returns 92.
Analysis:
This problem is a classical problem, the optimal solution is very complex, and belongs to the dynamic programming problem with aftereffect.
If you’re not writing an essay, the best thing to do during an interview is to use depth-first thinking, put queens in each row in turn, and use violent recursion to try out the possibilities of each column.
The time complexity index of this solution is still very high.
Because the first row has N choices, the second row has N choices, and the third row has N choices… , there are N rows, so the time complexity is O(N^N).
Suppose, record[0] = 2, record[1] = 4, when the depth-first traversal reaches I = 2, the figure shows the reasonable placement of three kinds of Queen in the third row, and the depth-first traversal of these three positions is carried out successively, repeating.
Code:
public static int nQueen(int n) {
if (n < 1) {
return 0;
}
int[] record = new int[n];
// Start at line 0
return process(0, n, record);
}
/ * * *@paramI Specifies the line * currently traversed@paramN How many lines *@paramRecord [0,i-1] =2 indicates that a Queen * has been placed in row 1 and column 2@returnThe reasonable number of squares with n queens in n rows and n columns */
public static int process(int i, int n, int[] record) {
// Iterate to the end of the last line of the next line recursion, indicating that this placement scheme is reasonable
if (i == n) {
return 1;
}
// Record the reasonable number of pendulum methods for [I,n-1] rows
int result = 0;
// Try a depth-first traversal for column [0,n-1] on row I
for (int j = 0; j < n; j ++) {
// Determine if Queen can be placed in row I and column J
if (isValid(i, j, record)) {
record[i] = j;
// Iterate over the next line
result += process(i + 1, n, record); }}return result;
}
// Check if Queen can be placed in row I and column J
public static boolean isValid(int i, int j, int[] record) {
// Check to see if there is a conflict between the Queen and the current position by traversing all queens passed by [0,i-1]
for (int k = 0; k < i; k ++) {
// Check whether it is the same column or whether it is collinear.
if (record[k] == j || Math.abs(k - i) == Math.abs(record[k] - j)) {
return false; }}return true;
}
Copy the code4.5 N Queen problem (optimization)
Although the n-queen problem cannot be optimized in terms of time complexity index, it can be optimized in terms of constant, and there are still many optimizations.
So the time complexity is still the same time complexity, so to speak, but I can make the constant time very low in the implementation.
How low is, for example, a 14 queen problem that runs 5s with a 4.4 solution and 0.2s with a 4.5 optimized solution? A 15 queen problem runs 1 minute with the 4.4 solution and 1.5 seconds with the 4.5 optimized solution.
Analysis:
Use bit operations to speed things up. Bit acceleration is a very common technique and is recommended to be mastered.
Since the use of bitwise operation, then and the code of the variable storage form has a relationship, this code variable type is 32-bit int, so can not solve the problem above 32 queens.
If you want to solve problems above 32 queens, you can change the parameter type to long.
Code:
public static int nQueen(int n) {
if (n < 1 || n > 32) {
return 0;
}
int limit = n == 32 ? -1 : (1 << n) - 1;
return process(limit, 0.0.0);
}
/ * * *@paramN How many lines *@paramThe colLim column is restricted so that position 1 cannot have queen and position 0 can have *@paramLeftDiaLim limit the left slash, position 1 can not put queen, position 0 can *@paramRightDiaLim right slash limit, 1 position can not put queen, 0 position can *@returnThe reasonable number of squares with n queens in n rows and n columns */
public static int process(int n, int colLim, int leftDiaLim, int rightDiaLim) {
// Whether the queen is full
if (colLim == n) {
return 1;
}
int mostRightOne = 0;
// All postqueen columns are in pos bit information
int pos = n & (~ (colLim | leftDiaLim | rightDiaLim));
int res = 0;
while(pos ! =0) {
// Select 1 from the right of the candidate queens
mostRightOne = pos & (~ pos + 1);
pos = pos - mostRightOne;
// Update the limit, enter recursion
res += process(n, colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
Copy the code