Məhsul Array Puzzle

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Çiy kərpic Amazon alma Asana BlackRock Bloomberg ByteDance Citadel DE Şou eBay Evernote Expedia Facebook Goldman Sachs google Houzz Intel LinkedIn lyft microsoft Morgan Stanley Nutanix Opera Kahin PayPal Paytm Kvalifikasiya Salesforce SAP XidmətNow Snapchat Boşalmaq masa cuqquldamaq Über Viza VMware Walmart Laboratoriyaları Yahoo Yandex
Geyim Groupon LeetCodeBaxılıb 611

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

Bir məhsulda array tapmaca problemi olduğu bir sıra qurmamız lazımdırth element i-dəki element xaricində verilən massivdəki bütün elementlərin məhsulu olacaqdırth mövqe.

misal

Input 

5

10 3 5 6 2

Buraxılış

180 600 360 300 900

Məhsul Array Bulmacasını həll etmək üçün alqoritm

1 Adım: Məhsulları saxlamaq üçün bir vektor məhsulu götürün.
a) Vektor məhsulu ilə başlayın

2 Adım: Solda [] və sağda [] iki sıra düzəldin, solda elementlərin məhsulunu ith indeksinin solunda massivdə saxlayır. sağ elementlərin məhsulunu ith indeksinin sağında saxlayır.

a. Solun ilk elementini 1, sağın son elementini 1 olaraq başlayın.
b. soldan, ith elementlərini sol massivin əvvəlki elementi ilə verilmiş massivin i-1 elementinin məhsulu ilə yeniləyin. (sol [i] = sol [i-1] * sıra [i-1]). bunu etməklə, məhsulu verilmiş massivdən əvvəlki indeksə qədər sol dizidə saxlayır.
c. sağdan, sağ massivin ith elementlərini verilmiş massivin i + 1-ci elementinin məhsulu ilə sağ massivin növbəti elementi ilə yeniləyin. (sağ [i] = sağ [i + 1] * sıra [i + 1]). bunu etməklə, məhsulu verilmiş massivdən əvvəlki indeksə qədər sol dizidə saxlayır.

3 Adım:  İndiki element xaricindəki məhsul, sol və sağ massiv elementlərinin məhsulu ilə eyni olacaqdır.
a) məhsul seriyası olacaq, məhsul [i] = sol [i] * sağ [i].

Məhsul Array Bulmacasının həlli üçün izah

Əvvəlcə dizini əvvəldən keçin və əvvəlki elementlərin məhsulunu hər i üçün saxlayın. İndi serialı arxadan keçin və cəmi sondan saxlayın və həmin elementdən sonra bütün elementlərin məhsulunu saxlayın.

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

sağ [] = {1800, 180, 60, 12, 2}

İndi bu massivdən istifadə edərək, i-dəki element xaricində verilmiş massivdəki bütün elementlərin məhsulunu tapınth mövqe.

məhsul [] = {180, 600, 360, 300, 900}

Həyata keçirilməsi

Məhsul Array Bulmacasını həll etmək üçün C ++ proqramı

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

Məhsul Array Bulmacasını həll etmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) burada n - massivdə mövcud olan elementlərin sayı. Burada yalnız 3 dəfə keçirik və məhsul seriyasını tapırıq.

Kosmik Mürəkkəblik

O (n) çünki elementlərin məhsullarını saxlamaq üçün sol və sağ massivlərdən istifadə edirik.

References

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