연속적인 하위 시퀀스로 배열 분할

난이도 중급
자주 묻는 질문 구글
탐욕스러운 더미조회수 75

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

정렬을 감안할 때 정렬(오름차순으로) 모든 하위 시퀀스에 연속 번호가 포함되도록 배열을 1보다 큰 길이의 하위 시퀀스 3 개 이상으로 분할 할 수 있는지 확인합니다.

입력:
arr [] = {1,2,3,3,4,5}
출력:
참된
설명 :
배열은 다음과 같이 2 개의 하위 시퀀스로 나눌 수 있습니다.
sub1 [] = {1, 2, 3}
sub2 [] = {3, 4, 5}

입력:
arr [] = {Z1, 2, 3, 3, 4, 4, 5, 5}
출력:
참된
설명 :
연속적인 하위 시퀀스는 다음과 같습니다.
sub1 [] = {1, 2, 3, 4, 5}
sub2 [] = {3, 4, 5}

연속적인 하위 시퀀스로 배열 분할

연속적인 하위 시퀀스로 배열을 분할하는 순진한 접근 방식

주어진 배열의 arr [i] 요소에 대해 새 하위 시퀀스를 형성하거나 (arr [i] – 1)로 끝나는 하위 시퀀스에 추가 될 수 있습니다.

항상 낫다 지원 새로운 서브 시퀀스를 형성하기 위해 새로운 서브 시퀀스를 형성하는 것은 길이가 1 미만인 일부 서브 시퀀스를 초래할 수 있습니다. (arr [i] – XNUMX)로 끝나는 하위 시퀀스가 ​​없으면 새 하위 시퀀스를 형성하는 것 외에는 옵션이 없습니다.

현재 요소를 수용 할 수있는 하위 시퀀스가 ​​두 개 이상있는 경우 항상 요소 수가 가장 적은 하위 시퀀스에 현재 요소를 추가합니다. 이렇게하면 길이가 3 미만인 하위 시퀀스를 최소화 할 수 있습니다.

암호알고리즘

  1. 배열의 첫 번째 요소는 항상 새 하위 시퀀스를 형성합니다.
  2. 인덱스 1 (0 기반 인덱싱)부터 배열을 탐색합니다.
  3. 현재 요소를 수용 할 수있는 하위 시퀀스가 ​​있는지 확인합니다. arr [i] 요소를 (arr [i] – 1)로 끝나는 하위 시퀀스에 추가 할 수 있습니다.
  4. 현재 요소를 수용 할 수있는 하위 시퀀스가없는 경우 새 하위 시퀀스를 형성합니다.
  5. 그렇지 않으면 현재 요소를 수용 할 수있는 최소 크기로 하위 시퀀스를 선택하고 선택한 하위 시퀀스에 현재 요소를 추가합니다.
  6. 배열을 순회 한 후 길이가 3 미만인 하위 시퀀스가 ​​있는지 확인하고, 그렇다면 false를 반환하고 그렇지 않으면 true를 반환합니다.

연속적인 하위 시퀀스로 분할 배열을위한 JAVA 코드

import java.util.ArrayList;

