인접 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스

난이도 중급
자주 묻는 질문 시스코 Expedia Qualtrics SAP 연구소 테라 데이타
배열 동적 프로그래밍조회수 76

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

문제 정책

당신은 주어진 정수 정렬. “인접 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스”문제는 인접 요소 간의 차이가 0 또는 1이되어야하는 최대 하위 시퀀스 길이를 알아 내도록 요구합니다.

arr[] = {1, 4, 5, 2, 6, 5, 4, 8}
5

설명

하위 시퀀스 = 4, 5, 6, 5, 4

arr[] = {1, -3, -2, 0, -1, -2, -3, -4}
6

설명

하위 시퀀스 = -3, -2, -1, -2, -3, -4

인접한 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스를 찾는 알고리즘

1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
  1. Initialize a variable temp to 0.
  2. Check if Map contains the key as arr[i-1],
    1. If true, then get the value of arr[i-1] and store it to temp.
  3. Check if Map contains the key as arr[i],
    1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
  4. Check if Map contains the key as arr[i+1],
    1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
  5. Check if the temp is greater than maxValue,
    1. If true then store the value of temp to maxValue.
  6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.

설명

우리는 주어진 정수 배열, 문제 설명은 최대 하위 시퀀스 길이를 알아 내도록 요청합니다. 그리고 선택된 하위 시퀀스는 0 또는 1 이외의 인접 값 사이에 차이가 있어야합니다.이 문제를 해결하기 위해 해싱 솔루션을 효율적으로 만들 수 있습니다. 우리는 키를 배열의 요소로 놓고 키의 값을 항상 최대 값을 찾아서 temp에 저장할 것입니다.

예를 고려하고 이것을 이해합시다.

도착 [] = {1, 4, 5, 2, 6, 5, 4, 8}

우리가하는 첫 번째 일은 지도 우리가 논의한 알고리즘에 따라 배열 요소와 값 temp를 저장할 것이기 때문입니다. maxValue의 값을 0으로 설정합니다.이 변수를 반환합니다. 그 변수에있는 것이 우리의 대답이 될 것입니다. 배열을 횡단하여 배열 길이에 도달하도록합니다. 새 값 i로 배열을 순회 할 때마다 temp 값을 0으로 초기화합니다.

i = 0, arr [i] = 1, temp = 0, maxValue = 0 Map = {}

어떤 조건이 충족되는지 확인하십시오. 이 경우 조건이 없습니다. 따라서 temp ++를 수행하고 temp가 maxValue보다 큰지 확인합니다. 참이면 temp를 maxValue에 저장하고 값과 temp를 맵에 삽입합니다.

i = 1, arr [i] = 4, temp = 0, maxValue = 1.

지도 = {1,1}

위의 조건과 동일하게 맵에 값을 삽입합니다.

i = 2, arr [i] = 5, temp = 0, maxValue = 1.

지도 = {1 : 1, 4 : 1}

이번에는 맵에 1 인 arr [i] -4이 포함되어있는 첫 번째 조건이 올바른지 확인합니다. 따라서 1을 temp로 취하고 temp ++를 수행합니다. 그런 다음 maxValue를 2로 변경하고 arr [i]와 temp를 삽입합니다.

이렇게 간단히 조건을 확인하고 온도 값을 가져옵니다. 지도에 계속 삽입하면 마침내 maxValue의 값을 출력으로 얻습니다.

인접 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스

암호

인접한 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스를 찾는 C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int maxValue = 0;
    for (int i=0; i<n; i++)
    {
        int temp = 0;
        if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
            temp = MAP[arr[i]-1];

        if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
            temp = MAP[arr[i]];

        if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
            temp = MAP[arr[i]+1];

        MAP[arr[i]] = temp + 1;

        if (maxValue < MAP[arr[i]])
            maxValue = MAP[arr[i]];
    }
    return maxValue;
}
int main()
{
    int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumLenSubsequence(arr, n);
    return 0;
}
5

인접 요소 간의 차이가 0 또는 1 인 최대 길이 하위 시퀀스를 찾는 Java 코드

import java.util.HashMap;

class subsequenceLength
{
    public static int getMaximumLenSubsequence(int[] arr)
    {
        int maxValue = 0;
        HashMap<Integer, Integer> MAP = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            int temp = 0;
            if (MAP.containsKey(arr[i] - 1))
            {
                temp = MAP.get(arr[i] - 1);
            }

            if (MAP.containsKey(arr[i]))
            {
                temp = Math.max(temp, MAP.get(arr[i]));
            }

            if (MAP.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, MAP.get(arr[i] + 1));
            }
            temp++;
            if (temp > maxValue)
            {
                maxValue = temp;
            }
            MAP.put(arr[i], temp);
        }
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
        System.out.println(getMaximumLenSubsequence(arr));
    }
}
5

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 우리는 단순히 배열의 모든 요소를 ​​순회했습니다. HashMap을 사용했기 때문에 선형 시간 복잡도에서이를 수행 할 수있었습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 지도의 요소와 관련된 데이터를 저장하기 때문에 공간 복잡성도 선형입니다.

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