Səhm Aralığı Problemi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Çatdırılma MAQ
QalaqBaxılıb 85

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.

Bu problem “Səhmlərə Qapalı Problem” maliyyə baxımından gəlir. Bu problemdə, hər günün səhm qiyməti üçün stok aralığını tapırıq. Hər hansı bir gündən əvvəl səhmlərin qiymətinin səhm qiymətindən az və ya ona bərabər olduğu hər hansı bir gündən əvvəlki maksimum ardıcıl günlərin sayı, uzunluq olaraq bilinir.

Səhm Aralığı ProblemiPin

Səhmlərin uzunluğu probleminin yuxarıdakı görüntüsündə olduğu kimi -

1-ci gün üçün səhm qiyməti 100 - ardıcıl əvvəlki günlərdə daha kiçik bir səhm qiyməti yoxdur, buna görə də span = 1

gün 2, səhm qiyməti 80 - ardıcıl əvvəlki günlərin daha az səhm qiyməti olmadığına görə, span = 1

gün 3, səhm qiyməti 60 - ardıcıl əvvəlki günlərin daha az səhm qiyməti olmadığına görə, span = 1

4. gün, səhm qiyməti 70 - gün 3, daha kiçik birja qiymətinə sahibdir, yəni 60, span = 2

gün 5, səhm qiyməti 60 - ardıcıl əvvəlki günlərin daha az səhm qiyməti olmadığına görə, span = 1

gün 6, səhm qiyməti 75 - gün 3, gün 4, day5, daha kiçik hissə qiymətlərinə sahibdir, yəni 60, 70, 60, buna görə də span = 4

7-ci gün, səhmlərin qiyməti 85 - gün 2, gün 3, gün 4, gün5 və 6-cı günlər daha kiçik hissə qiymətlərinə sahibdir, yəni müvafiq olaraq 80, 60, 70, 60, 75, buna görə span = 6

misal

Giriş-çıxışı anlamaq üçün Fondun Aralığı Probleminin bəzi nümunələrinə baxaq.

Giriş: qiymət = {100, 80, 60, 70, 60, 75, 85}

Çıxış: 7 günün müddəti: 1 1 1 2 1 4 6

Giriş: qiymət = {10, 4, 5, 90, 120, 80}

Çıxış: 6 günlük müddət: 1 1 2 4 5 1

Stack istifadə etmədən

Səhm Span problemi üçün sadəlövh metod

Alqoritm

  1. Başlanğıc və array n günün səhm qiymətini saxlamaq.
  2. Aralığı saxlamaq üçün n ölçülü S başqa bir sıra düzəldin.
  3. 1-dən n-1-ə keçin və S [] indiki indeksindəki dəyəri 1-ə kimi təyin edin. Xarici döngə indeksindəki qiymət qiymətdən çox və ya bərabər olduqda daxili döngəni -1-dən 0-a qədər başlayın. daxili döngə indeksini göstərin və daxili döngənin hər addımında S [] indiki indeksini artırın.
  4. S [] seriyasını çap edin.

Səhm Span Problemi üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std;  
  
void calculateSpan(int price[], int n, int S[]){  
    S[0] = 1;  
  
    for(int i = 1; i < n; i++){  
        S[i] = 1; 
  
        for (int j = i - 1; (j >= 0) &&  
                (price[i] >= price[j]); j--)  
            S[i]++;  
    }  
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 85};  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calculateSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

Səhm Span Problemi üçün Java Proqramı

Span of 7 days : 1 1 1 2 1 4 6

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n * n), burada n - səhm qiymətlərinin verildiyi günlərin sayı.

Köməkçi məkan: O (n), çünki n səhm qiymətlərinə span saxlamaq üçün yer istifadə etdik.

Stack istifadə

Səhm Span problemi üçün səmərəli metod

Alqoritm

  1. N gün səhm qiymətini saxlamaq üçün bir sıra başlayın.
  2. Aralığı və bütöv tip yığını saxlamaq üçün n ölçülü başqa bir S array yaradın.
  3. 1-dən n-1-ə keçin, bu zaman qalaq boş deyil və cari indeksin qiyməti yığının üstündəki qiymətə bərabər olan indeksdəki qiymətdən çox və ya ona bərabərdir, üstünü açın.
  4. S [] indiki indeksini yeniləyin, çünki indiki indeks + 1 yığını boş başqa bir indiki göstəricidir - yığının üstü və indiki indiki yığına daxil edin / əlavə edin.
  5. Döngədən sonra S [] massivini çap edin.

Səhm Span Problemi üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std;  
  
void calSpan(int price[], int n, int S[]){  
    
    stack<int> st; 
    st.push(0); 
  
    S[0] = 1; 
  
    for(int i = 1; i < n; i++){ 
        while ((!st.empty()) && (price[st.top()] <= price[i])){ 
            st.pop(); 
        }
  
        S[i] = (st.empty()) ? (i + 1) : (i - st.top()); 
  
        st.push(i); 
    }   
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 80 };  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

Səhm Span Problemi üçün Java Proqramı

import java.util.Arrays; 
import java.util.Stack; 
  
class spanStock{ 
    
    static void calSpan(int price[], int n, int S[]){ 
        
        Stack<Integer> st = new Stack<>(); 
        st.push(0); 
  
        S[0] = 1; 
  
        for(int i = 1; i < n; i++){ 
  
            while((!st.empty()) && (price[st.peek()] <= price[i])){ 
                st.pop(); 
            }
  
            S[i] = (st.empty()) ? (i + 1) : (i - st.peek()); 
  
            st.push(i); 
        }  
    } 
  
    static void display(int arr[]){ 
        System.out.print("Span of "+arr.length+" days : "); 
        for (int i = 0; i < arr.length; i++)  
            System.out.print(arr[i]+" ");  
    } 
  
    public static void main(String[] args){ 
        
        int price[] = {100, 80, 60, 70, 60, 75, 85}; 
        int n = price.length; 
        int S[] = new int[n]; 
  
        calSpan(price, n, S); 
  
        display(S); 
    } 
}
Span of 7 days : 1 1 1 2 1 4 6

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n - səhm qiymətlərinin verildiyi günlərin sayı.

Köməkçi məkan: O (n), çünki n səhm qiymətlərinə span saxlamaq üçün yer istifadə etdik.

References

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