İlk təkrarlanan element

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Citadel eBay Facebook Goldman Sachs google Intuit microsoft Nutanix Kahin PayPal Salesforce Arzu Yahoo
Geyim Sükut Hashing Axtarış ZyngaBaxılıb 1229

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.

Problem bəyanat

Biz verdik array n tam ədədi ehtiva edir. Tapmalıyıq ilk təkrarlanan element verilmiş massivdə. Təkrarlanan bir element yoxdursa, “Təkrarlanan tam ədəd tapılmadı” yazdırın.

Qeyd: Təkrarlanan elementlər birdən çox dəfə gələn elementlərdir. (Array dublikat ola bilər)

misal

Input

6

1 2 3 1 4 2

Buraxılış

1

İlk təkrarlanan element üçün yanaşma 1

Dizidən hər bir elementi seçən və irəlidə hərəkət edən iki dövrəni işə salın və massivdə təkrarlanmasını yoxlayın.
a) Birinci təkrarlanan tam olaraq çap olunduqda.
b) Başqa çap Təkrarlanan tam ədəd tapılmadı.
İki döngə əmri işlədiyimiz üçün O (N ^ 2) N, massivin ölçüsüdür.

Həyata keçirilməsi

İlk Təkrar Element üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  for(int i=0;i<n;i++) // select an element
    for(int j=i+1;j<n;j++) //traverse ahead and check for duplicate
        if(arr[i]==arr[j])
          {
            cout<<arr[i];
            return 0;
          }
  cout<<"No repeating integer found\n";
  return 0;
}

İlk Təkrar Element üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++) // select an element
        for(int j=i+1;j<n;j++) //traverse ahead and check for duplicate
            if(arr[i]==arr[j])
              {
                System.out.println(arr[i]);
                temp=1;
                i=n;j=n;
              }
        if(temp==0)
        System.out.println("No repeating integer found");
    }
}
5
10 3 5 3 2
3

İlk Təkrar Element üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (N ^ 2) burada N massivin ölçüsüdür. Burada bir element seçirik və bu elementin yanında olan digər elementlərə bərabər olub olmadığını yoxlayırıq.

Kosmik Mürəkkəblik: O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

İlk təkrarlanan element üçün yanaşma 2

Bu Hashing kimidir, sıra və indeksin sayını sıra elementi ilə birlikdə saxlayırıq.

1 Adım:
M vektoru yaradın ki, say və indeks cütlüyündə sıra elementinin indeksini ehtiva edən xəritə funksiyası kimi işləsin.
a) Burada indeks elementin təkrarlanan minimum göstəricisidir.
b) Sayı təkrarlanan saydır.

2 Adım: Xəritədə keçmək üçün bir iterator yaradın.

3 Adım: Dizinin hər elementini soldan seçməyimiz üçün elə bir döngə işlədin. Və indiki halda onun sayını yeniləyinsə massivdəki elementi tapın.

4 Adım: Element ilk dəfə gəlirsə, onu xəritəyə əlavə edin.
a) 1-ə bərabər say
b) i-də olsanız, i indeksində bir hadisə.

5 Adım: Xəritəyə keçərək minimum indeksi əldə edin.
a) Min_index-i INT_MAX-a başlayın
b) min_index tapmaq üçün xəritəni keçin, indeks əldə etmək üçün Map-in ikinci, sonra Second-nin ikincisini tapın.
c) Min_index-i müqayisə etmək üçün Daxili min funksiyasından istifadə edin.
d) Nəhayət, onu saxlayın.

6 Adım: Nəhayət, min_index INT_MAX-ə bərabər deyilsə, ilk təkrarlanan tam olaraq yazdırın, çünki təkrarlanan bir tam ədəd var. Else Print təkrarlanan bir tam ədədi yoxdur.

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  unordered_map<int,pair<int,int> > M;
  unordered_map<int,pair<int,int> > ::iterator it;//iterator to traverse the map
  for(int i=0; i<n; i++)//select an element
    {
      it = M.find(arr[i]); //find the element
      
      if(it != M.end())//if element already present update its count
      {
        pair<int,pair<int,int> > temp = (*it);
        pair<int,int> p = temp.second;
        p.second++;
        M.erase(it);
        M.insert(make_pair(arr[i],p));
      }
      
      else //if element came for the first time then add it into the map with count 1 and occurence at i
      M.insert(make_pair(arr[i],make_pair(i,1))); 
    }
  
  int min_index = INT_MAX; //obtaint the minimum index
  for(it = M.begin(); it != M.end(); it++) //traverse the entire map
    {
    pair<int,pair<int,int> > temp = (*it);
    pair<int,int> p = temp.second;
    if(p.second > 1)
      min_index = min(min_index,p.first);  //minimum index of the element that is repeating
    }
    
  if(min_index != INT_MAX)
  cout<<arr[min_index];
  else  
  cout<<"No repeating integer found\n";
  return 0;
}

Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int firstRepeated(int[] arr, int n)
    {
        int max = 0;
        for (int x = 0; x < n; x++) {
            if (arr[x] > max) {
                max = arr[x];
            }
        }
        int temp[]
            = new int[max + 1]; // the idea is to use
                                // temporary array as hashmap
        Arrays.fill(temp, 0);
        for (int x = 0; x < n; x++) {
            int num = arr[x];
            temp[num]++;
        }
        for (int x = 0; x < n; x++) {
            int num = arr[x];
            if (temp[num] > 1) {
                return x;
            }
        }
        return -1; // if no repeating element found
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int index = firstRepeated(arr,n); // index Of 1st repeating number
        if (index != -1) 
        {
            System.out.println(arr[index]);
        }
        else 
        {
            System.out.println("No repeating integer found");
        }
    }
}
7
1 3 5 30 2 1 3
1

İlk Təkrar Element üçün Mürəkkəblik Analizi

Zaman Mürəkkəbliyi: O (N) burada N - verilən massivin ölçüsüdür. Burada sayını sayırıq və təkrarlanan elementi yoxlayırıq.

Zaman Mürəkkəbliyi: O (N) çünki indiki elementləri saxlamaq üçün sıralanmamış bir xəritə istifadə edirik.

References

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