Dizidəki elementin birinci və son indeksləri arasındakı maksimum fərq

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon Piyada çox yol qət eləmək MakeMyTrip Ola Cabs SAP Laboratoriyaları
Geyim SükutBaxılıb 97

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Tutaq ki, səndə var array of tamsayılar. Problem "Bir sıra elementinin birinci və son indeksləri arasındakı maksimum fərq" bir sıra içərisində olan hər bir ədədin birinci və son indeksləri arasındakı fərqi, hamının maksimum olmasını tələb edir.

misal

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

Izahat

2-nin ilk indeksi → 0

2-nin son göstəricisi → 6

Maksimum fərq (6-0) = 6

Dizidəki elementin birinci və son indeksləri arasındakı maksimum fərqPin

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

Izahat

4-nin ilk indeksi → 4

4-nin son göstəricisi → 7

Maksimum fərq (7-4) = 3

Alqoritm

  1. Hamısını keçin array.
  2. Bir sıra hər bir element seçin və ilk və son element almaq və HashTable saxlanılır.
  3. Keçid xəritə:
    1. Hər elementin ilk və son göstəricisi arasındakı fərqi tapın.
    2. Maksimum fərqi bəzi dəyişənlərə daxil edin və əvvəlki dəyərdən maksimum dəyəri tapdıqda yeniləməyə davam edin.
  4. Maksimum fərqi qaytarın.

Izahat

Bizə bir tam array, bir dizinin hər bir dəyərinin ilk indeksi ilə son indeksi arasındakı fərqi tapmalıyıq. Birinci və son indeks arasındakı istənilən say üçün maksimum fərqi tapın. Bunun üçün istifadə edəcəyik Hashing. Bir sıra elementi götürəcəyik və ilk indeksini və son indeksini və ya ilk və sonuncu olduqda tapacağıq.

Bütün elementləri və ilk və son indeksləri xəritəyə qoyduqdan sonra xəritədən keçin. İndi hər bir elementi seçin və sonra ilk və son indeksini götürün və fərqi maksimum dərəcədə olacağı şəkildə tapacaqsınız. Dəyişəndən istifadə edə bilərik maksimum fərq maksimum fərqi izləmək. Hər elementin ilk və son indeksini saxlamaq üçün bir sinifdən və onun obyektindən istifadə edəcəyik.

Bir nümunəni nəzərdən keçirək:

misal

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

Bir sıra girişimiz var. Bunu həll etmək üçün bir sinifdən istifadə edəcəyik. Hər elementi ilk dəfə keçirsə axtaracağıq. Sonra indeksini ilk indeks olaraq saxlayacağıq və eyni element yenidən gələndə. Sonra hər dəfə indeksini ikinci indeks olaraq saxlayacağıq. Bu metoddan istifadə edərək bir xəritəmiz var:

Xəritə: 1-> 3: boş,

2-> 0: 6,

3-> 1, boş,

4-> 4: boş,

5-> 2: 7,

6-> 5: sıfır

Xəritədən keçəcəyik və hər bir dəyəri götürüb indekslərinin fərqlərini yoxlayacağıq. Sıfır dəyərlərə sahib olan bütün dəyərləri laqeyd yanaşacağıq. Beləliklə, bizdə 2 və 5 var və bunlardan da 2 ilə müqayisədə ilk və son indeks arasında maksimum fərq (6) var 5 fərqi olan (5). Beləliklə, 6-nı maksimum fərq olaraq qaytaracağıq və bu bizim cavabımız olacaq.

Dizidəki elementin ilk və son göstəriciləri arasındakı maksimum fərqi tapmaq üçün C ++ kodu

#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

Dizidəki elementin ilk və son indeksləri arasındakı maksimum fərqi tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara “N” massivdəki elementlərin sayıdır

Kosmik Mürəkkəblik

O (n) hara “N” massivdəki elementlərin sayıdır

Crack Sistemi Dizayn Müsahibələri
Translate »