Məşhurların problemi

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

Məşhur problemində N nəfərlik bir otaq var, Məşhuru tapın. Məşhur üçün şərtlər-

Əgər A Məşhurdursa

• Otaqdakı hər kəs A-nı bilməlidir.
• A otaqda kimsəni tanımamalıdır.

Bu şərtləri yerinə yetirən adamı tapmaq lazımdır.

misal

Input

bilir [] = {

{0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 0, 0},

{0, 0, 1, 0}}

Buraxılış

Məşhurların id: 2

Izahat

2 nömrəli şəxs heç kimi tanımır, lakin hamı onu tanıyır.

Məşhurların problemi üçün alqoritm

İndi problem ifadəsini bilirik, buna görə problem üçün istifadə olunan alqoritmə sürətlə gedirik. Burada əvvəlcə matrisdəki sütunu əvvəlcə düzəldirik. Sütunu düzəltmək üçün A və B göstəricilərini elə hərəkət etdiririk ki, A bilirsə B artırsa A artır, başqa artır B artır. Bunu A <B-a qədər edin. İndi sütunu qoyduqdan sonra A ünlü olub olmadığını yoxlayın. bütün üzvlər A və A-nı artıq heç kim bilməməlidir. İndi ünlü vəziyyətimiz yaxşıdırsa, başqa şəxsin kimliyini çap edin -1 yazdırın.

1. Başlanğıc və son künclərində iki göstərici saxlayırıq. (a, b)

2. verilmiş In matris dəyər

• Matrix [A] [B] = 1 olarsa, A B-ni bilir
• Başqa, A B bilmir
• A və B göstəricilərini elə hərəkət etdirin ki, A B-nin A hərəkət etdiyini bilirsə, başqa yerdə B hərəkət edin, A <B-yə qədər bunu edin.

3.  Nəhayət, iki şərti istifadə edərək A-nın məşhur olub olmadığını yoxlayın:

•  Hamısı üçün, A-ya bərabər olmayan istisna olmaqla, A-nı bilmələm
•  Hamısı üçün A məni bilməməlidir

Həyata keçirilməsi

Məşhurların Problemi üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
//Function to find the id of celebrity
int FindCelebId(int a,int n)
{
    int A = 0,B = n - 1; 
    //Finding celebity
    while(A < B)
    {
        if(a[A][B])
        {
            A++;
        }
        else
        {
            B--;
        }
    }
    //Check celebrity conditions
    //If A is celebrity
    //All members should know A
    //A should not now anyone
    for (int i = 0; i < n; i++)
    {
       if ((i != A) && (a[A][i] || !a[i][A]))
       {
            return -1;
       }
    }
 
    return A;
}
   
//main function
int main()
{
   //Number of people
    int n;
    int a[n][n]; 
    for(int i=0;i<n;i++) 
    { 
        for(int j=0;j<n;j++) 
        { 
            cin>>a[i][j]; 
        } 
    }
    int x = FindCelebId(a,n);
    if(x == -1){
        cout<<"No Celebrity found"; 
    }
    else{
        cout<<"Celebrity id is: "<<x;
    }
    return 0;
}

import java.util.Scanner;
class sum
{
    public static int FindCelebId(int a[][], int n)
    {
        int A = 0,B = n - 1; 
        //Finding celebity
        while(A < B)
        {
            if(a[A][B]==1)
            {
                A++;
            }
            else
            {
                B--;
            }
        }
        //Check celebrity conditions
        //If A is celebrity
        //All members should know A
        //A should not now anyone
        for (int i = 0; i < n; i++)
        {
           if ((i != A) && (a[A][i]==1 || a[i][A]==0))
           {
                return -1;
           }
        }
        return A;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[][] = new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                a[i][j] = sr.nextInt();
            }
        }
        int x = FindCelebId(a,n);
        if(x == -1)
        {
            System.out.println("No Celebrity found"); 
        }
        else
        {
            System.out.println("Celebrity id is: " + x);
        }
    }
}

4
0 0 1 0
0 0 1 0
0 0 1 0
0 0 1 0

Celebrity id is: 2