Задача с Leetcode. Поиск в двумерной матрице

Сложность: Средняя

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

▪️ в строке элементы отсортированы по возрастанию (слева - направо);
▪️ в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

Решение:

func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
if matrix[i][j] == target {
return true
}
if matrix[i][j] < target {
i++
} else {
j--
}
}
return false
}


Временная сложность: O(m + n)
Пространственная сложность: O(1)


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

Задача: Треугольник наибольшей площади

Условие: дается массив точек на плоскости X-Y, где точки [i] = [xi, yi], верните площадь самого большого треугольника, который может быть образован любыми тремя различными точками. Будут приняты ответы в пределах 10-5 от фактического ответа.

Пример:

Ввод: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Вывод: 2.00000
Объяснение:

Ввод: points = [[1,0],[0,0],[0,1]]
Вывод: 0.50000

Решение

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

👣 DynamoMQ

DynamoMQ - это библиотека очередей сообщений, использующая DynamoDB в качестве хранилища, написанная на Go.

$ go install github.com/vvatanabe/dynamomq/cmd/dynamomq@latest

▪️Github

Вакансия: Golang backend developer 
Компания: Market Lab 
Формат работы: гибрид (Москва) / удалёнка - по желанию
ЗП: от 320 000 до 500 000 руб. на руки

ChatLab - SaaS решение для маркетинга, реализовано в виде CRM системы с мессенджером.

📌Чем предстоит заниматься:
—Принимать участие в создании архитектуры и разработке новых фичей;
—Профилирование и оптимизация высоконагруженных микросервисов;
—Unit-testing.

💥Что ожидаем:
—Опыт на Golang от 3 лет;
—Опыт разработки микросервисов, многопоточных приложений;
—Опыт разработки Web-сервисов (REST, gRPC, Websocket), опыт с Unix-системами;
—Наличие опыта разработки на других языках.

🎁Мы предлагаем:
— Гибрид, офис или удалёнка по твоему желанию :)
— У нас нет места для лагов: мы работаем на новых Макбуках;
— Комфортный рабочий день с 11 до 18, в пятницу до 17, чтобы у тебя было время на отдых;
— Ты можешь легко выбрать удобный способ получения ЗП;
— Ценим рвение к росту и обучению и даем возможность обучаться за счет компании.

📲 Присылай резюме: @a18dima

Наиближайшая сумма трёх

Сложность: Средняя

Условие задачи: Дан целочисленный массив и целевое значение суммы. Нужно найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.

Каждый массив имеет единственное решение.

Пример:

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2
Объяснение: (-1 + 2 + 1 = 2)

Ввод: nums = [0,0,0], target = 1
Вывод: 0

Решение:

func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
ans := 0
dist := int(^uint(0) >> 1) //dist = infinity

for i :=0; i<len(nums); i++{
l := i+1
r := len(nums)-1

for l < r{
sum := nums[i] + nums[l] + nums[r]
if sum == target{
return sum
}
if sum < target{
l = l + 1
if target - sum < dist{
dist = target-sum
ans = sum
}
}else{
r = r - 1
if sum - target < dist{
dist = sum-target
ans = sum
}
}
}
}
return ans
}

Временная сложность: O(nlogn)

Пространственная сложность: O(1)

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

🦦 Otter

Самая быстрая библиотека golang in-memory cache, основанная на алгоритме S3-FIFO. Раюотает во много раз быстрее, чем Ristretto.

Внутри используется хеш таблица, которая имеет мьютекс на каждый бакет + seq lock для чтения + каждый бакет помещается в две кеш линии, что предотвращает false sharing и это намногооо быстрее map с мьютексом и sync.Map.
Также исрользуется несколько трюков для избегания частых локов политики вытеснения: при чтении используются wait-free буфферы, которые иногда могут терять данные, но так как главная задача кеша - хранить наиболее частые элементы, то потери незначительны + реализация mpsc очереди при записи, которая значительно превосходит каналы по перфомансу и принцип из статьи bp-wrapper, который коротко можно назвать "batch, batch, batch" aka кеш не обновляет политику мгновенно, а только после наполнения небольшого буффера.

go get -u github.com/maypok86/otter

▪️Github

🦫Реализация односвязного списка в Golang

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

Введение в односвязные списки

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

У односвязного списка:

⬅️ В каждом узле содержатся данные.
⬅️ В каждом узле имеется ссылка — указатель next  — на следующий узел последовательности.
⬅️ В последнем узле обычно имеется ссылка nil, которой указывается на конец списка.

Узел — основа связного списка
В сердце связного списка находится понятие узла.

УЗЕЛ — ЭТО СТРОИТЕЛЬНЫЙ БЛОК ИЛИ КОНТЕЙНЕР, В КОТОРОМ СОДЕРЖАТСЯ: 1) СОХРАНЯЕМЫЕ ДАННЫЕ — ЧТО БЫ ВЫ НИ ВЫБРАЛИ — И 2) УКАЗАТЕЛЬ НА ТО, ЧТО СЛЕДУЕТ ДАЛЬШЕ.

Этой простой структурой формируется основа для создания односвязных — с последовательно связанными узлами — списков и двусвязных, где у узлов имеются ссылки на следующий и предыдущий узлы:

