Rekursiyadan istifadə edərək yığını çeşidləyin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Goldman Sachs IBM Kuliza Yahoo
Recursion QalaqBaxılıb 99

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.

Problem bəyanat

“Rekursiyadan istifadə edərək yığını sırala” problemi sizə verildiyini bildirir qalaq məlumatların quruluşu. Cür rekursiyadan istifadə edən elementləri. Yalnız yığının aşağıda sadalanan funksiyalarından istifadə edilə bilər -

  • push (element) - elementi yığına daxil etmək.
  • pop () - pop () - verilmiş yığının üstündəki elementi silmək / silmək üçün.
  • isEmpty () - yığında hər hansı bir elementin olub olmadığını yoxlamaq.
  • top () - verilmiş yığının üstündəki elementə baxmaq / görmək.

Rekursiyadan istifadə edərək yığını çeşidləyinPin

misal

9 4 2 -1 6 20
20 9 6 4 2 -1

İzahat: Yığım artan sırada sıralanmış olduğundan. Maksimum element yuxarıdan gəlir. Yığın LIFO məlumat quruluşu olduğundan, çıxış azalan sırada görünür.

2 1 4 3 6 5
6 5 4 3 2 1

Alqoritm

  1. Başlanğıc a qalaq və içindəki elementləri itələyin.
  2. Bir yığını və bir elementi bir parametr olaraq qəbul edən yığını elementləri sıralanmış qaydada daxil etmək üçün bir funksiya yaradın. Yığının boş və ya verilmiş elementin yığının üst hissəsindəki elementdən böyük olduğunu yoxlayın, elementi yığının içərisinə itələyib geri qayıdın.
  3. Müvəqqəti bir dəyişən yaradın və yığının üst hissəsini orada saxlayın. Yığının üstündəki elementi açın və funksiyanın özünə rekursiv zəng edin. Yığındakı müvəqqəti dəyişəni itələyin.
  4. Eynilə, bir yığını parametr olaraq qəbul edən bir funksiya sort () yaradın. Yığının boş olmadığını yoxlayın, dəyişən x yaradın və yığının üst hissəsini içində saxlayın. Yığının üstündəki elementi açın. Funksiyanın özünə rekursiv bir zəng edin. Elementləri yığına sıralanmış qaydada daxil etmək üçün funksiyaya zəng edin.
  5. Main () sıralama funksiyasına zəng edin.
  6. Bir yığını parametr olaraq qəbul edən sıralanmış yığını çap etmək üçün bir funksiya yaradın. Yığın boş olmadığı zaman keçin, yığının məlumatlarını çap edin və növbəti elementə keçin.

Kodu

Rekursiyadan istifadə edərək bir yığını sıralamaq üçün C ++ proqramı

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

Rekursiyadan istifadə edərək yığını sıralamaq üçün Java Proqramı

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N ^ 2) burada n yığındakı elementlərin sayıdır. Çünki elementi yığının içərisinə itələdikdə, yığında mövcud olan bütün elementləri çıxarıb sonra əlavə edə bilərik. Bu vəziyyət giriş azalma sırasındadırsa baş verir.

Kosmik Mürəkkəblik

O (N) çünki n element üçün yığın boşluğu istifadə etdik. Mövcud elementimizi yerləşdirmək üçün elementləri çıxararkən. Çıxarılan elementləri saxlamalı idik və bu bizə xətti bir kosmik mürəkkəblik verir.

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