A seção algorítmica com a escrita de código em um quadro-negro ou papel é uma das etapas mais importantes de uma entrevista de emprego para os desenvolvedores conseguirem um emprego no Yandex. Decidimos conversar com mais detalhes sobre como essas seções são organizadas para ajudar futuros candidatos a se prepararem. Além disso, espero que muitos daqueles que não se atrevam a ir a Yandex para uma entrevista, com medo de testes muito difíceis, depois desta história entendam que, na realidade, tudo não é tão assustador!
Por isso, preparamos os seguintes materiais para você:
- Um concurso especial contendo tarefas semelhantes às que oferecemos para a entrevista.
- Este post . Explica por que você precisa conduzir essas seções, bem como entender todas as tarefas do concurso.
- Dois vídeos nos quais as tarefas do concurso são organizadas: no primeiro - a tarefa é mais simples, no segundo - duas tarefas são mais difíceis. Nesses vídeos, você aprenderá sobre os erros típicos cometidos ao passar pelas seções algorítmicas e ao escrever o código de produção.
Como entrevistamos desenvolvedores
Uma entrevista com qualquer desenvolvedor consiste em várias etapas:
- seção preliminar com um recrutador;
- entrevista técnica no skype;
- várias seções em tempo integral;
- entrevistas finais com os gerentes de contratação.
Na seção preliminar, o recrutador se familiariza com o candidato, aprende seus interesses e motivos para entender quais posições faz sentido considerá-lo. Uma entrevista técnica do Skype destina-se a uma avaliação preliminar das habilidades de um candidato e elimina aqueles que definitivamente não serão capazes de lidar com as seções de período integral.
Seções em tempo integral - o palco principal. São seções em tempo integral que respondem à pergunta sobre o que um candidato pode fazer. A seção algorítmica é uma das seções técnicas em período integral. Além da algorítmica, existem outros testes presenciais: por exemplo, os candidatos a desenvolvedores seniores devem passar pela seção de arquitetura, e os futuros líderes também responderão a perguntas sobre gerenciamento de equipes e projetos. Em geral, se um candidato tiver algum tipo de força em um campo específico (aprendizado de máquina, otimização de baixo nível, desenvolvimento de sistemas altamente carregados, desenvolvimento móvel ou qualquer outro), organizaremos uma seção com um especialista especializado.
A seção algorítmica verifica se o candidato é capaz de criar algoritmos para resolver problemas simples, avaliar a complexidade desses algoritmos e implementá-los sem erros, mantendo um equilíbrio entre a qualidade dos testes e a velocidade da solução.
Por que escrever código em um quadro-negro ou papel
Um estado natural para um programador é a programação em um ambiente de desenvolvimento integrado com destaque e rastreabilidade de sintaxe. Portanto, em uma entrevista, a ideia de escrever código em um quadro-negro ou papel inicialmente não parece muito natural. No entanto, esse método permite verificar duas propriedades muito importantes para cada desenvolvedor.
O primeiro deles é a capacidade de lidar rapidamente com o desempenho do código "a olho nu". Imagine que, ao escrever cada ciclo que aparece no programa, o desenvolvedor precise gastar tempo tentando verificar seu desempenho rastreando; ou que, quando um serviço falha na produção, ele sempre precisa executar o código no depurador. É claro que escrever e depurar até programas simples levará um tempo inaceitavelmente longo. Obviamente, é útil poder ler o código com revisões de código.
A segunda propriedade importante é a capacidade de pensar em um plano de solução com antecedência e segui-lo. Se não houver plano, isso levará a um grande número de correções, rasuras (em papel) e a reescrita de grandes partes de código. Na vida real, tudo isso diminui bastante o desenvolvimento, mas é parcialmente mascarado pela velocidade do trabalho no editor de código. Cartão e papel nesse sentido são superfícies impiedosas.
Naturalmente, levamos em conta que escrever código manualmente não é muito rápido. Portanto, nossas tarefas geralmente envolvem resolver não muito mais do que uma dúzia de linhas, e o número de tarefas que precisam ser resolvidas em uma seção é geralmente duas ou três.
Seções algorítmicas e programação esportiva
A programação esportiva está se desenvolvendo no futuro desenvolvedor, entre outras coisas, e a capacidade de rápida e sem erros implementar algoritmos simples de acordo com um plano predeterminado. Portanto, candidatos com experiência em programação esportiva realmente fazem um bom trabalho com as seções algorítmicas em entrevistas. Muitas vezes, é possível observar uma situação em que futuros trainees podem lidar facilmente com a seção algorítmica, resolvendo todos os problemas em 15 a 20 minutos, enquanto programadores mais experientes passam uma hora nas mesmas tarefas.
Ao mesmo tempo, a seção algorítmica com código de escrita é apenas uma das seções que testa as habilidades mínimas necessárias para qualquer desenvolvedor. Esta seção será tratada não apenas pelos programadores do Olympiad, mas também por desenvolvedores industriais experientes. O futuro desenvolvedor sênior ou líder de equipe certamente está aguardando a seção de arquitetura, na qual ele poderá revelar seus pontos fortes; Obviamente, esta seção nunca é colocada para estagiários e desenvolvedores juniores.
Concurso de Preparação para Entrevistas
Especialmente para que você possa imaginar o conteúdo das tarefas que fornecemos nas seções algorítmicas, montamos um concurso que pode ser usado na preparação de entrevistas. Tente resolver todos os problemas sem executar o depurador uma vez; escreva uma solução no bloco de notas sem realçar a sintaxe; encontre a solução mais curta possível que passará em todos os testes; pense sobre todos os problemas possíveis com antecedência e passe a solução pela primeira vez.
O concurso contém cinco tarefas. Você pode tentar resolvê-los você mesmo ou ler a análise com antecedência: ainda será útil, porque Você será capaz de treinar sua habilidade de codificação sem erros de um algoritmo conhecido anteriormente.
Análise de tarefas do concursoTarefa A. Pedras e jóias
Duas linhas de caracteres latinos minúsculos são fornecidas: cadeia J e cadeia S. Os caracteres incluídos na cadeia J são “jóias” e incluídos na cadeia S são “pedras”. É necessário determinar quantos caracteres de S são simultaneamente "jóias". Simplificando, você precisa verificar quantos caracteres de S estão em J.
Essa é uma tarefa de aquecimento muito simples, que inclui soluções em várias linguagens de programação, para que os participantes possam se acostumar com o sistema de teste.
O algoritmo é bastante simples: você precisa construir um conjunto a partir de uma linha com "jóias", depois seguir a linha com "pedras" e verificar cada caractere para inclusão neste conjunto. Use essa implementação do conjunto para garantir a complexidade linear da solução resultante, apesar de as linhas de entrada serem muito curtas e, portanto, é possível passar mesmo um algoritmo quadrático em complexidade.
Problema B. Unidades consecutivas
É necessário encontrar a seqüência mais longa de unidades no vetor binário e imprimir seu comprimento.
O algoritmo da solução é o seguinte: percorra todos os elementos da matriz; quando você encontra um, precisa aumentar o contador para a duração da sequência atual e, quando encontra zero, precisa redefinir esse contador. No final, você precisa exibir o máximo dos valores que o contador assumiu.
Verifique se você está lidando com a situação quando a matriz termina com a sequência de unidades desejada. Com uma implementação cuidadosa, essa situação não requer processamento especial.
Tente usar apenas a quantidade constante de memória adicional.
Tarefa C. Remoção duplicada
É fornecida uma matriz de números inteiros de 32 bits ordenados em ordem não decrescente. É necessário remover todas as repetições dele.
O algoritmo correto processa sequencialmente os elementos da matriz, comparando-os com a última saída. Lembre-se de atualizar a variável que contém o último elemento exibido e, além disso, não cometer erros ao processar o último elemento.
Para resolver esse problema, você não precisa usar memória adicional.
Tarefa D. Geração de sequências de colchetes
Dado um número inteiro . É necessário imprimir todas as seqüências de colchetes corretas encomendada lexicograficamente (consulte https://ru.wikipedia.org/wiki/Lexographic_order ). Somente parênteses são usados na tarefa.
Este é um exemplo de um problema algorítmico relativamente complexo. Geraremos uma sequência de um caractere; a cada momento, podemos atribuir um colchete de abertura ou de fechamento à sequência atual. Você pode adicionar um colchete de abertura se menos de n colchetes de abertura tiverem sido adicionados anteriormente e um colchete de fechamento se, na sequência atual, o número de colchetes exceder o número de colchetes de abertura. Tal algoritmo, com implementação cuidadosa, garante automaticamente a ordem lexicográfica na resposta; trabalha em um tempo proporcional ao produto do número de elementos na resposta a n; isso requer uma quantidade linear de memória adicional.
Um exemplo de algoritmo ineficaz seria o seguinte: geramos todas as sequências de colchetes possíveis e, em seguida, apenas produzimos aquelas que acabam sendo corretas. Ao mesmo tempo, o volume da resposta não permitirá resolver o problema mais rapidamente do que o algoritmo que resultará acima.
Problema E. Anagramas
Essa tarefa bastante simples é um exemplo típico de um problema, cuja solução é necessária para usar matrizes associativas. Ao decidir, é necessário considerar que os caracteres podem ser repetidos, portanto, você deve usar não conjuntos, mas dicionários. Portanto, a solução será a seguinte: compomos a partir de cada linha um dicionário que, para cada caractere, armazena o número de suas repetições; depois compare os dicionários resultantes. Se eles coincidirem, é necessário imprimir uma unidade, caso contrário - zero.
Solução alternativa: classifique as linhas de entrada e compare-as. Essa solução é pior, pois é mais lenta e também altera a entrada. Mas esta solução não usa memória adicional.
Se durante a entrevista você teve várias soluções que diferem em suas características, conte-nos. É sempre bom quando o desenvolvedor conhece várias opções para resolver o problema e pode falar sobre seus pontos fortes e fracos.
Tarefa F. Mesclar listas ordenadas
Dado matrizes de números inteiros não negativos, classificadas em ordem não decrescente, cada uma das quais não excede 100. É necessário construir o resultado de sua fusão: uma matriz classificada em ordem não decrescente, contendo todos os elementos do original matrizes. O comprimento de cada matriz não excede .
Para cada matriz, crie um ponteiro; Inicialmente, cada ponteiro está localizado no início da matriz correspondente. Colocaremos os elementos correspondentes às posições dos ponteiros em qualquer estrutura de dados que suporte a extração de um mínimo - pode ser um multiset ou, por exemplo, um heap. Em seguida, extrairemos o elemento mínimo dessa estrutura, responderemos, mudaremos a posição do ponteiro na matriz correspondente e colocaremos o próximo elemento dessa matriz na estrutura de dados.
Nesta tarefa, muitos têm dificuldade com o formato de entrada. Observe que os primeiros elementos das linhas não descrevem os elementos das matrizes, eles descrevem os comprimentos das matrizes!
Perguntas frequentes sobre o concurso
R: Definitivamente escrevi o código correto, mas os testes falham; provavelmente um erro neles?
P: Não, todos os testes estão corretos. Pense: você provavelmente não previu nenhuma situação incomum.
R: Escrevo em X, ele definitivamente precisa de mais memória na tarefa Y. Aumente os limites!
P: Todos os limites são definidos de forma que seja possível uma solução usando qualquer um dos idiomas disponíveis. Tente verificar se você acidentalmente leu todo o arquivo de entrada em tarefas com limites estritos de memória.
R: Algumas tarefas podem ser resolvidas com muito mais facilidade devido às limitações indicadas. Por que você está fazendo isso?
P: Simplificamos especificamente a entrada em algumas tarefas, para que os participantes se dediquem mais facilmente à implementação do algoritmo e não pensem, por exemplo, na velocidade do download de dados ou em outras coisas importantes na programação esportiva. Tente implementar exatamente os algoritmos que recomendamos - somente nessa situação você obterá o máximo benefício do concurso.
A: Eu não quero passar no concurso. Não posso?
Q: claro! O concurso não é obrigatório para todos os candidatos. No entanto, ainda recomendo resolvê-lo: será útil em qualquer caso.
A: O que mais você recomendaria para a preparação?
P: Leia nossas dicas na página oficial sobre entrevistas no Yandex: https://yandex.ru/jobs/ya-interview . Por conta própria, acrescentarei que a solução de problemas no leetcode.com é extremamente útil para qualquer desenvolvedor que pratique, independentemente de planejar uma entrevista em um futuro próximo ou participar de competições de programação. Mesmo uma pequena quantidade de prática permite que você se sinta mais confiante ao resolver tarefas de trabalho.
Conclusão
Frequentemente, assisto a conferências para desenvolvedores e gerentes de desenvolvimento, sou membro de muitas conversas sobre desenvolvimento, conduzi várias centenas de entrevistas e contratou um grande número de desenvolvedores no Yandex. A experiência sugere que seções algorítmicas com código de escrita em um quadro ou papel geralmente levantam questões. Concluindo, responderei aos mais populares deles.
Por que entrevistar em condições tão diferentes das reais condições de trabalho do desenvolvedor?
Isso permite que você entenda se o candidato pode encontrar problemas nos programas sem iniciar o depurador; se ele pode apresentar um plano do algoritmo com antecedência e segui-lo com precisão; ele pode criar um conjunto pequeno, mas suficiente de testes e depois verificar sua implementação em relação a esse conjunto de testes.
Essas seções oferecem uma vantagem injusta aos programadores esportivos?
A programação esportiva desenvolve algumas habilidades muito úteis nos desenvolvedores; portanto, os participantes da programação das Olimpíadas realmente se saem bem nas seções algorítmicas. Portanto, há uma vantagem, mas é justo. A seção algorítmica é apenas uma dentre muitas, portanto cada candidato terá oportunidades suficientes para mostrar seus pontos fortes!
Por que realizar seções algorítmicas se todos os algoritmos foram implementados por um longo tempo e você só precisa procurar a implementação deles em bibliotecas prontas?
Nas seções algorítmicas comuns a todos os desenvolvedores, testamos apenas as habilidades mínimas necessárias: a capacidade de apresentar e sem erros para implementar um algoritmo simples que contém loops, condições de verificação e possivelmente requer o uso de matrizes associativas. Esse tipo de código é constantemente escrito para implementar serviços do usuário.
Qual é o ponto em uma seção que não testa uma enorme quantidade de habilidades de desenvolvedor?
A seção algorítmica, de fato, verifica apenas o conjunto mínimo de habilidades necessárias para qualquer desenvolvedor. Testamos outras habilidades com a ajuda de outras seções.
Você realiza seções algorítmicas para desenvolvedores de todas as especialidades?
Sim As seções algorítmicas são realizadas para desenvolvedores de back-end, analistas, desenvolvedores de dispositivos móveis e front-end, desenvolvedores de infraestrutura e métodos de aprendizado de máquina e assim por diante.