Liczba trojaczków z sumą mniejszą niż podana wartość

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Cisco Cytadela Citrix Drzwiczki eBay Facebook Goldman Sachs Google Hulu IBM Infosys MATHWORKS Microsoft wyrocznia PayPal Qualtrics Samsung ServiceNow Splunk Kwadratowe Tencent Tesla Uber Visa VMware Laboratoria Walmart Yahoo Zoho
Akamai Szyk Groupon Postmates Dwa wskaźniki Dwa wskaźniki Aplikacje Worksodwiedzajacy 712

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

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ę,

  1. Jeśli suma jest większa niż podana suma, przesuń wskaźnik ostatniego elementu. (tablica [N-1]).
  2. 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.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »