Məhsulları Arrayda olan cütləri sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon BlackRock Moonfrog Laboratoriyaları Ola Cabs Snapchat Xome
Geyim SükutBaxılıb 61

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Məhsulları sıra problemində mövcud olan say cütlərində bir array, məhsul dəyəri massivdə olan bütün fərqli cütləri sayın.

misal

Input

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

Buraxılış

Məhsulu massivdə mövcud olan ayrı cütlərin sayı: 2

Cütlər bunlardır: (2, 3), (5, 3)

Kobud güc: Məhsulları Arrayda olan Say cütləri üçün 1 yanaşma

Bütün cütləri təkrarlayın və sonra həmin elementin massivdə olub olmadığını yoxlayın. Varsa, cavabı 1 artırın.

Alqoritm

  1. 0 ilə bir dəyişən ans başlayın.
  2. 0-dan n-1 aralığında I üçün bir döngə çalıştırın;
    1. J üçün i + 1 - n-1 aralığında bir döngə çalıştırın
      1. İndi 0-dan n-1 aralığında k üçün bir döngə çalıştırın
        1. A [i] * A [j] A [k] -ə bərabərdirsə, ans-ı 1 artırın və döngədən qopun.
      2. Ans çap et.

C ++ Proqramı

#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

JAVA Proqramı

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

Məhsulları Arrayda olan Say cütləri üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: Hamısı N ölçülü üç iç içə döngə istifadə edirik. Beləliklə, zamanın mürəkkəbliyi O (N ^ 3).

Kosmik mürəkkəblik: Əlavə yer istifadə etmirik, ona görə də yerin mürəkkəbliyi O (1).

Hashing-dən istifadə: Məhsulu Arrayda olan Count Cütləri üçün 2 yanaşma

Əsas fikir

Dizinin bütün elementlərini hash cədvəlində yerləşdirəcəyik. Bundan sonra cütlərin məhsulu massivdə varsa, bütün cütlər üzərində təkrarlayacağıq, sonra cavabı 1-ə artırırıq. Bir məhsulun massivdə olub olmadığını yoxlaya bilərik.

Alqoritm

  1. Bir hash cədvəli elan edin.
  2. Cavabı saxlayacaq 0 ilə bir dəyişən ans başlayın.
  3. 0-dan n-1 aralığında I üçün bir döngə çalıştırın.
    1. J üçün j + 1-dən n-1 aralığında bir döngə çalıştırın;
      1. A [i] və A [j] məhsulu hash cədvəlində varsa, ans-ı 1 artırın.
    2. Ans çap et.

Misal üçün:

A sıra üçün [] = {2, 4, 2, 4, 15, 8, 20}

Hash cədvəli belə görünəcək:

Məhsulları Arrayda olan cütləri sayınPin

C ++ proqramı

#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

JAVA Proqramı

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

Məhsulları Arrayda olan Say cütləri üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: Hər ikisi də N ölçülü iki iç içə döngə istifadə edirik. Beləliklə, zamanın mürəkkəbliyi O (N ^ 2).

Kosmik mürəkkəblik: Dizinin elementlərini saxlamaq üçün bir hash masa saxlayırıq. Yəni kosmik mürəkkəblik budur O (N).

References

Crack Sistemi Dizayn Müsahibələri
Translate »