type Node struct {
data int
next *Node
}

type LinkedList struct {
head *Node
}

Структура Node здесь фундаментальный строительный блок односвязного списка. В ней инкапсулируются основные компоненты каждого узла списка:

▪️Поле data  — это хранимые в узле данные или значение. Мы задали ему целочисленный int, хотя на практике это может быть любой тип данных, необходимый конкретному приложению.
▪️Поле next  — это ссылка или указатель на следующий узел связанного списка. Ею узлы связываются в последовательную цепочку. Когда узел в списке последний, полем next указывается на nil  — конец списка.

Фактически структурой Node определяется, как выглядит отдельный элемент связного списка — с данными, которые в нем содержатся, и ссылкой на следующий элемент.

Структура LinkedList  — это связный список в целом, ею управляется набор узлов:

▪️Поле head  — ссылка или указатель на первый узел связного списка. Это точка входа в список, через которую получается доступ ко всей последовательности узлов для манипулирования ими.
Вместе структуры Node и LinkedList  — основа односвязного списка на Go. Структурой Node определяется то, как структурируются отдельные элементы, структурой LinkedList  — как эти элементы организуются в целостную структуру данных.

Хотя связный список создается и без типа LinkedList, предпочитаю как первичную структуру данных именно его LinkedList  — такой контейнер для связного списка, где инкапсулируется весь список, и кроме того, способ контролировать поведение списка.

Вставка данных в связный список

📌Читать

@golangprofi

👣 Почему сообщество #golang старается не использовать сторонние библиотеки?

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

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

Сложность в поддержке - теперь вы и ваша команда должны поддерживать добавленную библиотеку в актуальном состоянии.

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

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

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

Примерами библиотек, которые, на мой взгляд, являются достойными для внимания:

- Библиотеки шин сообщений (Kafka, RabbitMQ и т.д.)
- Библиотеки БД (Mongo, Postgres).
- Сложные криптографические вещи алгоритмы, которые не поддерживаются стандартной библиотекой.

👇 Напишите в комментаряих о ваших любимых сторонних библиотеках.

@golangprofi

👣 Huh.

Huh: простая, мощная библиотека для создания терминальных форм (написана на Go).

▪️Github

@golangprofi

👣 SGSG - Svelte + Go + SQLite + gRPC

Это полнофункциональное приложение с открытым исходным кодом, в основе которого лежат два основных принципа: ПРОИЗВОДИТЕЛЬНОСТЬ и ПРОСТОТА. Идея заключается в том, что вы можете взять этот шаблон и использовать его для создания собственного проекта и он будет очень хорошо масштабироваться.

Кроме того, это не очередной шаблон для разработчиков. В нем есть все, что нужно для запуска в продакшен: конфигурация Nginx, развертывание Docker, GitHub Actions, логирование Grafana и т. д.

▪️Github

⁉️ Хотите научиться писать эффективные интеграционные тесты на Go?

Тогда ждём вас на практическом уроке от OTUS, где вы вместе с опытным экспертом:

- посмотрите, какое место в пирамиде тестирования занимают интеграционные тесты;
- узнаете, зачем их писать;
- напишете несколько тестов на практике;
- получите ответы на все возникающие вопросы.

⏰ Встречаемся 2 июля в 20:00 мск в преддверии старта курса «Golang Developer. Professional». Все участники вебинара получат специальную цену на обучение!

➡️ Пройдите короткий тест прямо сейчас, чтобы не пропустить бесплатный урок: РЕГИСТРАЦИЯ

Восстановить IP

Сложность: Средняя

Условие задачи: Рабочий IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.

Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.

Пример:

Ввод: s = "25525511135"
Вывод: ["255.255.11.135","255.255.111.35"]

Ввод: s = "0000"
Вывод: ["0.0.0.0"]

Решение задачи

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

👣 errtrace - это экспериментальный пакет на Go для отслеживания пути возврата ошибки, трассировка возврата.

Если трассировка стека отслеживает путь кода, который привел к ошибке, то трассировка возврата отслеживает путь кода, который ошибка прошла, чтобы добраться до пользователя. Часто это один и тот же путь, но в Go они могут различаться, поскольку ошибки - это значения, которые могут передаваться между горутинами (например, с помощью каналов).

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

▪️Github

👣 Go + gRPC + GORM + SQLite + GIN + Swagger

gRPC - это система удалённого вызова процедур (RPC) с открытым исходным кодом, первоначально разработанная в Google в 2015 году. Она имеет открытый исходный код и используется для коммуникаций с архитектурой клиент-сервер.

gRPC может использовать буферы протоколов в качестве определения интерфейса lang

▪️Github

⭐️ Две структуры с одинаковыми полями могут иметь разный размер.

Это явление известно как "padding", понятие, заимствованное из языка C++, но применимое и в Go.

Рассмотрим приведенный выше пример.

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

Она увеличивается до 32 байт, в то время как структура B остается меньше - 16 байт.

👣 Roboden-game

Создать RTS, которая бы хорошо работала в браузере с помощью #golang, сложная задача, но возможная.

Игра написана с использованием движка Ebitengine и даже доступна в Steam.

•Github
•Проект

#ebitengine #gamedev #golang