Podtablica z podaną sumą

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka American Express Apple Bloomberg ByteDance Kupang eBay Facebook Goldman Sachs Google LinkedIn Microsoft wyrocznia chciał Twilio Uber Chcieć Yahoo Yandex
Szyk Haszysz Hashingodwiedzajacy 1125

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W podtablicy z zadanym problemem sumarycznym daliśmy szyk zawierający n pozytywnych elementów. Musimy znaleźć podtablicę, w której suma wszystkich elementów podtablicy jest równa podanej_sumie. Podtablica jest uzyskiwana z oryginalnej tablicy poprzez usunięcie niektórych elementów z początku lub końca tablicy.

Przykład

za. Tablica wejściowa to: [1, 3, 7, 9, 11, 15, 8, 6]

Suma = 19
Wynik będzie następujący: 1 i 3 → [3, 7, 9], suma podtablicy = 19

b. Tablica wejściowa to: [1, 3, 7, 9, 11, 15, 8, 6]

Suma = 20
Wynik wyniesie: 0 i 3 → [1, 3, 7, 9], suma podtablicy = 20

do. Tablica wejściowa to: [1, 3, 7, 9, 11, 15, 8, 6]

Suma = 40
Wynik będzie następujący: Nie znaleziono podtablicy z podaną sumą.

re. Tablica wejściowa to: [4, 3, 2, 8, 9, 11]

Suma = 8
Wynik będzie wyglądał następująco: 3 i 3 → [8], suma podtablicy = 8

Podejście 1

Algorytm

Rozważ wszystkie podtablice i sprawdź sumę wszystkich podtablic.

  1. Uruchom dwie pętle.
  2. Pętla zewnętrzna przedstawia indeks początkowy.
  3. Pętla wewnętrzna znajduje wszystkie podtablice i sumę.
  4. Jeśli suma = aktualna_suma, bieżąca_suma jest sumą aktualnej podtablicy, wypisuje indeksy początku i końca.

Realizacja

Program w C ++ dla podtablicy z podaną sumą

#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int array[], int N, int sum)
{
    int current_sum, i, j;
    //i is start point and j - 1 is end point
    for (i = 0; i < N; i++)
    {
        current_sum = array[i];
        for (j = i+1; j < N + 1; j++)
        {
            if (current_sum == sum)
            {
                cout<<"Subarray with given sum is between indexes "<<i<<" and "<<j-1<<endl; 
                return 1;
            }
            else if (current_sum > sum)
            {
                break;
            }
           current_sum = current_sum + array[j];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarraySum(a,n,sum);
    return 0;
}

Program w języku Java dla tablicy podrzędnej z podaną sumą

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int N, int sum)
    {
        int current_sum, i, j;
        //i is start point and j - 1 is end point
        for (i = 0; i < N; i++)
        {
            current_sum = array[i];
            for (j = i+1; j < N + 1; j++)
            {
                if (current_sum == sum)
                {
                    System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1)); 
                    return 1;
                }
                else if (current_sum > sum)
                {
                    break;
                }
               current_sum = current_sum + array[j];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
8
1 3 8 9 11 13 17 21
28
Subarray with given sum is between indexes 2 and 4

Analiza złożoności

Złożoność czasowa

O (n * n) gdzie n jest rozmiarem podanej tablicy. Tutaj ustalamy punkt początkowy (i) podtablicy i obliczamy sumę wszystkich możliwych podtablic kończących się na j.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Podejście 2

Algorytm

Utwórz sumę podtablicy funkcjonować który przyjmuje tablicę i sumę jako argument i podaje indeksy początkowy i końcowy podtablicy o podanej sumie.

  1. Najpierw zainicjuj current_sum jako pierwszy element tablicy i zapisz indeks początkowy jako 0.
  2. Jeśli current_sum przekracza sumę, usuń element startujący i zwiększ indeks początkowy.
  3. Jeśli current_sum jest równa sumie, zwraca indeksy początkowy i końcowy.
  4. Dodaj elementy do current_sum jeden po drugim.
  5. Jeśli pętla się kończy, wypisz „Nie znaleziono podtablicy z podaną_ sumą”.

Implementacja dla podtablicy z podaną sumą

Program w C ++

#include <bits/stdc++.h>
using namespace std;
int SubarrySum(int array[], int n, int sum)
{
    //Initialize current_sum = first element.Therefore, start_index =0
    int current_sum = array[0];
    int start_index = 0;
    
    //if current_sum > sum remove last element
    for(int i = 1; i <= n; i++)
    {
        while(current_sum > sum && start_index < i-1)
        {
            current_sum = current_sum - array[start_index];
            start_index++;
        }
        if(current_sum == sum)
        {
            cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
            return 1;
        }
        //Add current element to current_sum
        if(i < n)
        {
          current_sum = current_sum + array[i];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarrySum(a,n,sum);
    return 0;
}

Program Java

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int n, int sum)
    {
            //Initialize current_sum = first element.Therefore, start_index =0
        int current_sum = array[0];
        int start_index = 0;

        //if current_sum > sum remove last element
        for(int i = 1; i <= n; i++)
        {
            while(current_sum > sum && start_index < i-1)
            {
                current_sum = current_sum - array[start_index];
                start_index++;
            }
            if(current_sum == sum)
            {
                System.out.println("Subarray with given sum is between indexes " + start_index + " and " + (i-1)); 
                return 1;
            }
            //Add current element to current_sum
            if(i < n)
            {
              current_sum = current_sum + array[i];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
6
10 6 8 4 3 8
34
No subarray found with given sum

Analiza złożoności

Złożoność czasowa

O (n * n) gdzie n jest rozmiarem podanej tablicy. Tutaj przechodzimy przez tablicę jeden raz i sprawdzamy warunki.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »