SQL · Jerarquías: árbol binario y organigrama

Esta serie mantiene la mente fresca resolviendo, uno a uno, los ejercicios de HackerRank. Cada entrada toma un tema concreto y lo agota; todas las consultas están en MySQL salvo donde se indique.

Te invito a intentar cada ejercicio antes de leer la solución.

Aquí las filas dejan de ser independientes: una tabla que se une consigo misma para saber quién es padre de quién, y cinco tablas encadenadas que hay que contar sin duplicar.

BST

The BST table is described as follows:

Binary Tree Nodes

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Input Format

Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

• Root: If node is root node.
• Leaf: If node is leaf node.
• Inner: If node is neither root nor leaf node.

Sample Input

Sample Output

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

Explanation

The Binary Tree below illustrates the sample:

      5
    /   \
   2     8
  / \   / \
 1   3 6   9

• 5 is the root node (P is NULL).
• 2 and 8 are inner nodes (they have children).
• 1, 3, 6, 9 are leaf nodes (they have no children).
• The output is ordered by the node value.

Solución

En este ejercicio es más notoria la diferencia con los demás ejercicios hasta ahora. Empezando porque debemos realizar una comparación de una columna sobre otra dentro de la misma tabla para tener un conteo de sus padres, y si esos mismos nodos no tienen hijos, el conteo dará 0, ya que no son mencionados (contados) en ninguna parte. Por eso, al final del CTE agrupamos por N para saber si se repite en la columna P.

Ahora, debemos filtrar las coincidencias teniendo en cuenta lo anterior con CASE WHEN .. THEN .... La parte aislada de toda la lógica es el nodo Root, y para esto es importante revisar la columna P, y por esto hacemos un INNER JOIN vinculando la N de BST y la N de BST_MATCHES.

WITH 
  BST_MATCHS AS (
    SELECT 
      v1.N,
      COUNT(v2.P) AS MATCHES_BY_P 
    FROM 
      BST v1 
      LEFT JOIN BST v2 ON v1.N = v2.P 
    GROUP BY 
      v1.N 
    ORDER BY 
      v1.N
  ) 
SELECT 
  v1.N, 
  CASE WHEN v2.P IS NULL THEN "Root" WHEN v1.MATCHES_BY_P = 0 THEN 'Leaf' ELSE "Inner" END 
FROM 
  BST_MATCHS v1 
  INNER JOIN BST v2 ON v2.N = v1.N 
ORDER BY
  N;

Company

New Companies

Amber's conglomerate corporation just acquired some new companies. Each of the companies follows this hierarchy:

Founder | Lead Manager | Senior Manager | Manager | Employee

Given the table schemas below, write a query to print the company_code, founder name, total number of lead managers, total number of senior managers, total number of managers, and total number of employees. Order your output by ascending company_code.

Note:

• The tables may contain duplicate records.
• The company_code is string, so the sorting should not be numeric. For example, if the company_codes are C_1, C_2, and C_10, then the ascending company_codes will be C_1, C_10, and C_2.

Input Format

The following tables contain company data:

• Company: The company_code is the code of the company and founder is the founder of the company.

• Lead_Manager: The lead_manager_code is the code of the lead manager, and the company_code is the code of the working company.

• Senior_Manager: The senior_manager_code is the code of the senior manager, the lead_manager_code is the code of its lead manager, and the company_code is the code of the working company.

• Manager: The manager_code is the code of the manager, the senior_manager_code is the code of its senior manager, the lead_manager_code is the code of its lead manager, and the company_code is the code of the working company.

• Employee: The employee_code is the code of the employee, the manager_code is the code of its manager, the senior_manager_code is the code of its senior manager, the lead_manager_code is the code of its lead manager, and the company_code is the code of the working company.

Sample Input

Company

Lead_Manager

Senior_Manager

Manager

Employee

Sample Output

C1 Monika 1 2 1 2
C2 Samantha 1 1 2 2

Explanation

In company C1, the only lead manager is LM1. There are two senior managers, SM1 and SM2, under LM1. There is one manager, M1, under senior manager SM1. There are two employees, E1 and E2, under manager M1.

In company C2, the only lead manager is LM2. There is one senior manager, SM3, under LM2. There are two managers, M2 and M3, under senior manager SM3. There is one employee, E3, under manager M2, and another employee, E4, under manager M3.

Solución

Bueno, mi solución principalmente fue empezando con ventanas, creo que solamente me termine complicando aunque me dio resultados, pero mi problema era que al usar INNER JOIN con ventanas se duplicaban resultados por tantas combinaciones, y entonces termine optando por optimizando mas la query y haciéndolo mas simplificado usando LEFT JOIN por separado y así hacer el recuerdo respecto de cada tabla y como igualmente habían datos duplicados usamos DISTINCT. ¡Sin duda, fue un buen ejercicio intermedio!

SELECT 
  c.company_code, 
  c.founder, 
  lm.total_lead_manager, 
  sm.total_senior_manager, 
  m.total_manager, 
  e.total_employee 
FROM 
  Company c 
  LEFT JOIN (
    SELECT 
      company_code, 
      COUNT(DISTINCT lead_manager_code) AS total_lead_manager 
    FROM 
      Lead_Manager 
    GROUP BY 
      company_code
  ) lm ON lm.company_code = c.company_code 
  LEFT JOIN (
    SELECT 
      company_code, 
      COUNT(DISTINCT senior_manager_code) AS total_senior_manager 
    FROM 
      Senior_Manager 
    GROUP BY 
      company_code
  ) sm ON sm.company_code = c.company_code 
  LEFT JOIN (
    SELECT 
      company_code, 
      COUNT(DISTINCT manager_code) AS total_manager 
    FROM 
      Manager 
    GROUP BY 
      company_code
  ) m ON m.company_code = c.company_code 
  LEFT JOIN (
    SELECT 
      company_code, 
      COUNT(DISTINCT employee_code) AS total_employee 
    FROM 
      Employee 
    GROUP BY 
      company_code
  ) e ON e.company_code = c.company_code 
ORDER BY 
  c.company_code ASC;