El otro día, los ganadores del campeonato de programación, que terminó a principios del verano, recibieron merecidos premios. Para hacer esto, los llamamos, así como a todos los otros finalistas de los 20 mejores de cada dirección a la oficina de Yandex Moscú. Una vez más, felicidades a quienes lograron llegar a la final.
Mientras tanto, preparamos una discusión sobre las tareas de campeonato que se ofrecieron a los desarrolladores front-end. Estas son tareas de la etapa de calificación. Le recordamos que el campeonato se celebró en cuatro áreas: backend, frontend, aprendizaje automático y análisis.
A. termómetro
Condición
Usando el navegador, muchos vieron un "termómetro" cuando construían una ruta de automóvil. Es una línea recta multicolor que muestra la congestión de carreteras en la ruta. En esta tarea, se propone escribir una función que adapte los datos del "termómetro" para diferentes tamaños de pantalla.
La entrada de función recibe una matriz de colores de longitud,
length y
width pantalla (
length ≥ width ) en la que se mostrará el termómetro. Los colores
GREEN ,
YELLOW y
RED corresponden a carga baja, media y alta, respectivamente. Los colores son comparables en términos de tráfico:
GREEN < YELLOW < RED .
La matriz inicial, comenzando desde el primer elemento, se divide en sucesivas submatrices disjuntas de longitud
length / width (el número siempre será un número entero). En cada subconjunto, es necesario organizar los colores de acuerdo con el grado creciente de congestión de las carreteras, elegir el color mediano y reemplazar todo el conjunto con él. En el caso de una matriz de longitud par, se selecciona la "mediana inferior" (elemento
n/2 en una fila ordenada de
n elementos). El resultado debería ser una variedad de colores de largo
width .
La solución debe proporcionarse como un módulo CommonJS:
module.exports = function (segments, width) {
El veredicto RE también significa que la solución presentada es incorrecta.
Solución
1. Divida la matriz inicial de segmentos en segmentos de
length / width .
2. En cada segmento, seleccione el color mediano, según la condición, y agregue el color encontrado a la matriz resultante.
solution.js module.exports = function solution(segments, width) { const blockSize = segments.length / width; const result = []; for (let i = 0; i < width; i++) { result.push(getMedian(segments.slice(i * blockSize, (i + 1) * blockSize))); } return result; }; function getMedian(array) { const map = { GREEN: 1, YELLOW: 2, RED: 3 }; return array.sort((a, b) => map[a] - map[b])[Math.floor((array.length - 1) / 2)]; }
B. Cliente Torrent
Condición
Decidiste escribir a tu cliente torrent. Su característica será que con su ayuda es posible transmitir solo texto.
El cliente de torrent está casi listo, lo más importante sigue siendo: recopilar el texto fuente de las piezas en las que se dividió para su transmisión.
Escriba una función que espere a que se carguen todos los fragmentos de texto y recopile la fuente de ellos.
La función toma un objeto de entrada con dos campos:
chunkCount y
chunkCount , y devuelve una promesa que contiene el texto fuente o un error en forma de una cadena del formato especificado.
chunkCount : la cantidad de piezas en las que se dividió el texto.
Cada texto tiene un identificador único y un tiempo de envío. Las piezas con un tiempo de envío posterior se encuentran más lejos desde el comienzo del texto.
emitter : un objeto con el que puede obtener fragmentos de texto descargados. Los fragmentos de texto pueden llegar con retrasos arbitrarios. El orden de las piezas puede ser cualquiera.
Si se recibe el mismo texto dos veces antes de que la descarga se haya completado con éxito, la función debería arrojar un error
"Duplicate: <id>" (con la identificación del texto en lugar de
<id> ).
Una vez que se han recibido todos los fragmentos de texto, es necesario combinarlos en una sola línea y devolver esta línea con una promesa. Si dos piezas tienen los mismos tiempos de envío, el orden de estas piezas en la cadena devuelta puede ser cualquiera.
Si la transferencia no se completa en un segundo, la función debería arrojar un error de
"Timed out" .
La entrada corresponde a dicha interfaz en TypeScript(
Descripción general de las interfaces TS).
interface Input { chunkCount: number; emitter: Emitter; } interface Emitter { on: (callback: (chunk: Chunk) => void) => void; } interface Chunk { id: number; timestamp: Date; data: string; }
La solución debe proporcionarse como un módulo CommonJS:
module.exports = function ({chunkCount, emitter}) {
El veredicto RE también significa que la solución presentada es incorrecta.
Solución
- Guarde los fragmentos cargados en un objeto
chunk . - En este caso, verificamos la existencia de
id . Si ya existe, cancele la promesa. - Después de cargar todas las piezas, ordenarlas y combinarlas.
- Paralelamente a esto, debe establecer un tiempo de espera de 1 s.
solution.js module.exports = function ({chunkCount, emitter: {on}}) { return new Promise((resolve, reject) => { const chunks = {}; let chunksDownloaded = 0; on(({id, data, timestamp}) => { if (typeof chunks[id] !== 'undefined') { reject(`Duplicate: ${id}`); } else { chunks[id] = {data, timestamp}; chunksDownloaded += 1; if (chunksDownloaded === chunkCount) { const result = Object.values(chunks) .sort((a, b) => a.timestamp - b.timestamp) .map(({data}) => data) .join(''); resolve(result); } } }); setTimeout(() => { reject('Timed out'); }, 1000); }); };
C. árbol binario
Condición
Al desarrollador Grisha se le encomendó la tarea de implementar un
árbol binario , pero entendió mal la esencia y cometió muchos errores. Ayúdelo a encontrarlos y arreglarlos.
Es necesario encontrar y corregir errores en el código
task.js Se debe exportar una clase para trabajar con un árbol binario. Interfaz de clase:
type Data = number; type ITraverseCallback = (data: Data) => void; interface IBinaryTreeNode { data: Data; left: IBinaryTreeNode | null; right: IBinaryTreeNode | null; static create(...items: Data[]): IBinaryTreeNode; constructor(data: Data); insert(data: Data): this; remove(data: Data): IBinaryTreeNode | null; search(data: Data): IBinaryTreeNode | null; inorder(callback: ITraverseCallback): this; preorder(callback: ITraverseCallback): this; postorder(callback: ITraverseCallback): this; }
Nota : Considere JSDoc el correcto.
El veredicto RE también significa que la solución presentada es incorrecta.
Opciones adicionalesEjemplo de entrada :
let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });
Conclusión 5-7-10-12-13-20-
Solución
class BinaryTreeNode { static create(...items) {
D. Yandex.Maps logo
Condición
El diseñador ha actualizado el logotipo de
Yandex.Maps (escala x5):
Tendrá que usarse en una variedad de condiciones. Para hacerlo lo más conveniente posible, complételo con un elemento HTML en CSS puro. El logotipo se puede usar en cualquier lugar de la interfaz, por lo que es importante que se muestre correctamente en cualquier fondo.
No puede usar imágenes (incluso a través de
data:uri ).
Opciones adicionales
- Colores del círculo central: #fff
- El color del círculo exterior: # f33
- El color de las "piernas": # e00000
La solución debe proporcionarse como un archivo CSS. Su archivo se conectará como
solution.css a una página HTML del formulario:
<!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>
Importante : el logotipo debe ubicarse en la esquina superior izquierda de la página, presionado estrechamente.
Su solución se probará en el
navegador Google Chrome 69 .
Recomendamos el uso de complementos para diseños con píxeles perfectos, como
PerfectPixel .
Solución
// . div { position: absolute; width: 6px; height: 6px; border: 5px solid #f33; border-radius: 8px; background: #fff; } // «» . // , 9 . div::after { content: ''; position: absolute; top: 6px; left: 2px; border-top: 15px solid #e00000; border-right: 7px solid transparent; transform: rotate(9deg); z-index: -1; }
E. malla de ladrillo
Condición
El desarrollador Ivan decidió refactorizar los estilos CSS de la página, después de lo cual rompió su apariencia.
Diseño inicial:
Debe alinear el aspecto con el diseño original con el menor número de cambios en el archivo CSS actual.
Importante : Al agregar elementos a la lista, la cuadrícula debería crecer de manera similar.
Estilos CSS después de refactorizar:
./solution.css .
Después de las correcciones, debe proporcionar un archivo CSS actualizado. Este archivo se conectará como una
solution.css fija.css a la
página HTML .
Opciones adicionalesSu solución se probará en el
navegador Google Chrome 69 . No es necesario cambiar la familia de fuentes y otras configuraciones de fuentes. En este caso, localmente, la fuente puede no coincidir con el estado esperado, porque las capturas de pantalla se tomaron en Ubuntu.
Recomendamos el uso de complementos para diseños con píxeles perfectos, como
PerfectPixel .
Solución
Los cambios solo deben hacerse con el selector
.event y sus descendientes.
:root { --color-gray: #4e4d4d; --color-main: #000000; --width-layout: 900px; --paddingx5: 50px; --paddingx4: 40px; --paddingx3: 30px; --paddingx2: 20px; --padding: 10px; --font-size-largex2: 40px; --font-size-large: 20px; --font-size-medium: 16px; --font-size-small: 14px; } body { margin: 0 auto; padding: var(--paddingx5) var(--paddingx4); font: var(--font-size-small)/1.4 arialregular; color: var(--color-main); width: var(--width-layout); } .hgroup { margin-bottom: var(--paddingx4); text-align: center; } .hgroup__title { font-size: var(--font-size-largex2); font-weight: normal; margin: 0; } .hgroup__desc { font-size: var(--font-size-large); font-weight: normal; color: var(--color-gray); margin: 0; } .events { list-style: none; margin: 0; padding: 0; // . // . columns: 3; column-gap: var(--paddingx4); } .events__item { // . break-inside: avoid; // margin . padding-bottom: var(--paddingx4); } .card { text-decoration: none; color: var(--color-main); display: block; } .card:hover .card__title { text-decoration: underline; } .card__image { width: 100%; display: block; height: 100px; background: var(--color-gray); margin-bottom: var(--padding); } .card__title { margin: 0 0 var(--padding); } .card__summary { margin: 0; color: var(--color-gray); }
F. Paseos en metro
Condición
Ahí está Devopia Petya. En el trabajo, debe estar de guardia en ciertos días durante los próximos 100 días. Petya llega al trabajo en metro. Se introdujeron boletos de metro que son válidos por un cierto número de días desde el primer viaje en ellos. Cuanto más tiempo sea válido el boleto, menor será el costo por día. Necesitamos ayudar a Petya a ahorrar dinero y calcular qué boletos necesita comprar con tres meses de anticipación, teniendo en cuenta el horario de sus deberes, para que su costo total sea lo más bajo posible. Y a Petya no le gusta llevar muchos boletos con él, y si hay varias opciones de boletos con el mismo costo mínimo, entonces Petya necesita uno con menos boletos. Si hay varias de esas opciones (con el mismo costo mínimo y número de boletos), entonces Pete se adaptará a cualquiera de ellas.
getCheapestTickets(days, tickets) escribir una función
getCheapestTickets(days, tickets) que tome el horario de servicio de Petya (
days ) y las posibles opciones de boletos como entrada y proporcione una lista de boletos (en forma de índices de la matriz de entrada de opciones de boletos) que necesita comprar Pete
El horario de servicio de Petya se da en forma de una serie ordenada de números (del 1 al 100 inclusive), cada uno de los cuales indica el número ordinal del día de servicio:
[2, 5, 10, 45]
Cada ticket se describe en la siguiente interfaz:
interface Ticket { duration: number;
El número de opciones de boletos no es más de 10, y se garantiza que todos los boletos tengan precios diferentes, y cuantos más días sea válido, menor será su costo en términos de un día.
La solución debe proporcionarse como un módulo CommonJS:
module.exports = function (days, tickets) {
El veredicto RE también significa que la solución presentada es incorrecta.
Opciones adicionalesEjemplosEn el primer y segundo día, Petya necesita comprar boletos de un día, el cuarto día son boletos de siete días, el vigésimo día, un día más.
El costo total de dichos boletos será el más bajo posible:
19 .
Solución
Una de las posibles soluciones es el método de programación dinámica, a saber:
1. Tome el primer día de servicio Petit.
2. Para encontrar la mejor solución para este día, calculamos las posibles opciones para cada uno de los boletos. Cada una de estas opciones consiste en el costo del boleto y el costo de la mejor solución el día de servicio después de la fecha de vencimiento de este boleto. El segundo término se calcula de manera similar, obteniendo así una recursión.
3. Además, considere la cantidad de boletos, si hay varias de esas opciones.
4. Se debe prestar especial atención a las soluciones de almacenamiento en caché en los días intermedios.
solution.js module.exports = function (days, tickets) { if (days.length === 0 || tickets.length === 0) { return []; } tickets = tickets .map((ticket, idx) => ({ ...ticket, idx })) .sort((a, b) => a.duration - b.duration); const daysSolutions = new Map(); function getDaySolution(idx) { if (daysSolutions.has(idx)) { return daysSolutions.get(idx); } const solution = { totalCost: Number.POSITIVE_INFINITY, totalTickets: Number.POSITIVE_INFINITY, ticketToBuy: null, next: null }; for (let i = 0, j = idx; i < tickets.length && j < days.length; i++) { while (j < days.length && days[j] < days[idx] + tickets[i].duration) { j++; } const nextDaySolution = j < days.length ? getDaySolution(j) : null; let totalCost = tickets[i].cost; let totalTickets = 1; if (nextDaySolution) { totalCost += nextDaySolution.totalCost; totalTickets += nextDaySolution.totalTickets; } if ( totalCost < solution.totalCost || (totalCost === solution.totalCost && totalTickets < solution.totalTickets) ) { solution.totalCost = totalCost; solution.totalTickets = totalTickets; solution.ticketToBuy = tickets[i].idx; solution.next = nextDaySolution; } } daysSolutions.set(idx, solution); return solution; } let solution = getDaySolution(0); const res = []; while (solution) { res.push(solution.ticketToBuy); solution = solution.next; } return res; };
Aquí hay un enlace a las tareas de análisis para desarrolladores de backend.