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.
Mündəricat
Problem bəyanat
“X-i Y-yə çevirmək üçün minimum əməliyyatlar” problemi sizə iki ədəd X və Y verildiyini bildirir, aşağıdakı əməliyyatlardan istifadə edərək X-i Y-ə çevirmək lazımdır:
Başlanğıc nömrəsi X-dir və aşağıdakı əməliyyatlar X-də və aralıq nəticə olaraq yaranan nömrələrdə aparıla bilər.
- ədədi 2-yə vurun.
- sayını 1 azaldır.
Yuxarıda göstərilən əməliyyatlardan istifadə edərək X-i Y-ə çevirmək üçün lazım olan minimum addım sayını öyrənin.
Məhdudiyyətlər: 0 <X, Y <1000
misal
X = 3, Y = 11
3
Izahat: 3 * 2 = 6, 6 * 2 = 12, 12-1 = 11 3 addım
X = 2, Y = 10
5
Explanation: 2 * 2 = 4, 4-1 = 3, 3 * 2 = 6, 6-1 = 5, 5 * 2 = 10 -> 5 addım
Yanaşma
Tətbiq edirik BFS əsaslı alqoritm. Sonra 2 əməliyyatı yerinə yetirə bilərik ya da 2-yə vururuq, ya da 1-i çıxardırıq. Bu şəkildə başlanğıc X sayından və verilmiş iki əməliyyatı yerinə yetirərək yarana biləcək bütün rəqəmlərə çata bilərik. Hər hansı bir yaradılan nömrə Y nömrəsinə bərabərdirsə əldə edilir. Beləliklə, sadəcə Y sayını yaratmaq üçün atılan addımların sayını qaytarırıq. Rəqəmlər yaradan zaman aşağıdakı məqamları nəzərə almaq vacibdir:
- Yaradılan nömrə məhdudiyyətləri təmin etmirsə, nömrənin BFS növbəsinə daxil edilməsinə məhəl qoymuruq.
- Hal-hazırda yaradılan nömrə əvvəllər yaradılıbsa. Sadəcə BFS növbəsinə əlavə etmədən nömrəni görməməzlikdən gəlirik. Bu günə qədər yaradılan nömrələri izləmək üçün bir hash seti istifadə olunur.
- Əməliyyat sayını izləyirik (adlı dəyişəndə) səviyyə) tələb olunan əməliyyatları həyata keçirərək X nömrəsindən başlanğıc sayından bir ədəd yaratmaq üçün yerinə yetirilmişdir.
X-i Y-ə çevirmək üçün Minimum Əməliyyatları tapmaq üçün alqoritm
- Bir yaradın queue BFS keçidi üçün X başlanğıc nömrəsini daxil edin və növbə səviyyəsindədir. X-in X-ə çevrilməsi üçün tələb olunan əməliyyatların sayı 0 olduğu üçün başlanğıc sayının səviyyəsi 0-dır.
- Bir yaradın HashSet indiyə qədər yaradılan nömrələri saxlayan.
- Sonra BFS keçidinə başlayın.
- Düyün dəyəri Y giriş nömrəsinə bərabərdirsə, növbədən bir qovşaq açın. Və bu düyünün qayıtma səviyyəsi (X-dən minimum əməliyyat sayı).
- Başqa bir halda, bu düyünü hash qrupumuza əlavə edin (ziyarət edildiyi kimi qeyd edin).
- İndi atılan düyün dəyərini 2 ilə vurun və dəstdə olub olmadığını yoxlayın.
- Bu qədər yaradılan rəqəm çoxluqda yoxdursa. Beləliklə, nömrəni səviyyə ilə birlikdə növbəyə daxil edin (yaradılan bu düyünün səviyyəsi = atılmış (ana) düyün səviyyəsi + 1).
- Atılan düyün dəyərini 1-ə endirin və dəstdə olub olmadığını yoxlayın.
- Bu qədər yaradılan rəqəm çoxluqda yoxdursa. Beləliklə, nömrəni səviyyə ilə birlikdə növbəyə daxil edin (yaradılan bu düyünün səviyyəsi = atılmış (ana) düyün səviyyəsi + 1).
- Geri qayıtma vəziyyəti ilə qarşılaşana qədər 3-9 addımlarını təkrarlayın addım-4.
Alqoritm aşağıda təsvir edilmişdir:
Kodu
X-yə çevirmək üçün minimum əməliyyatları tapmaq üçün C ++ kodu
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* class definition to treat
numbers generated as nodes */
class Node
{
public:
int num;
int level;
Node(int num,int level)
{
this->num = num;
this->level = level;
}
};
/* function to find minimum number of
operations required to convert x into y */
int minOperation(int x,int y)
{
queue<Node*> q;
unordered_set <int> us;
Node *node = new Node(x,0);
q.push(node);
while(!q.empty())
{
Node *top = q.front();
q.pop();
if(top->num == y)
return top->level;
us.insert(top->num);
/* Multiplication Operation */
if(us.find(2*top->num) == us.end())
{
Node *temp = new Node(2*top->num,top->level+1);
q.push(temp);
}
/* Subtraction Operation */
if(us.find(top->num-1) == us.end() && top->num-1 > 0)
{
Node *temp = new Node(top->num-1,top->level+1);
q.push(temp);
}
}
}
/* Main function */
int main()
{
int x = 2,y = 10;
cout<<minOperation(x,y)<<endl;
return 0;
}
5
X-i Y-ə çevirmək üçün Minimum Əməliyyatları tapmaq üçün Java Kodu
import java.util.*;
import java.io.*;
class TutorialCup
{
/* class definition to treat
numbers generated as nodes */
static class Node
{
int num;
int level;
Node(int num,int level)
{
this.num = num;
this.level = level;
}
}
/* function to find minimum number of
operations required to convert x into y */
static int minOperation(int x,int y)
{
Queue <Node> q = new LinkedList<>();
HashSet <Integer> hs = new HashSet<Integer>();
Node node = new Node(x,0);
q.add(node);
while(!q.isEmpty())
{
Node top = q.poll();
if(top.num == y)
return top.level;
hs.add(top.num);
/* Multiplication Operation */
if(!hs.contains(2*top.num))
{
Node temp = new Node(2*top.num,top.level+1);
q.add(temp);
}
/* Subtraction Operation */
if(!hs.contains(top.num-1) && top.num-1 > 0)
{
Node temp = new Node(top.num-1,top.level+1);
q.add(temp);
}
}
return 0;
}
/* Main function */
public static void main (String[] args)
{
int x = 2,y = 10;
System.out.println(minOperation(x,y));
}
}
5
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
Yuxarıdakı yanaşmadan istifadə edərək bir nömrə tapmaq üçün zamanın mürəkkəbliyini şərh etmək çətindir. Ancaq hələ də ən pis zaman mürəkkəbliyini şərh edə bilərik. Ən pis vəziyyətdə nə ola bilər, məhdudiyyət altında olan bütün rəqəmlərdən keçirik. Bütün nömrələrdən keçsək də, lazımi sayımızı tapa bilmirik. Beləliklə zamanın mürəkkəbliyi O (N), burada N verilmiş məhdudiyyətlər altında mümkün olan ən böyük elementdir.
Kosmik Mürəkkəblik
Kosmik mürəkkəbliyi də şərh etmək çətindir. Ancaq zamanın mürəkkəbliyi ilə etdiyimizə bənzəyir. Beləliklə, kosmik mürəkkəblik üçün də eyni. Ən pis vəziyyətdə, bütün elementləri növbəyə əlavə edəcəyik. Bu alqoritmi götürməyə məcbur edir O (N) boşluq, burada N verilən məhdudiyyət altında mümkün olan ən böyük rəqəmdir.
