Bir sıra itkin elementlərini tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çatdırılma Boz Portağal LinkedIn Nagarro Opera Sinopsis
Sükut Larsen & Toubro çeşidləyiciBaxılıb 92

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, bir aralığın itkin elementlərini tapın ”ifadəsi ilə sizə verildiyini bildirir array müəyyən bir aralığdakı fərqli elementlərin və aşağı və yüksək olaraq verilən bir aralığın. Bir sıra içərisində olmayan bütün itkin elementləri tapın. Çıxış sıralanmış qaydada olmalıdır.

misal

Bir sıra itkin elementlərini tapınPin

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

Izahat

Bunlar aşağı və yüksək olaraq verilmiş sıra içərisindəki serialdakı itkin rəqəmlərdir, yəni 1 və 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

Izahat

Bunlar aşağı və yüksək olaraq verilmiş sıra içərisindəki serialdakı itkin rəqəmlərdir, yəni 1 və 10.

Alqoritm

  1. Bəyan edin a təyin etmək.
  2. Dizini keçin və bütün elementləri dəstə qoyun.
  3. “İ” aşağıya, “i” isə yüksəkə bərabər olmasa da.
    • Bir dəstdə "i" yoxdursa.
      • 'İ' yazdırın.

Izahat

Verilən bir aralığdakı bir sıra içindəki bütün itkin elementləri aşağı və yüksək olaraq tapmağı xahiş edən bir problem ifadəsi verilir. Bunu həll etmək üçün bir dəstdən istifadə edəcəyik və dəyərləri verilmiş massivin çoxluğuna yığacağıq. Bizə aşağı və yüksək bir sıra verilir, bütün elementləri aşağı və yüksək daxil olaraq çap etməliyik.

Bu əmri almaq üçün artıq sıra elementlərini çoxluqda saxlayırıq. 'İ' -i aşağı səviyyədə başlatan bir döngə aparmalıyıq. döngəni 'i' dəyəri yüksək olana qədər işlədirik. Sonra dəstin 'i' dəyərini içermədiyini yoxlayın, sonra 'i' yazdırın. Beləliklə, bir sıra içərisində itkin olan bütün elementləri müəyyən bir aralıqda əldə edəcəyik. Bir nümunəni nəzərdən keçirək.

arr [] = {2, 3, 7, 8} aşağı = 1, yüksək = 9

Dizini keçməli və bir sıra bütün elementlərini çoxluğa qoymalıyıq. Bizim dəstimiz olacaq

set = [2,3,7,8]

Bir döngədə i-dən aşağıya qədər başlanğıc və döngə hündürlüyə qədər işləyir, yəni 'i' aşağı = 1 və yüksək = 9-a bərabərdir

i = 1, çoxluqda i yoxdursa, 1 yazdırır

[1]

i = 2, çoxluq '2' dəyərinə malikdir və heç nə etmir.

i = 3, çoxluq '3' dəyərinə malikdir və heç nə etmir.

i = 4, çoxluqda i yoxdursa, 4 yazdırır

[1, 4]

i = 5, çoxluqda i yoxdursa, 5 yazdırır

[1, 4, 5]

i = 6, çoxluqda i yoxdursa, 6 yazdırır

[1, 4, 5, 6]

i = 7, çoxluq '7' dəyərinə malikdir və heç nə etmir.

i = 8, çoxluq '8' dəyərinə malikdir və heç nə etmir.

i = 9, çoxluqda i yoxdursa, 1 yazdırır

[1, 4, 5, 6, 9]

Çıxışımız belə olacaq: [1, 4, 5, 6, 9]

Kodu

Bir aralığın itkin elementlərini tapmaq üçün C ++ kodu

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

Bir aralığın itkin elementlərini tapmaq üçün Java kodu

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n + (yüksək-aşağı + 1)) hara "N" massivdə mövcud elementlərin sayı, "Yüksək" və "Aşağı" verilən girişdir.

Kosmik Mürəkkəblik

O (n), ən pis halda, bütün elementlər fərqlidirsə. Bütün elementləri saxlamalıyıq. Beləliklə alqoritmin düzəldilməsi xətti vaxt tələb edir.

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