Növbəti Böyük Frekans Elementi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Capgemini microsoft UHG Optum
Geyim Sükut QalaqBaxılıb 104

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.

Növbəti daha böyük tezlik elementi problemində, ədədləri ehtiva edən bir n ölçülü bir sıra verdik. Hər bir rəqəm üçün array çap, cari saydan daha çox bir tezlikə sahib bir sıra içərisində olan rəqəm.

Növbəti Böyük Frekans ElementiPin

misal

Input 

a [] = {1, 1, 2, 3, 4, 2, 1}

Buraxılış 

-1 -1 1 2 2 1 -1

Input

a [] = {1, 1, 2, 3}

Buraxılış

-1 -1 -1 -1

Alqoritm

İndi Next Greater Frequency Element problemi üçün problem ifadəsini bilirik. Beləliklə, onun alqoritminə doğru irəliləyirik.

  1. N ölçülü bir [] massivi başladın.
  2. Tezliyi saxlamaq və 16 olaraq işə salmaq üçün INT0_MAX ölçülü başqa bir frekans [] yaradın.
  3. A [] cərgəsini keçin və a [i] indeksində frek [] sıra dəyərini artırın.
  4. Bir yığın yaradın və nəticəni saxlamaq üçün içərisinə 0 və n ölçülü bir sıra basın.
  5. 1-dən n-1-ə qədər keçin və freq [a [s.top ()]] dəki dəyərin freq [a [i]] dəki dəyərdən böyük olub olmadığını yoxlayın, cari vəziyyəti / i yığında itələyin.
  6. Başqa bir halda, freq [a [s.top ()]] dəki dəyər frekans [a [i]] dəyərindən az və yığın boş deyilsə, res [s.top ()] = a [i] və res olaraq yeniləyin üst pop. Cari vəziyyəti / i yığında itələyin.
  7. Yığın boş olmasa da, res [s.top ()] = -1 olaraq yeniləyin və üstünü açın.
  8. Res [] dizisini çap edin.

Növbəti Böyük Frekans Elemanı üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std; 

void NextGreaterFrequency(int a[], int n, int freq[]){ 
  
    stack<int> s;  
    s.push(0); 
      
    int res[n] = {0};
    
    for(int i = 1; i < n; i++){ 
        if(freq[a[s.top()]] > freq[a[i]]){ 
            s.push(i); 
        }    
        else{ 
            while((freq[a[s.top()]] < freq[a[i]]) && !s.empty()){ 
                res[s.top()] = a[i]; 
                s.pop(); 
            } 
            
            s.push(i); 
        } 
    } 
  
    while(!s.empty()){ 
        res[s.top()] = -1; 
        s.pop(); 
    } 
    for(int i = 0; i < n; i++){ 
        cout<<res[i]<<" "; 
    } 
} 
  
int main(){ 
  
    int a[] = {1, 1, 2, 3, 4, 2, 1}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int max = INT16_MAX; 
    
    for(int i = 0; i < n; i++){ 
        if (a[i] > max){ 
            max = a[i]; 
        } 
    } 
    int freq[max + 1] = {0}; 
      
    for(int i = 0; i < n; i++){ 
        freq[a[i]]++; 
    } 
  
    NextGreaterFrequency(a, n, freq); 
    return 0; 
}
-1 -1 1 2 2 1 -1

Next Greater Frequency Element üçün Java Proqramı

import java.util.*; 

class ngf{ 

    static void NextGreaterFrequency(int a[], int n, int freq[]){ 
    
        Stack<Integer> s = new Stack<Integer>();  
        s.push(0); 
        
        int res[] = new int[n]; 
        for(int i = 0; i < n; i++){ 
            res[i] = 0; 
        }
        
        for(int i = 1; i < n; i++){ 
        
            if(freq[a[s.peek()]] > freq[a[i]]){ 
                s.push(i); 
            }
            
            else{ 
                while (freq[a[s.peek()]] < freq[a[i]] && s.size()>0){ 
                    res[s.peek()] = a[i]; 
                    s.pop(); 
                } 
                
                s.push(i); 
            } 
        } 
        
        while(s.size() > 0){ 
            res[s.peek()] = -1; 
            s.pop(); 
        } 
        
        for(int i = 0; i < n; i++){ 
            System.out.print( res[i] + " "); 
        } 
    } 
    
    public static void main(String args[]){ 
    
        int a[] = {1, 1, 2, 3, 4, 2, 1}; 
        int n = a.length; 
        int max = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; i++){ 
            if(a[i] > max){ 
                max = a[i]; 
            } 
        } 
        int freq[] = new int[max + 1]; 
        
        for(int i = 0; i < max + 1; i++){ 
            freq[i] = 0; 
        }
        
        for(int i = 0; i < n; i++){ 
            freq[a[i]]++; 
        } 
        
        NextGreaterFrequency(a, n, freq); 
    } 
}
-1 -1 1 2 2 1 -1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n number a [] massivindəki elementlərin. Son cavabı saxlamaq üçün bir yığın və bir sıra istifadə edirik.

Kosmik Mürəkkəblik: O (max), burada maksimum INT16_MAX-ə bərabərdir. Burada max dəyəri 32767 olan sabitdir. Giriş massivində mövcud say sayını saxlamaq üçün bir tezlik massivi yaradırıq.

References

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