Word əlavə et və axtar - Məlumat quruluşu dizaynı LeetCode

Çətinlik səviyyəsi Mühit
alqoritmlər Geri qayıtma kodlaşdırma Layihə müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Sim cəhd edinBaxılıb 89

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem "Word əlavə et və axtar - Məlumat quruluşu dizaynı LeetCode" bizdən yeni bir şey yaratmağı və ya dizayn etməyimizi xahiş edir məlumatların quruluşu. Bir söz əlavə etmək və ya saxlamaq və axtarış funksiyasının sözdən normal bir ifadəni belə axtara biləcəyi sözləri axtarmaq üçün istifadə edilə bilənlər.

Məsələn :

Xəritədə string / word = “hey” saxlanılırsa, aşağıdakı funksiyalar eyni nəticəni verəcəkdir -

1. axtarış (..y).

2. axtarış (.e.).

3. axtarış (h ..).

Yuxarıdakı üç şey funksiyası Çağırışların doğru olması ilə nəticələnəcəkdir.

Word əlavə et və axtar - Məlumat quruluşu dizaynı LeetCodePin

misal

addword ("code")
addword ("java")
addword ("when")
search ("blue")
search ("java")
search ("co..")
False
True
True
addword ("who")
addword ("why")
search ("why")
search ("hey")
search ("the")
True
False
False

Ölçülənə bilən massiv və Hashmap istifadə

Alqoritm

  1. Yeni məlumat quruluşu üçün bir sinif başlatın.
  2. Bundan sonra ölçüsünü dəyişdirin array simli tip və a hashmap simli cütün növü və tam tip.
  3. A-nı qəbul edən yeni məlumat strukturuna söz əlavə etmək üçün bir funksiya yaradın sim parametri olaraq dəyişən.
  4. Bundan sonra, verilən sətrin xəritədə mövcud olub olmadığını yoxlayın, qayıdın.
  5. Başqa birisi verilmiş sətri massivin son indeksinə və xəritəyə əlavə edin.
  6. Eynilə, yeni bir məlumat quruluşunda bir sətir dəyişənini parametr olaraq qəbul edən sözü axtarmaq üçün başqa bir funksiya yaradın.
  7. Verilən sətir dəyişənini xəritədə axtarın.
  8. Əgər sim dəyişən xəritədə çap olunan “True” şəklindədir.
  9. Başqa bir normal ifadəni yoxlayın. Tapılıbsa “Doğru” yazdırın.
  10. "Yanlış" yazdırın.

Həyata keçirilməsi

Word əlavə et və axtarın C ++ kodu - Məlumat quruluşu dizaynı LeetCode

#include<bits/stdc++.h> 
using namespace std; 
  
class newStructure{ 
    vector <string> arr; 
      
    map <string, int> Map; 
  
    public: 
        void addword(string x){ 
            
            if(Map.find(x) != Map.end()) 
                return; 
                  
            int index = arr.size(); 
            arr.push_back(x); 
                  
            Map.insert(std::pair<string,int>(x, index)); 
        } 
              
              
        void search(string x){ 
            if(Map.find(x) != Map.end()){ 
                cout<<"True"<<endl;
                return;
            }    
            else{
                regex b(x);
                for(int i=0; i<arr.size(); i++){
                    if(regex_match(arr[i],b)){
                        cout<<"True"<<endl;
                        return;
                    }
                }
            }    
            cout<<"False"<<endl;
        } 
}; 
  
int main(){ 
    newStructure ds;
    
    ds.addword("code"); 
    ds.addword("java"); 
    ds.addword("when"); 
    
    ds.search("blue");
    ds.search("java");
    ds.search("co..");
    
    return 0;
}
False
True
True

Word əlavə et və axtar Java məlumat kodu - Məlumat quruluşu dizaynı LeetCode

import java.util.*; 
import java.util.regex.Pattern;

class newStructure{ 
    ArrayList<String> arr; 
    HashMap<String, Integer>  map; 
    
    public newStructure(){ 
        arr = new ArrayList<String>(); 
        map = new HashMap<String, Integer>(); 
    } 
    
    void addword(String x){ 
        if(map.get(x) != null) 
            return; 
        
        int s = arr.size(); 
        arr.add(x); 
        map.put(x, s); 
    } 
    
    void search(String x){ 
        if(map.get(x)!=null){
            System.out.println("True");
            return;
        } 
        else{
            Pattern regex = Pattern.compile(x);
            
            for(String s:arr){
                if(regex.matcher(s).matches()){
                    System.out.println("True");
                    return;
                }
            }
        }
        System.out.println("False");
    } 
} 

class Main{ 
    public static void main (String[] args){ 
        newStructure ds = new newStructure();
        
        ds.addword("code"); 
        ds.addword("java"); 
        ds.addword("when"); 
        
        ds.search("blue"); 
        ds.search("java"); 
        ds.search("co.."); 
        
    } 
}
False
True
True

Əlavə et və axtarış üçün mürəkkəblik analizi - Məlumat quruluşu dizaynı LeetCode

Zamanın mürəkkəbliyi

O (n * m) burada n - əlavə edilmiş sözlərin sayı və m - axtarılacaq sözlərin uzunluğu.

Kosmik Mürəkkəblik

O (n) çünki bu proqram ölçülənə bilən massivdə və hashmapdə n element üçün yer istifadə edir, ona görə də boşluq mürəkkəbliyi O (n) -dir.

References

Crack Sistemi Dizayn Müsahibələri
Translate »