L'autre jour, les gagnants du championnat de programmation, qui s'est terminé au début de l'été, ont reçu des prix bien mérités. Pour ce faire, nous les avons appelés, ainsi que tous les autres finalistes du top 20 de chaque direction au bureau de Yandex Moscou. Encore une fois, félicitations à ceux qui ont réussi à atteindre la finale.
En attendant, nous avons préparé une discussion sur les tâches du championnat qui ont été proposées aux développeurs front-end. Ce sont des tâches de l'étape de qualification. Nous vous rappelons que le championnat s'est déroulé dans quatre domaines: backend, frontend, machine learning et analytics.
A. Thermomètre
Condition
En utilisant le navigateur, beaucoup ont vu un "thermomètre" lors de la construction d'un itinéraire en voiture. Il s'agit d'une ligne droite multicolore, qui montre la congestion des routes sur l'itinéraire. Dans cette tâche, il est proposé d'écrire une fonction qui adapte les données du «thermomètre» pour différentes tailles d'écran.
L'entrée de fonction reçoit un tableau de couleurs de longueur
length et la taille de l'écran
width (
length ≥ width ) sur laquelle le thermomètre sera affiché. Les couleurs
GREEN ,
YELLOW et
RED correspondent respectivement à une charge faible, moyenne et élevée. Les couleurs sont comparables en termes de trafic:
GREEN < YELLOW < RED .
Le tableau initial, à partir du premier élément, est divisé en sous-réseaux disjoints successifs de longueur
length / width (le nombre sera toujours un entier). Dans chaque sous-réseau, il est nécessaire d'agencer les couleurs en fonction du degré croissant de congestion des routes, de choisir la couleur médiane et de remplacer l'ensemble avec. Dans le cas d'un tableau de longueur paire, la «médiane inférieure» est sélectionnée (élément
n/2 dans une rangée ordonnée de
n éléments). Le résultat doit être un tableau de couleurs de
width de longueur.
La solution doit être fournie sous forme de module CommonJS:
module.exports = function (segments, width) {
Le verdict RE signifie également que la solution soumise est incorrecte.
Solution
1. Divisez le tableau initial de segments en segments de
length / width .
2. Dans chaque segment, sélectionnez la couleur médiane, en fonction de la condition, et ajoutez la couleur trouvée au tableau résultant.
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)]; }
Client Torrent
Condition
Vous avez décidé d'écrire votre client torrent. Sa caractéristique sera qu'avec son aide, il est possible de transmettre uniquement du texte.
Le client torrent est presque prêt, la chose la plus importante reste: récupérer le texte source des morceaux dans lesquels il a été divisé pour la transmission.
Écrivez une fonction qui attendra le chargement de tous les morceaux de texte et collectera la source d'eux.
La fonction accepte un objet avec deux champs:
chunkCount et
emitter , et renvoie une promesse contenant soit le texte source, soit une erreur sous la forme d'une chaîne du format spécifié.
chunkCount - le nombre de morceaux dans lesquels le texte a été divisé.
Chaque morceau de texte a un identifiant unique et une heure d'envoi. Les pièces dont l'heure d'envoi est ultérieure sont situées plus loin que le début du texte.
emitter - un objet avec lequel vous pouvez obtenir des morceaux de texte téléchargés. Des morceaux de texte peuvent arriver avec des retards arbitraires. L'ordre des pièces peut être quelconque.
Si le même morceau de texte est reçu deux fois avant la fin du téléchargement, la fonction doit générer une erreur
"Duplicate: <id>" (avec l'id du morceau de texte à la place de
<id> ).
Une fois que tous les morceaux de texte ont été reçus, il est nécessaire de les combiner en une seule ligne et de renvoyer cette ligne en utilisant une promesse. Si deux pièces ont les mêmes heures d'envoi, l'ordre de ces pièces dans la chaîne retournée peut être quelconque.
Si le transfert n'est pas terminé dans une seconde, la fonction doit renvoyer une erreur
"Timed out" .
L'entrée correspond à une telle interface sur TypeScript(
Description générale des 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 solution doit être fournie sous forme de module CommonJS:
module.exports = function ({chunkCount, emitter}) {
Le verdict RE signifie également que la solution soumise est incorrecte.
Solution
- Enregistrez les morceaux chargés dans un objet de
chunk . - Dans le même temps, nous vérifions l'existence de
id . S'il existe déjà, annulez la promesse. - Après avoir chargé toutes les pièces, triez-les et combinez-les.
- En parallèle, vous devez définir un délai d'expiration 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. Arbre binaire
Condition
Le développeur Grisha a été chargé d'implémenter un
arbre binaire , mais il en a mal compris l'essence et a fait de nombreuses erreurs. Aidez-le à les trouver et à les réparer.
Il est nécessaire de rechercher et de corriger les erreurs dans le code
task.js Une classe doit être exportée pour fonctionner avec un arbre binaire. 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; }
Remarque : considérez JSDoc comme le bon.
Le verdict RE signifie également que la solution soumise est incorrecte.
Options supplémentairesExemple d'entrée :
let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });
Conclusion :
5-7-10-12-13-20-
Solution
class BinaryTreeNode { static create(...items) {
D. Yandex.Maps logo
Condition
Le designer a mis à jour le logo
Yandex.Maps (échelle x5):
Il devra être utilisé dans diverses conditions. Pour le rendre aussi pratique que possible, composez-le avec un élément HTML en CSS pur. Le logo peut être utilisé à n'importe quel endroit de l'interface, il est donc important qu'il s'affiche correctement sur n'importe quel arrière-plan.
Vous ne pouvez pas utiliser d'images (même à travers des
data:uri ).
Options supplémentaires
- Couleurs du cercle central: #fff
- La couleur du cercle extérieur: # f33
- La couleur des "jambes": # e00000
La solution doit être fournie sous forme de fichier CSS. Votre fichier sera connecté en tant que
solution.css à une page HTML du formulaire:
<!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>
Important : le logo doit être situé dans le coin supérieur gauche de la page, étroitement appuyé dessus.
Votre solution sera testée dans le
navigateur Google Chrome 69 .
Nous vous recommandons d'utiliser des plugins pour des mises en page parfaites en pixels, tels que
PerfectPixel .
Solution
// . 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. maillage de brique
Condition
Le développeur Ivan a décidé de refactoriser les styles CSS de la page, après quoi il a cassé son apparence.
Conception initiale:
Vous devez aligner l'apparence avec la conception d'origine avec le moins de modifications dans le fichier CSS actuel.
Important : lors de l'ajout d'éléments à la liste, la grille doit se développer de la même manière.
Styles CSS après refactoring:
./solution.css .
Après les corrections, vous devez fournir un fichier CSS mis à jour. Ce fichier sera connecté en tant que
solution.css fixe à la
page HTML .
Options supplémentairesVotre solution sera testée dans le
navigateur Google Chrome 69 . Il n'est pas nécessaire de modifier la famille de polices et les autres paramètres de police. Dans ce cas, localement, la police peut ne pas correspondre à l'état attendu, car des captures d'écran ont été prises dans Ubuntu.
Nous vous recommandons d'utiliser des plugins pour des mises en page parfaites en pixels, tels que
PerfectPixel .
Solution
Les modifications ne doivent être effectuées qu'avec le sélecteur
.event et ses descendants.
: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); }
Promenades en métro
Condition
Il y a Devopia Petya. Au travail, il doit être en service certains jours pendant les 100 prochains jours. Petya se met au travail en métro. Des tickets de métro ont été introduits et sont valables pendant un certain nombre de jours à partir du premier voyage. Plus le billet est valide, plus le coût par jour est faible. Il est nécessaire d'aider Petya à économiser de l'argent et à calculer les billets dont il a besoin pour acheter trois mois à l'avance, en tenant compte du calendrier de ses tâches, afin que leur coût total soit le plus bas possible. Et Petya n'aime pas emporter beaucoup de billets avec lui, et s'il y a plusieurs options de billets avec le même coût minimum, alors Petya en a besoin d'une avec moins de billets. S'il existe plusieurs de ces options (avec le même coût minimum et le même nombre de billets), Pete conviendra à chacune d'entre elles.
Vous devez écrire une fonction
getCheapestTickets(days, tickets) qui prend le calendrier de travail de Petya (
days ) et les options de ticket possibles en entrée et donne une liste des tickets (sous forme d'indices du tableau d'entrée des options de ticket) que vous devez acheter Pete.
Le calendrier des tâches de Petya est donné sous la forme d'un tableau trié de nombres (de 1 à 100 inclus), chacun indiquant le nombre ordinal du jour de service:
[2, 5, 10, 45]
Chaque ticket est décrit par l'interface suivante:
interface Ticket { duration: number;
Le nombre d'options de billets n'est pas supérieur à 10, et il est garanti que tous les billets ont des prix différents, et plus le nombre de jours de validité d'un billet est élevé, plus son coût en une journée est faible.
La solution doit être fournie sous forme de module CommonJS:
module.exports = function (days, tickets) {
Le verdict RE signifie également que la solution soumise est incorrecte.
Options supplémentairesDes exemplesLes premier et deuxième jours, Petya doit acheter des billets pour une journée, le quatrième jour est de sept jours, le vingtième jour encore une fois.
Le coût total de ces billets sera le plus bas possible:
19 .
Solution
Une des solutions possibles est la méthode de programmation dynamique, à savoir:
1. Prenez le premier jour de service Petit.
2. Pour trouver la meilleure solution pour cette journée, nous calculons les options possibles pour chacun des billets. Chacune de ces options comprend le coût du billet et le coût de la meilleure solution le jour de service suivant la date d'expiration de ce billet. Le deuxième terme est calculé de manière similaire, obtenant ainsi une récursivité.
3. En outre, considérez le nombre de billets, s'il existe plusieurs options de ce type.
4. Une attention particulière doit être accordée aux solutions de mise en cache dans les jours intermédiaires.
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; };
Voici un lien vers l'analyse des tâches pour les développeurs backend.