제품 배열 퍼즐

난이도 중급
자주 묻는 질문 수행자 어도비 벽돌 아마존 Apple 아사 BlackRock 블룸버그 게시물에서 ByteDance 드 쇼 이베이 Evernote Expedia Facebook 골드만 삭스 구글 Houzz 인텔 링크드인 리프트 Microsoft 모건 스탠리 (Morgan Stanley) 뉴타 닉스 운영 신탁 페이팔 Paytm Qualtrics 세일즈 포스 SAP ServiceNow Snapchat 스플 렁크 Tableau Twitter 동네 짱 비자, VM웨어 월마트 연구소 Yahoo Yandex 주차
배열 Groupon 리트코드조회수 611

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

제품에서 정렬 퍼즐 문제 우리는 i가 어디에 배열을 구성해야th 요소는 i에있는 요소를 제외하고 주어진 배열에있는 모든 요소의 곱이됩니다.th 위치.

입력 

5

10 3 5 6 2

산출

180 600 360 300 900

제품 배열 퍼즐을 해결하기위한 알고리즘

1 단계 : 벡터 제품을 가져와 제품을 저장하십시오.
a) 벡터 제품으로 초기화

2 단계 : left [] 및 right [] 두 개의 배열을 구성하고 left는 배열의 i 번째 인덱스 왼쪽까지 요소의 곱을 저장합니다. right는 i 번째 인덱스의 오른쪽 요소의 곱을 저장합니다.

ㅏ. left의 첫 번째 요소를 1로 초기화하고 right의 마지막 요소를 1로 초기화합니다.
비. 왼쪽부터 왼쪽 배열의 i-1 번째 요소를 왼쪽 배열의 이전 요소와 곱하여 왼쪽 배열의 i 번째 요소를 업데이트합니다. (왼쪽 [i] = 왼쪽 [i-1] * 배열 [i-1]). 이렇게하여 주어진 배열에서 왼쪽 배열의 이전 인덱스까지 제품을 저장합니다.
씨. 오른쪽에서 오른쪽 배열의 i + 1 번째 요소와 오른쪽 배열의 다음 요소를 곱하여 오른쪽 배열의 i 번째 요소를 업데이트합니다. (오른쪽 [i] = 오른쪽 [i + 1] * 배열 [i + 1]). 이렇게하면 주어진 배열에서 왼쪽 배열의 이전 인덱스까지 제품을 저장합니다.

3 단계 :  현재 요소를 제외한 제품은 왼쪽 및 오른쪽 배열 요소의 곱과 동일합니다.
a) 제품 배열은 product [i] = left [i] * right [i]입니다.

제품 배열 퍼즐 해결을위한 설명

먼저, 처음부터 배열을 순회하고 각 i에 대한 모든 이전 요소의 곱을 저장합니다. 이제 뒤쪽에서 배열을 탐색하고 끝에서 합계를 저장하고 해당 요소 뒤에있는 모든 요소의 곱을 저장합니다.

왼쪽 [] = {10, 30, 150, 900, 1800}

오른쪽 [] = {1800, 180, 60, 12, 2}

이제이 배열을 사용하여 주어진 배열의 모든 요소의 곱을 찾으십시오.th 위치.

제품 [] = {180, 600, 360, 300, 900}

실시

제품 배열 퍼즐을 해결하기위한 C ++ 프로그램

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

제품 배열 퍼즐을 해결하기위한 Java 프로그램

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

복잡성 분석

시간 복잡성

O (N) 여기서 n은 배열에있는 요소의 수입니다. 여기서 우리는 3 번만 횡단하고 제품 배열을 찾습니다.

공간 복잡성

O (N) 요소의 곱을 저장하기 위해 왼쪽 및 오른쪽 배열을 사용하기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »