👣 Тестовое задание для GoLang-разработчика

Описание задания
Необходимо разработать приложение, предоставляющее HTTP API для получения данных о парковках такси в г. Москва. Данные необходимо брать с этой страницы ("Актуальная версия").

Описание необходимого функционала
Приложение должно реализовывать:

▪Функционал загрузки данных из файла (локального и/или по ссылке) в хранилище данных (данные на источнике могут как удаляться, так и добавляться);

▪Обслуживание HTTP запросов к API-endpoints, которые реализуют поиск по хранимым данным;
Обслуживание HTTP запросов к роуту, возвращающему метрические данные (в формате prometheus) работы приложения.

▪Обновление данных в хранилище должно происходить без остановки обслуживания HTTP запросов к API с учетом того, что их объем может быть очень большим (и маппинг данных на источнике может изменяться).

Методы HTTP API должны возвращать ответ в формате json. Время обработки одного запроса к HTTP API (не загрузка данных в хранилище) - не более 2 мс. до первого байта HTTP ответа (TTFB). Проектирование самих методов API - на ваше усмотрение (минимально необходимый функционал - это поиск по global_id, id и mode).

Метрические данные должны включать в себя как минимум следующие метрики:

Общее количество обработанных запросов к API-endpoints;
Количество ошибок обработки HTTP запросов к API-endpoints (плюсом будет "разведение" по различным кодам ответов);
Данные по времени обработки HTTP запросов к API-endpoint;
Дополнительные метрики, на ваше усмотрение.

Требования к реализации

▪В качестве хранилища данных необходимо использовать Redis;
▪Все функции (экспортируемые и не экспортируемые) должны сопровождаться понятным комментарием (если возможно - на английском языке);
▪Не стоит излишне сокращать имена переменных и констант - код пишется для людей, и он должен быть максимально простым и понятным;
▪Можно использовать любые сторонние пакеты, но не использовать какой-либо фреймворк;
▪Весь ключевой функционал должен быть зафиксирован unit-тестами;
▪После завершения работы над заданием необходимо написать сопроводительную документацию по работе с приложением в файле README.md в корне репозитория;
▪Конфигурация параметров подключения к хранилищу данных должна иметь возможность управляться как флагами запуска, так и переменными окружения. Возможности конфигурирования должны быть описаны в файле README.md вашего репозитория.

Плюсами будут являться
▪Настройка CI (силами GitHub actions, TravisCI, etc) выполняющая запуск тестов и сборки на каждый коммит;
▪Автоматическая сборка Docker-образа с приложением;
▪Интуитивно-понятное разбитие коммитов - одной конкретной задаче - один коммит или PR (её правки - отдельный коммит или PR);
Написание всех текстов коммитов - на английском языке.

@golang_interview

👣 Тестовое задание для Mail.Ru Group

Текст задания:
Процессу на stdin приходят строки, содержащие интересующие нас URL. Каждый такой URL нужно дернуть и посчитать кол-во вхождений строки "Go". В конце работы приложение выводит на экран общее кол-во найденных строк "Go" во всех переданных URL, например:

$ echo -e 'https://golang.org\nhttps://golang.org\nhttps://golang.org' | go run 1.go
Count for https://golang.org: 9
Count for https://golang.org: 9
Count for https://golang.org: 9
Total: 27

Введенный URL должен начать обрабатываться сразу после вычитывания и параллельно с вычитыванием следующего. URL должны обрабатываться параллельно, но не более k=5 одновременно.

Обработчики url-ов не должны порождать лишних горутин, т.е. если k=1000 а обрабатываемых URL-ов нет, не должно создаваться 1000 горутин.

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

@golang_interview

👣 go-interview

Большой вборник вопросов технического собеседования, решенных с помощью Go

🖥 Github

@golang_interview

👣 Задание на разработку сервиса "Анти-брутфорс"

Общее описание
Сервис предназначен для борьбы с подбором паролей при авторизации в какой-либо системе.

Сервис вызывается перед авторизацией пользователя и может либо разрешить, либо заблокировать попытку.

Предполагается, что сервис используется только для server-server,т.е. скрыт от конечного пользователя.

Алгоритм работы

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

▪не более N = 10 попыток в минуту для данного логина.
▪не более M = 100 попыток в минуту для данного пароля (защита от обратного brute-force).
▪не более K = 1000 попыток в минуту для данного IP (число большое, т.к. NAT).

