Daily algorithm & interview questions, 28 days of special training in large factories - the 13th day (array)

This article comes from the special training column of algorithm interview questions , Here you are A large number of professional algorithm problems, such as （ Dynamic programming 21 God , Dachang special training 28 Wait a day ）
Welcome to study together .

link ： Portal

Reading guide

Fat friends in order to better help new students adapt to algorithms and interview questions , Recently, we began to carry out special raids step by step . In the last issue, we completed 21 days of dynamic programming, and now we will make a 28 day summary of various algorithms . What are you waiting for? Come and study together Twenty eight day challenge Well ！！

Special introduction

Xiaobai's training column , Suitable for newcomers who have just started. Welcome to subscribe Programming Xiaobai advanced

python Interesting hand training programs include things like 《 Robot chat 》《 Spoof program 》 Such an interesting article , Can make you happy to learn python Training project column

In addition, I want to learn JavaWeb Students who enter the factory can look at this column ： Transporters

This is a sprint factory interview column and algorithm competition practice. Let's cheer together The way ashore

Algorithm training for 28 days

Here are two arrays of integers nums1 and nums2
, Please return the intersection of two arrays as an array . Returns the number of occurrences of each element in the result , It should be consistent with the number of occurrences of elements in both arrays （ If the number of occurrences is inconsistent , Then consider taking the smaller value ）. You can ignore the order of the output results .

 Example  1：

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2,2]

 Example  2:

 Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 Output ：[4,9]

Ideas ： Because the same number may appear multiple times in both arrays , Therefore, you need to use a hash table to store the number of occurrences of each number . For a number , The number of occurrences in the intersection is equal to the minimum number of occurrences of the number in the two arrays .

First, traverse the first array , And record each number in the first array and the corresponding number of occurrences in the hash table , Then traverse the second array , For each number in the second array , If this number exists in the hash table , Then add this number to the answer , And reduce the number of occurrences in the hash table .

To reduce space complexity , First, traverse the shorter array and record each number and the corresponding number of occurrences in the hash table , Then traverse the longer array to get the intersection .

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        if (nums1.length > nums2.length) {
    
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
    
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
    
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
    
                intersection[index++] = num;
                count--;
                if (count > 0) {
    
                    map.put(num, count);
                } else {
    
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

stay MATLAB in , There's a very useful function reshape , It can put a m x n The matrix is remodeled to another different size （r x
c） The new matrix of , But keep its original data .

Give you a two-dimensional array mat It means m x n matrix , And two positive integers r and c , Represent the number of rows and columns of the matrix to be reconstructed respectively .

The reconstructed matrix needs to replace all elements of the original matrix with the same Row traversal order fill .

If the reshape The operation is feasible and reasonable , The new reshaping matrix is output ; otherwise , Output raw matrix .

 Example  1：


 Input ：mat = [[1,2],[3,4]], r = 1, c = 4
 Output ：[[1,2,3,4]]

 Example  2：


 Input ：mat = [[1,2],[3,4]], r = 2, c = 4
 Output ：[[1,2],[3,4]]

class Solution {
    
    public int[][] matrixReshape(int[][] nums, int r, int c) {
    
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != r * c) {
    
            return nums;
        }

        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) {
    
            ans[x / c][x % c] = nums[x / n][x % n];
        }
        return ans;
    }
}

Interview questions

undo log  How to roll back a transaction  ？
 for instance ：
  about  insert  Type of  sql, Will be in  undo log  At the bottom of the record, you  insert  The data coming in  ID, When you 
 Want to  roll back  when , according to  ID  Complete the precise deletion .
  about  delete  Type of  sql, Will be in  undo log  Record the data you just deleted in , When you roll back, you will delete 
 Data before division  insert  go in .
  about  update  Type of  sql, Will be in  undo log  Record the data before modification in , When rolling back, you just need to reverse 
update  that will do .
  about  select  Type of  sql, Don't worry about it ,select  There is no need to roll back .


 How to query slow  SQL  Cause of occurrence ？
  analysis  SQL  Implementation plan （explain extended）, Think about possible optimizations , Whether to hit the index, etc .
  No index or no index used ( This is the most common problem with slow queries , It's a programming flaw ).
  Out of memory .
  The Internet is slow .
  Whether the amount of data queried is too large （ You can use multiple queries , Other ways to reduce the amount of data ）.
  Whether unnecessary rows and columns are returned .
  Lock or deadlock .
 I/O  Small throughput , It's a bottleneck effect .
 sp_lock,sp_who, Active users view , The reason is that literacy competes for resources 

Click to get the information directly

Here you are python,Java Learning materials and interesting programming projects , More difficult to find resources . Anyway, it's not a loss to see .