0Pricing
Coding Interview Prep · Aula

Reconhecendo um problema de lacunas e ilhas

Identifique o padrão em um problema descrito em palavras e o princípio central de agrupamento.

Reconhecendo um problema de lacunas e ilhas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

O padrão que os entrevistadores estão testando

Quando um entrevistador sênior pede que você encontre sequências consecutivas de algo, você está diante de um problema de lacunas e ilhas. O nome vem de uma imagem mental: as linhas que pertencem juntas formam uma ilha, e as interrupções entre elas são lacunas.

  • Uma ilha é uma sequência máxima de linhas adjacentes segundo alguma regra (números inteiros consecutivos, datas consecutivas ou o mesmo status repetido).
  • Uma lacuna é o espaço ausente entre duas ilhas.

Reconhecer esse tipo de problema imediatamente já é, por si só, um sinal de senioridade. Muitos candidatos recorrem a um emaranhado de autojunções; a resposta elegante quase sempre usa funções de janela.

Enunciados que escondem uma ilha

O desafio é que os entrevistadores raramente dizem "lacunas e ilhas". Eles disfarçam o problema. Treine seu ouvido para expressões como:

  • "Encontre cada período em que um usuário esteve continuamente inscrito."
  • "Por quantos dias consecutivos o servidor permaneceu ativo?"
  • "Quais intervalos de IDs estão ausentes nesta tabela?"
  • "Agrupe linhas adjacentes com o mesmo status em uma única linha."

Todos esses casos têm a mesma estrutura: agrupe as linhas que estão próximas umas das outras e, depois, informe o início, o fim ou a ausência desses grupos. Depois que você traduz as palavras em ilhas, o SQL praticamente se escreve sozinho.

A ideia central: criar uma chave de grupo

Eis todo o truque em uma frase: se você conseguir atribuir a todas as linhas da mesma ilha uma chave de grupo idêntica, um simples GROUP BY poderá transformar cada ilha em uma única linha de resumo.

Portanto, o trabalho real em qualquer problema de lacunas e ilhas é calcular essa chave de grupo. Variantes diferentes a calculam de maneiras diferentes, mas todas compartilham esse objetivo. Depois que você tem a chave, a etapa final é trivial:

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

Um conjunto de dados concreto

Vamos partir dos dados. Imagine uma tabela logins que registra em quais números de dia um usuário entrou:

  • Dias presentes: 1, 2, 3, 7, 8, 10

Observando os dados, as ilhas são {1,2,3}, {7,8} e {10}. As lacunas são os dias 4 a 6 e o dia 9. Em uma entrevista, sua tarefa é fazer o banco de dados identificar essas três ilhas sem que você as aponte manualmente. Tenha este pequeno conjunto de dados em mente enquanto exploramos cada técnica.

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

Por que as abordagens ingênuas falham

Um primeiro impulso comum é comparar cada linha com a próxima usando uma autojunção e marcar as interrupções. Isso funciona para encontrar uma única lacuna, mas rapidamente se torna difícil de administrar:

  • Você precisa detectar tanto o início quanto o fim de cada ilha, o que significa fazer duas passagens ou duas junções.
  • As linhas das extremidades (a primeira e a última) exigem um tratamento especial.
  • Isso não se generaliza para "mostre o comprimento de cada sequência" sem mecanismos adicionais.

Os entrevistadores observam se você entra em uma guerra de autojunções ou reconhece que uma única passagem com uma função de janela é mais simples.

O modelo mental para detectar lacunas

Uma forma robusta de pensar é: uma nova ilha começa sempre que a linha atual não é adjacente à linha anterior. Use LAG para voltar uma linha e comparar.

Se day_no - LAG(day_no) for maior que 1 (ou NULL para a primeira linha), essa linha inicia uma nova ilha. Marcamos isso com um indicador igual a 1; caso contrário, usamos 0. Observe como esses indicadores ficam para os nossos dados.

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

Transformando indicadores em uma chave de grupo

Os indicadores da etapa anterior são 1, 0, 0, 1, 0, 1 para os dias 1,2,3,7,8,10. Observe que a soma acumulada desses indicadores produz um número que permanece constante dentro de uma ilha e aumenta a cada nova ilha: 1,1,1,2,2,3.

