No outro dia, os vencedores do campeonato de programação, que terminou no início do verão, receberam prêmios merecidos. Para fazer isso, nós os chamamos, assim como todos os outros finalistas, dos 20 primeiros de cada direção, até o escritório da Yandex Moscow. Mais uma vez, parabéns a quem conseguiu chegar à final.
Enquanto isso, preparamos uma discussão sobre as tarefas do campeonato que foram oferecidas aos desenvolvedores front-end. Essas são tarefas do estágio de qualificação. Lembramos que o campeonato foi realizado em quatro áreas: back-end, front-end, aprendizado de máquina e análise.
A. Termômetro
Condição
Usando o navegador, muitos viram um "termômetro" ao construir uma rota de carro. É uma linha reta multicolorida, que mostra o congestionamento de estradas na rota. Nesta tarefa, propõe-se escrever uma função que adapte os dados do "termômetro" para diferentes tamanhos de tela.
A entrada de função recebe uma matriz de cores de comprimento e
width tamanho da tela (
length ≥ width ) na qual o termômetro será exibido. As cores
GREEN ,
YELLOW e
RED correspondem a carga baixa, média e alta, respectivamente. As cores são comparáveis em termos de tráfego:
GREEN < YELLOW < RED .
A matriz inicial, iniciando no primeiro elemento, é dividida em sub-matrizes separadas sucessivas de comprimento
length / width (o número sempre será um número inteiro). Em cada sub-matriz, é necessário organizar as cores de acordo com o grau crescente de congestionamento das estradas, escolher a cor mediana e substituir todo o conjunto por ela. No caso de uma matriz de comprimento uniforme, a “mediana inferior” é selecionada (elemento
n/2 em uma linha ordenada de
n elementos). O resultado deve ser uma matriz de cores com
width de comprimento.
A solução deve ser fornecida como um módulo CommonJS:
module.exports = function (segments, width) {
O veredicto de ER também significa que a solução enviada está incorreta.
Solução
1. Divida a matriz inicial de segmentos em segmentos de
length / width .
2. Em cada segmento, selecione a cor mediana, com base na condição, e adicione a cor encontrada à 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
Condição
Você decidiu escrever seu cliente de torrent. Sua característica será que, com sua ajuda, é possível transmitir apenas texto.
O cliente de torrent está quase pronto, o mais importante permanece: coletar o texto de origem das partes em que foi dividido para transmissão.
Escreva uma função que espere que todos os pedaços de texto sejam carregados e colete a fonte deles.
A função aceita um objeto com dois campos:
chunkCount e
emitter e retorna uma promessa que contém o texto de origem ou um erro na forma de uma sequência do formato especificado.
chunkCount - o número de partes em que o texto foi dividido.
Cada pedaço de texto tem um identificador único e tempo de envio. As peças com um horário de envio posterior estão localizadas mais afastadas do início do texto.
emitter - um objeto com o qual você pode obter partes do texto baixadas. Partes do texto podem chegar com atrasos arbitrários. A ordem das peças pode ser qualquer.
Se o mesmo pedaço de texto for recebido duas vezes antes de o download ser concluído com êxito, a função lançará um erro
"Duplicate: <id>" (com o ID do pedaço de texto no lugar de
<id> ).
Uma vez que todas as partes do texto foram recebidas, é necessário combiná-las em uma linha e retorná-la usando uma promessa. Se duas peças tiverem os mesmos tempos de envio, a ordem dessas peças na sequência retornada poderá ser qualquer.
Se a transferência não for concluída dentro de um segundo, a função deverá gerar um erro
"Timed out" excedido
"Timed out" .
A entrada corresponde a essa interface no TypeScript(
Descrição geral das interfaces TS.)
interface Input { chunkCount: number; emitter: Emitter; } interface Emitter { on: (callback: (chunk: Chunk) => void) => void; } interface Chunk { id: number; timestamp: Date; data: string; }
A solução deve ser fornecida como um módulo CommonJS:
module.exports = function ({chunkCount, emitter}) {
O veredicto de ER também significa que a solução enviada está incorreta.
Solução
- Salve os pedaços carregados em um objeto de
chunk . - Nesse caso, verificamos a existência de
id . Se já existir, cancele a promessa. - Depois de carregar todas as peças, classifique e combine-as.
- Paralelamente, você precisa definir um tempo limite 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. Árvore binária
Condição
O desenvolvedor Grisha recebeu a tarefa de implementar uma
árvore binária , mas ele entendeu mal a essência e cometeu muitos erros. Ajude-o a encontrar e consertá-los.
É necessário encontrar e corrigir erros no código
task.js Uma classe deve ser exportada para trabalhar com uma árvore binária. Interface de classe:
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 o JSDoc o correto.
O veredicto de ER também significa que a solução enviada está incorreta.
Opções adicionaisExemplo de entrada :
let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });
Conclusão :
5-7-10-12-13-20-
Solução
class BinaryTreeNode { static create(...items) {
D. Yandex.Maps logo
Condição
O designer atualizou o logotipo
Yandex.Maps (escala x5):
Ele precisará ser usado em uma variedade de condições. Para torná-lo o mais conveniente possível, crie um elemento HTML em CSS puro. O logotipo pode ser usado em qualquer lugar da interface, por isso é importante que seja exibido corretamente em qualquer plano de fundo.
Você não pode usar imagens (mesmo através dos
data:uri ).
Opções adicionais
- Cores do círculo central: #fff
- A cor do círculo externo: # f33
- A cor das "pernas": # e00000
A solução deve ser fornecida como um arquivo CSS. Seu arquivo será conectado como
solution.css a uma página HTML do formulário:
<!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>
Importante : o logotipo deve estar localizado no canto superior esquerdo da página, bem pressionado.
Sua solução será testada no
navegador Google Chrome 69 .
Recomendamos o uso de plug-ins para layouts com pixels perfeitos, como o
PerfectPixel .
Solução
// . 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. Malha de tijolo
Condição
O desenvolvedor Ivan decidiu refatorar os estilos CSS da página, após o que ele quebrou sua aparência.
Projeto inicial:
Você precisa alinhar a aparência com o design original com o menor número de alterações no arquivo CSS atual.
Importante : Ao adicionar itens à lista, a grade deve crescer da mesma forma.
Estilos CSS após refatoração:
./solution.css .
Após as correções, você precisa fornecer um arquivo CSS atualizado. Este arquivo será conectado como um
solution.css fixo à
página HTML .
Opções adicionaisSua solução será testada no
navegador Google Chrome 69 . A família de fontes e outras configurações de fontes não precisam ser alteradas. Nesse caso, localmente, a fonte pode não corresponder ao estado esperado, porque foram capturadas capturas de tela no Ubuntu.
Recomendamos o uso de plug-ins para layouts com pixels perfeitos, como o
PerfectPixel .
Solução
As alterações devem ser feitas apenas com o seletor
.event e seus descendentes.
: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. Passeios de metrô
Condição
Há Devopia Petya. No trabalho, ele precisa estar de plantão em determinados dias pelos próximos 100 dias. Petya começa a trabalhar de metrô. Foram introduzidos bilhetes de metrô válidos por um certo número de dias desde a primeira viagem. Quanto mais o bilhete for válido, menor será o custo por dia. É necessário ajudar Petya a economizar dinheiro e calcular quais bilhetes ele precisa comprar com três meses de antecedência, levando em consideração a programação de suas tarefas, para que o custo total seja o mais baixo possível. E Petya não gosta de carregar muitos ingressos com ele e, se houver várias opções de ingressos com o mesmo custo mínimo, Petya precisará de um com menos ingressos. Se houver várias opções (com o mesmo custo mínimo e número de ingressos), Pete será adequado a qualquer uma delas.
Você precisa escrever uma função
getCheapestTickets(days, tickets) que leva a programação de serviço da Petya (
days ) e as possíveis opções de ticket como entrada e fornece uma lista de tickets (na forma de índices da matriz de entrada de opções de ticket) que você precisa comprar Pete.
O horário de serviço da Petya é fornecido na forma de uma matriz classificada de números (de 1 a 100 inclusive), cada um dos quais indica o número ordinal do dia de serviço:
[2, 5, 10, 45]
Cada ticket é descrito pela seguinte interface:
interface Ticket { duration: number;
O número de opções de ingressos não é superior a 10 e é garantido que todos os ingressos tenham preços diferentes. Quanto mais dias um bilhete for válido, menor será o custo em termos de um dia.
A solução deve ser fornecida como um módulo CommonJS:
module.exports = function (days, tickets) {
O veredicto de ER também significa que a solução enviada está incorreta.
Opções adicionaisExemplosNo primeiro e no segundo dia, a Petya precisa comprar ingressos de um dia, no quarto dia é de sete dias, no vigésimo dia, um dia novamente.
O custo total desses ingressos será o mais baixo possível:
19 .
Solução
Uma das soluções possíveis é o método de programação dinâmica, a saber:
1. Pegue o primeiro dia de serviço Petit.
2. Para encontrar a melhor solução para este dia, calculamos as opções possíveis para cada um dos tickets. Cada uma dessas opções consiste no custo do bilhete e no custo da melhor solução no dia de serviço após a data de vencimento desse bilhete. O segundo termo é calculado da mesma forma, obtendo assim uma recursão.
3. Além disso, considere o número de tickets, se houver várias opções.
4. Atenção especial deve ser dada às soluções de armazenamento em cache nos dias intermediários.
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; };
Aqui está um link para analisar tarefas para desenvolvedores de back-end.