La sección algorítmica con escribir código en una pizarra o papel es una de las etapas más importantes de una entrevista de trabajo para que los desarrolladores obtengan un trabajo en Yandex. Decidimos hablar con más detalle sobre cómo se organizan estas secciones para ayudar a los futuros candidatos en la preparación. Además, espero que muchos de los que no se atreven a venir a Yandex para una entrevista, por temor a las pruebas demasiado difíciles, ¡después de esta historia entiendan que en realidad no todo es tan aterrador!
Así que hemos preparado los siguientes materiales para usted:
- Un concurso especial que contiene tareas similares a las que damos para la entrevista.
- Esta publicación Explica por qué necesita llevar a cabo tales secciones, así como comprender todas las tareas del concurso.
- Dos videos en los que se clasifican las tareas del concurso: en el primero , la tarea es más simple, en el segundo , dos tareas son más difíciles. De estos videos aprenderá sobre los errores típicos cometidos al pasar por las secciones algorítmicas y al escribir el código de producción.
Cómo entrevistamos a los desarrolladores
Una entrevista con cualquier desarrollador consta de varias etapas:
- sección preliminar con un reclutador;
- entrevista técnica de skype;
- varias secciones a tiempo completo;
- entrevistas finales con gerentes de contratación.
En la sección preliminar, el reclutador se familiariza con el candidato, aprende sus intereses y motivos para comprender qué posiciones tiene sentido considerarlo. Una entrevista técnica de Skype está destinada a una evaluación preliminar de las habilidades de un candidato y elimina a aquellos que definitivamente no podrán hacer frente a las secciones de tiempo completo.
Secciones a tiempo completo: el escenario principal. Son secciones de tiempo completo que dan una respuesta a la pregunta de qué puede hacer un candidato. La sección algorítmica es una de las secciones técnicas a tiempo completo. Además del algoritmo, hay otras pruebas cara a cara: por ejemplo, los candidatos a desarrolladores senior deben pasar por la sección de arquitectura, y los futuros líderes también responderán preguntas sobre la gestión de equipos y proyectos. En general, si un candidato tiene algún tipo de fortaleza en un área específica (aprendizaje automático, optimización de bajo nivel, desarrollo de sistemas altamente cargados, desarrollo móvil o cualquier otro), organizaremos una sección con un especialista especializado.
La sección algorítmica verifica si el candidato puede encontrar algoritmos para resolver problemas simples, evaluar la complejidad de estos algoritmos e implementarlos sin errores, mientras mantiene un equilibrio entre la calidad de las pruebas y la velocidad de la solución.
¿Por qué escribir código en una pizarra o papel?
Un estado natural para un programador es programar en un entorno de desarrollo integrado con resaltado de sintaxis y trazabilidad. Por lo tanto, la idea en una entrevista de escribir código en una pizarra o papel inicialmente no parece demasiado natural. Sin embargo, este método le permite verificar dos propiedades que son muy importantes para cada desarrollador.
El primero de ellos es la capacidad de lidiar rápidamente con el rendimiento del código "a simple vista". Imagine que al escribir cada ciclo que aparece en el programa, el desarrollador necesita pasar tiempo tratando de verificar su rendimiento mediante el rastreo; o que cuando un servicio falla en la producción, siempre necesita ejecutar el código bajo el depurador. Está claro que escribir y depurar incluso programas simples le llevará un tiempo inaceptablemente largo. Por supuesto, es útil poder leer el código con revisiones de código.
La segunda propiedad importante es la capacidad de pensar por adelantado un plan de solución y luego seguirlo. Si no hay un plan, esto conducirá a una gran cantidad de correcciones, tachados (en papel) y reescritura de grandes piezas de código. En la vida real, todo esto ralentiza enormemente el desarrollo, pero está parcialmente enmascarado por la velocidad del trabajo en el editor de código. Tablero y papel en este sentido son superficies despiadadas.
Naturalmente, tenemos en cuenta que escribir código a mano no es demasiado rápido. Por lo tanto, nuestras tareas generalmente implican resolver no más de una docena de líneas, y el número de tareas que deben resolverse en una sección suele ser dos o tres.
Secciones algorítmicas y programación deportiva.
La programación deportiva se está desarrollando en el futuro desarrollador, entre otras cosas, y la capacidad de implementar rápidamente y sin errores algoritmos simples de acuerdo con un plan predeterminado. Por lo tanto, los candidatos con experiencia en programación deportiva, realmente, hacen un buen trabajo con las secciones algorítmicas en las entrevistas. A menudo puede observar una situación en la que los futuros aprendices pueden hacer frente fácilmente a la sección algorítmica, resolviendo todos los problemas en 15-20 minutos, mientras que los programadores más experimentados pasan toda la hora en las mismas tareas.
Al mismo tiempo, la sección algorítmica con código de escritura es solo una de las secciones que prueba las habilidades mínimas necesarias para cualquier desarrollador. Esta sección será manejada no solo por programadores de Olympiad, sino también por desarrolladores industriales experimentados. El futuro desarrollador senior o líder del equipo seguramente está esperando la sección de arquitectura, en la que podrá revelar sus puntos fuertes; Por supuesto, esta sección nunca se pone a los aprendices y desarrolladores junior.
Concurso de preparación de entrevistas
Especialmente para que puedas imaginar aproximadamente el contenido de las tareas que damos en las secciones algorítmicas, hemos organizado un concurso que se puede utilizar en la preparación para entrevistas. Intente resolver todos los problemas sin ejecutar el depurador una vez; escriba una solución en el Bloc de notas sin resaltar la sintaxis; piense en la solución más corta posible que pase todas las pruebas; Piense de antemano en todos los posibles problemas y apruebe la solución la primera vez.
El concurso contiene cinco tareas. Puede intentar resolverlos usted mismo, o puede leer el análisis de antemano: aún será útil, porque Podrá entrenar su habilidad de codificación sin errores de un algoritmo previamente conocido.
Análisis de tareas del concursoTarea A. Piedras y joyas.
Se dan dos líneas de caracteres latinos en minúscula: cadena J y cadena S. Los caracteres incluidos en la cadena J son "joyas" y se incluyen en la cadena S son "piedras". Es necesario determinar cuántos caracteres de S son simultáneamente "joyas". En pocas palabras, debe verificar cuántos caracteres de S hay en J.
Esta es una tarea de calentamiento muy simple, que incluye soluciones en varios lenguajes de programación, para que los participantes puedan acostumbrarse al sistema de prueba.
El algoritmo es bastante simple: necesita construir un conjunto a partir de una línea con "joyas", luego ir a lo largo de la línea con "piedras" y verificar la inclusión de cada personaje en este conjunto. Utilice dicha implementación del conjunto para garantizar la complejidad lineal de la solución resultante, a pesar de que las líneas de entrada son muy cortas y, por lo tanto, es posible pasar incluso un algoritmo de complejidad cuadrática.
Problema B. Unidades consecutivas
Se requiere encontrar la secuencia más larga de unidades en el vector binario e imprimir su longitud.
El algoritmo de solución es el siguiente: recorre todos los elementos de la matriz; cuando se encuentra con uno, necesita aumentar el contador para la longitud de la secuencia actual, y cuando cumple con cero, debe restablecer este contador. Al final, debe mostrar el máximo de los valores que tomó el contador.
Compruebe que está manejando la situación cuando la matriz termina con la secuencia de unidades deseada. Con una implementación cuidadosa, esta situación no requiere un procesamiento especial.
Intente usar solo la cantidad constante de memoria adicional.
Tarea C. Eliminación duplicada
Se proporciona una matriz de enteros de 32 bits ordenados en orden no decreciente. Es necesario eliminar todas las repeticiones.
El algoritmo correcto procesa secuencialmente los elementos de la matriz, comparándolos con la última salida. Debe recordar actualizar la variable que contiene el último elemento mostrado y, además, no cometer un error al procesar el último elemento.
Al resolver este problema, tampoco necesita usar memoria adicional.
Tarea D. Generación de secuencias de paréntesis
Dado un entero n . Se requiere imprimir todas las secuencias correctas de corchetes de longitud 2 cdotn ordenado lexicográficamente (ver https://ru.wikipedia.org/wiki/Lexographic_order ). Solo se usan paréntesis en la tarea.
Este es un ejemplo de un problema algorítmico relativamente complejo. Generaremos una secuencia de un personaje; En cada momento, podemos asignar un corchete de apertura o un corchete de cierre a la secuencia actual. Puede agregar un paréntesis de apertura si antes se han agregado menos de n paréntesis de apertura, y un paréntesis de cierre si en la secuencia actual el número de paréntesis de apertura excede el número de paréntesis de cierre. Tal algoritmo, con una implementación cuidadosa, garantiza automáticamente el orden lexicográfico en la respuesta; trabaja en un tiempo proporcional al producto del número de elementos en la respuesta a n; Esto requiere una cantidad lineal de memoria adicional.
Un ejemplo de algoritmo ineficaz sería el siguiente: generamos todas las secuencias de paréntesis posibles, y luego solo mostramos las que resultan correctas. Al mismo tiempo, el volumen de la respuesta no permitirá resolver el problema más rápido que el algoritmo que resultará más arriba.
Problema E. Anagramas
Esta tarea bastante simple es un ejemplo típico de un problema, para cuya solución es necesario usar matrices asociativas. Al decidir, debe tener en cuenta que los caracteres se pueden repetir, por lo que debe usar no conjuntos, sino diccionarios. Por lo tanto, la solución será la siguiente: componemos de cada línea un diccionario, que para cada carácter almacenará el número de sus repeticiones; luego compare los diccionarios resultantes. Si coinciden, es necesario imprimir una unidad; de lo contrario, cero.
Solución alternativa: ordene las líneas de entrada y luego compárelas. Esta solución es peor porque funciona más lento y también cambia la entrada. Pero esta solución no usa memoria adicional.
Si durante la entrevista tuvo varias soluciones que difieren en sus características, cuéntenos al respecto. Siempre es genial cuando el desarrollador conoce varias opciones para resolver el problema y puede hablar sobre sus fortalezas y debilidades.
Tarea F. Fusionar k listas ordenadas
Dado k matrices de enteros no negativos ordenados en orden no decreciente, cada uno de los cuales no excede de 100. Se requiere construir el resultado de su fusión: una matriz ordenada en orden no decreciente que contiene todos los elementos del original k matrices La longitud de cada matriz no excede 10 cdotk .
Para cada matriz, cree un puntero; inicialmente, cada puntero se encuentra al comienzo de la matriz correspondiente. Colocaremos los elementos correspondientes a las posiciones de los punteros en cualquier estructura de datos que admita la extracción de un mínimo; puede ser un conjunto múltiple o, por ejemplo, un montón. A continuación, extraeremos el elemento mínimo de esta estructura, lo pondremos en respuesta, cambiaremos la posición del puntero en la matriz correspondiente y colocaremos el siguiente elemento de esta matriz en la estructura de datos.
En esta tarea, muchos tienen dificultades con el formato de entrada. Tenga en cuenta que los primeros elementos de las líneas no describen los elementos de las matrices, ¡describen las longitudes de las matrices!
Preguntas frecuentes del concurso
R: Definitivamente escribí el código correcto, pero las pruebas fallan; probablemente un error en ellos?
P: No, todas las pruebas son correctas. Piensa: probablemente no previste ninguna situación inusual.
R: Escribo en X, definitivamente necesita más memoria en la tarea Y. ¡Eleva los límites!
P: Todos los límites se establecen de tal manera que sea posible una solución utilizando cualquiera de los idiomas disponibles. Intente comprobar si lee accidentalmente todo el archivo de entrada en tareas con límites de memoria estrictos.
R: Algunas tareas pueden resolverse mucho más fácilmente debido a las limitaciones indicadas. ¿Por qué haces esto?
P: Simplificamos específicamente la entrada en algunas tareas, para que sea más fácil para los participantes centrarse en la implementación del algoritmo y no pensar, por ejemplo, en la velocidad de descarga de datos o en otras cosas que son importantes en la programación deportiva. Intente implementar exactamente los algoritmos que recomendamos, solo en esta situación obtendrá el máximo beneficio del concurso.
A: No quiero pasar el concurso. ¿No puedo?
Q: por supuesto! El concurso no es vinculante para todos los candidatos. Sin embargo, todavía recomiendo resolverlo: será útil en cualquier caso.
A: ¿Qué más recomendarías para la preparación?
P: Lea nuestros consejos en la página oficial sobre entrevistas en Yandex: https://yandex.ru/jobs/ya-interview . Agregaré por mi cuenta que resolver problemas en leetcode.com es extremadamente útil para cualquier desarrollador en práctica, independientemente de si planea someterse a una entrevista en el futuro cercano o participar en competencias de programación. Incluso una pequeña cantidad de práctica le permite sentirse más seguro al resolver tareas de trabajo.
Conclusión
A menudo asisto a conferencias para desarrolladores y gerentes de desarrollo, soy miembro de muchos chats de desarrollo, he realizado cientos de entrevistas y contratado a un gran número de desarrolladores en Yandex. La experiencia sugiere que las secciones algorítmicas con código escrito en una pizarra o papel a menudo plantean preguntas. En conclusión, responderé al más popular de ellos.
¿Por qué entrevistar en condiciones que son tan diferentes de las condiciones reales de trabajo del desarrollador?
Esto le permite comprender si el candidato puede encontrar problemas en los programas sin iniciar el depurador; si puede idear un plan del algoritmo por adelantado y luego seguirlo con precisión; ¿puede llegar a un conjunto pequeño pero suficiente de pruebas y luego comparar su implementación con este conjunto de pruebas?
¿Estas secciones dan una ventaja injusta a los programadores deportivos?
La programación deportiva desarrolla algunas habilidades muy útiles en los desarrolladores, por lo que los participantes en la programación de las olimpiadas realmente obtienen buenos resultados en las secciones algorítmicas. Entonces hay una ventaja, pero es justo. ¡La sección algorítmica es solo una de muchas, por lo que cada candidato tendrá suficientes oportunidades para mostrar sus puntos fuertes!
¿Por qué realizar secciones algorítmicas si todos los algoritmos se han implementado durante mucho tiempo, y solo necesita poder buscar su implementación en bibliotecas listas para usar?
En las secciones algorítmicas comunes a todos los desarrolladores, probamos solo las habilidades mínimas necesarias: la capacidad de crear y sin errores para implementar un algoritmo simple que contenga bucles, verifique las condiciones y posiblemente requiera el uso de matrices asociativas. Este tipo de código se escribe constantemente para implementar servicios de usuario.
¿Cuál es el punto en una sección que no prueba una gran cantidad de habilidades de desarrollador?
La sección algorítmica, de hecho, verifica solo el conjunto mínimo de habilidades necesarias para cualquier desarrollador. Probamos otras habilidades con la ayuda de otras secciones.
¿Realizan secciones algorítmicas para desarrolladores de todas las especialidades?
Si Se llevan a cabo secciones algorítmicas para desarrolladores de back-end, analistas, desarrolladores móviles y front-end, desarrolladores de infraestructura y métodos de aprendizaje automático, etc.