Как прошел IT’s Tinkoff Solution Cup

Привет! Провели финал IT’s Tinkoff Solution Cup 22 апреля. Шесть треков, нестандартные задачи и призы. У нас получилось собрать офлайн много крутых разработчиков и близких по духу людей, порешать задачи и пообщаться с коллегами.

Рассказываем, как все прошло, и разбираем задачи разных треков.

Как готовили чемпионат

Идея чемпионата возникла, когда мы задумались над мероприятием для объединения сообщества. Хотелось чего-то фанового, практико-ориентированного и непохожего на классические олимпиады и контесты. Задумывали такой формат, чтобы участвовали мидлы и сеньоры без каких-то специфических навыков.

Соревнование готовили 60 человек, еще 150 подключали по разным задачам. Нам хотелось классного мероприятия — заявить о себе и воплотить креативные задумки. Многие организаторы до этого были участниками других чемпионатов и хотели провести что-то свое в новой роли.

Еще мотивировало общение с комьюнити: узнать людей из других компаний, обменяться новостями — кто какие продукты делает и какие технологии запускает. А финал проводили в Москве, и для кого-то мотивацией стало именно это — приехать и интересно провести время.

На отборочном туре запускали разные задания, в том числе немного алгоритмических задач — потому что их проще проверять автоматически, когда много участников. А в финале уделили внимание задачам, приближенным к реальности, — чтобы взглянуть на кейсы под интересным углом и применить результаты в работе.

Участникам было интересно проверить знания, логические способности и получить удовольствие от решения сложных задач. Мы организовали очные площадки с настольными играми, ИТ-квизами, подарками и общением.

Особенности Solution Cup:

Первый в истории Тинькофф чемпионат такого формата — восемь тысяч регистраций, четыре тысячи решенных задач и 700 человек на очных площадках в 14 городах.
Призовой фонд — 3,6 млн рублей на все треки.
Шесть треков — Mobile, Backend, Frontend, SRE, системный анализ и Data Engineering. Добавили редкие треки, потому что у нас в компании специалисты этих направлений активно растут.

Для системных аналитиков не так много всего проводится и сложно найти соревнования. Расскажем о том, что получилось, в отдельной статье.

В трек Backend включили пять языков: Java, Python, C#, Scala и Golang. Java — один из самых популярных в Тинькофф, а Scala и Go более редкие, но у нас есть для них задачи и активные команды разработчиков, которые развивают свои направления.

В SRE была командная работа: ребята создавали код под открытые лицензии Apache 2.0 — это значит, что решение можно использовать для своей работы дальше.

Рассказываем, чего ждали от участников и какие задачи решали на каждом треке.

Mobile

Для подготовки соревнований мы собрали команду из Android- и iOS-разработчиков с опытом в контестах и хакатонах, а также тех, кто хотел себя попробовать в новой роли. Мы брейнштормили и собирали идеи — от реализации хитрых анимаций до мини-игр. Выбирали те, что относятся к нашей экспертизе финтеха.

Так на отборочном этапе оказались задачи про валидацию номера карты с применением алгоритма Луна и расчет выдачи банкомата. Делали упор на то, что мы мобильные разработчики: на каждую платформу придумали список вопросов с разными уровнями сложности и задачу на поиск view.

Задача про банкомат. Есть банкомат, в котором хранятся купюры пяти номиналов: 20, 50, 100, 200 и 500 $. Изначально банкомат пуст. Клиент может использовать банкомат для внесения или снятия любой суммы.

При снятии банкомат отдает приоритет использованию банкнот большего номинала.

Например, если вы хотите снять 300 $ и есть две банкноты по 50 $, одна банкнота 100 $ и одна банкнота 200 $, то банкомат будет использовать банкноты по 100 и 200 $.

Но если вы попытаетесь снять 600 $, а есть три банкноты по 200 $ и одна банкнота 500 $, запрос на снятие средств будет отклонен, поскольку банкомат сначала попытается использовать 500 $, а затем не сможет использовать банкноты для выдачи оставшихся 100 $. Обратите внимание, что банкомату не разрешено использовать банкноты 200 $ вместо банкноты 500 $.

Для хранения состояния банкомата необходимо добавить поля, отвечающие за номиналы и количество банкнот заданного номинала.

private val denominations = intArrayOf(20, 50, 100, 200, 500) private val banknotesVariants = denominations.size private val currentAmount = LongArray(banknotesVariants)

private let denominations = [20, 50, 100, 200, 500] private var balance = [0, 0, 0, 0, 0]

Функция пополнения банкомата — это цикл с заполнением количества банкнот соответствующего номинала:

fun deposit(banknotesCount: IntArray) {     for (i in 0..currentAmount.lastIndex) {     currentAmount[i] = currentAmount[i] + banknotesCount[i] } }