Для подсчета и ограничения частоты запросов, можно использовать например алгоритм leaky bucket. Или иные аналогичные: https://en.wikipedia.org/wiki/Rate_limiting

Причем сервис будет поддерживать множество bucket-ов, по одному на каждый логин/пароль/ip.

Bucket-ы можно хранить:

▪в памяти (в таком случае нужно продумать удаление неактивных bucket-ов, чтобы избежать утечек памяти).
▪во внешнем хранилище (например redis или СУБД, в таком случае нужно продумать производительность).

White/black листы содержат списки адресов сетей, которые обрабатываются более простым способом:

▪Если входящий IP в whitelist, то сервис безусловно разрешает авторизацию (ok=true);
▪Если - в blacklist, то отклоняет (ok=false).

Архитектура

Микросервис состоит из API, базы данных для хранения настроек и black/white списков. Опционально - хранилище для bucket'ов. Сервис должен предоставлять GRPC или REST API.

Описание методов API
Попытка авторизации

Запрос:

▪login
▪password
▪ip

Ответ:

▪ok (true/false) - сервис должен возвращать ok=true, если считает что запрос нормальный и ok=false, если считает что происходит bruteforce.

Сброс bucket
Должен очистить bucket-ы соответствующие переданным login и ip.

▪login
▪ip

Добавление IP в blacklist
подсеть (IP + маска)
Удаление IP из blacklist
подсеть (IP + маска)
Добавление IP в whitelist
подсеть (IP + маска)
Удаление IP из whitelist
подсеть (IP + маска)

▪Достаточно IPv4
▪Пример подсети: 192.1.1.0/25 - представляет собой адрес 192.1.1.0 с маской 255.255.255.128
▪Во время работы сервиса при поступлении очередного IP мы проходимся по подсетям в черных и белых списках и вычисляем, принадлежит ли IP одной из них.

Конфигурация
Основные параметры конфигурации: N, M, K - лимиты по достижению которых, сервис считает попытку брутфорсом.

Command-Line интерфейс
Необходимо так же разработать command-line интерфейс для ручного администрирования сервиса. Через CLI должна быть возможность вызвать сброс бакета и управлять whitelist/blacklist-ом. CLI может работать через GRPC/HTTP интерфейс.

Развертывание
Развертывание микросервиса должно осуществляться командой make run (внутри docker compose up) в директории с проектом.

Тестирование
Рекомендуется выделить модуль обработки одного bucket и протестировать его с помощью unit-тестов.

Так же необходимо написать интеграционные тесты, проверяющие все вызовы API.

@golang_interview

👣 Тестовое задание Middle. Сервис по планированию задач

Список фичей:

▪Пользователь может добавлять, удалять, закрывать и заново открывать задачи
▪Названия задач должны быть уникальными для всех пользователей (удаленные не учитываются).
▪Пользователь может получить список всех задач любого другого пользователя, кроме удаленных.
▪Пользователь может закрывать, удалять и заново открывать только свои задачи
▪Задача проходит следующие состояния: CREATED <--> CLOSED -> DELETED. При этом задача в статусе CREATED не может сразу перейти в DELETED. Задача же в DELETED больше не может переходить ни в какое состояние.

В рамках задания DELETED можно трактовать как фактическое удаление элемента, а не выставление какого-либо статуса.

Веб-сервер принимает сообщения по придуманному нами протоколу - Simple Web Protocol.

Запросы и ответы состоят из одной строки.

Формат запроса: "USER COMMAND ARG"

Формат ответа: "RESULT ARG"

Описание формата:
1. USER — имя пользователя, который осуществляет действие.
2. COMMAND — команда. Варианты команд:
▪CREATE_TASK MyTask — создать задачу с названием MyTask
▪CLOSE_TASK MyTask — закрыть задачу MyTask
▪DELETE_TASK MyTask — удалить задачу MyTask
▪REOPEN_TASK MyTask — заново открыть задачу MyTask
▪LIST_TASK USER — Получить список задач пользователя (в статусе CREATED и CLOSED)
▪__DELETE_ALL — Удалить информацию о всех пользователях и их задачах. Используется в тестах, чтобы «чистить» данные между их выполнением. Формат ответа для этой команды не имеет значения, так как он нигде не валидируется.

