Знайдзіце колькасць супрацоўнікаў пад кожным супрацоўнікам


Узровень складанасці Лёгка
Часта пытаюцца ў Акаліта GE Healthcare Microsoft Мынтра Qualcomm Synopsys Teradata
хэшавання

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 для захоўвання ўсіх пар ключ-значэнне

Невялікая хітрасць

Цяпер мы маем на ўвазе не толькі супрацоўніка па дадзеных работнікаў, але і забяспечваем яго важнасць. Перад намі стаіць галоўная задача - паведаміць аб важнасці кожнага кіраўніка.

Давайце пройдзем працэс адзін за адным, калі мы выконваем BFS для вывучэння адпаведных дадзеных

  • Па-першае, мы змяшчаем элементы ў чарга.
  • Мы будзем працягваць разглядаць наступныя магчымасці, пакуль гэтая чарга не стане пустой
  • Па-другое, мы атрымліваем самы верхні элемент з чаргі
  • Мы атрымліваем спіс супрацоўнікаў, якімі займаецца супрацоўнік
  • Мы змяшчаем усе гэтыя коды супрацоўнікаў у свой стэк
  • У той жа час мы дадаем значэнне, з якім мы сутыкнуліся
  • Такім чынам, пакуль чарга не апусцее, у нас будзе ўвесь імпарт гатовы

Код 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 = Колькасць вяршыняў

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), бо нам патрэбна была толькі чарга

Спасылкі