Bir Arrayın Yığın Sıralanabilir olub olmadığını yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Akkolit Amazon
Geyim çeşidləyici QalaqBaxılıb 82

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.

Bir yoxlayın array stack sortable problemidir, təsadüfi qaydada 1-dən n-ə qədər elementləri ehtiva edən bir n ölçülü bir sıra verdik. Dizini müvəqqəti istifadə edərək artan sırada sıralayın qalaq yalnız bu iki əməliyyatı izlədikdə -

  • Elementi massivdəki başlanğıc indeksindən çıxarın və yığında saxlayın.
  • Yığının üst hissəsini açın və başqa bir massivin sonunda əlavə edin.

Bu yığını yığından istifadə edərək sıralamaq mümkün olub olmadığını yoxlayın.

Bir Arrayın Yığın Sıralanabilir olub olmadığını yoxlayınPin

misal

Input

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

Buraxılış

Verilən massiv yığından istifadə etməklə sıralana bilər.

Input

a [] = {2, 3, 1}

Buraxılış

Verilən massiv yığından istifadə etməklə sıralana bilməz.

Alqoritm

  1. N ölçülü bir [] massivi başladın.
  2. Massivi sıralamaq üçün elementləri saxlamaq üçün bir yığın və sonuna işarə etmək üçün bir dəyişən son = 0 yaradın.
  3. 0-dan n-1-ə keçin və yığının boş olub olmadığını yoxlayın, dizinin dəyərini yığının indiki indeksinə itələyin. Başqa biri yığının üst hissəsini dəyişən bir üst hissədə saxlayır. Üst hissə son + 1-ə bərabər olsa da, ucunu artırın və üstü açın. Yığının boş olub olmadığını yoxlayın. Dəyişən üstü yığının içindəki indiki kimi yeniləyin.
  4. Yığın boşdursa, dizinin dəyərini yığının içindəki indeksə itələyin.
  5. Başqa biri yığının üst hissəsini dəyişən bir üst hissədə saxlayır. Cari indeksdəki massivin dəyərinin yuxarıdan az olub olmadığını yoxlayın, dizi elementini yığının içərisinə itələyin. Başqa bir yalan qayıt.
  6. Doğru qayıdın.

Bir Arrayın Yığın Sıralana biləcəyini Yoxlamaq üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
bool check(int a[], int n){ 
    
    stack<int> S; 
  
    int end = 0; 
  
    for(int i = 0; i < n; i++){ 
        
        if(!S.empty()){ 
            
            int top = S.top(); 
  
            while(top == end + 1){ 
                end = end + 1; 
  
                S.pop(); 
  
                if(S.empty()){ 
                    break; 
                } 
  
                top = S.top(); 
            } 
  
            if(S.empty()) { 
                S.push(a[i]); 
            } 
            
            else{ 
                top = S.top(); 
  
                if(a[i] < top){ 
                    S.push(a[i]); 
                } 
                else{ 
                    return false; 
                } 
            } 
        } 
        else{ 
            S.push(a[i]); 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    int a[] = {4, 1, 2, 3}; 
    int n = sizeof(a) / sizeof(a[0]);
    
    check(a, n)? cout<<"Given array can be sorted using stack.": cout<<"Given array can not be sorted using stack.";    
    
    return 0; 
}
Given array can be sorted using stack.

Bir Arrayın Yığın Sıralanabilir olub olmadığını yoxlamaq üçün Java Proqramı

import java.util.Stack; 
  
class soryArray{ 
  
    static boolean check(int a[], int n){ 
        
        Stack<Integer> S = new Stack<Integer>(); 
  
        int end = 0; 
  
        for(int i = 0; i < n; i++) { 
            if(!S.empty()){ 
                int top = S.peek(); 
  
                while(top == end + 1){ 
                    end = end + 1; 
  
                    S.pop(); 
  
                    if(S.empty()){ 
                        break; 
                    } 
  
                    top = S.peek(); 
                } 
  
                if (S.empty()) { 
                    S.push(a[i]); 
                } 
                else{ 
                    top = S.peek(); 
  
                    if(a[i] < top) { 
                        S.push(a[i]); 
                    } 
                    else{ 
                        return false; 
                    } 
                } 
            } 
            else{ 
                S.push(a[i]); 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args) { 
  
        int a[] = {4, 1, 2, 3}; 
        int n = a.length; 
  
        if(check(a, n)){ 
            System.out.println("Given array can be sorted using stack."); 
        } 
        else{ 
            System.out.println("Given array can not be sorted using stack."); 
        } 
  
    } 
}
Given array can be sorted using stack.

Bir Dizinin Yığın Sıralana biləcəyini Yoxlamaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (n), burada n - massivdəki elementlərin sayı.

Kosmik Mürəkkəblik: O (n), çünki n elementi saxlamaq üçün yer istifadə etdik.

References

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