Zwiększenie kolejności długości o trzy z maksymalnym produktem

Poziom trudności Łatwo
Często zadawane pytania Amazonka Apple Cisco Cytadela Facebook Intuit Uber
Szyk Redfinodwiedzajacy 306

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu „Zwiększanie kolejności długości trzy z maksymalnym iloczynem” daliśmy plik szyk dodatnich liczb całkowitych. Znajdź podciąg o długości 3 z maksymalnym produktem. Kolejność powinna rosnąć.

Format wejściowy

Pierwszy i jedyny wiersz zawierający liczbę całkowitą N, oznaczającą rozmiar danej tablicy.

Drugi wiersz zawierający N liczb całkowitych oddzielonych spacjami.

Format wyjściowy

Pierwszy i jedyny wiersz zawierający 3 liczby całkowite, jeśli istnieje podciąg o długości 3 z wartością max_product i podciągiem jest w porządku rosnącym. W przeciwnym razie wypisz -1.

ograniczenia

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

Przykład

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

Wyjaśnienie:  [13, 14, 15] to podciąg o długości 3 z maksymalnym iloczynem.

5
5 4 3 2 1
-1

Wyjaśnienie:  Nie ma takiego podciągu o długości 3, który rośnie w kolejności.

Algorytm

LSL - największy najmniejszy element po lewej stronie.
LGR - największy większy element po prawej stronie.

a. Dla wszystkich elementów musimy znaleźć największy mniejszy element (LSL) po lewej stronie i największy większy element po prawej (LGR).

b. Uruchamiamy dwie zagnieżdżone pętle. Jednym z nich jest znalezienie LGR i LSL.

c. Maksymalny iloczyn LGR, LSL i liczby będzie największym rosnącym ciągiem o długości 3 z maksymalnym iloczynem.

Realizacja

Program w C ++ zwiększający kolejność długości trzy z maksymalnym produktem

#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;
}

Program Java do zwiększania kolejności długości trzy z maksymalnym produktem

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

Analiza złożoności

Złożoność czasowa

O (n ^ 2) gdzie n jest rozmiarem podanej tablicy. Tutaj znajdujemy największy najmniejszy element po lewej stronie, największy większy element po prawej stronie w każdej pozycji (i-tej) tablicy, których ustalenie wymaga czasu liniowego.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Wywiady dotyczące projektowania systemu pękania
Translate »