Znajdź parę z podaną różnicą

Poziom trudności Łatwo
Często zadawane pytania Amazonka Bloomberg Citrix Expedia Goldman Sachs Microsoft Nvidia wyrocznia Salesforce Twilio Twitter Visa VMware
Wyszukiwanie binarne Badawczy Sortowanieodwiedzajacy 384

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 podanym nieposortowanym szykznajdź parę elementów w podanej tablicy z podaną różnicą n.

Przykład

Wkład

arr [] = {120, 30, 70, 20, 5, 6},

różnica (n) = 40

Wydajność

[30, 70]

Wyjaśnienie

Tutaj różnica 30 i 70 równa się wartości n.

Wkład

arr [] = {120, 30, 70, 20, 5, 6},

różnica (n) = 10

Wydajność

[20, 30]

Wyjaśnienie

Tutaj różnica 20 i 30 równa się wartości n.

Wkład

arr = {120, 30, 70, 20, 5, 6},

różnica (n) = 30

Wydajność

Nie znaleziono pary z podaną różnicą

Wyjaśnienie

Tutaj nie ma takiej pary elementów, że różnica między nimi jest równa n.

Algorytm znajdowania pary z podaną różnicą

Teraz znamy stwierdzenie problemu. Więc szybko przejdź do części algorytmu. Najpierw sortujemy podaną tablicę, a następnie przechodzimy przez całą tablicę. Najpierw bierzemy dwa wskaźniki przy indeksie 0, a drugie przy indeksie 1. Teraz, jeśli różnica między nimi jest mniejsza niż podana różnica, przesuń drugi wskaźnik o 1. Jeśli różnica między nimi jest większa niż podana różnica, przesuń pierwszy wskaźnik o 1 Jeśli różnica między elementami jest taka sama, policz odpowiedź. Na koniec wydrukuj całkowitą liczbę zliczeń.

1: Najpierw posortuj podaną tablicę.

2: W tej tablicy weź dwa indeksy i i j zainicjalizuj i = 0 i j = 1.

3: Uruchom pętlę, aby sprawdzić, czy tablica [j] - tablica [i] = n,

  • Jeśli tablica [j] - tablica [i] = n, wypisuje tablicę [j] i tablicę [i].
  • Sprawdź, jeśli tablica [j] - tablica [i]> n, zwiększ i.
  • Jeśli tablica [j] - tablica [i] <n, zwiększ j.

4: Jeśli pętla dotrze do końca. Następnie wypisz „nie znaleziono pary”.

Realizacja

Program C ++ do znajdowania pary z podaną różnicą

#include <bits/stdc++.h>
using namespace std;
 
//In the given array -> array[] of N N 
//finding the pair with difference n
int FindPair(int array[], int N, int difference)
{
    //sort the given array
    sort(array, array+N);
    int i = 0;  
    int j = 1;
    while(i<N && j<N)
    {
        if (i != j && array[j]-array[i] == difference)
        {
            cout<<"pair with difference "<<difference<<" is: ";
            cout<<"["<<array[i]<<", "<<array[j]<<"]";
            return 1;
        }
        //if difference here is less than given difference
        // move right pointer(j)
        else if (array[j]-array[i] < difference) 
        {
            j++;
        }
        //if difference here is greater than given difference
        // move left pointer(i)
        else
        {
            i++;
        }
    }
    cout<<"No pair found";
    return 0;
}
 
//Main function to check above functions
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int diff;
    cin>>diff;
    FindPair(a, n, diff);
    return 0;
}

Program Java do wyszukiwania pary z podaną różnicą

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    //In the given array -> array[] of N N 
    //finding the pair with difference n
    public static int FindPair(int array[], int N, int difference)
    {
        //sort the given array
        Arrays.sort(array);
        int i = 0;  
        int j = 1;
        while(i<N && j<N)
        {
            if (i != j && array[j]-array[i] == difference)
            {
                System.out.println(array[i] + " " + array[j]);
                return 1;
            }
            //if difference here is less than given difference
            // move right pointer(j)
            else if (array[j]-array[i] < difference) 
            {
                j++;
            }
            //if difference here is greater than given difference
            // move left pointer(i)
            else
            {
                i++;
            }
        }
        System.out.println("No pair found");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int diff ;
        diff = sr.nextInt();
        FindPair(arr,n,diff);
    } 
}
6 
5 20 3 2 50 80
78
2 80

Analiza złożoności

Złożoność czasowa

O (NLogN) gdzie n jest rozmiarem tablicy. Tutaj używamy wbudowanej funkcji sortowania, która prowadzi nas do złożoności czasu nlogn.

Złożoność przestrzeni

O (1) ponieważ nie tworzymy dodatkowej przestrzeni podczas obliczania wyniku.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »