합이 주어진 값과 같은 두 개의 연결 목록에서 쌍을 계산합니다.

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 아 발라 라 Expedia 광신자 구글 과연 Microsoft 페이팔 테슬라
해싱 연결된 목록 정렬조회수 99

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

문제 정책

문제“주어진 값과 합이 같은 두 개의 연결 목록에서 쌍을 계산”하면 두 개의 연결 목록과 정수 값의 합이 주어집니다. 문제 설명은 총 쌍이 주어진 값과 같은 합계를 갖는지 알아 내도록 요청했습니다.

LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9
2

설명 : 주어진 값 6에 값을 합산하는 두 쌍 즉, 3, 8, 1, 9이 있습니다.

 

합이 주어진 값과 같은 연결 목록에서 쌍을 계산하는 알고리즘

1. Push all the integer values to the two different linked lists.
2. Declare a set.
3. Set the count to 0.
4. Iterate over the first linked list and put all the values of it into the linked list1.
5. Iterate over the second linked list
    1. Check if the set contains the difference between the value of x and a current element of linked list2.
        1. If true then increase the value of count by 1.
6. Return count.

설명

입력으로 정수 값이 제공됩니다. 그래서 우리는 그것들을 모두 연결 목록에 넣을 것입니다. C ++에서는이 솔루션을 수행하기 위해 연결 목록을 구현하는 방법을 외부에서 만들었습니다. 그러나 Java에는 모든 정수 값을 연결 목록에 쉽게 푸시 할 수있는 연결 목록 클래스가 내장되어 있습니다. 이제 우리는 숫자가 주어진 값에 합산되는 두 연결 목록에서 쌍을 찾아 내도록 요청했습니다.

모든 정수 값을 연결 목록에 푸시 할 것입니다. 우리는 사용할 것입니다 세트 데이터 구조는 연결된 list1의 모든 값을 순회하고 설정할 첫 번째 연결 목록의 모든 값을 저장합니다. 세트는 공통 요소가 세트에서 자동으로 제거되는 기능도 제공합니다. 따라서 다음 번에 집합을 사용하면 공통 요소에 문제가 없으며 연결된 목록에 공통 요소가 없습니다.

이제 연결 목록 1의 모든 값이 집합에 포함되었습니다. 이제 두 번째 연결 목록을 탐색하고 x와 두 번째 목록의 각 값 사이의 차이가 집합에 있는지 확인합니다. 존재한다면 우리는 지금 쌍을 찾았고 또한 우리는 count의 값을 1 증가시킬 것입니다. 이것은 1 개의 쌍이 발견되었다는 것을 의미합니다. 순회가 끝날 때. count의 값은 주어진 값과 동일한 합계를 갖는 쌍의 수입니다.

합이 주어진 값과 같은 두 개의 연결 목록에서 쌍을 계산합니다.

암호

합이 주어진 값과 같은 두 개의 연결 목록에서 쌍을 계산하는 C ++

#include<iostream>
#include<unordered_set>

using namespace std;

struct Node
{
    int data;
    struct Node* next;
};

void implementLinkedList(struct Node** headReference, int newItem)
{
    struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

    newNode->data = newItem;

    newNode->next = (*headReference);

    (*headReference) = newNode;
}
int getPairOfsum (struct Node* head1, struct Node* head2,int sum)
{
    int count = 0;

    unordered_set<int> SET;

    while (head1 != NULL)
    {
        SET.insert(head1->data);

        head1 = head1->next;
    }

    while (head2 != NULL)
    {
        if (SET.find(sum - head2->data) != SET.end())
            count++;

        head2 = head2->next;
    }
    return count;
}
int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    implementLinkedList (&head1,11);
    implementLinkedList (&head1, 6);
    implementLinkedList (&head1, 1);
    implementLinkedList (&head1, 8);

    implementLinkedList (&head2, 5);
    implementLinkedList (&head2, 3);
    implementLinkedList (&head2, 1);
    implementLinkedList (&head2, 9);

    int sum = 9;

    cout << "Count = "<< getPairOfsum (head1, head2, sum);
    return 0;
}
Count = 2

합이 주어진 값과 같은 두 개의 연결 목록에서 쌍을 계산하는 Java 코드

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

class PairOfSumInLinkedList1
{
    public static int getPairOfsum(LinkedList<Integer> head1, LinkedList<Integer> head2, int sum)
    {
        int count = 0;

        HashSet<Integer> SET = new HashSet<Integer>();

        Iterator<Integer> itr1 = head1.iterator();
        while (itr1.hasNext())
        {
            SET.add(itr1.next());

        }

        Iterator<Integer> itr2 = head2.iterator();
        while (itr2.hasNext())
        {
            if (!(SET.add(sum - itr2.next())))
                count++;

        }
        return count;
    }
    public static void main(String[] args)
    {
        Integer arr1[] = {11, 6, 1, 8};
        Integer arr2[] = {5, 3, 1, 9};

        LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));

        LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));

        int x = 9;

        System.out.println("Count = " + getPairOfsum(head1, head2, x));
    }
}
Count = 2

복잡성 분석

시간 복잡성

O (n1 + n2) 어디에 "n1" 및 "n2" 연결 목록의 요소 수입니다. 선형 시간 복잡성을 달성 할 수 있습니다. 연결된 목록을 모두 탐색하고 HashSet을 사용했기 때문입니다.

공간 복잡성

입력을 두 개의 연결 목록에 저장하고 HashSet을 사용했기 때문입니다. 선형 공간 복잡성 솔루션이 있습니다.

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