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
Podaliśmy tablicę zawierającą N liczbę elementów. W podanym szyk, Policz liczbę trójek z sumą mniejszą niż podana wartość.
Przykład
Wkład
za[] = {1, 2, 3, 4, 5, 6, 7, 8}
Suma = 10
Wydajność
7
Możliwe trojaczki to: (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5 ), (2,3,4, XNUMX, XNUMX)
Wkład
a [] = {3, 7, 9, 1, 2, 5, 11, 4}
Suma = 10
Wydajność
6
Możliwe trojaczki to: (3,1,2), (3,1,5), (3,1,4), (3,2,4), (1,2,5), (1,2,4 )
Podejście 1
Algorytm
1. Uruchom 3 zagnieżdżone pętle, wybierając wszystkie możliwe trojaczki.
2. Wynik inicjalizacji = 0.
3. Jeśli Suma elementów jest mniejsza niż Suma, liczba przyrostów.
4. Wydrukuj wyniki jako liczbę trójek spełniających warunek.
Realizacja
Program C ++ do liczenia trojaczków z sumą mniejszą niż podana wartość
#include <bits/stdc++.h>
using namespace std;
//Main function
int main()
{
int array[] = {3, 7, 9, 1, 2, 5, 11, 4};
int N = sizeof(array)/sizeof(array[0]);
int sum = 10;
int result = 0;
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
for (int i = 0; i < N-2; i++)
{
for (int j = i+1; j < N-1; j++)
{
for (int k = j+1; k < N; k++)
{
if(array[i]+array[j]+array[k] < sum)
{
result++;
}
}
}
}
cout<<"Number of Triplets found = ";
cout<<result;
return 0;
}
Number of Triplets found = 6
Program Java do liczenia trojaczków z sumą mniejszą niż podana wartość
import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int sum = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
int result=0;
for (int i = 0; i < n-2; i++)
{
for (int j = i+1; j < n-1; j++)
{
for (int k = j+1; k < n; k++)
{
if(a[i]+a[j]+a[k] < sum)
{
result++;
}
}
}
}
System.out.print("Number of Triplets found = ");
System.out.println(result);
}
}
5 6 1 2 3 2 1
Number of Triplets found = 5
Analiza złożoności
Złożoność czasowa
O (n * n * n) gdzie n jest rozmiarem podanej tablicy. Tutaj sprawdzamy wszystkie trojaczki i jeśli warunek jest prawdziwy, zwiększ liczbę wyniku.
Złożoność przestrzeni
O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.
Podejście 2
Algorytm
1. Sortuj podaną tablicę, inicjalizuj wynik = 0
2. Wykonaj iterację od i do N -2 (N to rozmiar tablicy) i weź tablicę [i] oraz pierwszy element trójki.
3. Zainicjuj pozostałe dwa elementy jako elementy narożne. tablica [i + 1] i tablica [N-1]
4. ruszaj j i k, aż spotkają się,
- Jeśli suma jest większa niż podana suma, przesuń wskaźnik ostatniego elementu. (tablica [N-1]).
- W przeciwnym razie, jeśli suma jest mniejsza niż podana suma, to może być k -j możliwych tird elementów spełniających, więc dodaj (kj) do wyniku. I przesuń wskaźnik tablicy [i + 1].
Krok 5: Wydrukuj wynik po zakończeniu pętli.
Realizacja
Program C ++ do liczenia trojaczków z sumą mniejszą niż podana wartość
#include <bits/stdc++.h>
using namespace std;
// Main function
int main()
{
int array[] ={1, 2,3,5,6, 3, 2, 5, 7};//input array
int N = sizeof(array)/sizeof(array[0]);//size of the input array(N)
int Sum = 9;//input Sum
int result = 0;//initilizing count of triplets
sort(array,array+N);//sorting the input array
//selecting first element
for(int i = 0; i < N - 2; i++)
{
int j=i+1,k=N-1;//second and third elements as last two elements
while(j<k)
{
// Sum of triplet is greater than or equalto given sum, move to find smaller values
if(array[i] + array[j] + array[k] >= Sum)
{
k--;
}
// Sum of triplet is less than given sum
else
{
//for current i and j there can be k-j elements, move j pointer
result += (k - j);
j++;
}
}
}
cout<<"Number of Triplets found = ";
cout<<result;
}
Number of Triplets found = 14
Program Java do liczenia trojaczków z sumą mniejszą niż podana wartość
import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int sum = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
int result=0;
Arrays. sort(a);//sorting the input array
//selecting first element
for(int i = 0; i < n - 2; i++)
{
int j=i+1,k=n-1;//second and third elements as last two elements
while(j<k)
{
// Sum of triplet is greater than or equalto given sum, move to find smaller values
if(a[i] + a[j] + a[k] >= sum)
{
k--;
}
// Sum of triplet is less than given sum
else
{
//for current i and j there can be k-j elements, move j pointer
result += (k - j);
j++;
}
}
}
System.out.print("Number of Triplets found = ");
System.out.println(result);
}
}
9 9 1 2 3 5 6 3 2 5 7
Number of Triplets found = 14
Analiza złożoności
Złożoność czasowa
O (n * n) gdzie n to liczba elementów obecnych w tablicy. Tutaj naprawiamy jeden element trójki, a następnie używamy dwóch metod wskaźnikowych, które działają O (N) w najgorszym przypadku dla jednego elementu.
Złożoność przestrzeni
O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.
