시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
N 개의 요소를 포함하는 배열을 제공했습니다. 주어진 정렬, 주어진 값보다 작은 합계를 가진 세 쌍둥이의 수를 센다.
예
입력
ㅏ[] = {1, 2, 3, 4, 5, 6, 7, 8}
합계 = 10
산출
7
가능한 트리플렛 : (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5 ), (2,3,4)
입력
a [] = {3, 7, 9, 1, 2, 5, 11, 4}
합계 = 10
산출
6
가능한 트리플렛 : (3,1,2), (3,1,5), (3,1,4), (3,2,4), (1,2,5), (1,2,4 )
접근법 1
암호알고리즘
1. 가능한 모든 트리플렛을 선택하여 3 개의 중첩 루프를 실행합니다.
2. 결과 초기화 = 0.
3. 요소의 합계가 합계보다 작 으면 개수를 늘립니다.
4. 조건을 충족하는 세 쌍의 개수로 결과를 인쇄합니다.
실시
주어진 값보다 작은 합계를 가진 삼중 항 수를위한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
//Main function
int main()
{
int array[] = {3, 7, 9, 1, 2, 5, 11, 4};
int N = sizeof(array)/sizeof(array[0]);
int sum = 10;
int result = 0;
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
for (int i = 0; i < N-2; i++)
{
for (int j = i+1; j < N-1; j++)
{
for (int k = j+1; k < N; k++)
{
if(array[i]+array[j]+array[k] < sum)
{
result++;
}
}
}
}
cout<<"Number of Triplets found = ";
cout<<result;
return 0;
}
Number of Triplets found = 6
주어진 값보다 작은 합계를 가진 삼중 항 수를위한 Java 프로그램
import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int sum = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
int result=0;
for (int i = 0; i < n-2; i++)
{
for (int j = i+1; j < n-1; j++)
{
for (int k = j+1; k < n; k++)
{
if(a[i]+a[j]+a[k] < sum)
{
result++;
}
}
}
}
System.out.print("Number of Triplets found = ");
System.out.println(result);
}
}
5 6 1 2 3 2 1
Number of Triplets found = 5
복잡성 분석
시간 복잡성
O (n * n * n) 여기서 n은 주어진 배열의 크기입니다. 여기에서 모든 트리플렛을 확인하고 조건이 참이면 결과 수를 늘립니다.
공간 복잡성
O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.
접근법 2
암호알고리즘
1. 주어진 배열 정렬, 초기화 결과 = 0
2. i에서 N -2 (N은 배열의 크기)까지 반복하고 array [i]와 삼중 항의 첫 번째 요소를 가져옵니다.
3. 다른 두 요소를 모서리 요소로 초기화합니다. 배열 [i + 1] 및 배열 [N-1]
4. j와 k가 만나서 할 때까지 움직입니다.
- 합계가 주어진 합계보다 크면 마지막 요소의 포인터를 이동합니다. (배열 [N-1]).
- 그렇지 않으면 합계가 주어진 합계보다 작 으면 k -j 개의 가능한 tird 요소가 만족할 수 있으므로 결과에 (kj)를 추가하십시오. 그리고 배열 [i + 1] 포인터를 이동합니다.
5 단계 : 루프를 종료 한 후 결과를 인쇄하십시오.
실시
주어진 값보다 작은 합계를 가진 삼중 항 수를위한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// Main function
int main()
{
int array[] ={1, 2,3,5,6, 3, 2, 5, 7};//input array
int N = sizeof(array)/sizeof(array[0]);//size of the input array(N)
int Sum = 9;//input Sum
int result = 0;//initilizing count of triplets
sort(array,array+N);//sorting the input array
//selecting first element
for(int i = 0; i < N - 2; i++)
{
int j=i+1,k=N-1;//second and third elements as last two elements
while(j<k)
{
// Sum of triplet is greater than or equalto given sum, move to find smaller values
if(array[i] + array[j] + array[k] >= Sum)
{
k--;
}
// Sum of triplet is less than given sum
else
{
//for current i and j there can be k-j elements, move j pointer
result += (k - j);
j++;
}
}
}
cout<<"Number of Triplets found = ";
cout<<result;
}
Number of Triplets found = 14
주어진 값보다 작은 합계를 가진 삼중 항 수를위한 Java 프로그램
import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int sum = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
//First for loop for selecting first element
//Second loop for second element
//Third loop for third element.
//check for triplets satisfing the condition, and increment result
int result=0;
Arrays. sort(a);//sorting the input array
//selecting first element
for(int i = 0; i < n - 2; i++)
{
int j=i+1,k=n-1;//second and third elements as last two elements
while(j<k)
{
// Sum of triplet is greater than or equalto given sum, move to find smaller values
if(a[i] + a[j] + a[k] >= sum)
{
k--;
}
// Sum of triplet is less than given sum
else
{
//for current i and j there can be k-j elements, move j pointer
result += (k - j);
j++;
}
}
}
System.out.print("Number of Triplets found = ");
System.out.println(result);
}
}
9 9 1 2 3 5 6 3 2 5 7
Number of Triplets found = 14
복잡성 분석
시간 복잡성
O (n * n) 여기서 n은 배열에있는 요소의 수입니다. 여기서 우리는 트리플렛의 한 요소를 수정 한 다음 한 요소에 대해 최악의 경우 O (N)을 실행하는 두 개의 포인터 메서드를 사용합니다.
공간 복잡성
O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.
