Pular para o conteudo principal
SeniorPath
Explorar conteudo
Menu / Fechar menu

24 de Março

Planejamento de cursos

Como transformar pre-requisitos em grafo dirigido e detectar quando uma dependência volta para ela mesma.

Grafos Intermediario 25 min TypeScript

#interviews#graphs#topological-sort#bfs#dfs

Você tem numCourses cursos numerados de 0 até numCourses - 1.

Cada par em prerequisites tem a forma [course, prereq] e significa:

  • para fazer course, você precisa concluir prereq antes

Retorne true se for possível concluir todos os cursos. Caso contrario, retorne false.

Exemplo:

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true

O que perceber antes de codar

  • O problema não pede necessariamente a ordem final. Pede saber se existe ciclo.
  • Dependência cria um grafo dirigido, não um grafo qualquer.
  • Visitar um no que já esta no caminho atual e sinal de ciclo.

Erros comuns

  • usar um único `visited` e esquecer a diferença entre "estou visitando agora" e "já terminei"
  • refazer a mesma busca muitas vezes sem memorizar os nos já resolvidos

Passo 1 - Traduzir o enunciado para grafo

O enunciado fica bem mais claro quando você para de pensar em "lista de pares" e passa a pensar em grafo:

  • cada curso e um vertice
  • cada dependência e uma aresta dirigida

Se um curso depende de outro, existe uma seta nessa relação.

Passo 2 - Entender o que torna a resposta impossivel

O único jeito de falhar de verdade e aparecer um ciclo.

Exemplo:

  • curso 0 depende de 1
  • curso 1 depende de 0

Isso significa que nenhum dos dois consegue começar.

Passo 3 - Escrever a versão inicial mais direta

Uma versão inicial razoavel e:

Funciona.

Mas pode repetir a mesma exploração várias vezes.

Passo 4 - Separar "em visita" de "já resolvido"

Aqui entram tres estados uteis:

  • 0: nunca visto
  • 1: estou visitando agora
  • 2: já explorei tudo abaixo e sei que esta seguro

Se você entra em um no com estado 1, encontrou ciclo. Se entra em um no com estado 2, não precisa explorar de novo.

O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.

Codigo inicial

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // sua solução aqui
  return false
}
solution.ts
Travado? Dicas disponiveis.

Ainda não resolveu?

Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.

Abrir a solucao de referencia

Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.

Solução

Complexidade final

Tempo: O(V + E)

Espaço: O(V + E)

Solução 1 - Busca em profundidade (DFS) com conjunto hash do caminho atual

Boa versão inicial porque o conceito de ciclo fica bem visível.

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = Array.from({ length: numCourses }, () => [])

  for (const [course, prereq] of prerequisites) {
    graph[course].push(prereq)
  }

  function hasCycle(course: number, path: Set<number>): boolean {
    if (path.has(course)) {
      return true
    }

    path.add(course)

    for (const prereq of graph[course]) {
      if (hasCycle(prereq, path)) {
        return true
      }
    }

    path.delete(course)
    return false
  }

  for (let course = 0; course < numCourses; course += 1) {
    if (hasCycle(course, new Set())) {
      return false
    }
  }

  return true
}

Funciona, mas repete trabalho demais.

Solução 2 - Busca em profundidade (DFS) com tres estados

Agora cada curso e explorado de forma mais inteligente.

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = Array.from({ length: numCourses }, () => [])

  for (const [course, prereq] of prerequisites) {
    graph[course].push(prereq)
  }

  const state = new Array(numCourses).fill(0)

  function dfs(course: number): boolean {
    if (state[course] === 1) {
      return false
    }

    if (state[course] === 2) {
      return true
    }

    state[course] = 1

    for (const prereq of graph[course]) {
      if (!dfs(prereq)) {
        return false
      }
    }

    state[course] = 2
    return true
  }

  for (let course = 0; course < numCourses; course += 1) {
    if (!dfs(course)) {
      return false
    }
  }

  return true
}

O insight forte não e a recursão em si. E separar “estou no caminho atual” de “já sei que esse subgrafo e seguro”.

O que dizer na entrevista

Uma explicação curta e boa seria:

Eu modelo os cursos como um grafo dirigido de dependências. O problema vira detecção de ciclo. Na versão forte, uso busca em profundidade (DFS) com tres estados: não visitado, visitando e resolvido. Se reencontro um no em estado visitando, achei um ciclo. Se o no já esta resolvido, não exploro de novo. A leitura por ordenacao topologica chega na mesma resposta pelo lado da busca em largura (BFS).

Isso mostra que você:

  • traduziu o problema para o modelo certo
  • identificou a causa real da impossibilidade
  • explicou por que não precisa refazer subgrafos já resolvidos

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

O ponto não e decorar esse problema.

O ponto e aprender a reconhecer dependências como grafo dirigido.
Proximo desafio Gerar parênteses Desafio anterior Cache LRU

Desafios relacionados

Número de ilhas

Maior substring sem caracteres repetidos

Três somas

Artigos relacionados

Enquadrar o problema antes de codificar

Reconhecer padrões em problemas

Como Explicar sua Solução sem se Perder