Seyrək Cədvəldən istifadə edərək məcmu cəmi sorğusu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon İctimai Sapient Zoho
GeyimBaxı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.

Seyrək cədvəl problemindən istifadə edilən aralıq cəmi sorğusunda bir sıra sorğusu var və bir tam ədədi verilmişdir array. Verilən tapşırıq aralığa daxil olan bütün tamların cəmini tapmaqdır.

misal

Input:

arr [] = {1,4,6,8,2,5}

Sorğu: {(0, 3), (2, 4), (1, 5)}

Çıxış:

19 16 25

Explanation: 0, 3 aralığında daxil olan tam ədədlərin cəmi 1 + 4 + 6 + 8-dir. Yenə 19, 2 aralığında olan tam ədədlərin cəmi 4 + 6 + 8-dir. 2 ədədlərinin cəmi 16, 1 daxil olmaqla 5 + 4 + 6 + 8 + 2 5-dir.

Seyrək Cədvəldən istifadə edərək məcmu cəmi sorğusuPin

Alqoritm

  1. 2 ölçülü matrisdən istifadə edərək seyrək bir masa düzəldin.
  2. Massivdən keçin və seyrək masanın hər sətrini [i] massivi ilə qeyd edin.
  3. Dizini iç içə keçin və sparse_table dəyərini əvvəlki sütunun seyrək cədvəlinin cəmi və sparse_table [i + 2] kimi yeniləyin. j-1 ] [j-1] və seyrək masaya saxla [i] [j].
  4. Hər bir sorğunun həlli üçün sola və sağa çıxırıq, nəticənin dəyərini 0 olaraq təyin edirik.
  5. Dizini 16-dan 0-a qədər keçin və solda + 2 olub olmadığını yoxlayınj -1, sağa bərabərdir, əgər doğrudursa,
    1. Çıxış dəyərini sparse_table [sol] [j] üzərinə əlavə edin və cəmi nəticəyə yazın.
    2. Soldan sola + 2 dəyərini yeniləyin
  6. Çıxış dəyərini qaytarın.

Seyrək Cədvəldən istifadə edərək Range Sum Sorğusunun izahı

Bir sıra və bir sorğu verilmişdir. Sorğuda bir aralığa daxil olan bütün tam ədədin cəmini tapın. Seyrək masa konsepsiyasından istifadə edəcəyik. Seyrək bir masa düzəldəcəyik. Seyrək cədvəl, bəzi əməliyyatlar aparacağımız və dəyərləri seyrək bir cədvəldə saxlayacağımız 2-ci bir matrisdir.

2d elan edin matris. Hər biri bir sətirlik bir sərhəd və maksimum 16 sütun götürdük. Burada xüsusilə 16 rəqəmi götürdük, çünki bundan sonra 2 gücünə qaldırılan 5-dən böyük bir rəqəm alacağıq, buna görə 16 kifayətdir. Sonra seyrək bir masa qurmağın ilk mərhələsinə keçəcək. Dizini seyr edərkən seyrək cədvəldəki dəyərləri verilmiş massiv elementi kimi qeyd edəcəyik və ya yeniləyəcəyik. Sonra içəriyə yerləşdirdik, yenə də sıra sıra sayına qədər gedirik. İ, j-dəki seyrək cədvəli i, j-1-dəki seyrək cədvəlin və i + 2-dəki seyrək cədvəlin cəmi kimi yeniləyinj-1, j-1. Bu seyrək cədvəl üçün son tələb olunan yeniləmə olacaqdır.

Sol, sağ aralıq olaraq verilən hər bir sorğu üçün massivi keçməliyik, lakin bundan əvvəl çıxış dəyərini 0-a qoyun. Hər dəfə 16-ə bərabər güc əldə edə bilmək üçün 0-dan 2-a qədər sıra keçin. 1 <

Həyata keçirilməsi

Seyrək Cədvəldən istifadə edərək Range Sum Query üçün C ++ proqramı

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

Seyrək Cədvəldən istifadə edərək Range Sum Query üçün Java proqramı

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n * log (n)) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n * log (n)) hara "N" massivdəki elementlərin sayıdır.

arayış

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