Mnożenie poprzedniego i następnego

Poziom trudności Łatwo
Często zadawane pytania Accenture Accolita Adobe Zestaw faktów UHG Optum
Szykodwiedzajacy 577

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

Mnożenie poprzedniego i następnego: w danym szyk zamień każdy element na iloczyn kolejnych i poprzednich elementów do niego. I dla pierwszego elementu (a [0]) musimy go zastąpić iloczynem next i siebie, dla ostatniego elementu (a [n-1]) musimy zastąpić go iloczynem poprzedniego i siebie).

Przykład

Wkład

9

4 8 6 9 12 2 43 2 1

Wydajność

32 24 72 72 18 516 4 43 2

Algorytm mnożenia poprzedniego i następnego

Krok 1: Utwórz zmienną do przechowywania poprzedniego elementu tablicy. przechowujemy to w taki sposób, aby nie zajmowało dodatkowego miejsca.
a) Pierwszy element będzie iloczynem pierwszego i drugiego.
b) Kolejne elementy będą iloczynem poprzedniego i następnego.

Krok 2: Utwórz tymczasową zmienną zastępczą, aby przechowywać poprzednią. po zapisaniu poprzedniego w temp, zaktualizuj poprzedni o aktualny element. po zapisaniu aktualnego w poprzednim, zaktualizuj aktualny element mnożąc temp i następny element tablicy.
a) aktualizujemy poprzedni element przed aktualizacją bieżącego, więc przechowujemy wartość w temp, aby nie stracić jej wartości.
b) aktualizujemy poprzedni o aktualny element, ponieważ dla następnego elementu aktualny jest poprzedni.

Krok 3: Ostatni element będzie iloczynem ostatniego i poprzedniego.

Krok 4: wypisuje tablicę, aby zobaczyć, czy jest aktualizowana, czy nie.

Realizacja

Program w C ++ do mnożenia poprzedniego i następnego

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int prev=a[0],temp; // previous element to be stored so that no extra space is used.
  a[0]=a[0]*a[1];
  cout<<a[0]<<"  ";
  for(int i=1;i<n-1;i++)
  {
    temp=prev;
    prev=a[i];//set previous to this element
    a[i]=a[i+1]*temp; // multiply prev and forward element
    cout<<a[i]<<"  ";
  }
  a[n-1]=a[n-1]*prev;
  cout<<a[n-1];
  return 0;
}

Program Java do mnożenia poprzedniego i następnego

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int prev=arr[0],temp; // previous element to be stored so that no extra space is used.
        arr[0]=arr[0]*arr[1];
        System.out.print(arr[0]+"  ");
        for(int i=1;i<n-1;i++)
        {
          temp=prev;
          prev=arr[i];//set previous to this element
          arr[i]=arr[i+1]*temp; // multiply prev and forward element
          System.out.print(arr[i]+"  ");
        }
        arr[n-1]=arr[n-1]*prev;
        System.out.println(arr[n-1]);
    }
}
5
1 2 3 4 5
2  3  8  15  20

Analiza złożoności mnożenia poprzedniego i następnego

Złożoność czasowa

Na) gdzie n jest długością podanej tablicy. Tutaj po prostu iterujemy przez podaną tablicę i obliczamy nasz wynik, który prowadzi nas do liniowej złożoności czasowej.

Złożoność przestrzeni

O (1) ponieważ używamy tylko kilku zmiennych do przechowywania poprzedniej wartości i odpowiedzi dla każdego indeksu.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »