Знайдіть кількість працівників під кожним працівником


Рівень складності Легко
Часто запитують у Accolite GE Healthcare Microsoft Мінтра компанія Qualcomm Синопсис Терадата
Хешування

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), оскільки нам потрібна була лише черга

посилання