모든 직원 아래의 직원 수 찾기

난이도 쉽게
자주 묻는 질문 수행자 GE 헬스 케어 Microsoft 미트라 퀄컴 Synopsys 테라 데이타
해싱조회수 38

HashMap은 가장 유용한 데이터 구조 중 하나입니다. 모든 직원 아래에있는 직원 수를 찾는 것은 유명한 영화의 시작을 생각 나게하는 문제입니다. 꿈속에서 꿈꾸는 것과 비슷합니다. 여기에는 직원 밑에서 일하는 직원이 있습니다.

문제 정책

그렇다면이 문제를 어떻게 해결해야할까요?

잘. 누군가가 미국에서 근무하는 직원 수를 세는 지루한 작업을 할당했습니다.

먼저 문제가 제시된 방식을 테스트 케이스로 다루겠습니다.

첫 번째는 직원이고 두 번째는 관리자 인 문자 쌍이 제공됩니다. 다른 사람에게 배정 된 직원의 수를 찾아야합니다.

모든 직원 아래의 직원 수 찾기
테스트 케이스 표시

접근과 이념

문제에 접근 할 수있는 방법에는 여러 가지가 있습니다. 그러나 대부분의 방법은 시간이나 공간에 무겁습니다. 내가 여기서 언급 한 것이 그것에 대해 가장 좋은 방법 인 것 같았다.

  • 첫째, 데이터 구조를 마무리하는 동안 Hashmap이 문제를 해결하는 가장 좋은 방법이라는 것을 깨달았습니다.
  • 둘째, 효율적으로 사용하면 깨달았습니다. 하나의 루프로 충분했습니다.
  • 우리는 해시 맵을 유지하고 있습니다.
  • 해시 맵의 키는 직원입니다.
  • 해시 맵의 값은 그 아래에있는 직원 수입니다.
  • 우리는 루프를 실행하고 있습니다.
  • 관리자 용 키가 이미 있는지 매번 확인합니다.
  • 그렇게하면 이전 값에 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);
}

Java에서 C ++로 이동할 때 HashMap에서 unorder_map으로 전환하는 방법을 알 수 있습니다.

모든 직원 아래의 직원 수 찾기를위한 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 번 이상 실행되는 대기열을 비 웁니다. 루프에서
    • queue = O (1) 작업에서 데이터를 제거합니다.
    • 클론을 얻기 위해 모든 인접 가장자리를 순회 = O (Adj)
    • neighbours = O (1) 연산 추가
  • 마지막으로 복잡성을 합산하면 = V * (O (1) + O (Adj) + O (1))
  • 이는 O (V) + O (V * Adj)로 요약됩니다.
  • 시간 복잡도 = O (V + E) 만들기
  • 공간 복잡성은 O (n)입니다.

참조

Translate »