주어진 차이가있는 모든 쌍 찾기

난이도 쉽게
자주 묻는 질문 아마존 블룸버그 게시물에서 시트릭스 Expedia 골드만 삭스 Microsoft 엔비디아 신탁 세일즈 포스 Twilio Twitter 비자, VM웨어
배열 이진 검색 정렬조회수 229

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

문제 정책

우리는 정렬 다른 요소를 포함하거나 배열에 반복되는 요소가 없습니다. 주어진 차이를 가진 모든 쌍을 찾으십시오. 주어진 다른 쌍이 없으면 인쇄하십시오. "주어진 다른 쌍 없음".

입력

10 20

90 70 20 80 50 25 35 15 100 150

산출

90 70

70 50

80 100

35 15 (차이가 20 인 요소 쌍이 인쇄 됨)

주어진 차이가있는 모든 쌍 찾기에 대한 접근 방식 1

배열에서 한 요소를 선택하는 두 개의 루프를 실행합니다. 인덱스 0부터 시작하여 주어진 차이를 가진 쌍을 얻기 위해 배열을 기대합니다.

a) 요소를 찾으면 인쇄하십시오.
b) 다른 인쇄, 찾을 수 없습니다.

실시

주어진 차이가있는 모든 쌍을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int flag=0;
  for(int i=0;i<n;i++)//select an element
  {
    for(int j=i+1;j<n;j++) // look forward in the array
        if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
        {
          cout<<a[i]<<"  "<<a[j]<<endl;
          flag=1;
        }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

주어진 차이가있는 모든 쌍을 찾기위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int flag=0;
        for(int i=0;i<n;i++)//select an element
        {
          for(int j=i+1;j<n;j++) // look forward in the array
              if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
              {
                System.out.println(a[i]+"  "+a[j]);
                flag=1;
              }
        }
        if(flag==0)
        System.out.println("No pair with given different");
    }
}
10 20
90 70 20 80 50 25 35 15 100 150
90  70
70  50
80  100
35  15

복잡성 분석

시간 복잡성

O (N * N) 여기서 N은 주어진 배열의 크기입니다. 두 개의 for 루프를 실행하여 각 쌍을 확인하기 만하면됩니다.

공간 복잡성

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

주어진 차이가있는 모든 쌍 찾기에 대한 접근 방식 2

1 단계 : 먼저 주어진 배열을 정렬합니다. O (NlogN)이 필요합니다.

2 단계 : 첫 번째 알고리즘과 같은 방식으로 첫 번째 요소에서 시작하는 모든 요소에 대해 일치하는 쌍을 찾습니다.

i) 여기서 우리는 이진 검색을 사용하여 요소를 찾습니다.
ii) 요소 a와 주어진 차이 n에 대해 우리는 a + n을 검색합니다.

입력

10 20

90 70 20 80 50 25 35 15 100 150

차이가 20 인 모든 요소 쌍 찾기

입력 배열에 알고리즘 적용,

단계별 작업

  1. 배열 정렬, 정렬 된 배열 : 15 20 25 35 50 70 80 90
  2. a = 15, 차이 (n) = 20이므로 a + n = 35, binary_search (35, 입력 배열) = True입니다. 인쇄 15 35. 앞으로 이동
  3. a = 20, 차이 (n) = 20이므로 a + n = 40, binary_search (40, 입력 배열) = False입니다. 앞으로 이동
  4. a = 25, 차이 (n) = 20이므로 a + n = 45, binary_search (45, 입력 배열) = False입니다. 앞으로 이동
  5. a = 35, 차이 (n) = 20이므로 a + n = 55, binary_search (55, 입력 배열) = False입니다. 앞으로 이동
  6. a = 50, 차이 (n) = 20이므로 a + n = 70, binary_search (70, 입력 배열) = True입니다. 인쇄 50 70. 앞으로 이동
  7. a = 70, 차이 (n) = 20이므로 a + n = 90, binary_search (90, 입력 배열) = True입니다. 인쇄 70 90. 앞으로 이동
  8. a = 80, 차이 (n) = 20이므로 a + n = 100, binary_search (100, 입력 배열) = True입니다. 인쇄 80 100. 앞으로 이동
  9. a = 90, 차이 (n) = 20이므로 a + n = 110, binary_search (110, 입력 배열) = False입니다. 앞으로 이동
  10. a = 100, 차이 (n) = 20이므로 a + n = 120, binary_search (120, 입력 배열) = False입니다. 루프 끝.

실시

주어진 차이가있는 모든 쌍을 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sort(a,a+n);
  int flag=0;
  for(int i=0;i<n-1;i++)//select an element
  {
      int diff=a[i]+d;
      if(binary_search(a,a+n,diff))
      {
          cout<<a[i]<<" "<<diff<<endl;
          flag=1;
      }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

주어진 차이가있는 모든 쌍을 찾기위한 Java 프로그램

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static int binary_search(int arr[], int l, int r, int x)
    {
        if (r >= l) 
        {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binary_search(arr, l, mid - 1, x);
            return binary_search(arr, mid + 1, r, x);
        }
        return -1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        int flag=0;
        for(int i=0;i<n-1;i++)//select an element
        {
            int diff=a[i]+d;
            if(binary_search(a,0,n-1,diff)!=-1)
            {
                System.out.println(a[i]+"  "+diff);
                flag=1;
            }
        }
        if(flag==0)
         System.out.println("No pair with given different");
    }
}
10 20
90 70 20 80 50 25 35 15 100 150
15 35
50 70
70 90
80 100

복잡성 분석

시간 복잡성

O (NlogN) 여기서 N은 주어진 배열의 크기입니다. 이진 검색은 O (logN)를 사용하므로 각 요소에 대해 이진 검색을 사용하는 데 시간 복잡도는 O (NlogN)입니다.

공간 복잡성

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

참조

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