func deposit(_ banknotes: [Int]) {     for i in 0 ..< banknotes.count {     balance[i] = balance[i] + banknotes[i] } }

Функция списания более интересная. Поскольку банкомат обязан отдавать предпочтение купюрам наибольшего номинала, вот что нужно сделать для списания:

Пройтись от самых крупных до самых мелких купюр, поэтапно вычитая набранную сумму из требуемой к выдаче.
Если после прохода по номиналам не удалось собрать заказанную сумму, мы возвращаем массив, содержащий −1.
В случае выдачи нужно обновить состояние банкомата, так как количество купюр в нем изменилось.

Функция для списания средств будет выглядеть так:

fun withdraw(amount: Int): IntArray { val toWithdraw = IntArray(banknotesVariants) var remainingAmountToWithdraw = amount for (i in toWithdraw.lastIndex downTo 0) {     val banknotesQuantity = min((remainingAmountToWithdraw / denominations[i]).toLong(), currentAmount[i]).toInt()     toWithdraw[i] = banknotesQuantity     remainingAmountToWithdraw -= banknotesQuantity * denominations[i]     if (remainingAmountToWithdraw <= 0) {         break     } }     if (remainingAmountToWithdraw != 0) {     return intArrayOf(-1) }     for (i in 0..currentAmount.lastIndex) {     currentAmount[i] = currentAmount[i] - toWithdraw[i] }  return toWithdraw }

func withdraw(_ amount: Int) -> [Int] { var result = [0, 0, 0, 0, 0] var remainingAmount = amount        for i in result.indices.reversed() {     let banknotesQuantity = min((remainingAmount / denominations[i]), balance[i])     result[i] = banknotesQuantity     remainingAmount -= banknotesQuantity * denominations[i]                if remainingAmount <= .zero {         break     } }        if remainingAmount != .zero {     return [-1] }        for i in 0 ..< balance.count {     balance[i] = balance[i] - result[i] }        return result }

Соберем все вместе, тогда итоговая реализация банкомата будет такой:

import java.util.Arrays import kotlin.math.min    class ATM {     private val denominations = intArrayOf(20, 50, 100, 200, 500)     private val banknotesVariants = denominations.size     private val currentAmount = LongArray(banknotesVariants)         fun deposit(banknotesCount: IntArray) {     for (i in 0..currentAmount.lastIndex) {         currentAmount[i] = currentAmount[i] + banknotesCount[i]     }     }         fun withdraw(amount: Int): IntArray {     val toWithdraw = IntArray(banknotesVariants)     var remainingAmountToWithdraw = amount     for (i in toWithdraw.lastIndex downTo 0) {         val banknotesQuantity = min((remainingAmountToWithdraw / denominations[i]).toLong(), currentAmount[i]).toInt()         toWithdraw[i] = banknotesQuantity         remainingAmountToWithdraw -= banknotesQuantity * denominations[i]         if (remainingAmountToWithdraw <= 0) {             break         }     }         if (remainingAmountToWithdraw != 0) {         return intArrayOf(-1)     }         for (i in 0..currentAmount.lastIndex) {         currentAmount[i] = currentAmount[i] - toWithdraw[i]     }         return toWithdraw     } }

class ATM {     private let denominations = [20, 50, 100, 200, 500]     private var balance = [0, 0, 0, 0, 0]        func deposit(_ banknotes: [Int]) {     for i in 0 ..< banknotes.count {         balance[i] = balance[i] + banknotes[i]     }     }        func withdraw(_ amount: Int) -> [Int] {     var result = [0, 0, 0, 0, 0]     var remainingAmount = amount            for i in result.indices.reversed() {         let banknotesQuantity = min((remainingAmount / denominations[i]), balance[i])         result[i] = banknotesQuantity         remainingAmount -= banknotesQuantity * denominations[i]                    if remainingAmount <= .zero {             break         }     }            if remainingAmount != .zero {         return [-1]     }            for i in 0 ..< balance.count {         balance[i] = balance[i] - result[i]     }            return result     } }

Backend

Во время соревнований большинство участников назвали интересной упрощенную задачу про нашу легендарную игру «5 букв». О ней и расскажем.

Нужно было реализовать метод для проверки решений, который принимает на вход две строки строгой длины в пять символов: загаданное слово и предположение игрока.

Мы упростили постановку: участникам не нужно проверять, существует ли слово, которое загадал игрок, осталось сравнить слова и вернуть ответ в виде массива из чисел.

Каждый элемент — это число, отвечающее за совпадения:

−1 — буква отсутствует;

0 — буква есть, но в другом месте;

1 — буква на месте.

Основная сложность крылась в пограничных кейсах. Например, при проверке повторяющихся букв нужно учитывать их количество: если в ответе «ТЕКСТ» есть только одна буква Е, а пользователь отправил слово «ЕГЕРЬ», то только одна буква Е должна быть помечена как 0, остальные — как −1.

