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

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