Цикличная сортировка

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

Алгоритм:
1.    Для каждого элемента массива ищем правильную позицию для вставки этого элемента.
2.    Когда мы находим правильную позицию, проверяем, не находимся ли мы уже в начале цикла. Если да, завершаем текущий цикл.
3.    Вставляем элемент на правильную позицию.
4.    Переходим к следующему элементу и повторяем процесс.
5.    Повторяем процесс до тех пор, пока не отсортируем все элементы.

Пример задачи: Отсортировать массив целых чисел с использованием цикличной сортировки.
 

package main
 
import "fmt"
 
func cycleSort(arr []int) {
      length := len(arr)
 
      for cycleStart := 0; cycleStart < length-1; cycleStart++ {
            item := arr[cycleStart]
            pos := cycleStart
 
            // Находим правильную позицию для текущего элемента
            for i := cycleStart + 1; i < length; i++ {
                  if arr[i] < item {
                        pos++
                  }
            }
 
            // Если текущая позиция совпадает с началом цикла, значит, элемент уже на своем месте
            if pos == cycleStart {
                  continue
            }
 
            // Пропускаем дубликаты
            for item == arr[pos] {
                  pos++
            }
 
            // Перемещаем элемент на его правильную позицию
            if pos != cycleStart {
                  item, arr[pos] = arr[pos], item
            }
 
            // Перемещаем оставшиеся элементы в текущий цикл
            for pos != cycleStart {
                  pos = cycleStart
                  for i := cycleStart + 1; i < length; i++ {
                        if arr[i] < item {
                              pos++
                        }
                  }
 
                  for item == arr[pos] {
                        pos++
                  }
 
                  if item != arr[pos] {
                        item, arr[pos] = arr[pos], item
                  }
            }
      }
}

#ПовторяемАлгосы

Алгосы не нужны

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

Я считаю, что они нужны. И сегодня я обсуждал это с коллегой, который просто растоптал меня своим аргументом 😅

Для того чтобы попасть в один желтый банк, я проходил 4 этапа собеседования. Мы успели алгосы порешать, пройти архитектурную секцию, скриминг и программирование. А что получил на выходе ? Переписываем простенький легаси php на новый фреймворк.

Вот от такого и действительно немного подгорает. Все компании начали пихать эту алгос секцию, отсеивать кандидатов. А для чего ? Для того, чтобы у них скилловые ребята делали подобные задачи?

Хочу, чтобы уровень вопросов соответствовал тому, чем ты будешь заниматься на этом месте.

Жиза?

Я снова в телеке

Новое видео - подкаст с Олегом Козыревым, Go-разработчиком, автором курсов и актером. Его можно считать отправной точкой в создании этого канала.

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

Но если подробнее то мы обсудили:
- Зачем нужен личный бренд Олегу?
- Минусы личного бренда для айтишника.
- Как найти первую аудиторию?
- Что значит качественный контент?
- Про контент план и теневой бан от ютуба
- Где больше денег – разработка или курсы?

И как обычно говорят блогеры - не забудьте поставить лайк и подписаться

YouTube: https://go.kotelov.com/youtube_podcast_ep49
Mave: https://go.kotelov.com/mave_podcast_ep49

#подкаст

Сегодня буду вещать о том как проходить собеседования. Тема доклада - «Грокаем технические собеседования (чит-коды на прохождение)» звучит? Мне кажется - топ. Поговорим что ждут от кандидатов, зачем нужна самопрезентация и немного советов дам из своего опыта.

Сейчас мчу в самый прикольный, на мой взгляд, офис ВК и это не Зингер.

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

Я разместил свое резюме на нескольких площадках для менторов и получил первые обращения. Провел с ними вводные созвоны и сделал несколько выводов:

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

- Я не хочу помогать людям в накрутке опыта. Да, в 2019 году при поиске работы я приписал себе лишние полгода опыта в студии, в которой работал всего месяц. Но это был первый и последний раз. Сразу поясню — накрутку не осуждаю, мне в целом плевать, кто что пишет в резюме, если он способен выполнять задачи в полной мере.

- Люди хотят изучать Go. Это не новость, иначе не было бы кучи курсов на эту тему. Если выделять основные причины, почему, то это:
* Деньги
* Надоел текущий язык программирования
* Go очень популярен
Но интересно то, что большая часть запросов приходит именно по переходу из PHP в Go.