public class SplitTheArrayIntoConsecutievSubsequences {
    private static boolean isPossible(int[] arr) {
        // If the lenght of arr is less than 3, it is not possible to split the array
        if (arr == null || arr.length < 3) {
            return false;
        }
        int n = arr.length;

        // List of subsequences
        ArrayList<ArrayList<Integer>> al = new ArrayList<>();

        // First element always forms a new subsequence
        ArrayList<Integer> eles = new ArrayList<Integer>();
        eles.add(arr[0]);
        al.add(eles);

        // Traverse the array starting from index 1
        for (int i = 1; i < n; i++) {
            // Required position of subsequence that can accommodate the current element
            int pos = -1;
            // Size of required subsequence
            int size = -1;
            // Check if there is some subsequence that can accommodate the current element
            for (int j = 0; j < al.size(); j++) {
                // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
                if (al.get(j).get(al.get(j).size() - 1) + 1 == arr[i]) {
                    if (pos == -1) {
                        pos = j;
                        size = al.get(j).size();
                    } else {
                        // Select the subsequence with minimum size
                        if (al.get(j).size() < size) {
                            pos = j;
                            size = al.get(j).size();
                        }
                    }
                }
            }

            // If there is no subsequence that can accommodate the current element
            // form a new subsequence
            if (pos == -1) {
                ArrayList<Integer> newAL = new ArrayList<>();
                newAL.add(arr[i]);
                al.add(newAL);
            } else {
                // else add it to the required subsequence
                al.get(pos).add(arr[i]);
            }
        }

        for (int i = 0; i < al.size(); i++) {
            // if there is some subsequence of length less than 3, return false
            if (al.get(i).size() < 3) {
                return false;
            }
        }
        // No subsequence of length less than 3, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

연속 하위 시퀀스로 배열 분할을위한 C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    // List of subsequences
    vector<vector<int>> v;
    
    // First element always forms a new subsequence
    vector<int> eles;
    eles.push_back(arr[0]);
    v.push_back(eles);
    
    // Traverse the array starting from index 1
    for (int i = 1; i < n; i++) {
        // Required position of subsequence that can accommodate the current element
        int pos = -1;
        // Size of required subsequence
        int size = -1;
        // Check if there is some subsequence that can accommodate the current element
        for (int j = 0; j < v.size(); j++) {
            // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
            if (v[j][v[j].size() - 1] + 1 == arr[i]) {
                if (pos == -1) {
                    pos = j;
                    size = v[j].size();
                } else {
                    // Select the subsequence with minimum size
                    if (v[j].size() < size) {
                        size = v[j].size();
                        pos = j;
                    }
                }            
            }
        }
        
        // If there is no subsequence that can accommodate the current element
        // form a new subsequence
        if (pos == -1) {
            vector<int> newV;
            newV.push_back(arr[i]);
            v.push_back(newV);
        } else {
            v[pos].push_back(arr[i]);
        }
    }
    
    for (int i = 0; i < v.size(); i++) {
        if (v[i].size() < 3) {
            return false;
        }
    }
    return true;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

복잡성 분석

시간 복잡성 = 의 위에2)
공간 복잡성 = O (N)

연속적인 하위 시퀀스로 어레이를 분할하기위한 최적의 접근 방식

arr [i] 요소의 경우 새 하위 시퀀스를 형성하거나 (arr [i] – 1)로 끝나는 다른 하위 시퀀스에 추가 할 수 있습니다. arr [i]를 수용 할 수있는 하위 시퀀스가 ​​두 개 이상있는 경우 추가합니다. 최소 길이의 하위 시퀀스에.

세 가지 유형의 하위 시퀀스 길이 만 중요합니다. 즉, p1, c2, p3, c1, p1 및 c2으로 표시되는 길이 2, 길이 3 및 길이 3보다 큰 하위 시퀀스, 여기서 p는 이전을 의미하고 c는 현재를 의미합니다.

모든 숫자에 대해 배열에서 발생하는 횟수를 먼저 세고, 길이 1과 2의 모든 하위 시퀀스에 분산 될 수 있는지 확인하고, 불가능한 경우 현재 숫자가 길이 1의 하위 시퀀스를 확장 할 수없는 경우 즉시 false를 반환하거나 2, 배열이 정렬 될 때 숫자가 없습니다. 따라서 끝에 길이 1 또는 2의 일부 하위 시퀀스가 ​​남아 있습니다.

그렇지 않으면 길이 1의 모든 하위 시퀀스가 ​​길이 2의 하위 시퀀스로 변환되고, 길이 2는 길이 3으로 변환되며, 나머지 요소는 길이 3 이상의 하위 시퀀스에 추가됩니다. 여전히 일부 요소가 분산되어 있지 않으면 길이 1의 하위 시퀀스에 기여합니다. 길이 3 이상에 기여하는 요소 만 새 길이 3 하위 시퀀스에 추가됩니다.

마지막에 길이 1이없고 길이 2 하위 시퀀스가 ​​true를 반환하고 그렇지 않으면 false를 반환합니다.

JAVA 코드

public class SplitArrayIntoConsecutiveSubsequences {
    private static boolean isPossible(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return false;
        }

        int p1 = 0, p2 = 0, p3 = 0;
        int c1 = 0, c2 = 0, c3 = 0;
        int i = 0;
        // prev denotes previous element
        // curr denotes current element
        int prev = 0, curr = 0;

        // Traverse the array
        while (i < n) {
            // Current becomes previous
            p1 = c1;
            p2 = c2;
            p3 = c3;

            prev = curr;
            curr = arr[i];

            int count = 0;
            // Count the frequency of current element
            while (i < n && arr[i] == curr) {
                i++;
                count++;
            }

            if (prev + 1 == curr) {
                // if element cannot be spread across subsequences of length 1 and 2
                if (count < p1 + p2) {
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = Math.max(0, count - (p1 + p2 + p3));
                c2 = p1;
                c3 = p2 + Math.min(p3, count - (p1 + p2));
            } else {
                // this element cannot be spread across any subsequence
                if (p1 != 0 || p2 != 0) {
                    // if there is any subsequence of length 1 or 2
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = count;
                c2 = 0;
                c3 = 0;
            }
        }

        // if there are no length 1 and length 2 subsequences return true, else return false
        return (c1 == 0 && c2 == 0);
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    int p1 = 0, p2 = 0, p3 = 0;
    int c1 = 0, c2 = 0, c3 = 0;
    int i = 0;
    // prev denotes previous element
    // curr denotes current element
    int prev = 0, curr = 0;
    
    // Traverse the array
    while (i < n) {
        // Current becomes previous
        p1 = c1;
        p2 = c2;
        p3 = c3;
        
        prev = curr;
        curr = arr[i];
        
        int count = 0;
        // Count the frequency of current element
        while (i < n && arr[i] == curr) {
            i++;
            count++;
        }
        
        if (prev + 1 == curr) {
            // if element cannot be spread across subsequences of length 1 and 2
            if (count < p1 + p2) {
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = std::max(0, count - (p1 + p2 + p3));
            c2 = p1;
            c3 = p2 + std::min(p3, count - (p1 + p2));
        } else {
            // this element cannot be spread across any subsequence
            if (p1 != 0 || p2 != 0) {
                // if there is any subsequence of length 1 or 2
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = count;
            c2 = 0;
            c3 = 0;
        }
    }

    // if there are no length 1 and length 2 subsequences return true, else return false
    return (c1 == 0 && c2 == 0);
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (1)

참조

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