Neulich erhielten die Gewinner der Programmiermeisterschaft, die im Frühsommer endete, wohlverdiente Preise. Dazu haben wir sie sowie alle anderen Finalisten aus den Top 20 jeder Richtung in das Büro von Yandex Moskau eingeladen. Nochmals herzlichen Glückwunsch an diejenigen, die es geschafft haben, das Finale zu erreichen.
In der Zwischenzeit haben wir eine Diskussion über die Meisterschaftsaufgaben vorbereitet, die Front-End-Entwicklern angeboten wurden. Dies sind Aufgaben aus der Qualifikationsphase. Wir erinnern Sie daran, dass die Meisterschaft in vier Bereichen stattfand: Backend, Frontend, maschinelles Lernen und Analytik.
A. Thermometer
Zustand
Mit dem Navigator sahen viele beim Bau einer Autoroute ein "Thermometer". Es ist eine mehrfarbige gerade Linie, die die Überlastung der Straßen auf der Route zeigt. In dieser Aufgabe wird vorgeschlagen, eine Funktion zu schreiben, die die Daten des „Thermometers“ für verschiedene Bildschirmgrößen anpasst.
Die Funktionseingabe erhält eine Reihe von Farben mit der Länge
length und der Bildschirmgröße
width (
length ≥ width ), auf denen das Thermometer angezeigt wird. Die verwendeten Farben
GREEN ,
YELLOW und
RED entsprechen einer geringen, mittleren bzw. hohen Belastung. Die Farben sind in Bezug auf den Verkehr vergleichbar:
GREEN < YELLOW < RED .
Das anfängliche Array, beginnend mit dem ersten Element, ist in aufeinanderfolgende disjunkte Subarrays mit der
length / width (die Zahl ist immer eine ganze Zahl). In jedem Subarray ist es erforderlich, die Farben entsprechend der zunehmenden Überlastung der Straßen anzuordnen, die mittlere Farbe auszuwählen und das gesamte Set durch diese zu ersetzen. Bei einem Array mit gerader Länge wird der „untere Median“ ausgewählt (Element
n/2 in einer geordneten Reihe von
n Elementen). Das Ergebnis sollte ein Array von Farben mit einer Länge und
width .
Die Lösung muss als CommonJS-Modul bereitgestellt werden:
module.exports = function (segments, width) {
Das RE-Urteil bedeutet auch, dass die eingereichte Lösung falsch ist.
Lösung
1. Teilen Sie das anfängliche Segment von Segmenten in Segmente mit
length / width .
2. Wählen Sie in jedem Segment die Medianfarbe basierend auf der Bedingung aus und fügen Sie die gefundene Farbe zum resultierenden Array hinzu.
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. Torrent Client
Zustand
Sie haben beschlossen, Ihren Torrent-Client zu schreiben. Seine Funktion wird sein, dass mit seiner Hilfe nur Text übertragen werden kann.
Der Torrent-Client ist fast fertig, das Wichtigste bleibt: den Quelltext aus den Teilen zu sammeln, in die er zur Übertragung aufgeteilt wurde.
Schreiben Sie eine Funktion, die darauf wartet, dass alle Textteile geladen werden, und die Quelle von ihnen sammelt.
Die Funktion akzeptiert ein Objekt mit zwei Feldern:
chunkCount und
emitter und gibt ein Versprechen zurück, das entweder den Quelltext oder einen Fehler in Form einer Zeichenfolge des angegebenen Formats enthält.
chunkCount - Die Anzahl der Teile, in die der Text aufgeteilt wurde.
Jeder Text hat eine eindeutige Kennung und Sendezeit. Stücke mit einer späteren Sendezeit befinden sich weiter vom Textanfang entfernt.
emitter - ein Objekt, mit dem Sie heruntergeladene Textteile erhalten können. Textteile können mit willkürlichen Zeitverzögerungen eintreffen. Die Reihenfolge der Stücke kann beliebig sein.
Wenn derselbe Text zweimal empfangen wird, bevor der Download erfolgreich abgeschlossen wurde, sollte die Funktion den Fehler
"Duplicate: <id>" (mit der ID des Textes anstelle von
<id> ).
Sobald alle Textstücke eingegangen sind, müssen sie zu einer Zeile zusammengefasst und diese Zeile mit einem Versprechen zurückgegeben werden. Wenn zwei Teile die gleichen Sendezeiten haben, kann die Reihenfolge dieser Teile in der zurückgegebenen Zeichenfolge beliebig sein.
Wenn die Übertragung nicht innerhalb einer Sekunde abgeschlossen ist, sollte die Funktion den Fehler
"Timed out" auslösen.
Die Eingabe entspricht einer solchen Schnittstelle in TypeScript(
Allgemeine Beschreibung der TS-Schnittstellen.)
interface Input { chunkCount: number; emitter: Emitter; } interface Emitter { on: (callback: (chunk: Chunk) => void) => void; } interface Chunk { id: number; timestamp: Date; data: string; }
Die Lösung muss als CommonJS-Modul bereitgestellt werden:
module.exports = function ({chunkCount, emitter}) {
Das RE-Urteil bedeutet auch, dass die eingereichte Lösung falsch ist.
Lösung
- Speichern Sie die geladenen Chunks in einem
chunk Objekt. - In diesem Fall prüfen wir, ob eine
id . Wenn es bereits existiert, stornieren Sie das Versprechen. - Nachdem Sie alle Teile geladen haben, sortieren und kombinieren Sie sie.
- Parallel dazu müssen Sie ein Timeout von 1 s einstellen.
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. Binärer Baum
Zustand
Der Entwickler Grisha erhielt die Aufgabe, einen
Binärbaum zu implementieren, aber er verstand die Essenz schlecht und machte viele Fehler. Hilf ihm, sie zu finden und zu reparieren.
Es ist notwendig, Fehler im Code
task.js zu finden und zu beheben. Eine Klasse muss exportiert werden, um mit einem Binärbaum arbeiten zu können. Klassenschnittstelle:
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; }
Hinweis : Betrachten Sie JSDoc als das richtige.
Das RE-Urteil bedeutet auch, dass die eingereichte Lösung falsch ist.
Zusätzliche OptionenEingabebeispiel :
let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });
Fazit :
5-7-10-12-13-20-
Lösung
class BinaryTreeNode { static create(...items) {
D. Yandex.Maps-Logo
Zustand
Der Designer hat das
Yandex.Maps- Logo (Maßstab 5) aktualisiert:
Es muss unter verschiedenen Bedingungen verwendet werden. Um es so bequem wie möglich zu gestalten, erstellen Sie ein HTML-Element in reinem CSS. Das Logo kann an jeder Stelle der Benutzeroberfläche verwendet werden. Daher ist es wichtig, dass es auf jedem Hintergrund korrekt angezeigt wird.
Sie können keine Bilder verwenden (auch nicht durch
data:uri ).
Zusätzliche Optionen
- Mittlere Kreisfarben: #fff
- Die Farbe des äußeren Kreises: # f33
- Die Farbe der "Beine": # e00000
Die Lösung muss als CSS-Datei bereitgestellt werden. Ihre Datei wird als
solution.css mit einer HTML-Seite des Formulars verbunden:
<!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>
Wichtig : Das Logo sollte sich in der oberen linken Ecke der Seite befinden und eng an diese gedrückt werden.
Ihre Lösung wird im
Google Chrome 69-Browser getestet.
Wir empfehlen die Verwendung von Plugins für pixelgenaue Layouts wie
PerfectPixel .
Lösung
// . 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. Brick Mesh
Zustand
Entwickler Ivan beschloss, die CSS-Stile der Seite zu überarbeiten, woraufhin er das Erscheinungsbild brach.
Erstes Design:
Sie müssen das Erscheinungsbild mit der geringsten Anzahl von Änderungen in der aktuellen CSS-Datei an das ursprüngliche Design anpassen.
Wichtig : Wenn Sie der Liste Elemente hinzufügen, sollte das Raster ähnlich wachsen.
CSS-Stile nach dem Refactoring:
./solution.css .
Nach den Korrekturen müssen Sie eine aktualisierte CSS-Datei bereitstellen. Diese Datei wird als feste
solution.css mit der
HTML-Seite verbunden .
Zusätzliche OptionenIhre Lösung wird im
Google Chrome 69-Browser getestet. Die Schriftfamilie und andere Schriftarteneinstellungen müssen nicht geändert werden. In diesem Fall stimmt die Schriftart lokal möglicherweise nicht mit dem erwarteten Status überein, da Screenshots in Ubuntu aufgenommen wurden.
Wir empfehlen die Verwendung von Plugins für pixelgenaue Layouts wie
PerfectPixel .
Lösung
Änderungen sollten nur mit dem
.event Selektor und seinen Nachkommen vorgenommen werden.
: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. U-Bahnfahrten
Zustand
Da ist Devopia Petya. Bei der Arbeit muss er an bestimmten Tagen für die nächsten 100 Tage im Dienst sein. Petja macht sich mit der U-Bahn an die Arbeit. Es wurden U-Bahn-Tickets eingeführt, die ab der ersten Fahrt für eine bestimmte Anzahl von Tagen gültig sind. Je länger das Ticket gültig ist, desto niedriger sind die Kosten pro Tag. Wir müssen Petya helfen, Geld zu sparen und zu berechnen, welche Tickets er drei Monate im Voraus kaufen muss, unter Berücksichtigung des Zeitplans seiner Aufgaben, damit ihre Gesamtkosten so niedrig wie möglich sind. Und Petya mag es nicht, viele Tickets bei sich zu haben, und wenn es mehrere Ticketoptionen mit den gleichen Mindestkosten gibt, braucht Petya eine mit weniger Tickets. Wenn es mehrere solcher Optionen gibt (mit den gleichen Mindestkosten und der gleichen Anzahl von Tickets), passt Pete zu jeder dieser Optionen.
Sie müssen die Funktion
getCheapestTickets(days, tickets) schreiben, die
getCheapestTickets(days, tickets) Dienstplan (
days ) und mögliche Ticketoptionen (
tickets ) als Eingabe verwendet und eine Liste der Tickets (in Form von Indizes aus dem Eingabearray der Ticketoptionen) enthält, die Sie kaufen müssen Pete.
Der Dienstplan von Petya wird in Form einer sortierten Reihe von Zahlen (von 1 bis einschließlich 100) angegeben, von denen jede die Ordnungszahl des Diensttages angibt:
[2, 5, 10, 45]
Jedes Ticket wird von der folgenden Schnittstelle beschrieben:
interface Ticket { duration: number;
Die Anzahl der Ticketoptionen beträgt nicht mehr als 10, und es wird garantiert, dass alle Tickets unterschiedliche Preise haben. Je mehr Tage ein Ticket gültig ist, desto niedriger sind die Kosten in Bezug auf einen Tag.
Die Lösung muss als CommonJS-Modul bereitgestellt werden:
module.exports = function (days, tickets) {
Das RE-Urteil bedeutet auch, dass die eingereichte Lösung falsch ist.
Zusätzliche OptionenBeispieleAm ersten und zweiten Tag muss Petya Tageskarten kaufen, am vierten Tag sieben Tage, am zwanzigsten Tag wieder einen Tag.
Die Gesamtkosten solcher Tickets sind so niedrig wie möglich:
19 .
Lösung
Eine der möglichen Lösungen ist die dynamische Programmiermethode, nämlich:
1. Nehmen Sie den ersten Tag des Dienstes Petit.
2. Um die beste Lösung für diesen Tag zu finden, berechnen wir die möglichen Optionen für jedes der Tickets. Jede dieser Optionen besteht aus den Kosten des Tickets und den Kosten der besten Lösung am Tag des Dienstes nach dem Ablaufdatum dieses Tickets. Der zweite Term wird ähnlich berechnet, wodurch eine Rekursion erhalten wird.
3. Berücksichtigen Sie zusätzlich die Anzahl der Tickets, wenn es mehrere solcher Optionen gibt.
4. Besondere Aufmerksamkeit sollte den Caching-Lösungen in den Zwischentagen gewidmet werden.
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; };
Hier ist ein Link zu Parsing-Aufgaben für Backend-Entwickler.