3. ARG — аргумент запроса или ответа. Может отсутствовать. Например, в запросе на создание задачи VASYA CREATE_TASK CleanRoom — это CleanRoom. А в ответе TASKS [MyTask1, MyTask2] — [MyTask1, MyTask2].

4. RESULT — ответ сервера о совершении действия. Варианты ответов.
▪CREATED — задача успешно создана
▪DELETED — задача успешно удалена
▪CLOSED — задача успешно закрыта
▪REOPENED — задача успешно открыта заново
▪TASKS [MyTask1, MyTask2] — список задач пользователя. Если задач нет, список пустой ([]). Задачи перечислены в порядке их создания.
▪WRONG_FORMAT — Неверный формат запроса
▪ACCESS_DENIED — Нет прав на совершение операции
▪ERROR — Любая другая ошибка

5. Все команды, а также имена пользователей регистрозависимые. В названии задач и имен пользователей не может быть пробелов.

6. Запросы валидируются в следующем порядке: формат запроса, право на совершение операции, все остальные проверки. Если первая проверка не прошла, остальные не выполняются.

Примеры запросов и ответов:
1.VASYA CREATE_TASK CleanRoom
CREATED

2.PETYA DELETE_TASK CleanRoom
ACCESS_DENIED

3.PETYA CREATE_TASK Task1
CREATED

4.PETYA CREATE_TASK Task2
CREATED

5. VASYA LIST_TASK PETYA
TASKS [Task1, Task2]

6. VASYA CREATE_TASK CleanRoom
ERROR

В данном примере состояние сервиса сохраняется между запросами, поэтому PETYA DELETE_TASK CleanRoom возвращает ACCESS_DENIED.

Дополнительные баллы
Учитывается общее оформление кода, архитектурное разделение компонентов, а также наличие Unit-тестов на отдельные части проекта.

@golang_interview

👣 Задание на разработку демона, осуществляющего "Системный мониторинг"

Общее описание

Демон - программа, собирающая информацию о системе, на которой запущена, и отправляющая её своим клиентам по GRPC.

Архитектура
▪GRPC сервер;
▪допускается использование временных (/tmp) файлов;
▪статистика хранится в памяти, долговременное хранение не предусмотрено.

Требования
Необходимо каждые N секунд выдавать информацию, усредненную за последние M секунд.

Например, N = 5с, а M = 15с, тогда демон "молчит" первые 15 секунд, затем выдает снапшот за 0-15с; через 5с (в 20с) выдает снапшот за 5-20с; через 5с (в 25с) выдает снапшот за 10-25с и т.д.

N и M указывает клиент в запросе на получение статистики.

Что необходимо собирать:

▪Средняя загрузка системы (load average).

▪Средняя загрузка CPU (%user_mode, %system_mode, %idle).

▪Загрузка дисков:

-tps (transfers per second);
-KB/s (kilobytes (read+write) per second);

▪Информация о дисках по каждой файловой системе:

-использовано мегабайт, % от доступного количества;
-использовано inode, % от доступного количества.
▪Top talkers по сети:

- по протоколам: protocol (TCP, UDP, ICMP, etc), bytes, % от sum(bytes) за последние M), сортируем по убыванию процента;
-по трафику: source ip:port, destination ip:port, protocol, bytes per second (bps), сортируем по убыванию bps.

▪Статистика по сетевым соединениям:

- слушающие TCP & UDP сокеты: command, pid, user, protocol, port;
-количество TCP соединений, находящихся в разных состояниях (ESTAB, FIN_WAIT, SYN_RCV и пр.).

Разрешено использовать только стандартную библиотеку языка Go!
Команды, которые могут пригодиться:

$ top -b -n1
$ df -k
$ df -i
$ iostat -d -k
$ cat /proc/net/dev
$ sudo netstat -lntup
$ ss -ta
$ tcpdump -ntq -i any -P inout -l
$ tcpdump -nt -i any -P inout -ttt -l
Статистика представляет собой объекты, описанные в формате Protobuf.

Информацию необходимо выдавать всем подключенным по GRPC клиентам с использованием однонаправленного потока.

Выдавать "снапшот" системы можно как отдельными сообщениями, так и одним жирным объектом.

Сбор информации, её парсинг и пр. должен осуществляться как можно более конкурентно.

Конфигурация

▪Через аргументы командной строки можно указать, на каком порту стартует сервер.
▪Через файл можно указать, какие из подсистем сбора включены/выключены.
Тестирование

