주어진 합계로 배열에서 삼중 항 찾기

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

정수 배열이 주어지면 다음에서 세 요소의 조합을 찾으십시오. 정렬 그 합계는 주어진 값 X와 같습니다. 여기서 우리가 얻은 첫 번째 조합을 인쇄합니다. 그러한 조합이 없으면 -1을 인쇄하십시오.

입력

N = 5, X = 15

arr [] = {10, 4, 2, 3, 5}

산출 

10, 2, 3

접근법 1

모든 트리플렛을 생성하고 그 합계를 주어진 값과 비교합니다. 아래 알고리즘에는 세 개의 루프가 있습니다.

암호알고리즘

  1. 먼저 입력 배열 정렬
  2. 첫 번째 요소를 arr [i]로 수정합니다. 여기서 i의 범위는 0에서 N-2입니다.
  3. 첫 번째 요소를 고정한 후 두 번째 요소를 arr [j]로 고정합니다. 여기서 j는 i + 1에서 N-1까지입니다.
  4. 두 번째 요소를 고정한 후 세 번째 요소를 arr [k]로 고정합니다. 여기서 k는 j + 1에서 N까지입니다.
  5. 합계, arr [i] + arr [j] + arr [k]를 구합니다.
  6. 삼중 항 합계가 값 X와 같으면 세 요소를 인쇄하고 그렇지 않으면 -1을 인쇄합니다.

실시

주어진 합계로 배열에서 삼중 항을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

주어진 합계를 사용하여 배열에서 삼중 항을 찾기위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if( a[i] + a[j] + a[k] == x)
                    {
                       System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                       i=n;j=n;k=n;
                       temp=1;
                    }
                }
            }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
10 4 2 3 5
10  2  3

복잡성 분석

시간 복잡성

O (n * n * n) 어디에 n 배열에있는 요소의 수입니다. 여기서 Ron XNUMX for 루프를 사용하여 가능한 모든 트리플렛을 확인합니다.

공간 복잡성

O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

접근법 2

암호알고리즘

  1. 이름 종류 입력 배열
  2. 첫 번째 요소를 arr [i]로 수정합니다. 여기서 i의 범위는 0에서 N-2입니다.
  3. 첫 번째 요소를 수정 한 후 다음 두 요소를 찾기 위해 두 포인터와 유사한 변수 (j = i + 1, k = N-1)를 가져 와서 정렬 된 배열에서 합계를 찾는 알고리즘을 탐색합니다.
  4. j가 k보다 작을 때 주어진 인덱스에 요소를 추가합니다. 즉, arr [i] + arr [j] + arr [k] Triplet 합계가 값 X와 같으면 XNUMX 개 요소를 인쇄하고 Triplet 합계가 다음보다 작 으면 XNUMX 개 요소를 인쇄합니다. 값 X, 그런 다음 j 값을 늘리고 그렇지 않으면 k 값을 줄입니다.

실시

주어진 합계로 배열에서 삼중 항을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}

주어진 합계를 사용하여 배열에서 삼중 항을 찾기위한 Java 프로그램

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 x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); //sort the array in ascending order
        int computed_sum;//sum computed at each step
        int temp=0;
        for(int i = 0; i < n - 2; i++) // fix one element and search for other two elements in linear time
        {
          int j = i+1 , k = n-1; // jth index starts from the next element of selected and k always starts at the ending index
          while(j < k)
          {
            computed_sum = a[i] + a[j] + a[k]; // add the elements at the given indices
            if(computed_sum == x)
              {
                System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                j=k;
                temp=1;
              }
            else if(computed_sum < x) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
              j++;
            else if(computed_sum > x)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
              k--;
          }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
1 4 2 3 5
-1

복잡성 분석

시간 복잡성

O (n * n * n) 어디에 n 배열에있는 요소의 수입니다. 여기서 Ron XNUMX for 루프를 사용하여 가능한 모든 트리플렛을 확인합니다.

공간 복잡성

O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조

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