합이 주어진 값보다 작은 삼중 항 수

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 시트릭스 문틀 이베이 Facebook 골드만 삭스 구글 훌루 IBM 인포시스 수학공부 Microsoft 신탁 페이팔 Qualtrics 삼성 ServiceNow 스플 렁크 사각형. 텐센트 테슬라 동네 짱 비자, VM웨어 월마트 연구소 Yahoo 조호 (Zoho)
아카 마이 배열 Groupon 출소자 두 포인터 두 포인터 작동 응용조회수 712

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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가 만나서 할 때까지 움직입니다.

  1. 합계가 주어진 합계보다 크면 마지막 요소의 포인터를 이동합니다. (배열 [N-1]).
  2. 그렇지 않으면 합계가 주어진 합계보다 작 으면 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) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »