Sabit zaman aralığı bir sıra üzərində əməliyyat əlavə edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Kod milləti DE Şou Directi Expedia google
Geyim Dinamik proqramlaşdırmaBaxılıb 59

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.

Verdiniz tam array və əvvəlcə 0 olaraq başlandı və eyni zamanda bir sıra verildi. Tapşırıq verilmiş ədədi sıra aralığına əlavə etmək və nəticəni əldə etmək üçündür.

misal

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

Izahat

Massivdə 50-a 0-yə 2 əlavə olunur, sıra halına gələcək {50, 50, 50, 0, 0}

Massivdə 20-a 3-yə 4 əlavə olunur, sıra halına gələcək {50, 50, 50, 20, 20}

Massivdə 30-a 1-yə 3 əlavə olunur, sıra halına gələcək {50, 80, 80, 80, 20}

Sabit zaman aralığı bir sıra üzərində əməliyyat əlavə edinPin

 

Alqoritm

  1. Aralığın hər bir sorğusu üçün addımları izləyin.
    1. Verilən dəyəri massivin sol indeksinə əlavə edin və özünə saxlayın.
    2. Dəyər dəyərinin sonuncu dizin indeksinə bərabər olmadığını yoxlayın, sonra verilmiş dəyəri massivin sağ + 1 mövqeyindən çıxarıb özünə saxla.
  2. Dizini çap etməzdən əvvəl massivi cərgədən keçərək yeniləyin və əvvəlki və cari dəyəri əlavə edin və massivin özündə saxlayın.
  3. Yenilənmədən sonra nəticələnən serialı çap edin.

Sabit zaman aralığının izahı bir sıra üzərində əməliyyat əlavə edin

Bir tam sıra və əlavə ediləcək say verilmişdir. Bizə bir sıra sorğu verilir. Aralığın başlanğıc nöqtəsini solda, aralığın bitmə nöqtəsini sağda ehtiva edir. Verilən aralığdakı verilmiş ədədi mümkün olan bütün ədədi əlavə etməyimiz istəndi. Və sonra nəhayət nəticələnən serialı çap edin. Bunun üçün əlavə əməliyyatını çox dəyişdirilmiş bir şəkildə həyata keçirəcəyik. Dizinin indeks dəyərlərini verilmiş dəyərlə massivin sol və sağ + 1 mövqeyində dolduracağıq və həmin massivi yeniləmədən əvvəl.

Hər bir sorğu üçün sola və sağa verilən dəyəri sağın sol indeksinə əlavə edəcəyik, yalnız sol indeksdə xatırlayın. Doğru dəyər üçün dəyər hüdudunun massivin son indeksinə bərabər olmadığını yoxlayacağıq, əgər verilən şərt təmin olunarsa, verilən dəyər indeksini yeniləyəcəyik, verilən dəyəri çıxardacağıq massivin sağ indeksini və onu massivin özünün sağ mövqe indeksinə saxla. Hər bir sorğu üçün bu əməliyyatları icra edəcəyik.

İndi serialı yazdırmalıyıq, amma bundan əvvəl bütün dəyəri yeniləyəcəyik, həyata keçirdiyimiz əlavə əməliyyatı, yeniləməyimiz lazımdır. Beləliklə, massivi gəzərək verilmiş massivin cari dəyərini və əvvəlki dəyərini əlavə edərək massivi yeniləyin və massivin cari vəziyyətinə saxlayın. Ardından, serialı çap edəcəyik.

Kodu

Sabit zaman aralığı üçün C ++ tətbiqetmə bir sıra üzərində əməliyyat əlavə edin

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

Sabit zaman aralığı üçün Java-da tətbiq bir sıra üzərində əməliyyat əlavə edin

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N + Q) hara "N" massivdəki elementlərin sayı və "Q" sorğuların sayıdır. Çünki sol indeksdəki dəyəri artırdıq və massivin sərhədində varsa sağdakı + 1 indeksini də azaldıq.

Kosmik Mürəkkəblik

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

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