Один из интересных тестов затрагивал три одинаковые буквы: АГАВА и ПАЛКА. Соответственно, ожидался результат 0, −1, −1, −1, 1:

0 (попали, но буква не там);

−1 (не попали);

−1 (букв А всего две, поэтому помечаем, что такой больше нет);

−1 (не попали);

1 (попали).

Разберем решение. Сначала собираем словарь, в котором отмечаем, сколько раз повторяются одинаковые буквы:

var result = new int[5]; var letterToRemainingCount = answer     .GroupBy(letter => letter)     .ToDictionary(letter => letter.Key, letter => letter.Count());

После помечаем совпавшие и отсутствующие буквы:

for (var letterIndex = 0; letterIndex < 5; letterIndex++) {     var letter = suggestion[letterIndex];     if (!letterToRemainingCount.ContainsKey(letter)) {         result[letterIndex] = -1;     }     else if (answer[letterIndex] == letter) {         letterToRemainingCount[letter]--;         result[letterIndex] = 1;     } }

В последнюю очередь отмечаем буквы, которые стоят не на своем месте:

for (var letterIndex = 0; letterIndex < 5; letterIndex++) {     if (result[letterIndex] != 0) {         continue;     }      var letter = suggestion[letterIndex];     if (!letterToRemainingCount.ContainsKey(letter)) {         throw new Exception();     }      if (letterToRemainingCount[letter] > 0) {         letterToRemainingCount[letter]--;          result[letterIndex] = 0;     }     else {         result[letterIndex] = -1;     } }

Полный код:

public static string Solve(string suggestion, string answer) {     var result = new int[5];     var letterToRemainingCount = answer         .GroupBy(letter => letter)         .ToDictionary(letter => letter.Key, letter => letter.Count());      for (var letterIndex = 0; letterIndex < 5; letterIndex++) {         var letter = suggestion[letterIndex];         if (!letterToRemainingCount.ContainsKey(letter)) {             result[letterIndex] = -1;         }         else if (answer[letterIndex] == letter) {             letterToRemainingCount[letter]--;              result[letterIndex] = 1;         }     }      for (var letterIndex = 0; letterIndex < 5; letterIndex++) {         if (result[letterIndex] != 0) {             continue;         }          var letter = suggestion[letterIndex];         if (!letterToRemainingCount.ContainsKey(letter)) {             throw new Exception();         }          if (letterToRemainingCount[letter] > 0) {             letterToRemainingCount[letter]--;              result[letterIndex] = 0;         }         else {             result[letterIndex] = -1;         }     }      return string.Join(", ", result); }

Frontend

Готовить задания для фронтенд-секции мы начали еще в январе. Так как фронтенд — это не только JavaScript, очень важно было декомпозировать составление задач по областям, чтобы каждый участник оргкомитета взял на себя определенную часть работы. Еще в начале договорились уйти от алгоритмических задач, чтобы соревнования получились максимально интересными, а задачи были связаны с реальными проектами. Именно так появились задания на теорию (викторина) и практику.

С начала подготовки до финала мы собирались каждую неделю и обсуждали, придумывали и выбирали задачи, а перед турниром попросили коллег, которые не участвовали в чемпионате, порешать их. Мы старались подойти к соревнованиям ответственно и найти слабые или непонятные места. А теперь подробнее пример задачи.

Часто в работе фронтенд-приложения нужно загрузить файл на сервер. Иногда файл очень большой или есть ограничения на максимальный размер запроса. В таких случаях приходится разбивать файл на /** Настройки загрузки */ type Options = { readonly maxChunks: number; readonly chunkSize: number; } /** Интерфейс источника данных */ interface Source { readonly size: number; read(start: number, end: number): Blob; } /** Функция обратного вызова, отправляющая данные на сервер */ type SendCb = (data: Blob, offset: number) => Promise<void>;

Теперь определим алгоритм работы загрузчика. Мы создадим массив «потоков», размер которого будет равен максимальному количеству параллельно отправляемых чанков.

Под потоком будем подразумевать промис, который последовательно считает и отправляет чанки друг за другом, пока они не закончатся. И с помощью Promise.all будем ждать завершения всех потоков.

Для этого внутри функции upload объявим пустую функцию uploadNextChunk (функция потока).

function uploadNextChunk(): Promise<void> {     ...        }

Тогда сам код функции загрузки будет выглядеть как:

await Promise.all(     new Array(options.maxChunks).fill(0).map(         () => uploadNextChunk(),     ), );

Конструкция new Array(<количество>).fill(0) нужна для того, чтобы созданный массив имел значения. Если бы мы использовали только new Array(<количество>), то не смогли бы воспользоваться методом map.

