Sözü tapın

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon google
SimBaxılıb 65

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.

Sözü tapın bir interaktiv problem. İnteraktiv problem, bizə verilən məlumatların əvvəlcədən təyin edilməməsi deməkdir. Dəyərləri çap edə və ya spesifik olaraq zəng edə bilərik funksiyası qarşılıqlı əlaqə qurmaq və ya həll ilə bağlı daha çox məlumat əldə etmək. Hər addımdan sonra da etməliyik QIZARMAQ düzgün cavabı almaq üçün bufer. İndi görün sözün tam olaraq nə olduğunu təxmin edin !!! N sözləri verdik və hər bir sözün uzunluğu eyni olsun ki, X olsun. Bu məsələdə, bir rəqəm yazsaq, interaktivçi bizə tam ədədi Y verir. Y tahmin sözünə uyğun simvol sayını təmsil edir. . Sözün həmişə N sözləri arasında hər hansı bir sözlə uyğun gəldiyini təxmin edin. Sözü yazdıraraq yalnız interaktora bir neçə sual veririk. Verilən sualın həddini aşmadan tahmin sətrini tapıb çap etməliyik.

Sözü tapın - interaktiv problem!

Verilən sualın həddi 10, N-nin (sözlərin sayı) dəyəri 6-dır. Burada bütün uzunluqlu 8 sözləri götürürük. Girişin verilən qiymətinə baxın.

sözlər = {"abcdefgh", "riwqsgrd", "nhtrgjue", "kueshtew", "ticqehac", "nmvdswqz"}.

Sualı interaktordan soruşmaq üçün “abcdefgh” yazdırırıq və interaktordan tam 2 dəyəri veririk. İndi anladıq ki, cari rəqəm heç vaxt təxmin nömrəmiz olmayacaq. “Riwqsgrd” yazaraq başqa bir sual verin. Bu vəziyyətdə interaktör 1 tam dəyər verir. Sonra bu sözü də cavab siyahımızdan çıxarırıq. Üçüncü sualı “ticqehac” yazaraq verin. Bu vəziyyətdə, interaktör bir tam ədədin 3-i verir. Burada indiki sözün bütün simvolları ilə təxmin sözünə uyğun gəldiyinə görə söz tapdıq.

Burada yalnız 3-cü sualda cavabımızı aldıq, buna görə bu etibarlı bir həlldir.

Alqoritm

Step:1 Sort the words in dictionary order.
Step:2 While wordlist.size !=0 and question_asked<=q then:
       A) Pick one random word and ask the question using it.
       B) If interactor answer equal to the length of the word then return the current word.
       C) Create one more list and add all those words whose characters matched by random picked number greater than the answer given by interactor.
       D) wordlist = new_wordlist(created in step 2.C).
Step:3 If no word found then return/print -1.

Həyata keçirilməsi

/*C++ Implementation of Guess The Word Problem.*/ 
#include<bits/stdc++.h> 
using namespace std; 
void findSecretWord(vector<string> &wordlist,int guessCnt,int wordlength) 
{
    /*Check edge case.*/
    if(wordlist.size()==0) 
    {
        return;
    }
    int flag=0;
    /*sort(wordlist.begin(), wordlist.end()).*/
    while (wordlist.size()>0&&guessCnt--) 
    {
        /*Get random pick*/
        string candidate = wordlist[rand() % (wordlist.size())];
        /*ask question by printing word.*/
        cout<<candidate<<endl;
        int found;
        /*answer to the question asked.*/
        cin>>found;
        /*Checking current word is guess word or not*/
        if(found==wordlength) 
        {
            flag=1;
            /*Print the Guess Word.*/
            cout<<candidate<<endl;
            break;
        }
        /*Logical reduction of the wordlist.*/
        vector<string> wordlist2;
        for(int i=0;i<wordlist.size();i++) 
        {
            int match=0;
            for(int j=0;j<wordlength;j++)
            {
                if(wordlist[i][j]==candidate[j])
                {
                    match++;
                }
            }
            if(match==found) 
            {
                wordlist2.push_back(wordlist[i]);
            }
        }
        wordlist=wordlist2;
    }
    if(flag==0)
    {
        cout<<-1<<endl;
    }
}
int main() 
{
    /*input values.*/
    int n;
    /*number of words.*/
    cin>>n;
    /*length of word.*/
    int w;
    cin>>w;
    /*maximum limit of question asked.*/
    int q;
    cin>>q;
    vector<string> wordlist;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        wordlist.push_back(x);
    }
    findSecretWord(wordlist,q,w);
    return 0;
}
6
8
10
abcdefgh riwqsgrd nhtrgjue kueshtew ticqehac nmvdswqz
Interactor               You
                       nmvdswqz
    0
                       abcdefgh
    2
                       ticqehac 
    8
                       ticqehac

Zamanın mürəkkəbliyi

O (N * N) burada N - bizə verilən sözlərin sayı. Burada vaxtın mürəkkəbliyi ilə maraqlana bilmərik, çünki təsadüfi funksiyadan istifadə edirik, sonra kodun necə işlədiyini təxmin edə bilmirik. Müxtəlif nümunələr götürərək kod mürəkkəbliyini bir neçə dəfə yoxlamaq üçün zaman mürəkkəbliyinin təsadüfi olaraq dəyişdiyini gördük. Burada da hər zaman söz siyahısının uzunluğunu azaltdığımızı görürük. Beləliklə, ən pis zaman mürəkkəbliyinin O (N * N) olduğunu söyləyə bilərik.

 Kosmik Mürəkkəblik

O (N) burada N - bizə verilən sözlərin sayı. Bu dəyərləri saxlamaq üçün simli bir vektordan istifadə edirik. Beləliklə, yuxarıdakı kodda istifadə olunan maksimum boşluq O (N) -dir.

References

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