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
Verilmiş bir array müsbət tam ədədi. Bütün ədədlər tək sayda baş verən bir rəqəm xaricində hətta bir neçə dəfə baş verir. Bir massivdə tək sayda baş verən ədədi tapmaq məcburiyyətindəyik.
misal
Input
1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6
Buraxılış
4
Tək nömrələrdə baş verən ədədə görə 1 yanaşma
Bir sıra içərisində tək sayda meydana gələn ədədi tapmaq üçün XOR əməliyyatı anlayışından istifadə edirik.
Bildiyimiz kimi
A xor A = 0 ----- Mülkiyyət 1
yəni iki oxşar elementin xoru sıfırdır.
Həmçinin,
A xor 0 = A -----Mülkiyyət 2
yəni sıfır olan hər hansı bir elementin xor eyni ədədi verir.
Beləliklə alqoritmimiz olacaq,
Alqoritm
1. İlk elementdən başlayın və massivin son elementinə qədər keçin. Bir sıra bütün elementlərin XOR həyata keçirir.
2. Sayı EVEN dəfələrlə baş verərsə, 1 nömrəli nöqtədən Sıfır olacaqdır [1 xassəsinə görə]
3. 1 saylı nöqtədən gələn XOR, tək sayda baş verərsə, ədədə bərabər olacaqdır [2 xüsusiyyətinə görə]
Həyata keçirilməsi
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
//initialize the value as first element
int val = a[0];
for(int i=1;i<n;i++)
{
//XOR of each element so that we can find the number occurring odd number of times
val = val^a[i];
}
cout<<val<<endl;
return 0;
}
Java Proqramı
import java.util.Arrays;
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();
}
//initialize the value as first element
int val = arr[0];
for(int i=1;i<n;i++)
{
//XOR of each element so that we can find the number occurring odd number of times
val = val^arr[i];
}
System.out.println(val);
}
}
5 13 5 3 2 1
8
Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi
Zamanın mürəkkəbliyi: O (N)
Kosmik Mürəkkəblik: O (1)
Tək nömrələrdə baş verən ədədə görə 2 yanaşma
Bir Hash və ya Xəritə bir sıra elementləri əlavə edin.
Alqoritm
1. Hash və ya Map-də dəyərləri əlavə edin
2. Kimi bir sıra elementi edin açar və elementlərin meydana gəlmə sayı dəyər açarın.
3. Bir sıra bütün elementlərini əlavə etdikdən sonra xəritələri tarayın dəyər və harada tək sayla bir rəqəm alsaq, o zaman açar cavabdır.
Həyata keçirilməsi
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
//map to store 2 int values where first one is for the array element and second one for its count
map<int,int> M;
map<int,int>::iterator it;
int main()
{
int size;
cin>>size;
int arr[size];
for(int i=0;i<size;i++)
cin>>arr[i];
for(int i=0;i<size;i++)
{
it = M.find(arr[i]);
// if the number is not present in the map then add it by making its count as 1
if(it == M.end())
{
M.insert(make_pair(arr[i],1));
}
else //if the number is present then simply increase its count by 1
{
pair<int,int> p = *it;
M.erase(it);
//p.second+1 is done for increasing the count by 1
M.insert(make_pair(p.first,p.second+1));
}
}
for(it = M.begin(); it != M.end(); it++)
{
//check for odd as if remainder is 1 then if evaluates to true
if((it->second) % 2 )
{
cout<<it->first<<endl;
return 0;
}
}
return 0;
}
Java Proqramı
import java.util.HashMap;
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();
}
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for(int i=0;i<n;i++)
{
int temp = m.get(arr[i])==null? 1: m.get(arr[i])+1;
m.put(arr[i], temp);
}
for (Integer i : m.keySet())
{
int x = m.get(i);
if(x%2==1)
{
System.out.println(i);
return;
}
}
}
}
5 1 2 2 2 1
2
Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi
Zamanın mürəkkəbliyi: O (N)
Kosmik Mürəkkəblik: O (N)
Tək nömrələrdə baş verən ədədə görə 3 yanaşma
Son və ən asan düşünülən həll, bütün massivi GÜÇLƏMƏKdir.
Alqoritm
1. Dizidən bir element götürün.
2. Dizinin başlanğıcından sonuna qədər bir döngə aparın və # 1 nöqtəsində götürülmüş elementlə qarşılaşdığımız zaman sayını artırmağa davam edin.
3. 2-ci nöqtədəki say təkdirsə, cavabı alarıq və ya bir sıra növbəti elementləri üçün taramaya davam edirik.
Həyata keçirilməsi
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
int main()
{
int size; cin>>size;
int arr[size];for(int i=0;i<size;i++) cin>>arr[i];
//select each element as reference
for(int i=0;i<size;i++)
{
int count_of_element = 0;
for(int j=0;j<size;j++)
{
//if the number is same as the reference number
if(arr[j] == arr[i])
count_of_element++;
}
//check for odd as if remainder is 1 then if evaluates to true
if(count_of_element % 2)
{
cout << arr[i] <<endl;
return 0;
}
}
return 0;
}
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();
}
//select each element as reference
for(int i=0;i<n;i++)
{
int count_of_element = 0;
for(int j=0;j<n;j++)
{
//if the number is same as the reference number
if(arr[j] == arr[i])
count_of_element++;
}
//check for odd as if remainder is 1 then if evaluates to true
if(count_of_element % 2==1)
{
System.out.println(arr[i]);
return;
}
}
}
}
6 1 2 3 2 1 2
2
Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi
Zamanın mürəkkəbliyi: O (N * N)
Kosmik Mürəkkəblik: O (1)
