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

난이도 중급
자주 묻는 질문 수행자 아마존 인상 MakeMyTrip 올라 택시 SAP 연구소
배열 해시조회수 97

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

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

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

설명

2의 첫 번째 색인 → 0

2의 마지막 색인 → 6

최대 차이 (6-0) = 6

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

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

설명

4의 첫 번째 색인 → 4

4의 마지막 색인 → 7

최대 차이 (7-4) = 3

암호알고리즘

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

설명

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

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

예를 들어 보겠습니다.

도착 [] = {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) 어디에 "엔' 배열의 요소 수입니다.

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