Su anbarı nümunəsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook
GeyimBaxılıb 86

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.

Su Anbarı Nümunəsi, n çox böyük olduğu müəyyən bir n maddə siyahısından k su anbarı maddələrini təsadüfi seçmə üsuludur.
Məsələn, Google, YouTube və s.-də axtarış siyahıları.

Su anbarı nümunəsiPin

Su anbarı nümunəsi üçün sadəlövh yanaşma

Su anbarı tikin array k ölçüsündə, verilmiş siyahıdan təsadüfi maddələr seçin. Seçilən məhsul su anbarında yoxdursa, əlavə edin, əks halda növbəti maddəyə davam edin.

  1. K ölçülü su anbarı massivi yaradın.
  2. Curr-ı 0 olaraq başladın, curr doldurulacaq rezervuar massivinin cərəyan vəziyyətini təmsil edir. Curr k-dən az olduqda, 3 və 4-cü addımı təkrarlayın.
  3. 0-dan n arasında təsadüfi bir rəqəm yaradın (daxil deyil). Yaradılan təsadüfi ədədin rand olmasına icazə verin.
  4. Axınlıqdakı [rand] element artıq rezervuar massivində mövcuddursa, 3-cü addımı təkrarlayın. Başqa su anbarını [axını] axın [rand] və artım axını kimi təyin edin.
  5. Rezervuar massivinin elementlərini çap edin.

Rezervuar Nümunəsi üçün JAVA Kodu

public class ReservoirSampling {
    private static void selectReservoir(int[] stream, int k) {
        int n = stream.length;
        int reservoir[] = new int[k];
        // Index where the current item has to be placed
        int curr = 0;

        while (curr < k) {
            // Randomly generate an index between 0 to n
            int i = (int) (Math.random() * n) % n;
            boolean found = false;
            // Check if it is already present
            for (int j = 0; j < curr; j++) {
                if (reservoir[j] == stream[i]) {
                    found = true;
                    break;
                }
            }
            // If not present add it to the reservoir list
            if (!found) {
                reservoir[curr] = stream[i];
                curr++;
            }
        }

        // Print the randomly selected items
        for (int i = 0; i < k; i++) {
            System.out.print(reservoir[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example
        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int k = 5;
        selectReservoir(stream, k);
    }
}

Rezervuar Nümunəsi üçün C ++ Kodu

#include <bits/stdc++.h>
using namespace std;

void selectReservoir(int stream[], int k, int n) {
    int reservoir[k];
    // Index where the current item has to be placed
    int curr = 0;
    
    srand(time(0));
    
    while (curr < k) {
        // Randomly generate an index between 0 to n
        int i = rand() % n;
        bool found = false;
        // Check if it is already present
        for (int j = 0; j < curr; j++) {
            if (reservoir[j] == stream[i]) {
                found = true;
                break;
            }
        }
        // If not present add it to the reservoir list
        if (!found) {
            reservoir[curr] = stream[i];
            curr++;
        }
    }
    
    // Print the randomly selected items
    for (int i = 0; i < k; i++) {
        cout<<reservoir[i]<<" ";
    }
    cout<<endl;
}

int main() {
    // Example
    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int k = 5;
    int n = sizeof(stream) / sizeof(stream[0]);
    selectReservoir(stream, k, n);
    return 0;
}
2 12 9 3 5

Kod su anbarlarını təsadüfi seçdiyindən çıxış fərqli ola bilər.

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = Tamam2
Kosmik Mürəkkəblik = O (1) 
burada k - rezervuar massivində mövcud olan elementlərin sayı.

Su anbarı nümunəsi üçün optimal yanaşma

Yuxarıdakı problem, müəyyən bir axın üçün səmərəli şəkildə həll edilə bilər,

  1. K ölçüsündə bir su anbarı massivi yaradın və axının ilk k maddələrini massivə kopyalayın.
  2. Axını indeksdən (k + 1) n-ə keçir.
  3. Axındakı ith elementi üçün təsadüfi bir rəqəm yaratmaq üçün j deyin, əgər rəqəm 0 ilə (k - 1) arasındadırsa, rezervuarı [j] axını [i] ilə əvəz edin.
  4. Su anbarı massivi, axından seçilmiş k təsadüfi nömrələri ehtiva edir, onları çap edin.

Rezervuar Nümunəsi üçün JAVA Kodu

public class ReservoirSampling {
    private static void selectReservoir(int[] stream, int k) {
        int n = stream.length;
        int reservoir[] = new int[k];

        // Copy first k items to the reservoir array
        for (int i = 0; i < k; i++) {
            reservoir[i] = stream[i];
        }

        // Traverse the remaining stream
        for (int i = k; i < n; i++) {
            // Generate a random number between 0 to n
            int randomNumber = (int) (Math.random() * n) % n;
            // If this number lies between 0 to k, replace reservoir[randomNumber] with stream of i
            if (randomNumber >= 0 && randomNumber < k) {
                reservoir[randomNumber] = stream[i];
            }
        }

        // Print the reservoir array
        for (int i = 0; i < k; i++) {
            System.out.print(reservoir[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int k = 5;
        selectReservoir(stream, k);
    }
}

Rezervuar Nümunəsi üçün C ++ Kodu

#include <bits/stdc++.h>
using namespace std;

void selectReservoir(int stream[], int k, int n) {
    int reservoir[k];
    
    // Copy first k items to the reservoir array
    for (int i = 0; i < k; i++) {
        reservoir[i] = stream[i];
    }
    
    srand(time(0));
    
    // Traverse the remaining stream
    for (int i = k; i < n; i++) {
        // Generate a random number between 0 to n
        int randomNumber = rand() % n;
        
        // If this number lies between 0 to k, replace reservoir[randomNumber] with stream of i
        if (randomNumber >= 0 && randomNumber < k) {
            reservoir[randomNumber] = stream[i];
        }
    }
    
    // Print the randomly selected items
    for (int i = 0; i < k; i++) {
        cout<<reservoir[i]<<" ";
    }
    cout<<endl;
}

int main() {
    // Example
    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int k = 5;
    int n = sizeof(stream) / sizeof(stream[0]);
    selectReservoir(stream, k, n);
    return 0;
}
11 2 8 4 6

Kod su anbarlarını təsadüfi seçdiyindən çıxış fərqli ola bilər.

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n) 
Kosmik Mürəkkəblik = O (1)
burada n - axındakı ümumi elementlərin sayı və k - rezervuar massivindəki elementlərin sayı.

References

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