Coding Interview Prep · Lezione

Attraversare un organigramma

Percorrere una gerarchia dipendente-manager a qualsiasi profondità

Attraversare un organigramma è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

La domanda sull'organigramma

"Data una tabella employees con id, name e manager_id, elenchi tutte le persone subordinate a un determinato manager, a qualsiasi profondità." Questo è uno dei quesiti più comuni nei colloqui sulle CTE ricorsive.

La tabella è autoreferenziale: manager_id rimanda all'id di un'altra riga. In questa lezione la percorrerà sia verso il basso, per trovare i subordinati, sia verso l'alto, per ricostruire la catena gerarchica.

La tabella di esempio

Immagini questi dati. Il CEO ha NULL come manager. Tutti gli altri fanno riferimento a un manager nella catena gerarchica.

1 Ada (manager NULL)
2 Ben (manager 1)
3 Cleo (manager 1)
4 Dan (manager 2)
5 Eve (manager 4)

La profondità è quindi: Ada → Ben → Dan → Eve. Lo tenga presente mentre percorriamo la struttura.

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    manager_id INT REFERENCES employees(id)
);

Percorrere la gerarchia verso il basso da un manager

Per elencare tutti i subordinati di un manager scelto, il membro di ancoraggio seleziona quel manager, oppure i suoi subordinati diretti, e il membro ricorsivo segue manager_id verso il basso.

Qui partiamo da Ben (id 2) e raccogliamo tutte le persone sotto di lui.

WITH RECURSIVE subtree AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees WHERE id = 2
    UNION ALL
    SELECT e.id, e.name, e.manager_id, s.depth + 1
    FROM employees e
    JOIN subtree s ON e.manager_id = s.id
)
SELECT name, depth FROM subtree ORDER BY depth;

Leggere il risultato

La query qui sopra restituisce Ben alla profondità 1, Dan alla profondità 2 ed Eve alla profondità 3. Il membro di ancoraggio ha inizializzato Ben; la prima iterazione ha trovato Dan, il cui manager è Ben; la seconda iterazione ha trovato Eve, il cui manager è Dan; la terza iterazione non ha trovato nessuno, quindi la ricorsione si è arrestata.

Se l'intervistatore chiede "a quanti livelli sotto Ben si trova Eve?", la colonna depth risponde direttamente: 3 meno 1 equivale a 2 livelli.

Risale fino al CEO

La domanda inversa è altrettanto comune: "Mostri l'intera catena gerarchica di Eve fino al CEO." Inverta la direzione della JOIN — il membro ricorsivo ora segue manager_id della riga corrente verso il genitore.

WITH RECURSIVE chain AS (
    SELECT id, name, manager_id, 1 AS lvl
    FROM employees WHERE id = 5
    UNION ALL
    SELECT e.id, e.name, e.manager_id, c.lvl + 1
    FROM employees e
    JOIN chain c ON e.id = c.manager_id
)
SELECT name, lvl FROM chain ORDER BY lvl;

Dal basso verso l'alto: si inverte la JOIN

L'unica differenza strutturale tra percorrere la gerarchia verso il basso e percorrerla verso l'alto è la condizione di JOIN:

Verso il basso (trovare i subordinati): e.manager_id = cte.id — abbina i dipendenti il cui manager è una riga già presente.
Verso l'alto (trovare i manager): e.id = cte.manager_id — abbina il dipendente il cui id è il manager della riga corrente.

Saper spiegare chiaramente questa inversione impressiona gli intervistatori.

Creare un albero indentato

Una risposta ben curata formatta il risultato come un albero indentato, usando depth per ripetere gli spazi. Questo dimostra che sa presentare i risultati gerarchici, non soltanto calcolarli.

WITH RECURSIVE org AS (
    SELECT id, name, 1 AS depth
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT REPEAT('  ', depth - 1) || name AS tree
FROM org
ORDER BY depth;

Accumulo del percorso

Per mostrare il percorso completo dal CEO a ogni persona, mantenga una stringa path. È la stessa tecnica della lezione precedente, applicata all'organigramma.

WITH RECURSIVE org AS (
    SELECT id, name, CAST(name AS VARCHAR(500)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, o.path || ' / ' || e.name
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT name, path FROM org ORDER BY path;

Contare i subordinati per manager

Una domanda di approfondimento frequente è: "Quante persone riportano direttamente o indirettamente a ciascun manager?" Usi il sottoalbero ricorsivo per ogni manager, quindi aggreghi i risultati. Uno schema comune consiste nell'eseguire la ricorsione una volta per ogni radice e usare GROUP BY sul manager iniziale.

Qui contiamo tutti i subordinati indiretti di Ada, il CEO, percorrendo l'intero albero e contando le righe sotto la radice.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 0 AS depth
    FROM employees WHERE id = 1
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT COUNT(*) - 1 AS total_reports FROM org;

Errori comuni

Faccia attenzione a queste insidie tipiche dei colloqui:

Direzione errata della JOIN — usare e.manager_id = cte.id quando si voleva risalire restituisce l'insieme sbagliato.
Dimenticare il filtro del membro di ancoraggio — omettere WHERE id = X inizializza ogni riga e restituisce l'intera foresta.
Errore di uno nella profondità — decida se il seme ha profondità 0 o 1 e mantenga questa convenzione.

Perché non usare semplicemente una self-join?

Una self-join può recuperare un numero fisso di livelli: una JOIN per i subordinati diretti, due per quelli di secondo livello e così via. Tuttavia, è necessario conoscere in anticipo la profondità e scrivere una JOIN per ogni livello.

Una CTE ricorsiva gestisce una profondità arbitraria e sconosciuta con una sola query. Quando un intervistatore dice "la gerarchia può avere un numero qualsiasi di livelli", sta escludendo le semplici self-join e indicando la ricorsione.

Verifica rapida

Si assicuri di saper invertire la direzione dell'attraversamento.

Riepilogo

L'attraversamento di un organigramma è lo schema ricorsivo applicato a una tabella autoreferenziale:

Verso il basso: si inizializza un manager e si esegue il join e.manager_id = cte.id.
Verso l'alto: si inizializza un dipendente e si esegue il join e.id = cte.manager_id.
Si mantengono depth per l'indentazione e path per l'intera catena.
La ricorsione gestisce qualsiasi profondità sconosciuta, cosa che un self-join non può fare.

Successivamente: usare la ricorsione per generare serie di numeri e di date.

Domande Frequenti

La lezione «Attraversare un organigramma» è gratuita?

Sì — il testo completo di «Attraversare un organigramma» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Attraversare un organigramma»?

Percorrere una gerarchia dipendente-manager a qualsiasi profondità Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Attraversare un organigramma»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a Coding Interview Prep