В голове возникла мысль: может всё-таки стоит сделать какой-то контент на тему перехода из PHP в Go? Беглый поиск по YouTube показал, что подобные видео есть, но лично для себя я не нашел ни одного, который бы зацепил.

В общем, я поселил эту мысль в голове и буду её развивать. А теперь ещё и рассказал её вам, и ваши реакции на этот пост будут приближать меня к её реализации.

Я не пропал

Мне как-то раз друг сказал, что если я начинаю чем-то заниматься, то мне сразу надо пройти курсы, прочитать книги, изучить всё и подготовиться. Зря я тогда начал это отрицать.

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

Пост ни о чем, просто решил напомнить о себе и заодно узнать: я один такой, который хочет во всем, чем он занимается, добиться хоть каких-то результатов, а не просто зайти не в ту дверь?

Ну и если книгу читали, тоже скажите свое мнение, а то я пока понять не могу, нравится мне или нет

BFS (Breadth-First Search) или поиск в ширину

Основные применения метода поиска в ширину:
- Поиск кратчайшего пути в невзвешенных графах
- Проверка связности графа
- Поиск в лабиринтах и задачах на графы
- Определение уровня узлов в деревьях и графах
- Поиск компонент связности
- Сериализация и десериализация деревьев и графов

Алгоритм:
1.    Начнаем с определения начальной вершины.
2.    Помещаем начальную вершину в очередь и отмечаем ее как посещенную.
3.   Пока очередь не пуста, извлекаем вершину из очереди и проверяем все ее непосещенные соседние вершины.
4.    Добавляем каждую непосещенную соседнюю вершину в очередь и отмечаем ее как посещенную.
5.    Повторяем этот процесс до тех пор, пока не будут посещены все вершины графа или не будет найден целевой элемент.

По времени и памяти у нас O(V + E), где (для временной сложности):
- V — количество вершин (узлов) в графе.
- E — количество рёбер (или связей) в графе

Пример задачи: Найти кратчайший путь от начальной вершины до целевой вершины в графе.
 

package main
 
import (
     "fmt"
)
 
type Graph struct {
     Nodes map[string][]string
}
 
func NewGraph() *Graph {
     return &Graph{
         Nodes: make(map[string][]string),
     }
}
 
func (g *Graph) AddEdge(src, dest string) {
     g.Nodes[src] = append(g.Nodes[src], dest)
     g.Nodes[dest] = append(g.Nodes[dest], src) // для ненаправленного графа
}
 
func BreadthFirstSearch(graph *Graph, start, target string) []string {
     visited := make(map[string]bool)
     queue := make([]string, 0)
     parents := make(map[string]string)
 
     queue = append(queue, start)
     visited[start] = true
 
     for len(queue) > 0 {
         node := queue[0]
         queue = queue[1:]
 
         if node == target {
              path := []string{node}
              for node != start {
                   node = parents[node]
                   path = append([]string{node}, path...)
              }
              return path
         }
 
         for _, neighbor := range graph.Nodes[node] {
              if !visited[neighbor] {
                   visited[neighbor] = true
                   queue = append(queue, neighbor)
                   parents[neighbor] = node
              }
         }
     }
 
     return nil // Целевая вершина не достижима
}

Судя по реакциям и просмотрам, алгоритмы не зашли. Но сути это не меняет — я буду продолжать их постить, и наоборот, еще и статью на эту тему напишу!

Еще заметил, что у постов больше просмотров, чем людей в канале... Кто эти люди и почему они не подписались? Может, контент не устроил или подача, или в целом не интересно всё, что тут происходит. Этого я уже не узнаю, ну и ладно.

Пятница, время немного подумать о том, что было полезного сделано:
- Теперь я есть на платформе solvery.io, оказалось не так просто к ним попасть. Анкеты заполни, тесты пройди, видео запиши, курс изучи — короче, приключение на 5 минут.
- Пришел запрос на аудит приложения — это вообще что-то новое и интересное, будем работать.
- Почти дочитал «Пиши, сокращай», всё самое интересное оказалось в конце книги, позже сделаю отзыв.
- Перешел в новую команду во ВКонтакте и получил первые интересные таски.

Фотка кошки с пятничным настроем для сбора ваших лайков.

У меня нет такой любви к кофе как показывают в мемах и стереотипах про программистов, но вот готовить его - обожаю.

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

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

А сейчас мчим купаться и загорать, пока вы тут видос смотрите