Yeniləmə olmadan aralıq cəmi sorğuları

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 bəyanat

"Yeniləmə olmadan aralıq cəmi sorğuları" problemində bir array of tamsayılar və bir sıra. Problem ifadəsi, verilən aralıqdakı bütün elementlərin cəmini tapmağı xahiş edir.

misal

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}

40 24

Izahat

(0, 4) aralığı arasındakı bütün rəqəmlərin cəmi 40-a, (1, 3) aralığı arasındakı bütün rəqəmlərin cəmi 24-ə bərabərdir.

Pin

 

Alqoritm

1. Verilmiş massivlə eyni ölçüdə bir sıra sumArray yaradın.
2. Verilən massivdən keçin və sumArray-ın əvvəlki elementinin və verilmiş massivin cari elementinin cəmini saxlayın və sumArray-da saxlayın.
3. Hər bir sorğu üçün, sol 0-a bərabərdirsə, sumArray [sağ],
4. Başqa halda sumArray [sağ] - sumArray [sol - 1] qayıdır.

Izahat

Bir ədəd tam və bir sıra verdik, hər bir sorğu üçün verilən aralığdakı bütün elementlərin cəmini tapmağımız istəndi. Sorğuların hər biri bir sıra başlanğıc və bitmə nöqtəsi kimi bir sıra ibarətdir. Bu sual heç bir yeniləmə sorğusu içermir. Bu, sualın cavabını taparkən hər hansı bir şeyi yeniləməyə ehtiyac olmadığını göstərir. Verilən massivi elə quracağıq ki, 0 indeksdən indiki indeksədək bütün elementlərin cəmi qurulmuş massivin ith mövqeyində olsun. Bu şəkildə, hər bir sorğu əlavə O (n) boşluğu ilə O (1) -də həll ediləcəkdir.

Yaratdığımız sumArray-ı quracağıq. Bu sumArray-da 0-dan i-yə qədər olan elementlərin cəmi sumArray-ın ith mövqeyində saxlanacaqdır. Bunu sumArray-ın əvvəlki dəyərini və verilmiş massivin cari dəyərini topladığımızdan və keçərkən sumArray-ın cari indeks vəziyyətinə yerləşdirdiyimizdən hesablayacağıq. Beləliklə, kimsə bu mövqedəki bütün rəqəmlərin cəminin nə olduğunu soruşduqda, yalnız hər bir misilsiz sıra elementləri üçün həmin mövqenin dəyərini qaytarmalıyıq.

Hər hansı bir aralıqdan ibarət bir sorğu alanda və aralığın sol və ya başlanğıc nöqtəsinin 0-a bərabər olduğunu tapsaq, yalnız sumArray [sağ] dəyərini qaytaracağıq, yuxarıda müzakirə etdiyimiz şey, sol aralığın 0-a bərabər deyilsə sumArray [sağ] və sumArray [sol-1] fərqini qaytaracağıq. Bunlar cavablar tələb olunacaq. Bu yanaşma eyni zamanda istifadə etdiyimiz ən asan yollardan biridir Dinamik proqramlaşdırma.

Kodu

Yeniləmə olmadan aralıq cəmi sorğuları üçün C ++ kodu

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

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

    return 0;
}

40
24

Yeniləmədən Range sum sorğuları üçün Java kodu

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}

40
24

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N + Q),  çünki sumArray-ı hesablamaq üçün O (N) və sonra hər sorğu üçün O (1) vaxt lazımdır.

Kosmik Mürəkkəblik

Verilən yanaşmada, elementlərin cəmini 0-dan i-yə qədər saxlamaq üçün yeni bir sıra sumArray yaratdıq. Beləliklə, bu yanaşma tələb edir O (N) yer. Ancaq orijinal massivi də dəyişdirə bilərdik. O zaman kosmik mürəkkəblik sabit səviyyəyə enmiş olardı.