Юнит-тесты
▪по возможности мок интерфейсов и проверка вызовов конкретных методов;
▪тесты вспомогательных функций и пр.

Интеграционные тесты

▪потестировать факт потока статистики, можно без конкретных цифр;
▪можно посоздавать файлы, пооткрывать сокеты и посмотреть на изменение снапшота.

Клиент

Необходимо реализовать простой клиент, который в реальном времени получает и выводит в STDOUT статистику по одному из пунктов (например, сетевую информацию) в читаемом формате (например, в виде таблицы).

@golang_interview

👣 Тестовое задание на разработку инструмента "SQL-мигратор"

Общее описание

Аналог инструментов, приведенных в секции "Database schema migration" awesome-go.

Инструмент, работающий с миграциями, написанными на Go или представленными в виде SQL-файлов.

Позволяет:

▪генерировать шаблон миграции;
▪применять миграции;
▪откатывать миграции.

Архитектура

Тулза должна создавать свои служебные таблицы в БД и работать с ними.

Требования

Установка в $GOPATH/bin командой go get github.com/awesomegother/migrator/cmd/gomigrator.

Или можно использовать её API в своих программах напрямую, импортировав библиотеку как пакет.

При этом вся логика тулзы должна располагаться в internal, а экспортируемое API в pkg.

Команды

Необходимо реализовать следующие команды (флаги команд см. в разделе Конфигурирование).

Создание миграции
$ gomigrator create <имя_миграции>

Применение всех миграций
$ gomigrator up
Откат последней миграции
$ gomigrator down
Повтор последней миграции (откат + накат)
$ gomigrator redo
Вывод статуса миграций
$ gomigrator status

Таблица из:

▪Статус (применена, применяется, ошибка и пр.)
▪Время последнего обновления статуса
▪Имя миграции

Вывод версии базы
$ gomigrator dbversion
- по сути номер последней примененной миграции.

Формат миграций
Вы должны предоставить пользователю API для описания up/down шагов миграции.

Если миграция в формате Go-кода, то она может иметь формат:

func Up_migration(o *someObject) {
}

func Down_migration(o *someObject) {
}
Где someObject - один из аргументов, которые вы считаете, могут пригодиться при описании миграции (транзакция, структура вашей библиотеки и пр.)

Если миграция в формате SQL, то необходимо придумать способ разделения между Up и Down шагами, например, с помощью комментариев.

Драйвер
Поддержки PostgreSQL достаточно.

Консистентность

Запуск тулзы в параллельных процессах возможен (например, две ноды приложения решили на старте применить свои миграции), при этом процессы не должны мешать друг другу и дублировать свои миграции, что можно реализовать с помощью блокировок на уровне БД (SELECT FOR UPDATE, pg_advisory_lock, etc).

Если идентификаторы миграций совпадают (ID, время, имя, пр. атрибут, который вы решили выбрать для идентификации миграции), то возможно, что один из процессов пропускает свои миграции, так как они уже применены другим.

Логирование
На ваше усмотрение, но здорово, когда инструмент имеет понятный и подробный вывод о ходе своей работы и статусе выполнения команды (ошибка, успех, что было сделано, какие идентификаторы и пр.).

Конфигурация
Основные параметры:

▪Строка подключения (DSN) к БД
▪Путь к директории с файлами миграций
▪Тип миграции: go/sql

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

dsn: $DB_DSN

Тестирование

Юнит-тесты
▪по возможности мок интерфейсов и проверка вызовов конкретных методов;
▪тесты вспомогательных функций и пр.

Интеграционные тесты
▪docker-compose + проверка работы тулзы на контейнере с PSQL;
▪тестовые миграции можно хардкодить;
▪можно напрямую дергать PSQL, чтобы проверить результат миграций.

@golang_interview

👣 Почему reflect и unsafe выводит разные значения у одного объекта в Golang?

Рассмотрим код:

package main

import (
"fmt"
"reflect"
"unsafe"
)

