Policz pary, których produkty istnieją w zestawieniu

Poziom trudności Łatwo
Często zadawane pytania Accolita Amazonka BlackRock Laboratorium księżycowej żaby! Ola Cabs Snapchat Xome
Szyk Haszyszodwiedzajacy 61

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.

W parach zliczeniowych, których produkty występują w problemie z tablicami, daliśmy szyk, policz wszystkie różne pary, których wartość iloczynu znajduje się w tablicy.

Przykład

Wkład

A [] = {2, 5, 6, 3, 15}

Wydajność

Liczba różnych par, których iloczyn istnieje w tablicy to: 2

Pary to: (2, 3), (5, 3)

Brute force: Podejście 1 dla zliczania par, których produkt istnieje w tablicy

Powtórz wszystkie pary, a następnie sprawdź, czy ten element istnieje w tablicy, czy nie. Jeśli istnieje, zwiększ odpowiedź o 1.

Algorytm

  1. Zainicjuj zmienną ans wartością 0.
  2. Uruchom pętlę dla I w zakresie od 0 do n-1;
    1. Uruchom pętlę dla j w zakresie od i + 1 do n-1
      1. Teraz uruchom pętlę dla k w zakresie od 0 do n-1
        1. Jeśli A [i] * A [j] jest równe A [k], to zwiększ ans o 1 i przerwij pętlę.
      2. Drukuj ans.

Program w C ++

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (A[i] * A[j] == A[k])
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 5, 6, 3, 15, 30};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 4

Program JAVA

public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (A[i] * A[j] == A[k])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array is: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 5, 6, 3, 15, 30};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array is: 4

Analiza złożoności dla par, których produkt istnieje w tablicy

Złożoność czasowa: Używamy trzech zagnieżdżonych pętli, wszystkie o rozmiarze N. Więc złożoność czasowa wynosi O (N ^ 3).

Złożoność przestrzeni: Nie używamy żadnej dodatkowej przestrzeni, więc złożoność przestrzeni jest O (1).

Korzystanie z haszowania: podejście 2 dla zliczania par, których produkt istnieje w tablicy

Główny pomysł

Wszystkie elementy tablicy będziemy umieszczać w tablicy haszującej. Następnie dokonamy iteracji po wszystkich parach, jeśli iloczyn par istnieje w tablicy, a następnie zwiększamy odpowiedź o 1. Możemy sprawdzić, czy w tablicy występuje iloczyn, czy nie, wyszukując w tablicy haszującej w stałym czasie.

Algorytm

  1. Zadeklaruj tablicę skrótów.
  2. Zainicjuj zmienną ans wartością 0, która zapisze odpowiedź.
  3. Uruchom pętlę dla I w zakresie od 0 do n-1.
    1. Uruchom pętlę dla j w zakresie od j + 1 do n-1;
      1. Jeśli iloczyn A [i] i A [j] jest obecny w tablicy haszującej, należy zwiększyć ans o 1.
    2. Drukuj ans.

Na przykład:

Dla tablicy A [] = {2, 4, 2, 4, 15, 8, 20}

Tabela skrótów będzie wyglądać następująco:

Policz pary, których produkty istnieją w zestawieniuszpilka

Program w C ++

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    unordered_set<int> hash_table;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        hash_table.insert(A[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (hash_table.count(A[i] * A[j]) == 1)
            {
                ans++;
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 7

Program JAVA

import java.util.*; 
public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        Set<Integer> hash_table=new HashSet<Integer>();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            hash_table.add(A[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if(hash_table.contains(A[i]*A[j])==true)
                {
                    ans++;
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array are: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array are: 7

Analiza złożoności dla par, których produkt istnieje w tablicy

Złożoność czasowa: Używamy dwóch zagnieżdżonych pętli, obie o rozmiarze N. Więc złożoność czasowa wynosi O (N ^ 2).

Złożoność przestrzeni: Utrzymujemy tablicę mieszającą do przechowywania elementów tablicy. Tak więc jest złożoność przestrzeni NA).

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »