Bir yığında k yığını necə səmərəli şəkildə tətbiq etmək olar?

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fourkites
Geyim QalaqBaxılıb 89

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.

Tək yığında k yığınlarını tətbiq edən yeni bir məlumat quruluşu dizayn edin və tətbiq edin. Yeni məlumat quruluşu bu iki əməliyyatı dəstəkləməlidir -

  • push (element, stack_number): elementi verilmiş sayda itələyən qalaq.
  • pop (stack_number): verilmiş bir yığın sayından yuxarı elementi çıxaran.

Bir yığında k yığını necə səmərəli şəkildə tətbiq etmək olar?Pin

misal

Input 

itələmək (15, 2)
itələmək (45, 2)
itələmək (17, 1)
itələmək (49, 1)
itələmək (39, 1)
itələmək (11, 0)
itələmək (9, 0)
itələmək (7, 0)
pop (2)
pop (1)
pop (0)

Buraxılış

Yığın 2: 45 yığılmış element
Yığın 1: 39 yığılmış element
Yığın 0: 7 yığılmış element

Input 

itələmək (100, 1)
itələmək (200, 0)
itələmək (300, 0)
pop (1)
pop (0)

Buraxılış 

Yığın 1: 100 yığılmış element
Yığın 0: 300 yığılmış element

K yığını tək bir massivdə səmərəli şəkildə həyata keçirmək üçün alqoritm

  1. Yaratmaq array yığın elementlərini saxlamaq üçün arr [], bütün yığınların üst elementlərinin indeksini saxlamaq üçün top [] və sonrakı [] bütün yığınların növbəti elementinin yenilənməsini davam etdirmək üçün.
  2. Pulsuz siyahının başlanğıc indeksini saxlamaq üçün pulsuz bir dəyişən yaradın.
  3. Üst [] bütün dəyərlərini -1 və sonrakı [] dəyərlərini indeks + 1 olaraq keçin və təyin edin.
  4. Element və yığın nömrəsini parametr olaraq qəbul edən push () funksiyası yaradın və verilmiş sayın bir yığınının “Stack Overflow” -un tam çap olub olmadığını yoxlayın və qayıdın.
  5. Else Initialise dəyişən i deyir və pulsuz olaraq yeniləyir. Pulsuz olaraq növbəti (i), sonrakı (i) kimi verilmiş sayın yığının üst hissəsi, verilən sayın yığının üstü kimi i kimi yeniləyin və sonda massivdəki elementi i indeksinə itələyin.
  6. Yığın nömrəsini parametr olaraq qəbul edən pop () funksiyası yaradın və verilən sayın yığınının boş olub olmadığını yoxlayın “Stack Underflow” və geri qayıdın.
  7. Else Initialise bir dəyişən i deyir və verilmiş bir ədədin üst hissəsində yeniləyir. Verilən sayın yığınının üst hissəsini next (i), next (i) kimi sərbəst, I kimi pulsuz olaraq yeniləyin və sonda massivdəki elementi I indeksinə qaytarın.

Tək bir massivdə k yığını səmərəli şəkildə həyata keçirmək üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
class newStack{ 
    int *arr;   
    int *top;   
    int *next;  
    
    int n, k; 
    int free; 
public: 
    
    newStack(int k, int n); 
  
    bool isFull(){  
        return(free == -1);  
    } 
  
    void push(int item, int sn); 
  
    int pop(int sn); 
  
    bool isEmpty(int sn){  
        return (top[sn] == -1); 
    } 
}; 
  
newStack::newStack(int k1, int n1){ 
    
    k = k1, n = n1; 
    arr = new int[n]; 
    top = new int[k]; 
    next = new int[n]; 
  
    for(int i = 0; i < k; i++) 
        top[i] = -1; 
  
    free = 0; 
    for(int i=0; i<n-1; i++) 
        next[i] = i+1; 
    next[n-1] = -1; 
} 
  
void newStack::push(int item, int sn){ 
    
    if(isFull()){ 
        cout << "\nStack Overflow\n"; 
        return; 
    } 
  
    int i = free;     
  
    free = next[i]; 
  
    next[i] = top[sn]; 
    top[sn] = i; 
  
    arr[i] = item; 
} 
  
int newStack::pop(int sn){ 
    
    if(isEmpty(sn)){ 
         cout<<"\nStack Underflow\n"; 
         return INT_MAX; 
    } 
  
    int i = top[sn]; 
  
    top[sn] = next[i];  
  
    next[i] = free; 
    free = i; 
  
    return arr[i]; 
} 
  
int main(){ 
    
    int k = 3, n = 10; 
    newStack ks(k, n); 
  
    ks.push(15, 2); 
    ks.push(45, 2); 
  
    ks.push(17, 1); 
    ks.push(49, 1); 
    ks.push(39, 1); 
  
    ks.push(11, 0); 
    ks.push(9, 0); 
    ks.push(7, 0); 
  
    cout << "Popped element from stack 2 : " << ks.pop(2) << endl; 
    cout << "Popped element from stack 1 : " << ks.pop(1) << endl; 
    cout << "Popped element from stack 0 : " << ks.pop(0) << endl; 
  
    return 0; 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Java proqramı, k yığını tək bir massivdə səmərəli şəkildə tətbiq etmək

class kstack{ 
    
    static class newStack{ 
        int arr[];   
        int top[];   
        int next[];  
        
        int n, k; 
        int free; 
  
        newStack(int k1, int n1){ 
            
            k = k1; 
            n = n1; 
            arr = new int[n]; 
            top = new int[k]; 
            next = new int[n]; 
  
            for(int i = 0; i < k; i++) 
                top[i] = -1; 
  
            free = 0; 
            for(int i = 0; i < n - 1; i++) 
                next[i] = i + 1; 
            next[n - 1] = -1;
        } 
  
        boolean isFull(){ 
            return (free == -1); 
        } 
  
        void push(int item, int sn){ 
            
            if(isFull()){ 
                System.out.println("Stack Overflow"); 
                return; 
            } 
  
            int i = free; 
  
            free = next[i]; 
  
            next[i] = top[sn]; 
            top[sn] = i; 
  
            arr[i] = item; 
        } 
  
        int pop(int sn){ 
            
            if(isEmpty(sn)){ 
                System.out.println("Stack Underflow"); 
                return Integer.MAX_VALUE; 
            } 
  
            int i = top[sn]; 
  
            top[sn] = next[i]; 
  
            next[i] = free; 
            free = i; 
  
            return arr[i]; 
        } 
  
        boolean isEmpty(int sn){ 
            return (top[sn] == -1); 
        } 
  
    } 
  
    public static void main(String[] args){ 
        
        int k = 3, n = 10; 
          
        newStack ks = new newStack(k, n); 
  
        ks.push(15, 2); 
        ks.push(45, 2); 
  
        ks.push(17, 1); 
        ks.push(49, 1); 
        ks.push(39, 1); 
  
        ks.push(11, 0); 
        ks.push(9, 0); 
        ks.push(7, 0); 
  
        System.out.println("Popped element from stack 2 : " + ks.pop(2)); 
        System.out.println("Popped element from stack 1 : " + ks.pop(1)); 
        System.out.println("Popped element from stack 0 : " + ks.pop(0)); 
    } 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: push () və pop () sabit vaxtdan istifadə edir, yəni O (1). Üst və sonrakı hissələrin saxlanılması müvafiq olaraq O (k) və O (n) vaxt tələb edəcəkdir.

Kosmik Mürəkkəblik: O (n), burada n elementləri saxlanılır.

References

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