배열 요소의 첫 번째 인덱스와 마지막 인덱스 간의 최대 차이-TutorialCup

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

당신은 정렬 of 정수. "배열에있는 요소의 첫 번째 인덱스와 마지막 인덱스 간의 최대 차이"문제는 그 차이가 모두 최대가되도록 배열에있는 각 숫자의 첫 번째 인덱스와 마지막 인덱스 간의 차이를 알아 내도록 요구합니다.

차례

예

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

설명

2의 첫 번째 색인 → 0

2의 마지막 색인 → 6

최대 차이 (6-0) = 6

핀

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

설명

4의 첫 번째 색인 → 4

4의 마지막 색인 → 7

최대 차이 (7-4) = 3

암호알고리즘

전체 횡단 정렬.
배열의 각 요소를 선택하고 첫 번째와 마지막 요소를 가져 와서 HashTable에 저장합니다.
횡단 지도:
1. 각 요소의 첫 번째 색인과 마지막 색인의 차이점을 찾으십시오.
2. 최대 차이를 일부 변수에 저장하고 이전 값보다 최대 값을 찾을 때마다 계속 업데이트하십시오.
최대 차이를 반환합니다.

설명

우리는 주어진 정수 배열의 각 값에 대한 첫 번째 인덱스와 마지막 인덱스의 차이를 찾아야합니다. 첫 번째와 마지막 색인 사이의 숫자에 대한 최대 차이를 찾으십시오. 이를 위해 우리는 해싱. 배열 요소를 가져 와서 첫 번째 인덱스와 마지막 인덱스를 알아 내거나 처음과 마지막에 언제 발생하는지 알아냅니다.

모든 요소와 첫 번째 및 마지막 색인을지도에 넣은 후지도를 횡단합니다. 이제 각 요소를 선택한 다음 첫 번째와 마지막 색인을 가져 와서 최대 값이되어야하는 차이를 알아낼 것입니다. 변수를 사용할 수 있습니다. 최대차 최대 차이를 주시합니다. 클래스와 그 객체를 사용하여 모든 요소의 첫 번째와 마지막 인덱스를 저장합니다.

예를 들어 보겠습니다.

예

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

배열 입력이 있습니다. 이를 해결하기 위해 우리는 클래스를 사용할 것입니다. 처음으로 통과하는 경우 모든 요소를 찾습니다. 그런 다음 해당 인덱스를 첫 번째 인덱스로 저장하고 동일한 요소가 다시 올 때. 그런 다음 매번 인덱스를 두 번째 인덱스로 저장합니다. 이 방법을 사용하면 다음과 같은 맵이 있습니다.

맵 : 1-> 3 : null,

2-> 0 : 6,

3-> 1, null,

4-> 4 : null,

5-> 2 : 7,

6-> 5 : null

지도를 탐색하고 각 값을 가져 와서 지수의 차이를 확인합니다. null 값을 가진 모든 값을 무시할 것입니다. 그래서 우리는 2와 5가 있고 2 첫 번째와 마지막 색인 사이에 최대 차이 (6)가 있습니다. 5 차이가 있습니다 (5). 그래서 우리는 최대 차이로 6을 반환 할 것이고 그것이 우리의 대답이 될 것입니다.

배열에있는 요소의 첫 번째 인덱스와 마지막 인덱스 간의 최대 차이를 찾는 C ++ 코드

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}

Maximum difference b/w the first and last index of a number= 6

배열에있는 요소의 첫 번째 색인과 마지막 색인 사이의 최대 차이를 찾는 Java 코드

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}

Maximum difference b/w the first and last index of a number= 6

복잡성 분석

시간 복잡성

O (N) 어디에 "엔' 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔' 배열의 요소 수입니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러