func main() {
s := "hello, world!"
hello := s[:5]
world := s[7:]
fmt.Printf("s = %s, sh = %v, sp = %d\n",
s,
*(*reflect.StringHeader)(unsafe.Pointer(&s)),
reflect.ValueOf(&s).Pointer(),
)

fmt.Printf("hello = %s, helloh = %v, hellop = %d\n",
hello,
*(*reflect.StringHeader)(unsafe.Pointer(&hello)),
reflect.ValueOf(&hello).Pointer(),
)

fmt.Printf("world = %s, worldh = %v, worldp = %d\n",
world,
*(*reflect.StringHeader)(unsafe.Pointer(&world)),
reflect.ValueOf(&world).Pointer(),
)

slice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
s1 := slice[:5]
s2 := slice[4:]
fmt.Printf("slice = %v, sh = %v, sp = %d\n",
slice,
*(*reflect.SliceHeader)(unsafe.Pointer(&slice)),
reflect.ValueOf(slice).Pointer(),
)

fmt.Printf("s1 = %v, s1h = %v, s1p = %d\n",
s1,
*(*reflect.SliceHeader)(unsafe.Pointer(&s1)),
reflect.ValueOf(s1).Pointer(),
)

fmt.Printf("s2 = %v, s2h = %v, s2p = %d\n",
s2,
*(*reflect.SliceHeader)(unsafe.Pointer(&s2)),
reflect.ValueOf(s2).Pointer(),
)
}
вывод

s = hello, world!, sh = {4817792 13}, sp = 824633786960
hello = hello, helloh = {4817792 5}, hellop = 824633786976
world = world!, worldh = {4817799 6}, worldp = 824633786992

slice = [1 2 3 4 5 6 7 8 9 10], sh = {824633860176 10 10}, sp = 824633860176
s1 = [1 2 3 4 5], s1h = {824633860176 5 10}, s1p = 824633860176
s2 = [5 6 7 8 9 10], s2h = {824633860208 6 6}, s2p = 824633860208

В случае со строкой, выводится другой sh от Pointer() 4817792 и 824633786960 (для примера), в то время как в слайсах они одинаковые.

Почему в данном случае у s и hello одинаковые sh - 4817792, а у world отличается, при том ,что по сути это срез исходной строки?

Тот же вопрос и про слайсы. Что значат эти числа?

Ответ

Пишите свой ответ в комментариях👇

@golang_interview

👣 Тестовое задание для разработчика на Go

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

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

1. Сервис получает информацию о новом заказе, создаёт в БД чеки для всех принтеров точки указанной в заказе и ставит асинхронные задачи на генерацию PDF-файлов для этих чеков. Если у точки нет ни одного принтера - возвращает ошибку. Если чеки для данного заказа уже были созданы - возвращает ошибку.

2. Worker'ы с помощью wkhtmltopdf генерируют PDF-файл из HTML-шаблона. Имя файла должно иметь следущий вид <ID заказа>_<тип чека>.pdf (123456_client.pdf). Файлы должны хранится в папке media/pdf в корне проекта.

3. Приложение опрашивает сервис на наличие новых чеков. Опрос происходит по следующему пути: сначала запрашивается список чеков которые уже сгенерированы для конкретного принтера, после скачивается PDF-файл для каждого чека и отправляется на печать.

📌 Технические требования

Сервис должен быть написан на GO
База данных - PostgreSQL
Все инфраструктурные вещи необходимые для сервиса (PostgreSQL, Redis, wkhtmltopdf) запускать в docker с помощью docker-compose, сам проект не нужно оборачивать в docker

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

📌 Модели

▪Принтер (Printer). Каждый принтер печатает только свой тип чеков. Поле api_key принимает уникальные значения, по нему однозначно определяется принтер. Для этой модели должны быть fixtures (принтеры для обоих типов чеков для нескольких точек).

Поле Тип Значение Описание
name CharField название принтера
api_key CharField ключ доступа к API
check_type CharField kitchen|client тип чека которые печатает принтер
point_id IntegerField точка к которой привязан принтер

▪Чек (Check). Информация о заказе для каждого чека хранится в JSON, нет необходимости делать отдельные модели.

Поле Тип Значение Описание
printer_id ForeignKey принтер
type CharField kitchen|client тип чека
order JSONField информация о заказе
status CharField new|rendered|printed статус чека
pdf_file FileField ссылка на созданный PDF-файл

API
Добавить описание доступных методов в файл api.yml (swagger-спецификация).

@golang_interview

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

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

Нужно посчитать количество появлений элементов первого массива (лучше брать тот, что покороче) — используем для этого словарь. Потом пройтись по второму массиву и вычитать из словаря те элементы, которые есть в нем. По ходу добавляем в результат те элементы, у которых частота появлений больше нуля.

package main

import (
"fmt"
)

