시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“최대 최소 형태로 주어진 배열 재 배열”문제에서 우리는 정렬 된 정렬 N 개의 요소를 포함합니다. 대체 요소가 ith max 및 ih min이되도록 지정된 정렬 된 양의 정수 배열을 재정렬합니다. 요소 재배 열에 대한 더 나은 이해는 아래를 참조하십시오.
Array [0] = 배열의 최대 값, Array [1] = 배열의 최소값, Array [2] = 배열의 두 번째 최대 값, Array [3] = 배열의 두 번째 최소값, Array [4] = 배열의 세 번째 최대 값 …… 등등.
예
7 1 2 3 4 5 6 7
7 1 6 2 5 3 4
암호알고리즘
- 수정 된 배열을 저장할 보조 더미 배열을 만듭니다.
- 배열의 코너 인덱스로 낮음과 높음을 초기화합니다.
- 대체 최대 및 최소를 복사하려면 변수 X를 저장하고 True를 초기화하십시오.
- X = True이면 최대 값을 복사하고 X = False이면 최소값을 복사합니다.
- 루프를 실행하여 요소를 보조 배열에 복사합니다. 요소를 새 배열에 복사 한 후 X 값을 반대로합니다.
- X가 True이면 끝에서 요소를 복사하고 X가 False이면 뒤로 이동하여 앞쪽에서 요소를 복사하고 앞으로 이동합니다.
- 보조 배열을 주어진 배열에 복사합니다.
- 배열을 인쇄하면 요소가 재 배열됩니다.
실시
주어진 배열을 최대 최소 형태로 재배 열하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
//function to rearrange the given sorted array in maximum minimum form
void RearrangeMaxMin(int array[], int N)
{
int temp[N];//auxilary dummy array with all zeroes
for (int i=0; i<N; i++)
{
temp[i] = 0;
}
int low=0, high=N-1; // corner indices of the array
int X = true; // indication for which element should be copied
//copying elements into the temp array
//according to the given condition
for (int i=0; i<N; i++)
{
if(X)
{
temp[i] = array[high--];
}
else
{
temp[i] = array[low++];
}
X = !X;
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
// main function
int main()
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array\n";
PrintArray(array,N);
RearrangeMaxMin(array,N);
cout << "\nOutput array\n";
PrintArray(array,N);
return 0;
}
Input array 1 2 3 4 5 6 7 8 9 Output array 9 1 8 2 7 3 6 4 5
주어진 배열을 최대 최소 형식으로 재 배열하기위한 Java 프로그램
import java.util.Scanner;
class sum
{
//function to rearrange the given sorted array in maximum minimum form
public static void RearrangeMaxMin(int array[], int N)
{
int temp[] = new int [N];//auxilary dummy array with all zeroes
for (int i=0; i<N; i++)
{
temp[i] = 0;
}
int low=0, high=N-1; // corner indices of the array
int X = 1; // indication for which element should be copied
//copying elements into the temp array
//according to the given condition
for (int i=0; i<N; i++)
{
if(X==1)
{
temp[i] = array[high--];
}
else
{
temp[i] = array[low++];
}
if(X==1)
{
X=0;
}
else
{
X=1;
}
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
System.out.println("Input array");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
RearrangeMaxMin(a,n);
System.out.println("Output array");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
}
5 5 4 3 2 1
Input array 5 4 3 2 1 Output array 1 5 2 4 3
복잡성 분석
시간 복잡성
의 위에) 여기서 n은 주어진 배열에있는 요소의 수입니다. 여기서 우리는 최대 n 번 실행되는 두 개의 포인터 메서드를 사용합니다. 따라서이 경우 시간 복잡도는 선형이라고 말할 수 있습니다.
공간 복잡성
의 위에) 최대 요소와 최소 요소의 형태로 요소를 저장하기 위해 보조 배열을 사용하기 때문입니다.
