ყველა თანამშრომლის ქვეშ იპოვნეთ თანამშრომლების რაოდენობა  


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი GE Healthcare microsoft მიტრა Qualcomm ანოტაცია Teradata
ჰაშინგი

HashMaps მონაცემთა ერთ-ერთი ყველაზე სასარგებლო სტრუქტურაა. იპოვნეთ თანამშრომლების რაოდენობა ყველა თანამშრომლის ქვეშ, ეს არის პრობლემა, რომელიც ცნობილი ფილმის გახსენებას მახსენებს. Akin ოცნება ოცნება. აქ, ჩვენ გვყავს თანამშრომელი, რომელიც მუშაობს დასაქმებულის ქვეშ და ა.შ.

პრობლემის განცხადება  

რა უნდა გავაკეთოთ ამ საკითხისგან?

კარგად ვიღაცამ აშშ-ს დაავალა ეს მომაბეზრებელი ამოცანა - ითვლიან იმ თანამშრომლების რაოდენობას, ვინც მათ ქვეშ მუშაობს.

პირველ რიგში, მოდით განვსაზღვროთ საცდელი შემთხვევა, თუ როგორ წარმოგვიდგინეს პრობლემა:

მოცემულია სიმბოლოების წყვილი, რომელთაგან პირველი არის თანამშრომელი, ხოლო მეორე მენეჯერი. ჩვენ უნდა ვიპოვოთ თანამშრომლების რაოდენობა, რომლებიც სხვებისთვის არიან დანიშნულნი.

ყველა თანამშრომლის ქვეშ იპოვნეთ თანამშრომლების რაოდენობა
საცდელი შემთხვევის ჩვენება

მიდგომა და იდეოლოგია  

პრობლემების მოგვარების უამრავი მეთოდი არსებობს. ამასთან, გზების უმეტესობა ან დროზე მძიმეა, ან სივრცეში. ის, რაც აქ ვახსენე, საუკეთესო გზა ჩანდა ამის გასავლელად.

  • პირველ რიგში, მონაცემთა სტრუქტურების დასრულებისას მივხვდი, რომ Hashmaps პრობლემის გადაჭრის საუკეთესო გზა იყო
  • მეორეც, მივხვდი, თუ ეფექტურად გამოიყენებოდა. მხოლოდ ერთი მარყუჟი საკმარისი იყო.
  • ჩვენ ვიცავთ ჰეშმაპს.
  • ჰეშმაპის გასაღებები არიან თანამშრომლები
  • ჰეშმაპის მნიშვნელობა არის მათ ქვეშ მყოფი თანამშრომლების რაოდენობა
  • ჩვენ ვაწარმოებთ მარყუჟს.
  • ჩვენ ყოველ ჯერზე ვეძებთ, თუ მენეჯერის გასაღები უკვე გვაქვს
  • თუ ასეა, წინა მნიშვნელობას ვუმატებთ 1-ს
  • ყოველ ჯერზე ვეძებთ, თუ თანამშრომლის გასაღები უკვე გვაქვს
  • თუ ამას ვაკეთებთ, ჩვენ მისი ქსელის ქვეშ მყოფი ხალხი ვმუშაობთ
იხილეთ ასევე
მინიმალური ბილიკის ჯამი

ჯავის კოდი ყველა თანამშრომლის ქვეშ დასაქმებულთა რაოდენობის დასადგენად  

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- ს საკვანძო მნიშვნელობის ყველა წყვილის შესანახად

მცირე შესწორება  

ახლა ჩვენ არა მხოლოდ თანამშრომელი გვყავს დასაქმებულის მონაცემებით, არამედ მოცემულია თითოეული თანამშრომლის მნიშვნელობაც. ჩვენ გვევალება მამონტის ამოცანა, რომ ყველა მენეჯერისთვის შევატყობინოთ მნიშვნელობის ჯამი.

მოდით, პროცესი სათითაოდ გავიაროთ, როდესაც BFS- ს ვასრულებთ, შესაბამისი მონაცემების შესასწავლად

  • პირველ რიგში, ჩვენ ელემენტებს ვაყენებთ ა რიგში.
  • ჩვენ გავაგრძელებთ შემდეგ შესაძლებლობების განხილვას, სანამ ეს რიგი არ დაიცლება
  • მეორეც, რიგისგან მივიღებთ ყველაზე მაღალ ელემენტს
  • ჩვენ ვიღებთ თანამშრომელთა ჩამონათვალს, რომლებიც აიღო თანამშრომელმა
  • ჩვენ ყველა ამ თანამშრომლის კოდებს ვათავსებთ ჩვენს სტეკში
  • ამავდროულად, ჩვენ ვამატებთ იმ იმპორტს, რომელიც შეგვხვდა
  • ამრიგად, სანამ რიგი არ დაიცლება, ყველა იმპორტი მზად იქნება
იხილეთ ასევე
ორი ჯამი Leetcode ამოხსნა

ჯავის კოდი ყველა თანამშრომლის ქვეშ დასაქმებულთა რაოდენობის დასადგენად  

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 = ვერტიკების რაოდენობა

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), რადგან ჩვენ მხოლოდ რიგი გვჭირდებოდა

ლიტერატურა