Geekly articles weekly

Programming Championship: tugas parsing untuk pengembang front-end

Suatu hari, pemenang kejuaraan pemrograman, yang berakhir pada awal musim panas, menerima hadiah yang layak. Untuk melakukan ini, kami memanggil mereka, serta semua finalis lainnya dari 20 besar setiap arah ke kantor Yandex Moscow. Sekali lagi, selamat untuk mereka yang berhasil mencapai final.

Sementara itu, kami menyiapkan diskusi tentang tugas-tugas kejuaraan yang ditawarkan kepada pengembang front-end. Ini adalah tugas dari tahap kualifikasi. Kami mengingatkan Anda bahwa kejuaraan diadakan di empat bidang: backend, frontend, pembelajaran mesin, dan analitik.

A. Termometer


Ketentuan


Menggunakan navigator, banyak yang melihat "termometer" ketika membangun rute mobil. Ini adalah garis lurus multi-warna, yang menunjukkan kemacetan jalan pada rute. Dalam tugas ini, diusulkan untuk menulis fungsi yang mengadaptasi data "termometer" untuk ukuran layar yang berbeda.

Input fungsi diberi berbagai warna dengan panjang yang length dan lebar ukuran layar ( length ≥ width ) di mana termometer akan ditampilkan. Warna-warna GREEN , YELLOW dan RED -masing sesuai dengan beban rendah, sedang dan tinggi. Warna sebanding dalam hal lalu lintas: GREEN < YELLOW < RED .

Array awal, mulai dari elemen pertama, dibagi menjadi beberapa sub-susunan length / width (angka akan selalu berupa bilangan bulat). Di setiap subarray, perlu untuk mengatur warna sesuai dengan meningkatnya tingkat kemacetan jalan, pilih warna median dan ganti seluruh set dengan itu. Dalam kasus array dengan panjang genap, “median bawah” dipilih (elemen n/2 dalam deretan n elemen yang dipesan). Hasilnya harus berupa array warna dengan panjang width .

