Znajdź trójkę w tablicy z podaną sumą

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

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

Mając tablicę liczb całkowitych, znajdź kombinację trzech elementów w szyk których suma jest równa danej wartości X. Tutaj wypisujemy pierwszą otrzymaną kombinację. Jeśli nie ma takiej kombinacji, wypisz -1.

Przykład

Wkład

N = 5, X = 15

arr [] = {10, 4, 2, 3, 5}

Wydajność 

10, 2, 3

Podejście 1

Generowanie wszystkich trójek i porównanie sumy z podaną wartością. Poniższy algorytm zawiera trzy pętle.

Algorytm

  1. Najpierw posortuj tablicę wejściową
  2. Napraw pierwszy element jako arr [i], gdzie i mieści się w zakresie od 0 do N-2.
  3. Po zamocowaniu pierwszego elementu, napraw drugi element jako arr [j], gdzie j waha się od i + 1 do N-1.
  4. Po zamocowaniu drugiego elementu ustal trzeci element jako arr [k], gdzie k waha się od j + 1 do N.
  5. Znajdź sumę, arr [i] + arr [j] + arr [k].
  6. Jeśli suma Triplet jest równa wartości X, wypisz trzy elementy w przeciwnym razie wypisz -1.

Realizacja

Program w C ++ do wyszukiwania trójki w tablicy z podaną sumą

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

Program w języku Java do znajdowania trójki w tablicy z podaną sumą

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if( a[i] + a[j] + a[k] == x)
                    {
                       System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                       i=n;j=n;k=n;
                       temp=1;
                    }
                }
            }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
10 4 2 3 5
10  2  3

Analiza złożoności

Złożoność czasowa

O (n * n * n) gdzie n to liczba elementów obecnych w tablicy. Tutaj mamy Ron trzy dla pętli i sprawdzamy każdą możliwą trójkę.

Złożoność przestrzeni

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

Podejście 2

Algorytm

  1. Imię rodzaj tablica wejściowa
  2. Napraw pierwszy element jako arr [i], gdzie i mieści się w zakresie od 0 do N-2.
  3. Po ustaleniu pierwszego elementu, aby znaleźć następne dwa elementy, weź zmienne podobne do dwóch wskaźników (j = i + 1, k = N-1) i przejdź przez algorytm znajdowania sumy w posortowanej tablicy.
  4. Podczas gdy j jest mniejsze niż k Dodaj elementy o podanych indeksach, tj. Arr [i] + arr [j] + arr [k], jeśli suma tripletu jest równa wartości X, wypisz trzy elementy w innym przypadku, jeśli suma tripletu jest mniejsza niż wartość X, następnie zwiększ wartość j, w przeciwnym razie zmniejsz wartość k.

Realizacja

Program w C ++ do wyszukiwania trójki w tablicy z podaną sumą

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}

Program w języku Java do znajdowania trójki w tablicy z podaną sumą

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 x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); //sort the array in ascending order
        int computed_sum;//sum computed at each step
        int temp=0;
        for(int i = 0; i < n - 2; i++) // fix one element and search for other two elements in linear time
        {
          int j = i+1 , k = n-1; // jth index starts from the next element of selected and k always starts at the ending index
          while(j < k)
          {
            computed_sum = a[i] + a[j] + a[k]; // add the elements at the given indices
            if(computed_sum == x)
              {
                System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                j=k;
                temp=1;
              }
            else if(computed_sum < x) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
              j++;
            else if(computed_sum > x)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
              k--;
          }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
1 4 2 3 5
-1

Analiza złożoności

Złożoność czasowa

O (n * n * n) gdzie n to liczba elementów obecnych w tablicy. Tutaj mamy Ron trzy dla pętli i sprawdzamy każdą możliwą trójkę.

Złożoność przestrzeni

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

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »