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.
Spis treści
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.
- Uruchom dwie pętle.
- Pętla zewnętrzna przedstawia indeks początkowy.
- Pętla wewnętrzna znajduje wszystkie podtablice i sumę.
- 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.
- Najpierw zainicjuj current_sum jako pierwszy element tablicy i zapisz indeks początkowy jako 0.
- Jeśli current_sum przekracza sumę, usuń element startujący i zwiększ indeks początkowy.
- Jeśli current_sum jest równa sumie, zwraca indeksy początkowy i końcowy.
- Dodaj elementy do current_sum jeden po drugim.
- 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.