Solusinya harus disediakan sebagai modul CommonJS:

 module.exports = function (segments, width) { // Your code here. };

Putusan RE juga berarti bahwa solusi yang diajukan salah.

Opsi tambahan
MasukKesimpulan
 const segments = ['GREEN', 'GREEN', 'RED', 'GREEN', 'YELLOW', 'RED', 'GREEN', 'YELLOW', 'RED', 'YELLOW']; const width = 5;
['GREEN', 'GREEN', 'YELLOW', 'GREEN', 'YELLOW']

Solusi


1. Pecahkan array awal segmen menjadi segmen length / width .
2. Di setiap segmen, pilih warna median, berdasarkan kondisi, dan tambahkan warna yang ditemukan ke array yang dihasilkan.

solusi.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. Klien Torrent


Ketentuan


Anda memutuskan untuk menulis klien torrent Anda. Fiturnya adalah dengan bantuannya dimungkinkan untuk mengirimkan teks saja.

Klien torrent hampir siap, yang paling penting tetap: untuk mengumpulkan teks sumber dari bagian-bagian di mana ia dibagi untuk transmisi.

Tulis fungsi yang akan menunggu semua bagian teks dimuat dan kumpulkan sumbernya.

Fungsi menerima objek dengan dua bidang: chunkCount dan emitter , dan mengembalikan janji yang mengandung teks sumber atau kesalahan dalam bentuk string dari format yang ditentukan.

chunkCount - jumlah bagian di mana teks dipecah.

Setiap bagian teks memiliki pengidentifikasi dan waktu pengiriman yang unik. Potongan dengan waktu pengiriman yang lebih lama berada lebih jauh dari awal teks.

emitter - objek yang bisa Anda gunakan untuk mendapatkan potongan teks yang diunduh. Potongan-potongan teks mungkin tiba dengan penundaan waktu yang sewenang-wenang. Urutan potongan bisa apa saja.

Jika potongan teks yang sama diterima dua kali sebelum unduhan selesai dengan sukses, fungsi tersebut akan menimbulkan kesalahan "Duplicate: <id>" (dengan id bagian teks menggantikan <id> ).

Setelah semua bagian teks telah diterima, perlu untuk menggabungkannya menjadi satu baris dan mengembalikan baris ini menggunakan janji. Jika dua potong memiliki waktu kirim yang sama, urutan keping-keping ini dalam string yang dikembalikan dapat berupa apa saja.

Jika transfer tidak selesai dalam satu detik, fungsi tersebut akan menimbulkan kesalahan "Timed out" .

Input sesuai dengan antarmuka pada TypeScript
( Gambaran umum antarmuka TS.)

 interface Input { chunkCount: number; emitter: Emitter; } interface Emitter { on: (callback: (chunk: Chunk) => void) => void; } interface Chunk { id: number; timestamp: Date; data: string; }


Solusinya harus disediakan sebagai modul CommonJS:

 module.exports = function ({chunkCount, emitter}) { //  Promise };

Putusan RE juga berarti bahwa solusi yang diajukan salah.

Opsi tambahan
Contohnya
MasukKesimpulan
 { chunkCount: 3, emitter: {on: (fn) => { fn({id: 5314, data: 'The Good, ', timestamp: new Date('2019-01-01')}); fn({id: 1543, data: 'd the Ugly', timestamp: new Date('2019-01-03')}); fn({id: 2494, data: 'the Bad an', timestamp: new Date('2019-01-02')}); }} }
Resolved with "The Good, the Bad and the Ugly"
 { chunkCount: 1, emitter: {on: (fn) => { fn({id: 0, data: 'hello', timestamp: new Date('2019-01-01')}); fn({id: 0, data: 'world', timestamp: new Date('2019-01-02')}); }} }
Rejected with "Duplicate id: 0"
 { chunkCount: 2, emitter: {on: (fn) => {}} }
Rejected with "Timed out"

Solusi


  • Simpan potongan yang dimuat ke objek chunk .
  • Pada saat yang sama, kami memeriksa keberadaan id . Jika sudah ada, maka batalkan janjinya.
  • Setelah memuat semua bagian, urutkan dan kombinasikan.
  • Sejalan dengan ini, Anda perlu mengatur batas waktu 1 detik.


solusi.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. Pohon biner


Ketentuan


Pengembang Grisha diberi tugas untuk mengimplementasikan pohon biner , tetapi ia kurang memahami esensi dan membuat banyak kesalahan. Bantu dia menemukan dan memperbaikinya.

Penting untuk menemukan dan memperbaiki kesalahan dalam kode task.js Kelas harus diekspor untuk bekerja dengan pohon biner. Antarmuka kelas:

 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; }

Catatan : Pertimbangkan JSDoc yang benar.

Putusan RE juga berarti bahwa solusi yang diajukan salah.

Opsi tambahan
Contoh Input :
 let output = ''; BinaryTreeNode.create(10, 5, 13, 7, 20, 12).inorder((data) => { output += data + '-'; });

Kesimpulan :
 5-7-10-12-13-20-

Solusi


 /** * @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


Ketentuan


Desainer telah memperbarui logo Yandex.Maps (skala x5):



Ini perlu digunakan dalam berbagai kondisi. Untuk membuatnya senyaman mungkin, buat dengan satu elemen HTML di CSS murni. Logo dapat digunakan di sembarang tempat antarmuka, jadi penting untuk ditampilkan dengan benar di latar belakang apa pun.

Anda tidak dapat menggunakan gambar (bahkan melalui data:uri ).

Opsi tambahan

- Warna Lingkaran Tengah: #fff
- Warna lingkaran luar: # f33
- Warna "kaki": # e00000

Solusinya harus disediakan sebagai file CSS. File Anda akan terhubung sebagai solution.css ke halaman HTML dalam formulir:

 <!DOCTYPE html> <html> <head> <style> body { margin: 0; } </style> <link rel="stylesheet" href="solution.css"> </head> <body> <div></div> </body> </html>

Penting : logo harus terletak di sudut kiri atas halaman, ditekan dengan seksama.

Solusi Anda akan diuji di browser Google Chrome 69 .

Kami menyarankan untuk menggunakan plugin untuk tata letak pixel-perfect, seperti PerfectPixel .

Solusi


 //          . 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


Ketentuan


Pengembang Ivan memutuskan untuk memperbaiki gaya CSS halaman tersebut, setelah itu ia merusak penampilannya.

Desain awal:

Anda perlu menyesuaikan tampilan dengan desain asli dengan jumlah perubahan paling sedikit pada file CSS saat ini.

Penting : Saat menambahkan item ke daftar, kisi harus tumbuh sama.

Gaya CSS setelah refactoring: ./solution.css .

Setelah koreksi, Anda perlu menyediakan file CSS yang diperbarui. File ini akan terhubung sebagai solution.css tetap.css ke halaman HTML .

Opsi tambahan
Solusi Anda akan diuji di browser Google Chrome 69 . Keluarga font dan pengaturan font lainnya tidak perlu diubah. Dalam kasus ini, secara lokal, font mungkin tidak cocok dengan keadaan yang diharapkan, karena tangkapan layar diambil di Ubuntu.

Kami menyarankan untuk menggunakan plugin untuk tata letak pixel-perfect, seperti PerfectPixel .

Solusi


Perubahan hanya boleh dilakukan dengan pemilih .event dan turunannya.

 :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. Naik kereta bawah tanah


Ketentuan


Ada Devopia Petya. Di tempat kerja, ia harus bertugas pada hari-hari tertentu selama 100 hari ke depan. Petya mulai bekerja dengan metro. Tiket kereta bawah tanah diperkenalkan yang berlaku untuk beberapa hari sejak perjalanan pertama. Semakin lama tiket berlaku, semakin rendah biaya per hari. Adalah penting untuk membantu Petya menghemat uang dan menghitung tiket apa yang dia butuhkan untuk membeli tiga bulan sebelumnya, dengan mempertimbangkan jadwal tugasnya, sehingga total biaya mereka serendah mungkin. Dan Petya tidak suka membawa banyak tiket, dan jika ada beberapa opsi tiket dengan biaya minimum yang sama, maka Petya membutuhkan satu tiket dengan lebih sedikit tiket. Jika ada beberapa opsi seperti itu (dengan biaya minimum dan jumlah tiket yang sama), maka Pete akan memenuhi semua itu.

Anda perlu menulis fungsi getCheapestTickets(days, tickets) yang menjadikan jadwal tugas Petya ( days ) dan opsi tiket yang memungkinkan sebagai input dan memberikan daftar tiket (dalam bentuk indeks dari array input opsi tiket) yang perlu Anda beli Pete.

Jadwal tugas Petya diberikan dalam bentuk susunan angka yang diurutkan (mulai dari 1 hingga 100), yang masing-masing menunjukkan nomor urut hari tugas:

 [2, 5, 10, 45] //     , ,        .

Setiap tiket dijelaskan oleh antarmuka berikut:

 interface Ticket { duration: number; //  ,           ,    ( 1  100 ) cost: number; //   ( 1  100 ) }

Jumlah opsi tiket tidak lebih dari 10, dan dijamin bahwa semua tiket memiliki harga yang berbeda, dan semakin hari tiket berlaku, semakin rendah biayanya dalam satu hari.

Solusinya harus disediakan sebagai modul CommonJS:

 module.exports = function (days, tickets) { // Your code here. };

Putusan RE juga berarti bahwa solusi yang diajukan salah.

Opsi tambahan
Contohnya

MasukKesimpulan
 const days = [1, 2, 4, 6, 7, 8, 9, 10, 20]; const tickets = [ { cost: 3, duration: 1 }, { cost: 10, duration: 7 }, { cost: 20, duration: 30 } ];
[0, 0, 1]

Pada hari pertama dan kedua Petya perlu membeli tiket satu hari, pada hari keempat adalah tujuh hari, pada hari kedua puluh satu hari lagi.

Total biaya tiket tersebut akan serendah mungkin: 19 .

Solusi


Salah satu solusi yang mungkin adalah metode pemrograman dinamis, yaitu:

1. Ambil Petit hari tugas pertama.
2. Untuk menemukan solusi terbaik untuk hari ini, kami menghitung opsi yang memungkinkan untuk masing-masing tiket. Setiap opsi tersebut terdiri dari biaya tiket dan biaya solusi terbaik pada hari tugas setelah tanggal kedaluwarsa tiket ini. Istilah kedua dihitung dengan cara yang sama, sehingga mendapatkan rekursi.
3. Selain itu, pertimbangkan jumlah tiket, jika ada beberapa opsi seperti itu.
4. Perhatian khusus harus diberikan pada solusi caching di hari-hari sementara.

solusi.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; };


Berikut ini tautan ke tugas parsing untuk pengembang backend.

Source: https://habr.com/ru/post/id460139/

More articles:


All Articles