Ар бир кызматкерге ылайык кызматкерлердин санын табуу


Кыйынчылык деңгээли жеңил
Көп суралган Accolite GE Саламаттыкты сактоо Microsoft Myntra Qualcomm Synopsys Терадата
Hashing

HashMaps маалыматтардын эң пайдалуу түзүмдөрүнүн бири. Ар бир кызматкердин кызматкерлеринин санын табуу - бул атактуу кинонун башталышын эсиме салган көйгөй. Түшүндө кыялданганга окшош. Мына, бизде кызматкердин астында иштеген кызматкер ж.б.у.с.

Маселени билдирүү

Ошентип, биз бул маселени эмне кылышыбыз керек?

Мейли. Кимдир бирөө АКШда алардын астында иштеген кызматкерлердин санын эсептөө милдетин тапшырган.

Биринчиден, көйгөйдүн бизге кандайча берилгенин бир сыноо иши менен бөлүшөлү:

Бизге каармандардын жуптары берилет, биринчиси кызматкер, экинчиси менеджер. Башкаларга бекитилген кызматкерлердин санын табышыбыз керек.

Ар бир кызматкерге ылайык кызматкерлердин санын табуу
Тест иши көрсөтүлгөн

Ыкма жана идеология

Маселени чечүүнүн көптөгөн жолдору бар. Бирок, жолдордун көпчүлүгү же убагында же мейкиндикте оор. Бул жерде мен айткан бир нерсе ага баруунун эң мыкты жолу болуп көрүндү.

  • Биринчиден, маалымат структураларын бүтүрүп жатып, Hashmaps бул көйгөйдү чечүүнүн мыкты жолу экендигин түшүндүм
  • Экинчиден, натыйжалуу пайдаланылса, түшүндүм. Бир эле цикл жетиштүү болду.
  • Хэшмапты жүргүзүп жатабыз.
  • Хэшмаптын ачкычтары - кызматкерлер
  • Хэшмаптын мааниси - алардын алдындагы кызматкерлердин саны
  • Биз цикл иштеп жатабыз.
  • Бизде менеджер үчүн ачкыч болсо, ар бир жолу карайбыз
  • Андай кылсак, мурунку мааниге 1 кошобуз
  • Кызматкер үчүн ачкыч болсо, ар бир жолу карайбыз
  • Эгер андай болсо, анда биз анын тармагында иштеген адамдар

Ар бир кызматкерге ылайык кызматкерлердин санын табуу үчүн Java коду

void group(lisa[][],int x,int y)
{
    unordered_map<char,int>store;
    for(int i=0;i<x;i++)
    {
    if(store.find(lisa[i][1])!=lisa.end())
    {
        if(store.find(lisa[i][0])!=lisa.end())
            store[lisa[i][1]]=lisa[[i][0]]+store[lisa[i][1]]+1;
        else
            store[lisa[i][1]]=store[lisa[i][1]]+1;
        else
            store.put[lisa[i][1]]=1;
    }
    for (int data : store)  
    {
        cout<<"Key = " + datagetKey() + ", Value = "+entry.getValue());
    }
}
int main() 
{
     Character[6][2]lisa;
        lisa[0][0]='A';
        lisa[0][1]='C';            
        lisa[1][0]='B';
        lisa[1][1]='C';
        lisa[2][0]='C';
        lisa[2][1]='F';
        lisa[3][0]='D';
        lisa[3][1]='E';
        lisa[4][0]='E';
        lisa[4][1]='F';
        lisa[5][0]='F';
        lisa[5][1]='F';
        group(lisa,6,2);
}

HashMap дан unordered_mapга Javaдан C ++ га өткөндө кандайча өтүп жаткандыгыбызды байкаса болот.

Ар бир кызматкерге ылайык кызматкерлердин санын табуу үчүн C ++ коду

