Söz nümunəsi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Capital One
Sükut Hashing SimBaxılıb 94

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.

Hamımız sözə rast gəldik nümunələri kimi “ABBA”, “AABB” və s. Həmişə bu mübahisənin nəyə aid ola biləcəyini düşünürük. Bu gün babble istifadə etməyə çalışdığımız bir problemi həll etməyə çalışacağıq. Bir çox sim problemlər işə kömək etmir. Bir naxış və bir cümlə nəzərə alaraq cümlənin naxışa uyğun olub olmadığını / naxışla uyğun olub-olmadığını araşdırmalıyıq.

misal

Nümunəmizin “AWWBSW” olduğunu düşünək. Beləliklə, nümunə boyunca gələn cümlələr ola bilər

Böyük bir böyük körpə qoyun

Pişik Köpək Köpəyi Fil Gəmisi Köpəyi

Daha yaxşı bir anlayış əldə etmək üçün xəritələrə baxaq

Bir sıra söz nümunəsi simvolları üçün mümkün bir sıra xəritənin göstərilməsiPin
Bir simvol dəsti üçün mümkün bir sıra xəritənin göstərilməsi
Eyni söz nümunəsi üçün başqa bir mümkün söz Xəritəçəkmə dəstiPin
Eyni söz nümunəsi üçün başqa bir mümkün söz Xəritəçəkmə dəsti

Izahat

Beləliklə, xəritələrə tabe olduğumuz müddətdə yaxşı işlər görürük

Artıq problem problemlə işləməyimizə kömək edə biləcək bir məlumat quruluşu tapmaq üçün azalır.

Sıralar, yığınlar və Diziler əlaqələri davam etdirmək çətin olacaq. Beləliklə, HashMaps-a gedərdik.

HashMaps əsas dəyər cütləri şəklində məlumatları ehtiva edir və beləliklə yuxarıdakı problem üçün ideal seçim kimi görünür.

İndi problemimiz barədə bir az bildiyimizə görə edəcəyimizi necə edəcəyimizə baxaq.

  • Bütün eşlemelerin bir hashmap yaradın
  • Simli üzərində təkrarlayın və hər bir simvol və sözə baxın
    • Haşmapdakı sözlə uyğun gələn xarakterə baxın
    • Xəritəçəkmə və xarakter uyğun gəlmirsə, yalnış qayıdırıq
  • Hər hansı bir uyğunsuzluqla qarşılaşmırıqsa, onda yalnız mükəmməl bir uyğunluq tapdığımıza əminik!

Kodu nəzərdən keçirək

Word Xəritəçəkmə üçün Java Kodu

class Solution 
{
    public boolean wordPattern(String pattern, String str) 
    {
    String words[]=str.split(" ");
    if(pattern.length()!=words.length)
        return false;
    boolean ans=true;
    HashMap<Character,String>mapping=new HashMap<Character,String>();
    for(int i=0;i<words.length;i++)
    {
        if(mapping.containsKey(pattern.charAt(i)))
        {
            if(!words[i].equals(mapping.get(pattern.charAt(i))))
            {ans=false;break;}
        }
        else
        {
            if(mapping.containsValue(words[i]))
            {ans=false;break;}
            mapping.put(pattern.charAt(i),words[i]);    
        }
    }
    return ans;
    }
}

Söz Xəritəçəkmə üçün C ++ Kodu

class Solution 
{
public:
    bool wordPattern(string pattern, string str) 
    {
    std::string w;                 
    std::stringstream ss(str);
    std::vector<std::string> words; 

    while (ss >> w)
    {
        words.push_back(w);
    }
        
    if(words.size() != pattern.size()) 
        return false;
    
    map<char,string> a;
    map<string,char> b;
    
    for(int i = 0; i < words.size(); i++)
    {
        a[pattern[i]] = words[i];
        b[words[i]] = pattern[i];
    }
    
    for(int i = 0; i < words.size(); i++)
    {
        if(a[pattern[i]] != words[i] || b[words[i]] != pattern[i])
        {
            return false;
        }
    }
     
    return true;
   }
};

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O (n)

Niyə?

Gəlin bizə verilən simli 5 sözdən ibarət olduğunu düşünək. (İndiki kimi təkrarlamalar nəzərə alınmır)

  • Sıranın üstündən döngə salacağıq
  • Hər bir söz sətirdəki hər bir naxışla uyğunlaşacaqdır.
    • Beləliklə, yaradılacaq hashmap eyni ölçüdə olacaq, yəni 5
  • Sözlərdən birinin iki dəfə göründüyünü düşünək. Müvafiq sözlər 4-ə enir.
    • Əgər hashmap daha böyük ölçüdə olacaqsa, mütləq qaydanı pozuruq.
    • Beləliklə kosmik mürəkkəblik O (n)
  • Hər sözü bir dəfə nəzərdən keçiririk. Hansı təkrar sayını 5 edir
  • Bu zaman mürəkkəbliyini xətti / O (n) kimi edir

Beləliklə, şaqqıltılı naxışlardan bir məna kəsib onları uyğunlaşdırmağın kiçik bir icmalı idi!

References

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