시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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) 요소의 곱을 저장하기 위해 왼쪽 및 오른쪽 배열을 사용하기 때문입니다.
