시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
배열이 있다고 가정합니다. 정수. 여기서 "0"은 입력으로 간주되는 숫자가 아닙니다. 여기에 유효한 입력이 아닙니다. "첫 번째 요소를 두 배로하고 0을 끝으로 이동"문제는 0 이외의 숫자가 발견되고 그 다음 숫자가 동일한 숫자 인 경우 배열을 재 배열하도록 요청한 다음 숫자를 두 배로 표시하고 다음 숫자는 XNUMX입니다. 마지막으로 끝에있는 모든 XNUMX을 누릅니다.
예
arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0
설명 : 3은 연속적으로 발생하는 숫자이므로 먼저 3을 두 배로 만들어 6으로 만들고 다음 3을 0으로 표시합니다. 또한 모든 XNUMX은 last.x로 이동되었습니다.
첫 번째 요소를 두 배로 늘리고 XNUMX을 끝까지 이동하는 알고리즘
1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
1. If true, then make the current value twice of the self.
2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
1. Check if arr[i] != 0.
1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
1. Arr[count]=0 and do count++.
5. Print the array.
설명
주어진 방식으로 재정렬 할 배열이 주어집니다. 현재 번호가 다음 번호와 같으면 다음 번호를 변경하도록 요청했습니다. 변화는 현재 숫자를 두 배로 늘려야한다는 것입니다. 그리고 주어진 조건이 만족되면 다음 숫자를 0으로 표시하십시오. 이 수정 후에는 우리가 만들었거나 이미 배열에있는 배열의 마지막에있는 모든 XNUMX을 이동해야합니다. 그런 다음 출력이 반환되어야합니다.
0에서 n – 1까지 배열을 탐색합니다. 각 값이 0이 아닌지 확인합니다. 0의 값을 변경할 수 없기 때문입니다. 그리고 현재 요소가 arr [i] = = arr [i + 1]로 다음 요소와 같은지 확인합니다. 현재 번호의 다음 번호를 검색하기 때문에 n-1을 마지막 순회 지점으로 사용했습니다. 따라서 검색 할 마지막 요소로 n을 찾으면 null 포인터 예외가 발생합니다. 주어진 조건이 충족되면 현재 요소를 선택하고 현재 값의 두 배로 다음 값을 0으로 업데이트합니다. 배열의 모든 값에 대해이 작업을 수행해야합니다.
이제 모든 값을 0으로 마지막으로 이동하십시오. 이를 위해 배열을 다시 탐색하고 값이 같지 않은지 확인한 다음 왼쪽으로 이동합니다. 모든 값을 왼쪽으로 이동 한 후 마지막으로 이동 한 값의 인덱스를 갖게됩니다. 루프를 반복하고 그 카운트에서 n 값까지 모든 값을 0으로 업데이트합니다. 마지막으로 배열을 인쇄합니다.
암호
첫 번째 요소를 두 배로 늘리고 XNUMX을 이동하여 문제를 끝내기위한 C ++ 코드
#include<iostream>
using namespace std;
void shiftZeroAtLast(int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++)
if (arr[i] != 0)
arr[count++] = arr[i];
while (count < n)
arr[count++] = 0;
}
void arrayModification(int arr[], int n)
{
if (n == 1)
return;
for (int i = 0; i < n - 1; i++)
{
if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
{
arr[i] = 2 * arr[i];
arr[i + 1] = 0;
i++;
}
}
shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {3,3,5,0,1,0,0,1,0};
int n = sizeof(arr) / sizeof(arr[0]);
arrayModification(arr, n);
cout << "Modified array: ";
printArray(arr, n);
return 0;
}
Modified array: 6 5 1 1 0 0 0 0 0
첫 번째 요소를 두 배로 늘리고 XNUMX을 이동하여 문제를 끝내기위한 Java 코드
class arrayRearrange
{
public static void shiftZeroAtLast(int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++)
if (arr[i] != 0)
arr[count++] = arr[i];
while (count < n)
arr[count++] = 0;
}
public static void arrayModification(int arr[], int n)
{
if (n == 1)
return;
for (int i = 0; i < n - 1; i++)
{
if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
{
arr[i] = 2 * arr[i];
arr[i + 1] = 0;
i++;
}
}
shiftZeroAtLast(arr, n);
}
public static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int arr[] = {3,3,5,0,1,0,0,1,0};
int n = arr.length;
arrayModification(arr, n);
System.out.print("Modified array: ");
printArray(arr, n);
}
}
Modified array: 6 5 1 1 0 0 0 0 0
복잡성 분석
시간 복잡성
의 위에) 어디에 "엔" 배열의 요소 수입니다. 우리는 단순히 배열을 두 번 탐색하여 알고리즘이 선형 시간으로 실행되도록했습니다.
공간 복잡성
알고리즘에는 O (1) 추가 공간이 있지만 프로그램은 입력을 저장하는 데 O (N) 총 공간을 사용합니다.
