Układanka z tablicą produktów

Poziom trudności Średni
Często zadawane pytania Accolita Adobe Amazonka Apple Asana BlackRock Bloomberg ByteDance Cytadela DE Shaw eBay Evernote Expedia Facebook Goldman Sachs Google Houzz Intel LinkedIn lyft Microsoft Morgan Stanley Nutanix działać wyrocznia PayPal Paytm Qualtrics Salesforce SAP ServiceNow Snapchat Splunk Żywy obraz Twitter Uber Visa VMware Laboratoria Walmart Yahoo Yandex
Szyk Groupon LeetKododwiedzajacy 610

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 produkcie szyk zagadka, musimy skonstruować tablicę, w której ith element będzie iloczynem wszystkich elementów w danej tablicy z wyjątkiem elementu w ith pozycji.

Przykład

Wkład 

5

+10 (3) 5 6 2 XNUMX XNUMX +XNUMX (XNUMX) XNUMX XNUMX XNUMX XNUMX XNUMX +XNUMX XNUMX XNUMX XNUMX

Wydajność

+180 (600) 360 300 900 XNUMX XNUMX +XNUMX (XNUMX) XNUMX XNUMX XNUMX XNUMX XNUMX +XNUMX XNUMX XNUMX XNUMX

Algorytm rozwiązywania łamigłówki z tablicą produktów

Krok 1: Weź produkt wektorowy do przechowywania produktów.
a) Zainicjuj go przez produkt wektorowy

Krok 2: Skonstruuj dwie tablice left [] i right [], left przechowuje iloczyn elementów na lewo od i-tego indeksu w tablicy. right przechowuje iloczyn elementów na prawo od i-tego indeksu.

za. Zainicjuj pierwszy element left jako 1 i ostatni element right jako 1.
b. od lewej, zaktualizuj i-te elementy lewej tablicy iloczynem i-1-tego elementu danej tablicy z poprzednim elementem lewej tablicy. (lewa [i] = lewa [i-1] * tablica [i-1]). robiąc to, przechowuje produkt do poprzedniego indeksu w lewej tablicy z podanej tablicy.
do. od prawej, zaktualizuj i-te elementy prawej tablicy iloczynem i + 1-tego elementu danej tablicy z następnym elementem prawej tablicy. (prawy [i] = prawy [i + 1] * tablica [i + 1]). robiąc to, przechowuje produkt do poprzedniego indeksu w lewej tablicy z podanej tablicy.

Krok 3:  Produkt z wyjątkiem obecnego elementu będzie taki sam jak iloczyn lewych i prawych elementów tablic.
a) tablica iloczynu będzie wyglądać następująco: iloczyn [i] = lewy [i] * prawy [i].

Wyjaśnienie rozwiązywania łamigłówki tablicy produktów

Najpierw przejrzyj tablicę od początku i zapisz iloczyn wszystkich poprzednich elementów dla każdego i. Teraz przejdź przez tablicę od tyłu i zapisz sumę od końca i zapisz iloczyn wszystkich elementów po tym elemencie.

lewo [] = {10, 30, 150, 900, 1800}

prawy [] = {1800, 180, 60, 12, 2}

Teraz używając tych tablic znajdź iloczyn wszystkich elementów w danej tablicy z wyjątkiem elementu w ith pozycji.

produkt [] = {180, 600, 360, 300, 900}

Realizacja

Program w C ++ do rozwiązywania łamigłówek z tablicą produktów

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int left[n],right[n];
  vector<int> product;
  left[0] = 1; //initialize the first element as 1
  for(int i=1;i<n;i++)
  {
     left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
  }
  right[n-1]=1;//initialzie the first element as 1
  for(int i=n-2;i>=0;i--)
  {
     right[i]=right[i+1]*arr[i+1]; //store the product till just next index
  } 
  for(int i=0;i<n;i++)
  {
     product.push_back(left[i]*right[i]);
  }
  for(int i=0;i<n;i++)//display the product array
  {
     cout<<product[i]<<"  "; 
  }
  return 0;
}

Program w języku Java do rozwiązywania łamigłówek macierzy produktów

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
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 left[] = new int [n];
        int right[] = new int [n];
        Vector<Integer> product = new Vector<Integer>(); 
        left[0] = 1; //initialize the first element as 1
        for(int i=1;i<n;i++)
        {
           left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
        }
        right[n-1]=1;//initialzie the first element as 1
        for(int i=n-2;i>=0;i--)
        {
           right[i]=right[i+1]*arr[i+1]; //store the product till just next index
        } 
        for(int i=0;i<n;i++)
        {
           product.add(left[i]*right[i]);
        }
        for(int i=0;i<n;i++)//display the product array
        {
           System.out.print(product.get(i)+"  "); 
        }
    }
}
5
10 3 5 6 2
180  600  360  300  900

Analiza złożoności

Złożoność czasowa

Na) gdzie n to liczba elementów obecnych w tablicy. Tutaj przechodzimy tylko 3 razy i znajdujemy tablicę produktów.

Złożoność przestrzeni

Na) ponieważ używamy lewej i prawej tablicy do przechowywania produktów elementów.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »