Üç yığının mümkün maksimum bərabər məbləğini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fanatics Fourkites
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.

Stack3 [], stack1 [] və stack2 [] təmsil edən 3 sıra verilmişdir yığışdırır və bunların başlanğıc indeksi seriallar üstləri kimi qəbul edilir. Üç yığının hamısında mümkün olan ümumi maksimum cəmi tapın, yəni stack1, stack2 və stack3 elementlərinin cəmi bərabərdir. Ortaq maksimum cəmi tapmaq üçün hər bir massivdə üst hissənin götürülməsinə icazə verilir.

Üç yığının mümkün maksimum bərabər məbləğini tapınPin

misal

Input 

stack1 [] = {3, 2, 1, 1, 1}
stack2 [] = {4, 3, 2}
stack3 [] = {1, 1, 4, 1}

Çıxış:   5

Input 

stack1 [] = {3, 10}
stack2 [] = {4, 5}
stack3 [] = {2, 1}

Çıxış:   0

Alqoritm

İndi Üç yığının mümkün maksimum bərabər cəmini tapın problem ifadəsini bilirik. Beləliklə, indi tətbiqi üçün istifadə olunan alqoritmi tez bir zamanda oxuyun.

  1. Yığanları təmsil edən 3 massivi işə salın.
  2. Hər üç massivin elementlərinin cəmini ayrıca hesablayın. Bütün massivlərin top yəni birinci elementini 3 olaraq saxlamaq üçün 0 dəyişəni elan edin.
  3. Bir sıra yuxarı hissəsinin ölçüsünə bərabər olub olmadığını yoxlamaq üçün 0 qaytarın.
  4. Başqa bir halda, bütün massivlərin fərdi cəmi bərabərdirsə, cəmi qaytarın.
  5. Birinci cərgənin cəmi ikinci sıra və üçüncü sıra fərdi cəmindən böyük və ya ona bərabərdirsə, birinci massivin yuxarı elementini cəmindən çıxarın və birinci massivin yuxarı dəyişənini artırın.
  6. Başqa bir halda, ikinci massivin cəmi birinci sıra və üçüncü sətrin fərdi cəmindən çox və ya ona bərabərdirsə, ikinci sətrin yuxarı elementini cəmindən çıxarın və ikinci sətrin yuxarı dəyişənini artırın.
  7. Başqa bir halda, üçüncü massivin cəmi birinci sıra ilə ikinci sətrin fərdi cəmindən çox və ya ona bərabərdirsə, üçüncü sətrin yuxarı elementini cəmindən çıxarın və üçüncü sətrin yuxarı dəyişənini artırın.

Üç yığının mümkün maksimum bərabər məbləğini tapmaq üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 

int maxSum(int stack1[], int stack2[], int stack3[], int n1, int n2, int n3){ 
    int sum1 = 0, sum2 = 0, sum3 = 0; 
    
    for(int i=0; i < n1; i++){ 
        sum1 += stack1[i]; 
    }      

    for(int i=0; i < n2; i++){ 
        sum2 += stack2[i]; 
    } 
    
    for(int i=0; i < n3; i++){ 
        sum3 += stack3[i]; 
    }
    
    int top1 =0, top2 = 0, top3 = 0;
    
    while(1){ 
        if((top1 == n1) || (top2 == n2) || (top3 == n3)){ 
            return 0; 
        }
        
        if((sum1 == sum2) && (sum2 == sum3)){ 
            return sum1; 
        }
        
        if((sum1 >= sum2) && (sum1 >= sum3)){ 
            sum1 -= stack1[top1++]; 
        }
        
        else if((sum2 >= sum3) && (sum2 >= sum3)){ 
            sum2 -= stack2[top2++]; 
        }
        
        else if(sum3 >= sum2 && sum3 >= sum1){ 
            sum3 -= stack3[top3++]; 
        }
    } 
} 
int main(){

    int stack1[] = {3, 2, 1, 1, 1}; 
    int stack2[] = {4, 3, 2}; 
    int stack3[] = {1, 1, 4, 1}; 
    
    int n1 = sizeof(stack1)/sizeof(stack1[0]); 
    int n2 = sizeof(stack2)/sizeof(stack2[0]); 
    int n3 = sizeof(stack3)/sizeof(stack3[0]); 
    
    cout << maxSum(stack1, stack2, stack3, n1, n2, n3) << endl; 
    
    return 0; 
}
5

Üç yığının mümkün maksimum bərabər məbləğini tapmaq üçün Java Proqramı

class MaxPossibleSum{ 

    public static int maxSum(int stack1[], int stack2[], int stack3[], int n1, int n2, int n3){ 
        int sum1 = 0, sum2 = 0, sum3 = 0; 
        
        for(int i=0; i < n1; i++){ 
            sum1 += stack1[i]; 
        } 
        
        for(int i=0; i < n2; i++){ 
            sum2 += stack2[i]; 
        }
        
        for(int i=0; i < n3; i++){ 
            sum3 += stack3[i]; 
        }
        
        int top1 =0, top2 = 0, top3 = 0; 
        int ans = 0; 
        
        while (true){ 
        
            if((top1 == n1) || (top2 == n2) || (top3 == n3)){ 
                return 0; 
            }
            
            if((sum1 == sum2) && (sum2 == sum3)){ 
                return sum1; 
            }
            
            if((sum1 >= sum2) && (sum1 >= sum3)){ 
                sum1 -= stack1[top1++]; 
            }
            
            else if((sum2 >= sum3) && (sum2 >= sum3)){ 
                sum2 -= stack2[top2++]; 
            }
            
            else if((sum3 >= sum2) && (sum3 >= sum1)){ 
                sum3 -= stack3[top3++]; 
            }
        } 
    } 
    
    public static void main(String[] args){
        int stack1[] = {3, 2, 1, 1, 1}; 
        int stack2[] = {4, 3, 2}; 
        int stack3[] = {1, 1, 4, 1}; 
        
        int n1 = stack1.length; 
        int n2 = stack2.length; 
        int n3 = stack3.length; 
        
        System.out.println(maxSum(stack1, stack2, stack3, n1, n2, n3)); 
    } 
}
5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n1 + n2 + n3) burada n1, n2 və n3 sırasıyla stack1, stack2 və stack3 massivlərindəki elementlərin sayıdır.

Köməkçi məkan: O (1) sabit məkandan istifadə etdiyimiz üçün.

References

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