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

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 , It is suitable for new comers or examiners python Class 2 students are 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

Please judge a 9 x 9 Is the Sudoku effective . It only needs According to the following rules , Verify that the numbers you have filled are valid .

Numbers 1-9 Only once in a row . Numbers 1-9 It can only appear once in each column . Numbers 1-9 Separated by thick solid lines in each 3x3
Only once in the palace .（ Please refer to the example figure ）

Be careful ：

An effective Sudoku （ Part has been filled in ） Not necessarily solvable . Just follow the above rules , Verify that the numbers you have filled in have
The effect is enough . Blank space ‘.’ Express . Here are two strings ：ransomNote and magazine , Judge ransomNote Can it be done by
magazine The characters inside make up .

If possible , return true ; Otherwise return to false .

magazine Each character in can only be in ransomNote Used once in .

 Example  1：

 Input ：ransomNote = "a", magazine = "b"
 Output ：false

 Example  2：

 Input ：ransomNote = "aa", magazine = "ab"
 Output ：false

 Example  3：

 Input ：ransomNote = "aa", magazine = "aab"
 Output ：true

Ideas ： The title requires a string \textit{magazine}magazine To construct a new string
\textit{ransomNote}ransomNote, And \textit{ransomNote}ransomNote
Each character in can only be used once , You just need to satisfy the string \textit{magazine}magazine Every English letter in
(\texttt{‘a’-‘z’})(’a’-’z’) The number of statistics is greater than or equal to \textit{ransomNote}ransomNote
The statistical times of the same letter in .

class Solution {
    
    public boolean canConstruct(String ransomNote, String magazine) {
    
        if (ransomNote.length() > magazine.length()) {
    
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
    
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
    
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
    
                return false;
            }
        }
        return true;
    }
}

Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .

Be careful ： if s and t Each character in the has the same number of occurrences , said s and t They are mutually alphabetic words .

 Example  1:

 Input : s = "anagram", t = "nagaram"
 Output : true

 Example  2:

 Input : s = "rat", t = "car"
 Output : false

Ideas ：t yes ss The heterotopic words of are equivalent to 「 Two strings are sorted equal 」. So we can do string ss and tt
Sort them separately , You can judge whether the sorted strings are equal . Besides , If ss and tt The length is different ,tt It must not be ss The heterotopic words of .

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        if (s.length() != t.length()) {
    
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

Interview questions

Redis  data structure   The difference between a compressed list and a jump table 
  Compressed list （ziplist） It's essentially an array of bytes , yes  Redis  A linear system designed to save memory 
 data structure , It can contain more than one element , Each element can be a byte array or an integer .
30
  Skip list （skiplist） Is an ordered data structure , It maintains multiple fingers pointing to other nodes in each node 
 The needle , So as to achieve the purpose of fast access to nodes . Jump table support average  O（logN）、 The worst  O（N） Complexity 
 Node lookup for , You can also batch process nodes through sequential operations 


Redis  How to realize master-slave synchronization ？
 Full amount of synchronization 
master  The server will start a background process for  redis  The data in generate a  rdb  file , meanwhile ,
 The server will cache all received write commands from the client （ Include to add 、 Delete 、 Change ）, When the background save process is finished 
 After finishing , Will be the  rdb  The document is passed to  slave  The server , and  slave  The server will  rdb  The file is saved on disk and 
 Load the data into memory by reading the file , After that  master  The server will cache the 
 Command to pass  redis  The transport protocol is sent to  slave  The server , then  slave  The server applies these commands in turn to 
 Finally, the data consistency is achieved on the local data set .


 The incremental synchronization 
 from  redis 2.8  Version before , Partial synchronization is not supported , When the connection between master and slave servers is broken ,master  clothing 
 Servers and  slave  Full data synchronization between servers .
 from  redis 2.8  Start , Even if the master-slave connection is broken in the middle , And there's no need for full synchronization , Because starting with this version 
 The concept of partial synchronization is integrated . The implementation of partial synchronization depends on  master  Server memory for each  slave  service 
 The synchronizer maintains a synchronization log and synchronization identification , Every  slave  The server is following  master  When the server synchronizes, it will 
 Carry your own synchronization ID and the last synchronization location . When the master-slave connection is broken ,slave  Server partition time 
（ Default  1s） Take the initiative to try and  master  Server to connect , If the offset ID carried from the server is still 
master  In the synchronous backup log on the server , Then from  slave  The offset sent starts to continue the last synchronization operation 
 do , If  slave  The offset sent is no longer  master  In the synchronous backup log of （ Probably due to the disconnection between the master and the slave 
 For a long time or for a short time  master  The server received a large number of write operations ）, Must be carried out 
 A full update . During partial synchronization ,master  The instructions recorded in the locally recorded synchronous backup log will be recorded in sequence 
 Send to  slave  Server to achieve data consistency .


Redis  Master slave synchronization policy 
 Master slave just connected , Do full synchronization ; When the full synchronization is over , Incremental synchronization . Of course , If necessary ,
slave  Full synchronization can be initiated at any time .redis  Strategy is , in any case , You will first attempt incremental synchronization ,
 If you don't succeed , Require full synchronization from slave .

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 .