Verilən bir dəyəri cəmləyən dörd element tapın (Hashmap)

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon google microsoft
Geyim Sükut çeşidləyiciBaxılıb 105

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.

"Verilən bir dəyəri cəmləyən dörd element tapın (Hashmap)" problemi, bir tam sıra və cəm adlanan bir sayın olduğunu düşünür. Problem problemi, verilmiş “cəmi” dəyərinə qədər olan dörd elementin massivdə olub-olmadığını müəyyənləşdirməyi xahiş edir. Doğru olarsa, funksiya “Bəli”, əks halda “Xeyr” çıxardır.

misal

Verilən bir dəyəri cəmləyən dörd element tapın (Hashmap)Pin

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

Alqoritm

  1. Döngəni keçin, i <n - 1.
    1. Döngəni keçin, j = i + 1 <n olarkən
      1. Arr [i] + arr [j] dəyərini val-a qədər saxlayın və cədvəldə cəmi-valın olub olmadığını yoxlayın.
        1. Doğrudursa, açarı alın və nömrəni tapın və doğru qayıdın.
      2. Başqa halda, i və j düymələrini arr [i] + arr [j] kimi açarla birlikdə hash cədvəlinə qoyun.
  2. Saxta qayıdın.

Izahat

Verilən dəyəri cəmləşdirən massivdə dörd elementin olub olmadığını müəyyənləşdirməyi xahiş edən bir problem ifadəsi verilir. Bəli, onda təqib edin, onda funksiya bəli yazmalıdır, əksinə xeyr yazdırın. İstifadə edəcəyik qarışdırma bu problemi həll etmək. Odur ki, açarı mümkün alt sıra halına gətirən elementimiz kimi saxlaya bilərik və onu indekslərimiz kimi qiymətləndirə bilərik.

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

misal

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, cəmi = 25

Burada bir nümunə götürdük. Biz elan etdik Boolean true və false qayıdacaq funksiya. Mübahisələrimizdən biri hər hansı bir siyahı və ya vektor olduğu üçün xəritəmizdə istifadə edəcəyimiz obyekt xüsusiyyətini də istifadə edəcəyik. Beləliklə, əsasən serialları keçəcəyik, ancaq bir sıra hər bir elementini bir dəfəyə xarici döngədə götürürük və bir indeks gələn elementlərin qalan hissəsini ikinci daxili döngə ilə keçirik.

Arr [i] + arr [j] olan hər iki elementin cəmini götürürük və val adlanan dəyişənə saxlayırıq və sonra cəmi-valın olub olmadığını yoxlayırıq. heshtable yoxsa, yoxsa, elementləri xəritəyə itələyin, fərz edək ki, massivin 2 və 7 elementi var (arr [i] və arr [j]) cəmi 9, 25-9 olan cəmi-val 18 olur hash cədvəlində yoxdur, buna görə 9 və cəmi indeksləri 0 və 1 olanları itələyirik, beləliklə cədvəldə cəm-arr [i] + arr [j] nin olub olmadığını tapa bilərik. Mövcud olduqda, sadəcə açarın dəyərlərini əldə edin və bəzi şərtləri yoxlayın, əgər yerinə yetirilirsə, geriyə dönün. Bu o deməkdir ki, cavabımızı tapdıq.

Verilən bir dəyəri cəmləyən dörd elementi tapmaq üçün C ++ kodu (Hashmap)

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

Verilən bir dəyəri cəmləyən dörd elementi tapmaq üçün Java kodu (Hashmap)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n)2hara "N" massivdəki elementlərin sayıdır. HashMap-dən istifadə etmək, bu zaman mürəkkəbliyini əldə etməyimizə imkan verdi, əks halda mümkün olmazdı.

Kosmik Mürəkkəblik

O (n)2hara "N" massivdəki elementlərin sayıdır. Ən pis vəziyyətdə xəritədə saxlanılması lazım olan N ^ 2 cütlüyü ola bilər. Beləliklə, kosmik mürəkkəblik polinomdur.

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