Programming Championship: sorting out tasks for front-end developers
Recently, the winners of the programming championship, which ended in early summer, received well-deserved prizes. To do this, we called them, as well as all the other finalists from the top 20 of each direction to the Moscow office of Yandex. Congratulations again to those who managed to reach the final.
In the meantime, we have prepared an analysis of the tasks of the championship, which were offered to front-end developers. These are tasks from the qualifying stage. We remind you that the championship was held in four areas: backend, frontend, machine learning and analytics.
A. Caps Thermometer
Condition
Using the navigator, many saw the "thermometer" when building a car route. It is a multi-colored straight line, which shows the congestion of roads on the route. In this task, it is proposed to write a function that adapts the data of the “thermometer” for different screen sizes.
')
The input of the function is an array of colors of length
length and screen size width ( length ≥ width ), on which the thermometer will be displayed. The colors used are GREEN , YELLOW and RED low, medium and high load, respectively. The colors are comparable in terms of road congestion: GREEN < YELLOW < RED .
The initial array, starting from the first element, is divided into successive non-intersecting subarrays of length
length / width (the number will always be an integer). In each sub-array, it is necessary to order the colors by increasing the degree of road congestion, select the median color and replace it with the entire set. In the case of an even-length array, the “lower median” is selected (element n/2 in an ordered row of n elements). The result should be an array of colors of length width .
The solution must be provided as a CommonJS module:
module.exports = function (segments, width) { // Your code here. };
The verdict RE also means that the submitted solution is incorrect.
Extra options
| Input | Conclusion |
| ['GREEN', 'GREEN', 'YELLOW', 'GREEN', 'YELLOW'] |
Decision
1. We divide the initial array of segments into segments of length
length / width .
2. In each segment, select the median color based on the condition, and add the found color to the resulting array.
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
Condition
You have decided to write your torrent client. Its feature is that with its help you can only transfer text.
The torrent client is almost ready, the most important thing remains: to collect the source code from the pieces into which it was broken for transmission.
Write a function that will wait for the download of all the pieces of text and collect from them the original one.
The function takes an object with two fields as input:
chunkCount and emitter , and returns a promise containing either the source text or an error in the form of a string of the specified format.
chunkCount - the number of pieces into which the text was broken.
Each piece of text has a unique identifier and the time it was sent. Pieces with a later dispatch time are located further from the beginning of the text.
emitter is an object with which you can get loaded pieces of text. Pieces of text can come with arbitrary time delays. The order of the pieces can be any.
If the same piece of text is received twice before the download is successfully completed, the function should produce the error
"Duplicate: <id>" (with the id of the piece of text in place <id> ).
Once all the pieces of text have been received, it is necessary to join them into one line and return this line using promise. If the two pieces have the same send time, the order of these pieces in the returned string can be anything.
If the transmission is not completed within a second, the function should produce a
"Timed out" error.
The input data correspond to such an interface in TypeScript.
( General description of TS interfaces.)
interface Input { chunkCount: number; emitter: Emitter; } interface Emitter { on: (callback: (chunk: Chunk) => void) => void; } interface Chunk { id: number; timestamp: Date; data: string; }
The solution must be provided as a CommonJS module:
module.exports = function ({chunkCount, emitter}) { // Promise };
The verdict RE also means that the submitted solution is incorrect.
Extra options
Examples
| Input | Conclusion |
| Resolved with "The Good, the Bad and the Ugly" |
| Rejected with "Duplicate id: 0" |
| Rejected with "Timed out" |
Decision
- Save the loaded pieces to the
chunkobject. - In this case, check for the existence of
id. If it already exists, then cancel the promis. - After loading all the pieces, sort them and combine them.
- In parallel with this, you need to set a timeout of 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. Binary tree
Condition
The developer, Grisha, was given the task of implementing a binary tree , but he didn’t understand the essence well and made many mistakes. Help him find and fix them.
It is necessary to find and fix errors in the
task.js code. Must be exported class to work with binary tree. Class interface:
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; }
Note : Consider JSDoc correct.
The verdict RE also means that the submitted solution is incorrect.
Extra options
Input example :
Conclusion :
let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });
Conclusion :
5-7-10-12-13-20- Decision
/** * @typedef Data * @type {Number} */ class BinaryTreeNode { /** * @param {...Data} items * @returns {BinaryTreeNode} */ static create(...items) { // e - . const root = new BinaryTreeNode(items[0]); // return . // .slice(1), . return items.slice(1).reduce((node, data) => node.insert(data), root); } /** * @param {Data} data */ constructor(data) { /** * @type {Data} */ this.data = data; // . /** * @type {BinaryTreeNode | null} */ this.left = null; /** * @type {BinaryTreeNode | null} */ this.right = null; } /** * . * , . * * @param {Date} data * @returns {BinaryTreeNode} */ insert(data) { // . if (data < this.data) { if (this.left === null) { this.left = new BinaryTreeNode(data); } else { this.left.insert(data); } } else { if (this.right === null) { this.right = new BinaryTreeNode(data); } else { this.right.insert(data); } } // , . return this; } /** * . * , . * * @param {Data} data * @returns {BinaryTreeNode | null} */ remove(data) { // {}. // . if (data < this.data) { // `this.left`. this.left = this.left && this.left.remove(data); } else if (data > this.data) { // `this.right`. this.right = this.right && this.right.remove(data); } else { if (this.left === null && this.right === null) { return null; } if (this.left === null) { return this.right; } else if (this.right === null) { return this.left; } const aux = findMinNode(this.right); this.data = aux.data; this.right = this.right.remove(aux.data); } // , . return this; } /** * . * * @param {Data} data * @returns {BinaryTreeNode | null} */ search(data) { // . if (data < this.data) { // `this.left`. return this.left && this.left.search(data); } if (data > this.data) { // `this.right`. return this.right && this.right.search(data); } // , , `null`. if (data === this.data) { return this; } return null; } /** * , . * . * * @param {Function} callback * @returns {BinaryTreeNode} */ inorder(callback) { if (this.left !== null) { this.left.inorder(callback); } callback(this.data); if (this.right !== null) { this.right.inorder(callback); } // , . return this; } /** * , . * * @param {Function} callback * @returns {BinaryTreeNode} */ preorder(callback) { callback(this.data); if (this.left !== null) { // . this.left.preorder(callback); } if (this.right !== null) { this.right.preorder(callback); } // , . return this; } /** * , . * * @param {Function} callback * @returns {BinaryTreeNode} */ postorder(callback) { if (this.left !== null) { this.left.postorder(callback); } if (this.right !== null) { // . this.right.postorder(callback); } // , . callback(this.data); return this; } } /** * , . * * @param {BinaryTreeNode} node * @returns {BinaryTreeNode} */ function findMinNode(node) { // . // true false. if (node.left === null) { return node; } else { return findMinNode(node.left); } } module.exports = BinaryTreeNode;
D. Yandex.Maps logo
Condition
The designer has updated the Yandex.Maps logo (x5 scale):
It will need to be used in a variety of conditions. To make this as convenient as possible, roll it using a single HTML element on pure CSS. The logo can be used in any place of the interface, so it is important that it is correctly displayed on any background.
Use pictures (even through
data:uri ) is impossible.
Extra options
- Colors of the central circle: #fff
- The color of the outer circle: # f33
- Color "legs": # e00000
- Colors of the central circle: #fff
- The color of the outer circle: # f33
- Color "legs": # e00000
The solution must be provided as a CSS file. Your file will be connected as
solution.css to an HTML page like this:
<!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>
Important : the logo should be in the upper left corner of the page, closely pressed to it.
Your solution will be tested in Google Chrome 69 browser .
We recommend using plugins for pixel-perfect-layout, for example PerfectPixel .
Decision
// . 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
Condition
Developer Ivan decided to refactor the CSS styles of the page, after which he broke its appearance.
Initial design:
It is necessary to bring the appearance in accordance with the original design with the least amount of changes in the current CSS-file.
Important : When adding items to the list, the grid should likewise expand downwards.
CSS styles after refactoring:
./solution.css .
After corrections, you need to provide an updated CSS file. This file will be connected as a fixed
solution.css to the HTML page .
Extra options
Your solution will be tested in Google Chrome 69 browser . The family and other font parameters do not need to be changed. In this case, locally you may not have the same font with the expected state, since the screenshots are made in Ubuntu.
We recommend using plugins for pixel-perfect-layout, for example PerfectPixel .
We recommend using plugins for pixel-perfect-layout, for example PerfectPixel .
Decision
Changes need to be made only with the
.event selector and its heirs.
: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. Subway rides
Condition
There is Petya devops. At work, he needs to be on duty on certain days for the next 100 days. Petya gets to work by metro. Subway tickets were entered into the metro, which are valid for a certain number of days from the date of the first trip. The longer the validity period of the ticket, the lower the cost per day. We need to help Petya save money and calculate which tickets he needs to buy for three months in advance, taking into account his duty schedule, so that their total cost is as low as possible. And Petya does not like to carry a lot of tickets with him, and if there are several variants of tickets with the same minimum cost, then Pete needs one with fewer tickets. If there are several such options (with the same minimum cost and the number of tickets), then Pete will do any of them.
You need to write a function
getCheapestTickets(days, tickets) , which accepts Petit's schedule of duty ( days ) and possible variants of tickets ( tickets ), and gives a list of tickets (in the form of indices from the input array of ticket options) that you need to buy Pete
Petit's duty schedule is specified in the form of a sorted array of numbers (from 1 to 100 inclusive), each of which indicates the ordinal number of the day of duty:
[2, 5, 10, 45] // , , .
Each subscription ticket is described by the following interface:
interface Ticket { duration: number; // , , ( 1 100 ) cost: number; // ( 1 100 ) }
The number of ticket options is no more than 10, and it is guaranteed that all tickets have a different cost, and the more days a ticket is valid, the lower its cost per one day.
The solution must be provided as a CommonJS module:
module.exports = function (days, tickets) { // Your code here. };
The verdict RE also means that the submitted solution is incorrect.
Extra options
Examples
On the first and second days, Petya needs to buy one-day tickets, on the fourth day, a seven-day, on the twentieth day, one more day.
The total cost of such tickets will be as low as possible:
| Input | Conclusion |
| [0, 0, 1] |
On the first and second days, Petya needs to buy one-day tickets, on the fourth day, a seven-day, on the twentieth day, one more day.
The total cost of such tickets will be as low as possible:
19 .Decision
One of the possible solutions is the dynamic programming method, namely:
1. Take the first day of duty Petit.
2. To find the best solution for this day, we will calculate the possible options for each of the tickets. Each such option consists of the cost of the ticket and the cost of the best decision on the day of duty, following the day of expiration of the ticket. The second term is calculated in the same way, thus obtaining recursion.
3. Additionally, we take into account the number of tickets if there are several such options.
4. Particular attention should be paid to caching solutions in intermediate days.
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; }; Here is a link to a task analysis for backend developers.
Source: https://habr.com/ru/post/460139/
All Articles