Fərqli Nömrələrə sahib alt dəstləri sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Cisco Expedia Mintra SAP Laboratoriyaları Taksi4Sure
Geyim Sükut AltBaxılıb 59

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.

Hamımız bir reportajda bir anda ya da digərində alt problemlə mübarizə aparmışıq. Müsahibə verənlər bu problemləri də sevirlər. Bu problemlər, hər hansı bir tələbənin düşüncə prosesinin yanında anlayışını da araşdırmalarına kömək edir. Beləliklə, heç bir fikir vermədən birbaşa problemə atlayaq.

Bölmə-1

Problem Bəyanatı

Bizə bir nömrəli kombinasiya / sıra təqdim edilmişdir. Unikal cüt ədədlərə sahib ola biləcəyimiz alt qrupların sayını qeyd etməliyik.

Kiçik bir nümunə götürək:

Input:

[1,2,5,6,3,2,1,1,8]

Mümkün alt qruplar:

[2,6]

[6,8]

[2,6,8]

Qeyd: Eyni nömrələrə sahib alt dəstlər fərqli hesab olunmayacaq

Eyni sualı mümkün cavab alt qruplarından birini vurğulayaraq göstərim.

Fərqli Nömrələrə sahib alt dəstləri sayın

Bölmə-2

Analiz

İstədiyimizi tapmaq üçün bir çox yol var. The Gücün tətbiqi Mümkün olan bütün alt qrupları tapmaq, sonra qaydalarımızı təmin edənləri tapmaq olardı.

Yuxarıda göstərilən metod başınızı bir divara vurmaqdan başqa bir şey deyil. Beləliklə, axmaq səslənməyinizdən çəkinmək üçün mümkün qədər yaxşı vaxtda cavab almağa kömək edəcək ən asan üsulları işlətdim.

Hər dəfə cüt sayla qarşılaşanda iki seçimimiz olur

  • Ya alt hissədə olmağı seçə bilər
  • Alt dəstdən kənarda qalmağı seçə bilər

Beləliklə, indi yanımızda olan yeganə vəzifə sayın bənzərsiz olub olmadığını müəyyən etməkdir. (Yuxarıda göstərilən qayda sayəsində)

Prosesi sıfırlayaq:

  • Birincisi, a HashSet qarşılaşdığımız cüt ədədlərin bir mağazasını saxlamaq
  • İkincisi, bir dövrəni işə salın
  • Bir rəqəmin bərabər olub olmadığını yoxlayın
  • Nömrə bərabər olsa, ona HashSet əlavə edirik
  • HashSet, yalnız daxil olmağın unikal elementlərinə sahib olmağımızı təmin edən öz sifarişinə malikdir
  • Sonra HashSet-də elementlərin sayını tapırıq
  • Bu say, sahib olduğumuz tək cüt ədədlərin sayını göstərir
  • Bu saydan sonra alt dəstlərin sayını tapmaq üçün istifadə edə bilərik
  • Alt dəstlərin sayı = 2 ^ saymaq-1

Yuxarıdakı proses aşağıdakı kimi kodlaşdırıla bilər:

Fərqli Nömrələrə sahib sayma alt dəstləri üçün Java kodu

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

Fərqli Nömrələrə sahib sayma alt dəstləri üçün C ++ kodu

Java-dan C ++ dilinə keçdiyimiz zaman HashSet əvəzinə Sırasız Dəstdən istifadə edəcəyik və bizə uyğun bir neçə parametr ətrafında fırladın.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

Fərqli Nömrələrə sahib sayma alt qrupları üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi = O (n)

Kosmik Mürəkkəblik = O (n)

Zamanın mürəkkəbliyi

  • Dizidən keçdiyimiz zaman O (n) olur
  • Alt elementə əlavə etməzdən əvvəl hər bir elementi nəzərdən keçiririk

Kosmik Mürəkkəblik

  • Ən pis vəziyyətdə bütün dizini saxlaya biləcəyimiz kimi O (n)
Crack Sistemi Dizayn Müsahibələri
Translate »