Essa soma acumulada é a nossa chave de grupo criada. Envolvemos a consulta dos indicadores em uma CTE e fazemos a soma com outra função de janela:

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

Concluindo o exemplo resolvido

Agora acrescente o GROUP BY final sobre a chave de grupo. Cada valor distinto de grp representa uma ilha, e informamos seus limites e seu tamanho:

O resultado corresponde exatamente às três ilhas que identificamos visualmente: 1-3 (comprimento 3), 7-8 (comprimento 2) e 10-10 (comprimento 1). Essa receita de três camadas (indicador, soma acumulada e agrupamento) é a base de quase todas as respostas sobre lacunas e ilhas que você escreverá.

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

A adjacência é específica do domínio

A única parte que muda entre os problemas é a definição de adjacente. Reconhecer a regra correta de adjacência é metade do processo de reconhecer o problema:

  • Inteiros: são adjacentes quando a diferença é exatamente 1.
  • Dias do calendário: são adjacentes quando uma data é o dia seguinte (date = prev + INTERVAL '1 day').
  • Períodos de status: são adjacentes quando o valor do status não muda em relação à linha anterior.

A estrutura é a mesma, mas a comparação dentro do CASE muda. Identificar qual regra de adjacência se aplica é a pergunta de esclarecimento que você deve fazer em voz alta na entrevista.

Perguntas de esclarecimento a fazer

Antes de escrever uma linha de SQL, ganhe pontos esclarecendo o escopo. Boas perguntas de esclarecimento sobre lacunas e ilhas:

  • "Devo tratar os dados por usuário ou globalmente?" (Isso determina se você adicionará PARTITION BY user_id.)
  • "Pode haver valores duplicados no mesmo dia, e eles interrompem ou prolongam uma sequência?"
  • "Você quer as ilhas, as lacunas ou ambas?"
  • "A sequência é garantidamente ordenada ou devo ordená-la?"

Fazer essas perguntas mostra que você já resolveu esse tipo de problema antes e entende seus casos extremos.

Ilhas por grupo com PARTITION BY

Os dados reais de entrevistas quase sempre são agrupados, por exemplo, logins por usuário. A correção é mecânica: adicione PARTITION BY user_id a cada função de janela para que as ilhas nunca atravessem os limites entre usuários.

A estrutura é idêntica; basta particionar. É por isso que dominar primeiro o caso de uma única sequência compensa: passar para uma análise por grupo exige apenas uma alteração de cláusula.

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

Verificação rápida

Teste seu instinto de reconhecimento de padrões.

Recapitulação: reconhecendo o formato

Agora você consegue identificar um problema de lacunas e ilhas pelo seu disfarce e nomear a estratégia:

  • Palavras-gatilho: consecutivo, contínuo, ininterrupto, sequência, intervalos ausentes, agrupar linhas adjacentes.
  • Ideia central: atribua a todas as linhas da mesma sequência uma chave de grupo idêntica e, depois, faça GROUP BY por essa chave.
  • Receita: marque novas ilhas com LAG, transforme os indicadores em uma chave usando uma soma acumulada e, depois, agregue.
  • A adjacência é específica do domínio (inteiros, datas ou status inalterado).
  • Adicione PARTITION BY para análises por grupo e esclareça o escopo antes de programar.

Em seguida, vamos aprimorar o método mais elegante de criar a chave: o truque da diferença entre números de linha.

Perguntas Frequentes

A aula “Reconhecendo um problema de lacunas e ilhas” é grátis?

Sim — o texto completo de “Reconhecendo um problema de lacunas e ilhas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Reconhecendo um problema de lacunas e ilhas”?

Identifique o padrão em um problema descrito em palavras e o princípio central de agrupamento. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Reconhecendo um problema de lacunas e ilhas”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Reconhecendo um problema de lacunas e ilhas
  2. O truque da diferença de números de linha
  3. Encontrando lacunas em uma sequência
  4. Ilhas com mudanças de data e status
← Voltar para Coding Interview Prep