// На вход подаются два неупорядоченных массива любой длины.
// Необходимо написать функцию, которая возвращает пересечение массивов
func intersection(a, b []int) []int {
counter := make(map[int]int)
var result []int

for _, elem := range a {
counter[elem]++
}

for _, elem := range b {
if count, ok := counter[elem]; ok && count > 0 {
counter[elem] -= 1
result = append(result, elem)
}
}
return result
}

func main() {

a := []int{23, 3, 1, 2}
b := []int{6, 2, 4, 23}
// [2, 23]
fmt.Printf("%v\n", intersection(a, b))
a = []int{1, 1, 1}
b = []int{1, 1, 1, 1}
// [1, 1, 1]
fmt.Printf("%v\n", intersection(a, b))
}

Пишите свое решение в комментариях👇

@golang_interview

👣 Почему Done() из интерфейса Context возвращает <-chan struct{}? Из какой горутины у нас что то записывается в этот канал и почему с этого канала возвращается пустая структура?

Метод Done() интерфейса Context возвращает канал <-chan struct{} для того, чтобы обеспечить механизм для оповещения о завершении операции в асинхронной среде. Когда операция завершается или контекст отменяется, канал закрывается. При этом значение пустой структуры struct{} записывается в этот канал, чтобы сигнализировать о завершении операции.

Обычно, главная горутина начинает операцию, создавая контекст, и передает его во все создаваемые горутины, которые выполняют асинхронную работу. Если в какой-то момент операция должна быть завершена, главная горутина вызывает метод cancel() у контекста. Это приводит к закрытию канала Done() во всех горутинах, подписанных на этот контекст. Когда горутина получает закрытый канал, это означает, что операция должна быть завершена.

Значение пустой структуры struct{} используется в качестве сигнала о завершении операции, потому что оно не занимает память и может быть передано по каналу без накладных расходов. Таким образом, когда канал закрывается, это означает, что операция завершена, и это сигнализирует всем горутинам, которые ждут завершения операции, что они могут продолжить выполнение.

А каналы в Go являются механизмом коммуникации и синхронизации, особенно между горутинами. Они позволяют передавать значения между горутинами и синхронизировать их работу.

@golang_interview

👣 Экономное вычисление выражений в польской записи

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

Например, выражение в польской записи выглядит как

(* 5 (+ 3 4))

Пусть выражения в польской записи состоят из имён переменных (от a до z), круглых скобок и трёх знаков операций: #, $ и @ (смысл операций мы определять не будем).

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

Требуется составить программу econom.go, вычисляющую количество операций, которые нужно выполнить для экономного вычисления выражения. Примеры работы программы приведены в таблице:

Набор тестов для программы экономного вычисления выражений в польской записи