Чтобы все части загрузились по одному разу, мы можем создать очередь, из которой будем брать описание следующего чанка для загрузки, или использовать счетчик блоков:

// Общее количество чанков, которое надо загрузить const chunksCount = Math.ceil(file.size / options.chunkSize);  // Количество чанков, оставшихся незагруженными let chunksLeft = chunksCount;  Теперь допишем нашу функцию uploadNextChunk: // Если мы уже прочитали весь файл, то просто завершаем работу «потока» if (!chunksLeft) {return Promise.resolve();}  // Вычисляем смещение, с которого надо прочитать данные const offset = (chunksCount - chunksLeft) * options.chunkSize;  // и уменьшаем количество оставшихся частей chunksLeft--;  // И отправляем чанк на сервер return send(  file.read(offset, offset + options.chunkSize), offset)     .then(uploadNextChunk()) );

После того как загрузится текущий чанк, функция uploadNextChunk встанет в очередь микрозадач для загрузки последующей части. В случае ошибки поток прервется и Promise.all, используемый в основной функции, вернет выброшенную ошибку.

Но остальные потоки пока ничего не знают об ошибке и будут отправлять чанки, пока они есть, — не очень хорошее поведение. Чтобы его избежать, заведем переменную error с признаком ошибки и при каждом последующем вызове uploadNextChunk будем анализировать ее значение. Тогда весь код будет выглядеть так:

export async function upload(file: Source, send: SendCb, options: Options): Promise<void> {    // Общее количество чанков, которое надо загрузить    const chunksCount = Math.ceil(file.size / options.chunkSize);     // Количество чанков, оставшихся незагруженными    let chunksLeft = chunksCount;    let error = false;     await Promise.all(new Array(options.maxChunks).fill(0).map(() => uploadNextChunk()));     function uploadNextChunk(): Promise<void> {        // Если мы уже прочитали весь файл, то просто завершаем работу «потока»        if (!chunksLeft) {return Promise.resolve();}         // Вычисляем смещение, с которого надо прочитать данные        const offset = (chunksCount - chunksLeft) * options.chunkSize;         // и уменьшаем количество оставшихся частей        chunksLeft--;         // И отправляем чанк на сервер        return send(file.read(offset, offset + options.chunkSize), offset).then(            // если ошибка была в другом «потоке», то досрочно завершаем этот            () => error ? Promise.resolve() : uploadNextChunk(),            e => {                error = true;                return Promise.reject(e);            }        );    } }

SRE

Объявив подготовку к соревнованиям открытой, мы собрали оргкомитет по нашему треку и решили, что проведем все в формате хакатона. Запланировали

Оконные функции lead и lag позволяют получить следующее и предыдущее значения поля в рамках окна. Логично их использовать так, как они и задумывались: lead — для следующего значения, а lag — для предыдущего.

Обычно мы так и делаем. Если изменить сортировку для одной из этих функций, то она сделает то же, что и другая с нормальной сортировкой. Почему так происходит? Попробуем рассмотреть на таблице ниже:

При изменении направления сортировки оконные функции начинают работать как их противоположность

В примере ответ 1 — верный, поля из задания всегда равны. Но можно ли всегда полагаться на это? На самом деле нет. Когда в поле сортировки есть одинаковые значения, мы не можем гарантированно знать, каким будет порядок строк в окне.

Например, если бы в примере мы выполняли сортировку не по столбцу с, а по столбцу b или d, то мы и СУБД не смогли бы однозначно определить порядок строк. Тогда значения в полях col1 и col2 различались бы — и мы не смогли бы найти верный ответ.

Это говорит нам, что важно не только понимать, как работает запрос, но и иметь представление о данных внутри запроса.

Впечатления и итоги

Отзывы с очных площадок были очень теплыми. Многим понравился формат, и участники писали, что соскучились по живым мероприятиям. Мы классно провели время, пообщались.

Победителям, занявшим первые места в отборе, мы оплатили поездку в Москву на финал. Приятно, что две трети финалистов приехали из регионов и даже из Беларуси.

Финал в Москве прошел в лофтовом пространстве Goelro. Приехали почти 300 участников:

— Backend — 75;

— Frontend — 55;

— системный анализ — 35;

— Data Engineering — 35;

— iOS — 28;

— Android — 27;

— SRE — 20.

Тем же вечером провели награждение победителей.

Нас так зарядила атмосфера соревнований и дух комьюнити, что мы уже изучили обратную связь. К следующим соревнованиям постараемся улучшить технические аспекты, а правила и временные рамки сделать понятнее и проще.

Ловите атмосферу на фотографиях в альбоме и делитесь впечатлениями в комментариях. А полные разборы заданий публикуем на главной странице соревнования. Спасибо всем, кто был с нами!

ссылка на оригинал статьи https://habr.com/ru/articles/733090/