시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"정렬 된 배열의 발생 수 계산"문제에서 정렬 된 정렬. X의 정렬 된 배열에서 발생 횟수 또는 빈도를 계산합니다. 여기서 X는 정수입니다.
예
입력
13
1 2 2 2 2 3 3 3 4 4 4 5 5
3
산출
3
정렬 된 배열에서 발생 횟수에 대한 접근 방식 1
1. 수정 된 이진 검색을 수행하여
2. 다음과 같이 X의 첫 번째 발생을 찾으십시오.
- 배열의 중간 요소가 X와 같은지 확인하십시오.
- 같거나 더 큰 요소가 중간에 있으면 파티션을 시작에서 중간 -1로 줄입니다. 배열 중간의 왼쪽에 첫 번째 발생이있을 것입니다.
- 중간 요소가 더 작 으면 배열이 정렬 될 때 중간 요소의 오른쪽을 확인합니다.
- 첫 번째 발생을 반환합니다.
3. 이제 유사하게 다음을 수행하여 배열에서 X의 마지막 발생을 찾습니다.
- 배열의 중간 요소가 X와 같은지 확인하십시오.
- 같거나 더 작은 요소가 중간에 있으면 파티션을 mid + 1에서 high로 늘립니다. 배열 중간의 오른쪽에 마지막 발생이있을 것입니다.
- 배열의 왼쪽에서 Else 검색
- 마지막 발생을 반환
4. 이제 발생 횟수는 단순히 마지막 발생 – 첫 번째 발생 +1입니다.
실시
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int first = INT_MAX;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found then check the left part for further occurence
{
if(mid < first)
first = mid;
high = mid-1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return first;
}
int last_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int last = INT_MIN;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found check in right subpart for last occurence
{
if(mid > last)
last = mid;
low = mid+1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return last;
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
int last = last_occurence(a,n,X);
if(last != INT_MIN)
count += last;
int first = first_occurence(a,n,X);
if(first != INT_MAX)
count -= first;
cout<<last-first+1<<endl;
return 0;
}
자바 프로그램
import static java.lang.Math.min;
import java.util.Scanner;
class sum
{
public static int first_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int first = 10000000;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found then check the left part for further occurence
{
if(mid < first)
first = mid;
high = mid-1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return first;
}
public static int last_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int last = -1;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found check in right subpart for last occurence
{
if(mid > last)
last = mid;
low = mid+1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return last;
}
public static int abs(int x)
{
if(x<0)
x=x*-1;
return x;
}
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 X = sr.nextInt(); // number whose count is to be found out
int count = 0; //initially its count is zero
int last = last_occurence(arr,n,X);
if(last != -1)
count += last;
int first = first_occurence(arr,n,X);
if(first != 10000000)
count -= first;
System.out.println(last-first+1);
}
}
8 1 1 2 2 2 3 4 5 2
3
정렬 된 배열의 발생 횟수에 대한 복잡성 분석
시간 복잡성 – O (logN) 여기서 N은 배열의 크기입니다. 여기서 우리는 logN 시간 복잡성을 유도하는 이진 검색을 사용합니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.
정렬 된 배열에서 발생 횟수에 대한 접근 방식 2
- 알고리즘 1과 동일한 접근 방식을 수행하지만 upper_bound () 및 lower_bound 함수를 사용합니다.
- upper_bound ()를 사용하여 마지막 발생을 계산하고 lower_bound () 함수를 통해 첫 번째 발생을 계산합니다.
- 발생 횟수는 단순히 upper_bound ()로 얻은 인덱스입니다.
- 하한().
Low_bound (), Upper_bound는 표준 템플릿 라이브러리 (STL) 함수입니다.
실시
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
count = upper_bound(a,a+n,X) - lower_bound(a,a+n,X);
cout<<count;
return 0;
}
8 1 1 2 2 2 3 4 5 4
1
정렬 된 배열의 발생 횟수에 대한 복잡성 분석
시간 복잡성 – O (logN) 여기서 N은 배열의 크기입니다. 여기서 우리는 logN 시간 복잡도가있는 inbuild STL 함수를 사용합니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.
정렬 된 배열에서 발생 횟수에 대한 접근 방식 3
- 간단히 루프를 실행하십시오.
- X와 같은 요소를 얻으면 개수를 늘리기 시작합니다.
- X가 카운트를 증가시키는 것을 볼 때까지 X와 다른 숫자를 얻는 즉시 얻은 카운트를 정렬 된 배열로 표시합니다.
설명
배열의 처음부터 끝까지 하나의 루프를 실행하고 x == a [i]인지 확인한 다음 개수를 늘립니다. 여기에 예를 들어 보겠습니다. a [] = {1, 2, 2, 2, 3, 4} 및 x = 2이면 x의 개수는 3입니다. 따라서 최종 답은 3입니다.
실시
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
for(int i=0;i<n;i++)
if(a[i]==X)
count++;
cout<<count;
return 0;
}
자바 프로그램
import static java.lang.Math.min;
import java.util.Scanner;
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 X = sr.nextInt(); // number whose count is to be found out
int count = 0; //initially its count is zero
for(int i=0;i<n;i++)
if(arr[i]==X)
count++;
System.out.println(count);
}
}
8 1 1 2 2 2 3 4 5 1
2
정렬 된 배열의 발생 횟수에 대한 복잡성 분석
시간 복잡성 – O (N) 전체 배열을 횡단하고 x의 주파수를 계산하기 때문입니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.