Выражение Количество операций
x 0
($xy) 1
($(@ab)c) 2
(#i($jk)) 2
(#($ab)($ab)) 2
(@(#ab)($ab)) 3
(#($a($b($cd)))(@($b($cd))($a($b($cd))))) 5
(#($(#xy)($(#ab)(#ab)))(@z($(#ab)(#ab)))) 6

Решение

package main

func main() {
println(opCount("(#($(#xy)($(#ab)(#ab)))(@z($(#ab)(#ab))))"))
println(opCount("($xy)"))
println(opCount("x"))
}

func opCount(expr string) int {
expressions := map[string]bool{}
var openBraces []int
for i, c := range expr {
switch c {
case '(':
openBraces = append(openBraces, i)
case ')':
lastOpenBrace := len(openBraces) - 1
subExprStart := openBraces[lastOpenBrace]
subExpr := expr[subExprStart:i]
expressions[subExpr] = true
openBraces = openBraces[:lastOpenBrace]
}
}
return len(expressions)
}

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

const oper = node_t("oper")
const expr = node_t("expr")

type node struct {
t node_t
v string
}

func opCount(input string) int {
expressions := map[string]bool{}
var stack []node
for _, c := range input {
switch c {
case '$', '#', '@':
stack = append(stack, node{t: oper, v: fmt.Sprintf("%s", c)})
default:
stack = append(stack, node{t: expr, v: fmt.Sprintf("%s", c)})
}
for canFold(stack) {
lastIdx := len(stack) - 1
operIdx := lastIdx - 2
folded := node{t: expr, v: stack[operIdx].v + stack[operIdx+1].v + stack[operIdx+2].v}
expressions[folded.v] = true
stack[operIdx] = folded
stack = stack[:operIdx+1]
}
}
return len(expressions)
}

func canFold(stack []node) bool {
stackLen := len(stack)
return stackLen >= 3 && stack[stackLen-3].t == oper && stack[stackLen-2].t == expr && stack[stackLen-1].t == expr
}

Пишите свое решение в комментариях👇

@golang_interview

👣 Тестовое задание в Keenetic (NDMSystem) на junior+/Midle- программиста.

# Очередь на go с REST интерфейсом

## ТЗ

Реализовать брокер очередей в виде веб сервиса. Сервис должен обрабатывать 2 метода:

1. PUT /queue?v=message
Положить сообщение message в очередь с именем queue (имя очереди может
быть любое), пример:

curl -XPUT http://127.0.0.1/pet?v=cat
curl -XPUT http://127.0.0.1/pet?v=dog
curl -XPUT http://127.0.0.1/role?v=manager
curl -XPUT http://127.0.0.1/role?v=executive

в ответ {пустое тело + статус 200 (ok)}
в случае отсутствия параметра v - пустое тело + статус 400 (bad request)

2. GET /queue

Забрать (по принципу FIFO) из очереди с названием queue сообщение и вернуть в теле http запроса, пример (результат, который должен быть при выполненных put’ах выше):

curl http://127.0.0.1/pet => cat
curl http://127.0.0.1/pet => dog
curl http://127.0.0.1/pet => {пустое тело + статус 404 (not found)}
curl http://127.0.0.1/pet => {пустое тело + статус 404 (not found)}
curl http://127.0.0.1/role => manager
curl http://127.0.0.1/role => executive
curl http://127.0.0.1/role => {пустое тело + статус 404 (not found)}

при GET-запросах сделать возможность задавать аргумент timeout

curl http://127.0.0.1/pet?timeout=N

если в очереди нет готового сообщения получатель должен ждать либо до момента прихода сообщения либо до истечения таймаута (N - кол-во секунд). В случае, если сообщение так и не появилось - возвращать код 404. Получатели должны получать сообщения в том же порядке как от них поступал запрос, если 2 получателя ждут сообщения (используют таймаут), то первое сообщение должен получить тот, кто первый запросил.

Порт, на котором будет слушать сервис, должен задаваться в аргументах командной строки.

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

Желательно (но не обязательно) весь код расположить в одном go-файле (предполагается, что решение будет не больше 500 строк кода) для удобства проверки, никаких дополнительных файлов readme и т.п. не требуется, создание классической структуры каталогов (cmd/internal/...) не требуется.

Комментарии приветствуются и помогут нам понять ход Ваших мыслей при разработке.

Лаконичность кода будет восприниматься крайне положительно, не нужна "гибкость" больше, чем требуется для решения именно этой задачи, не нужны логи процесса работы программы (только обработка ошибок), никакого дебага и т.д... чем меньше кода - тем лучше!

Оцениваться корректность реализации (заданные условия выполняются),архитектурная составляющая (нет лишних действий в программе, только
решающие задачи программы), лаконичность и понятность кода (субъективно, конечно, но думайте о том, насколько будет понятен ваш. код для других, это куда более важно в командной разработке, чем сложный "крутой" код).

@Golang_google

👣 Тестовое задание дорожки в парке

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

Программа должна считывать со стандартного потока ввода количество аттракционов и их координаты. При этом координаты каждого аттракциона задаются парой целых чисел (в декартовой системе).

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

Например, для входных данных

12
2 4
2 5
3 4
3 5
6 5
6 6
7 5
7 6
5 1
5 2
6 1
6 2
программа должна выводить число 14.83.

@golang_interview

👣 Составьте программу, выполняющую построение графа делителей натурального числа такого, что .

Вершинами графа делителей являются все делители числа x, такого, что 0<x<2^32.

Ребро соединяет вершины u и v в том случае, если u делится на v, и не существует такого w, что u делится на v, и w делится на u.

Пример графа делителей изображён на рисунке.

@golang_interview

👣 Примеры, упражнения и тесты на Golang

Лучший способ изучить новый язык программирования — это практика. В этом репозитории собрано более 100 задач для Go. Изначально автор создал проект для своего курса, но позже добавил упражнения для всех желающих изучить этот язык:

🖥 Github

@golang_interview

👣 Вопросы и ответы для собеседования Back-end/Golang разработчика и не только

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

🖥 Github

@golang_interview