Ən yaxın sol və sağ kiçik elementlər arasında maksimum fərqi tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Fourkites
Geyim QalaqBaxılıb 69

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

Verilmiş bir array n ölçülü bir []. “Ən yaxın sol və sağ kiçik elementlər arasındakı maksimum fərqi tapmaq” problemi bir funksiya yaratmağımızı xahiş edir. Beləliklə sola ən yaxın kiçik elementi və sağa ən kiçik elementi təmsil edən sol [] və sağ [] iki sıra yaradır. Sonra sol [i] - sağ [i] massivlərinin mütləq fərqinin maksimumunu tapın.

Ən yaxın sol və sağ kiçik elementlər arasında maksimum fərqi tapınPin

misal

a[ ] = {2, 1, 8}
1
a[ ] = {2, 4, 8, 7, 7, 9, 3}
4

Ən yaxın sol və sağ kiçik elementlər arasında maksimum fərqi tapmaq üçün alqoritm

  1. Başlanğıc və array n ölçülü bir [].
  2. Bir sıra qəbul edən sola və sağa kiçik ölçülü elementləri tapmaq üçün bir funksiya yaradın, ölçüsü və daha kiçik elementləri parametrləri kimi saxlamaq üçün bir sıra yaradın.
  3. Bir yaradın qalaq tam tipli məlumat quruluşu.
  4. A [] massivindən keçin. Yığın boş deyilsə və yığının üst hissəsindəki element indiki indeksdə [] massivindəki elementdən böyük və ya ona bərabərdirsə, elementi yığının tp-sinə qoyun.
  5. Yığın boş olmadığını yoxlayın, yığının yuxarı hissəsindəki element olaraq kiçik elementlər üçün cari indeksdəki dəyəri yeniləyin. Başqa bir sıra, indiki indeksdəki dəyəri 0 kimi kiçik elementlər üçün yeniləyin.
  6. Yığıncaqdakı a]] cərəyanındakı indiki göstəricini itələyin / daxil edin.
  7. Eynilə, bir sıra qəbul edən və parametr olduğu ölçüdə olan maksimum fərqi tapmaq üçün başqa bir funksiya yaradın.
  8. Sol tərəfə ən kiçik elementi saxlamaq üçün n ölçülü solda bir sıra düzəldin. Verilmiş massivli kiçik elementlər üçün funksiyanı axtarın, ölçüsü və parametr olduğu kimi sol massiv.
  9. Eynilə, sağdakı ən kiçik elementi saxlamaq üçün n ölçülü bir sağa doğru bir sıra yaradın. Orijinal massivi [] tərs çevirin və verilmiş massivlə kiçik elementlər üçün funksiyanı çağırın, onun ölçüsü və parametr olduğu kimi sağ massiv.
  10. 0-dan n-1-ə keçin və sol və sağ massivin mütləq fərqinin maksimumunu tapın.
  11. Nəticəni çap edin.

Kodu

Ən yaxın sol və sağ kiçik elementlər arasında maksimum fərqi tapmaq üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
void SmallerElement(int a[], int n, int SE[]){ 
    stack<int>S; 
  
    for(int i=0; i<n; i++){ 
        
        while(!S.empty() && S.top() >= a[i]){ 
            S.pop(); 
        }
  
        if(!S.empty()){ 
            SE[i] = S.top();
        }
  
        else{
            SE[i] = 0;
        }
  
        S.push(a[i]); 
    } 
} 
  
int findMaxDiff(int a[], int n){ 
    int left[n]; 
  
    SmallerElement(a, n, left); 
  
    int right[n]; 
    
    reverse(a, a + n); 
    SmallerElement(a, n, right); 
  
    int result = -1; 
    for(int i=0 ; i< n ; i++){ 
        result = max(result, abs(left[i] - right[n-1-i]));
    }
   
    return result; 
} 
  
int main(){ 
    int a[] = {2, 4, 8, 7, 7, 9, 3}; 
    int n = sizeof(a)/sizeof(a[0]);
    
    cout << findMaxDiff(a, n) << endl; 
    
    return 0; 
}
4

Ən yaxın sol və sağ kiçik elementlər arasında maksimum fərqi tapmaq üçün Java Proqramı

import java.util.*; 
  
class MaximumOfDifference{ 
  
    static void SmallerElement(int a[], int n, int SE[]){ 
        
        Stack<Integer> S = new Stack<>(); 
  
        for(int i = 0; i < n; i++){ 
            
            while(!S.empty() && S.peek() >= a[i]){ 
                S.pop(); 
            } 
  
            if(!S.empty()){ 
                SE[i] = S.peek(); 
            }  
            
            else{ 
                SE[i] = 0; 
            } 
  
            S.push(a[i]); 
        } 
    } 
  
    static int findMaxDiff(int a[], int n){ 
        int[] left = new int[n]; 
  
        SmallerElement(a, n, left); 
  
        int[] right = new int[n]; 
        
        reverse(a); 
        SmallerElement(a, n, right); 
  
        int result = -1; 
        for(int i = 0; i < n; i++){ 
            result = Math.max(result, Math.abs(left[i] - right[n - 1 - i])); 
        } 
 
        return result; 
    } 
  
    static void reverse(int a[]){ 
        int i, k, n = a.length, t; 
        
        for(i = 0; i < n / 2; i++){ 
            t = a[i]; 
            a[i] = a[n - i - 1]; 
            a[n - i - 1] = t; 
        } 
    } 
      
    public static void main(String args[]){ 
        int a[] = {2, 4, 8, 7, 7, 9, 3}; 
        int n = a.length; 
        
        System.out.println(findMaxDiff(a, n)); 
    } 
}
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) burada n - verilmiş a [] massivindəki tam ədədin sayı. Yalnız yeni bir sıra keçdiyimiz üçün zamanın mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (n), çünki n element üçün yer istifadə etdik. Soldan və sağdan iki sıra yaratdıq. Beləliklə, kosmik mürəkkəblik də xətti olur.

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