#include<bits/stdc++.h>
using namespace std;
void group(char lisa[][2],int x)
{
    unordered_map<char,int>store;
    for(int i=0;i<x;i++)
    {
        int a=lisa[i][1];
        int b=lisa[i][0];
    if(store.find(lisa[i][1])!=store.end())
    {
        if(store.find(lisa[i][0])!=store.end())
            store[a]=store[b]+store[a]+1;
        else
            store[a]=store[a]+1;
    }
        else
            store[a]=1;
    }
    for (auto data : store)  
    {
        cout<<"Key = "<<data.first<< ", Value = "<<data.second<<endl;        
    }
}
int main() 
{
    char lisa[6][2];
        lisa[0][0]='A';
        lisa[0][1]='C';            
        lisa[1][0]='B';
        lisa[1][1]='C';
        lisa[2][0]='C';
        lisa[2][1]='F';
        lisa[3][0]='D';
        lisa[3][1]='E';
        lisa[4][0]='E';
        lisa[4][1]='F';
        lisa[5][0]='F';
        lisa[5][1]='F';
        group(lisa,6);
}
[[A,C],[B,C],[C,F],[D,E],[E,F],[F,F]]
{{A:0},{B,0},{C,2},{D,0},{E,1},{F,5}}

Комплекстик анализ

Убакыт татаалдыгы = O (N)

Бардык элементтер аркылуу өтүп жаткан бир циклди иштетсек

Космостун татаалдыгы = O (N)

Бардык ачкыч-жуптарды сактоо үчүн HashMap колдонуп жатабыз

Small Tweak

Эми, бизде кызматкерлердин маалыматтары боюнча гана эмес, ар бир кызматкердин маанилүүлүгү дагы камтылган. Бизде ар бир менеджердин маани-маңызын билдирип туруу милдети турат.

Келгиле, тийиштүү маалыматтарды карап чыгуу үчүн BFS жүргүзүп жатканда бир-бирден өтүп кетели

  • Биринчиден, биз a элементтерин коюп жатабыз кезек.
  • Бул кезек бошогончо, кийинки мүмкүнчүлүктөрдү карай беребиз
  • Экинчиден, кезекте турган эң жогорку элементти алабыз
  • Биз кызматкер кабыл алган кызматкерлердин тизмесин алабыз
  • Бул кызматкерлердин бардык кодекстерин үймөгүбүзгө салып жатабыз
  • Ошол эле учурда, биз импорттолгон нерселерди кошуп жатабыз
  • Ошентип, кезек бошогончо, импорттолгон нерселердин бардыгы даяр болот

Ар бир кызматкерге ылайык кызматкерлердин санын табуу үчүн Java коду

class Solution 
{
    public int getImportance(List<Employee> employees, int id) 
    {
        int sum=0;
        Queue<Integer>trav=new LinkedList<>();
        trav.add(id);
        while(!trav.isEmpty())
        {
            int cur=trav.remove();
            for(int i=0;i<employees.size();i++)
            {
                if(employees.get(i).id==cur)
                {
                    sum=sum+employees.get(i).importance;
                    List<Integer>nxt=employees.get(i).subordinates;
                    for(int j=0;j<nxt.size();j++)
                        trav.add(nxt.get(j));
                    break;
                }
            }
        }
        return sum;
    }
}

Ар бир кызматкерге ылайык кызматкерлердин санын табуу үчүн C ++ коду

class Solution 
{
public:
    int getImportance(vector<Employee*> employees, int id) 
    {
        int sum=0;
        queue<int>trav;
        trav.push(id);
        while(!trav.empty())
        {
            int cur=trav.front();
            trav.pop();
            for(int i=0;i<employees.size();i++)
            {
                if(employees[i]->id==cur)
                {
                    sum=sum+employees[i]->importance;
                    vector<int>nxt=employees[i]->subordinates;
                    for(int j=0;j<nxt.size();j++)
                        trav.push(nxt[j]);
                    break;
                }
            }
        }
        return sum;    
    }
};
[[1,5,[2,3]],[2,3,[]],[3,3,[]]] 1
11

Комплекстик анализ

Убакыттын татаалдыгы = O (V + E)

Космостун татаалдыгы = O (n)

V = Vertices саны

E = Четтердин саны

  • Биринчиден, V жолу өткөн кезекти бошотуп жатабыз. Циклде
    • Берилиштерди кезектен алып жатабыз = O (1) операциясы
    • Бардык коңшулардын четтерин басып өтүп, клонду алуу = O (Adj)
    • Кошуналарды кошуу = O (1) операциясы
  • Акырында, татаалдыкты жыйынтыктасак = V * (O (1) + O (Adj) + O (1))
  • Кайсы O (V) + O (V * Adj) чейин кайнайт
  • Убакытты татаалдаштыруу = O (V + E)
  • Космостун татаалдыгы O (n), анткени бизге кезекте туруу керек болчу

шилтемелер