a % b = k가되는 배열의 모든 쌍 (a, b) 찾기

난이도 하드
자주 묻는 질문 아마존 아르 세슘 지시 무료 Yahoo
배열 해시 모듈 식 산술조회수 105

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

문제 정책

"% b = k가되도록 배열에서 모든 쌍 (a, b) 찾기"문제는 정수 배열과 다음과 같은 정수 값이 주어짐을 나타냅니다. k. 문제 설명은 배열에서 x % y = k (주어진 값)가되는 방식으로 쌍을 찾을 것을 요청합니다.

arr[] = {3, 4, 7, 5, 6 }
k = 3
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

설명

이 4 쌍은 a % b = k가 참일 때 확인되었습니다.

a % b = k가되는 배열의 모든 쌍 (a, b) 찾기

arr[]={2, 3, 5, 1},
k = 2
(2, 3) (2, 5) (5, 3)

설명

이 3 쌍은 a % b = k가 참일 때 확인되었습니다.

암호알고리즘

  1. 선언 지도 인수 중 하나를 부울.
  2. 원본 횡단 정렬 True Boolean 값이있는 배열의 모든 값을 맵에 저장합니다.
  3. 말할 부울 변수 설정 페어체크 거짓으로.
  4. 0에서 n-1까지 배열을 탐색합니다 (n은 배열의 길이).
    1. 주어진 k 값에 맵에 항목이 있고 k가 현재 배열 요소보다 작은 지 확인합니다. true이면 k 값과 해당 배열 요소를 인쇄하고 해당 부울 값을 true로 설정합니다.
    2. k가 현재 배열 요소보다 작거나 같은지 확인합니다.
      1. 참이면 벡터를 만들고 arr [i] -k 값의 모든 제수를 찾아 벡터에 저장합니다.
      2. 그 벡터를 가로 지르고 벡터의 요소와 배열 요소가 쌍을 이루어 모듈로가 완료되었을 때 조건을 만족하는지 확인합니다.
        1. 벡터와 현재 배열 요소를 인쇄하고 부울 값을 true로 설정합니다.
  5. 반품 페어체크.

설명

정수 배열과 정수 값 k가 주어집니다. x % y = k가되는 쌍 (x, y)에 대해 모듈로 연산을 수행 할 때 해당 쌍을 인쇄해야하는 방식으로 쌍을 찾으십시오. 정수 배열을 사용하여이를 수행해야합니다. 숫자 x % y에 대해 모듈로 연산을 수행 할 때 k 값을 제공하는 모든 쌍을 찾으십시오. 이를 위해 벡터 및 맵이라는 컬렉션 또는 STL 중 하나를 사용할 것입니다.

모든 배열 요소를 맵에 넣고 모두 "true"부울 값으로 표시합니다. 다음과 같은 부울 변수를 초기화해야합니다. 페어체크 거짓으로. 올바른 쌍을 찾으면 업데이트 할 것입니다. 이제 우리는 배열을 횡단 할 것입니다. 그리고 주어진 k 값이 맵에 있는지 확인하십시오. 또한 k가 현재 배열 요소보다 작은 경우. 그런 다음 그 쌍을 인쇄합니다. 작은 수를 큰 수로 나누면 나머지는 작은 수로 남게됩니다.

위의 조건이 거짓이되면 현재 요소가 k보다 큰지 확인합니다. 참이면 현재 배열 요소와 k의 차이를 전달하는 벡터를 선언해야합니다. 그러면 가능한 쌍이 반환되는 벡터가 반환됩니다. 각 값을 선택하고 벡터에서 현재 배열 요소 모듈로 반환 된 값이 나머지 k를 제공하는지 확인합니다. true이면 쌍을 인쇄하고 pairCheck 값을 true로 표시합니다. 이는 하나 이상의 쌍을 찾았 음을 의미합니다. 동일한 단계로 추가 값을 진행하고 가능한 모든 결과를 인쇄하십시오.

암호

a % b = k가되는 배열에서 모든 쌍 (a, b)을 찾기위한 C ++ 구현

#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

vector<int> findPossibleDiv(int n)
{
    vector<int> vecDiv;

    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                vecDiv.push_back(i);
            else
            {
                vecDiv.push_back(i);
                vecDiv.push_back(n / i);
            }
        }
    }
    return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
    unordered_map<int, bool> MAP;
    for (int i = 0; i < n; i++)
        MAP[arr[i]] = true;

    bool pairCheck = false;
    for (int i = 0; i < n; i++)
    {
        if (MAP[k] && k < arr[i])
        {
            cout << "(" << k << ", " << arr[i] << ") ";
            pairCheck = true;
        }
        if (arr[i] >= k)
        {
            vector<int> vec = findPossibleDiv(arr[i] - k);

            for (int j = 0; j < vec.size(); j++)
            {
                if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
                {
                    cout << "(" << arr[i] << ", "<< vec[j] << ") ";
                    pairCheck = true;
                }
            }
            vec.clear();
        }
    }
    return pairCheck;
}
int main()
{
    int arr[] = { 3, 4, 7, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (pairModulousK(arr, n, k) == false)
        cout << "No such pair exists";
    return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

a % b = k가되도록 배열에서 모든 쌍 (a, b)을 찾는 Java 코드

import java.util.HashMap;
import java.util.Vector;

class PairModuloK
{
    public static Vector<Integer> findPossibleDiv(int n)
    {
        Vector<Integer> vecDiv = new Vector<>();

        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                if (n / i == i)
                    vecDiv.add(i);
                else
                {
                    vecDiv.add(i);
                    vecDiv.add(n / i);
                }
            }
        }
        return vecDiv;
    }
    public static boolean pairModulousK(int arr[], int n, int k)
    {
        HashMap<Integer, Boolean> MAP = new HashMap<>();
        for (int i = 0; i < n; i++)
            MAP.put(arr[i], true);

        boolean pairCheck = false;
        for (int i = 0; i < n; i++)
        {
            if (MAP.get(k) && k < arr[i])
            {
                System.out.print("(" + k + ", " + arr[i] + ") ");
                pairCheck = true;
            }
            if (arr[i] >= k)
            {
                Vector<Integer> vec = findPossibleDiv(arr[i] - k);

                for (int j = 0; j < vec.size(); j++)
                {
                    if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
                    {
                        System.out.print("(" + arr[i] + ", "
                                         + vec.get(j) + ") ");
                        pairCheck = true;
                    }
                }
                vec.clear();
            }
        }

        return pairCheck;
    }
    public static void main(String args[])
    {
        int arr[] = {3, 4, 7, 6, 5};
        int k = 3;

        if (pairModulousK(arr, arr.length, k) == false)
            System.out.println("No such pair exists");
    }
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)

복잡성 분석

시간 복잡성

O (n * sqrt (최대)) 어디에 "최대" 배열의 최대 요소입니다. 이번에는 우리가

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 이 공간은지도에 요소를 저장하는 데 필요합니다.

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