Maksimum məhsul ilə üçün uzunluğunun artması

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Cisco Citadel Facebook Intuit Über
Geyim RedfinBaxılıb 306

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

“Maksimum məhsul ilə uzunluğun üçünün artması” problemində bir array müsbət tam ədədi. Maksimum məhsul ilə 3 uzunluğunun altını tapın. Nəticə artmaqdadır.

Giriş Formatı

Verilmiş massivin ölçüsünü göstərən tam bir N sayını ehtiva edən ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Maksimum_ məhsul ilə 3 uzunluqlu bir ardıcıllıq varsa və ardıcıllıq artmaqda olarsa, 3 ədədi ehtiva edən ilk və yalnız bir sətir. Əks təqdirdə, -1 yazdırın.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 3
  • -10 ^ 9 <= a [i] <= 10 ^ 9

misal

8
11 12 13 6 7 8 14 15
13 14 15

Explanation:  [13, 14, 15], maksimum məhsul ilə 3 uzunluğunun bir sonrakı hissəsidir.

5
5 4 3 2 1
-1

Explanation:  Sıralanan artan 3 uzunluğunda belə bir ardıcıllıq yoxdur.

Alqoritm

LSL - solda ən böyük element.
LGR - sağdakı ən böyük böyük element.

a. Bütün elementlər üçün solunda ən böyük kiçik elementi (LSL) və sağda ən böyük elementi (LGR) tapmaq lazımdır.

b. İki iç içə döngə işlədirik. Biri LGR və LSL tapmaqdır.

c. LGR, LSL və sayının məhsulunun maksimumu, maksimum məhsul ilə 3 uzunluğunun ən böyük artan ardıcıllığı olacaqdır.

Həyata keçirilməsi

Maksimum məhsulla üçün uzunluğunun nəticəsini artırmaq üçün C ++ proqramı

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


int FindLSL(int array[], int index, int n)
{
    int maxValue = -1, maxIndex = -1;
    for (int i = 0; i < index; i++)
    {
        if ((array[i] < array[index]) && (array[i] > maxValue))
        {
            maxValue = array[i];
            maxIndex =i;
        }
    }
    
    return maxIndex;
}

int FindLGR(int array[], int index, int n)
{
    int maxValue = -1, maxIndex = -1;
    for (int i = index+1; i < n; i++)
    {
        if ((array[i] > array[index]) && (array[i] > maxValue))
        {
            maxValue = array[i];
            maxIndex =i;
        }
    }
    
    return maxIndex;
}

void FindSequence(int array[], int sequence[3], int n)
{
    int maxProduct = 0;
    for(int i = 0; i < n ; i++)
    {
        int leftLargestIndex = FindLSL(array, i,n);
        int leftLargestValue = leftLargestIndex == -1 ? 0:array[leftLargestIndex];
        int rightLargestIndex = FindLGR(array, i,n);
        int rightLargestValue = rightLargestIndex == -1 ? 0:array[rightLargestIndex];
        if (leftLargestValue*array[i]*rightLargestValue > maxProduct)
        {
            maxProduct = array[leftLargestIndex]*array[i]*array[rightLargestIndex];
            sequence[0] = leftLargestValue;
            sequence[1] = array[i];
            sequence[2] = rightLargestValue;
        }
    }
}

int main()
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sequence[3];
    for(int i=0;i<3;i++)
    {
        sequence[i]=-1000000;
    }
    FindSequence(a,sequence,n);
    int flag=0;
    for(int i=0;i<3;i++)
    {
        if(sequence[i]==-1000000)
        {
            flag=1;
        }
    }
    if(flag==1)
    {
        cout<<-1<<endl;
    }
    else{
    for (int i = 0; i < 3; i++)
    {
        cout<<sequence[i]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

Maksimum məhsulla üçün uzunluğunun nəticəsini artırmaq üçün Java proqramı

import java.util.Random;
import java.util.Scanner;
class sum
{
    public static int FindLSL(int array[], int index, int n)
    {
        int maxValue = -1, maxIndex = -1;
        for (int i = 0; i < index; i++)
        {
            if ((array[i] < array[index]) && (array[i] > maxValue))
            {
                maxValue = array[i];
                maxIndex =i;
            }
        }

        return maxIndex;
    }

    public static int FindLGR(int array[], int index, int n)
    {
        int maxValue = -1, maxIndex = -1;
        for (int i = index+1; i < n; i++)
        {
            if ((array[i] > array[index]) && (array[i] > maxValue))
            {
                maxValue = array[i];
                maxIndex =i;
            }
        }

        return maxIndex;
    }

    public static void FindSequence(int array[], int sequence[], int n)
    {
        int maxProduct = 0;
        for(int i = 0; i < n ; i++)
        {
            int leftLargestIndex = FindLSL(array, i,n);
            int leftLargestValue = leftLargestIndex == -1 ? 0:array[leftLargestIndex];
            int rightLargestIndex = FindLGR(array, i,n);
            int rightLargestValue = rightLargestIndex == -1 ? 0:array[rightLargestIndex];
            if (leftLargestValue*array[i]*rightLargestValue > maxProduct)
            {
                maxProduct = array[leftLargestIndex]*array[i]*array[rightLargestIndex];
                sequence[0] = leftLargestValue;
                sequence[1] = array[i];
                sequence[2] = rightLargestValue;
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sequence[] = new int[3];
        for(int i=0;i<3;i++)
        {
            sequence[i]= -1000000;
        }
        FindSequence(a,sequence,n);
        int flag=0;
        for(int i=0;i<3;i++)
        {
            if(sequence[i]==-1000000)
            {
                flag=1;
            }
        }
        if(flag==1)
        {
            System.out.println(-1);
        }
        else{
        for(int i=0;i<3;i++)
        {
            System.out.print(sequence[i]+" ");
        }
        System.out.println();
        }
    }
}
5
72 24 12 -10 -16
-1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) hara n verilmiş massivin ölçüsüdür. Burada massivin hər mövqeyində (ith) solda ən kiçik, sağda ən böyük elementi tapırıq, bunu tapmaq üçün xətti vaxt tələb olunur.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

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