Проверить что заданная строка является палиндромом.

Пример 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Объяснение: "amanaplanacanalpanama" – палиндром.

Пример 2:
Input: s = "race a car"
Output: false
Объяснение: "raceacar" – не палиндром.

Пример 3:
Input: s = " "
Output: true
Объяснение: "" – пустая строка это палиндром.

                                
package main

import (
	"fmt"
)

func main() {
	fmt.Println(isPalindrome("A man, a plan, a canal: Panama")) // true
	fmt.Println(isPalindrome("race a car")) // false
	fmt.Println(isPalindrome(" ")) // true
}

func isPalindrome(s string) bool {
	if s == "" {
		return true
	}

	begin, end := 0, len(s) - 1

	for begin < end {
		for begin < end && !isAlphanumericChar(s[begin]) {
			begin++
		}
		for begin < end && !isAlphanumericChar(s[end]) {
			end--
		}
		if begin < end && charToLower(s[begin]) != charToLower(s[end]) {
			return false
		}
		begin++
		end--
	}

	return true
}

func charToLower(c byte) byte {
	if c >= 'A' && c <= 'Z' {
		c += 32
	}
	return c
}

func isAlphanumericChar(c byte) bool {
	return (c >= '0' && c <= '9') ||
        (c >= 'a' && c <= 'z') ||
        (c >= 'A' && c <= 'Z')
}
                                
                            

В массиве чисел, переместить все нули в конец массива.

Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Пример 2:
Input: nums = [0]
Output: [0]

                                
package main

import (
	"fmt"
)

func main() {
	fmt.Println(moveZeroes([]int{0,1,0,3,12})) // 1,3,12,0,0
	fmt.Println(moveZeroes([]int{0})) // 0
}

// Вариант решения с дополнительной памятью
func moveZeroes(nums []int) []int {
	ans := make([]int, len(nums), len(nums))
	numZeroes := 0

	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			ans[numZeroes] = nums[i]
			numZeroes++
		}
	}

	return nums
}

// Вариант решения без дополнительной памяти,
// очень хороший и больше для мидла
func moveZeroes(nums []int) []int {
	nonZeroIndex := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[i], nums[nonZeroIndex] = nums[nonZeroIndex], nums[i]
			nonZeroIndex++
		}
	}

	return nums
}
                                
                            

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

⚠️ Важно: решение не должно использовать дополнительную память.

Пример 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Пример 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

                                
package main

import (
  "fmt"
)

func main() {
		fmt.Println(removeDuplicates([]int{1,1,2})) // 2
		fmt.Println(removeDuplicates([]int{0,0,1,1,1,2,2,3,3,4})) // 5
}

func removeDuplicates(nums []int) int {
    ln := len(nums)
    if ln <= 1 {
        return ln
    }

    j := 0
    for i := 1; i < ln; i++ {
        if nums[j] != nums[i] {
            j++
            nums[j] = nums[i]
        }
    }

    return j + 1
}
                                
                            

Есть односвязный список, нужно определить есть ли в этом списке цикл.

Пример 1:
Input: 3 → 2 → 0 → -4 → 2 (из -4 список возвращается в 2)
Output: true

Пример 2:
Input: 1 → 2 → 1 (из 2 возвращается в 1)
Output: true

Пример 3:

Input: 0 → 1 → 2 → 3
Output: false

                                
package main

import (
	"fmt"
)

func main() {
	head := &ListNode{3, nil}
	head.Next = &ListNode{2, &ListNode{0, &ListNode{-4, head}}}

	head2 := &ListNode{1, nil}
	head2.Next = &ListNode{2, &ListNode{0, head2}}

	head3 := &ListNode{0, nil}
	head2.Next = &ListNode{1, &ListNode{2, &ListNode{3, head2}}}

	fmt.Println(hasCycle(head)) // true
	fmt.Println(hasCycle(head2)) // true
	fmt.Println(hasCycle(head3)) // false
}

type ListNode struct {
	Val int
	Next *ListNode
}

// hashmap solution
func hasCycle(head *ListNode) bool {
	seen := make(map[*ListNode]int)

	for head!=nil {
		if _, ok := seen[head]; ok {
			return true
		} else {
			// create an entry
			seen[head] = 1
		}
		head = head.Next
	}

	return false
}

// two pointers solution
func hasCycle(head *ListNode) bool {
	first, second := head, head
	for first != nil && first.Next != nil {
		first = first.Next.Next
		second = second.Next
		if first == second {
			return true
		}
	}
	return false
}
                                
                            

Написать алгоритм сжатия строки по следующему принципу:

Пример 1:
Input: aaaaabbbbbbbbcd
Output: a5b8c1d1

Пример 2:
Input: abcaaaaaaaaaaaaaaaaaabbc
Output: a1b1c1a18b2c1

                                
package main

import (
  "fmt"
)

func main() {
	fmt.Println(squeeze("aaaaabbbbbbbbcd")) // a5b8c1d1
	fmt.Println(squeeze("abcaaaaaaaaaaaaaaaaaabbc")) // a1b1c1a18b2c1
	fmt.Println(squeeze("aaaa")) // a4
	fmt.Println(squeeze("abcde")) // a1b1c1d1e1
}

func squeeze(data string) string {
	var result strings.Builder

	repeated := 1

	for i := 0; i < len(data); i++ {
		if i < len(data) - 1 && data[i] == data[i+1] {
			repeated++
		} else {
			result.WriteString(fmt.Sprintf("%c%d", data[i], repeated))
			repeated = 1
		}
	}

	return result.String()
}
                                
                            

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

Input: []Trip[{"x", "d"}, {"c", "e"}, {"e", "b"}, {"d", "c"}]
Output: [x d c e b]

                                
package main

import (
	"fmt"
)

type Trip struct {
	from string
	to   string
}

func main() {
	trips := []Trip{
		{"c", "e"},
		{"x", "d"},
		{"d", "c"},
		{"e", "b"},
	}

	fmt.Println(route(trips)) // [x d c e b]
}

func route(trips []Trip) []string {
	result := make([]string, 0, len(trips) + 1)
	head := ""
	tos := make(map[string]bool)
	adjList := make(map[string]string)

	// transform array to adjacency list
	for _, part := range trips {
		adjList[part.from] = part.to
		tos[part.to] = true
	}

	// find the head
	for _, part := range trips {
		if _, ok := tos[part.from]; !ok {
			head = part.from
			break
		}
	}

	if head == "" {
		panic("Wrong data set, head is not defined")
	}

	result = append(result, head)

	// traverse from the head and collect a result
	for {
		result = append(result, adjList[head])
		if _, ok := adjList[head]; !ok {
			break
		}

		head = adjList[head]
	}

	return result
}
                                
                            

Дан массив интервалов, нужно объединить пересекающиеся интервалы и вернуть результирующий массив.

Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пример 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

                                
package main

import (
	"fmt"
)

func main() {
	fmt.Println(merge([][]int{{1,3},{2,6},{8,10},{15,18}})) // [[1,6],[8,10],[15,18]]
	fmt.Println(merge([][]int{{1,4},{4,5}})) // [[1,5]]
}

func merge(s [][]int) [][]int {
    // sort intervals by start value
    sort.Slice(s, func(i,j int) bool {
        return s[i][0] < s[j][0]
    })

    res := [][]int{s[0]} // its guaranteed that there will be at least one interval.
    i := 0

    for idx := 1; idx < len(s); idx++ {
        switch {
        case s[idx][0] >= res[i][0] && s[idx][0] <= res[i][1]:
            //  start of the second interval lays inside first
            res[i][0], res[i][1] = Min(res[i][0], s[idx][0]), Max(res[i][1], s[idx][1])
        case s[idx][1] >= res[i][0] && s[idx][1] <= res[i][1]:
            // the end of the second interval lays inside first
            res[i][0], res[i][1] = Min(res[i][0], s[idx][0]), Max(res[i][1], s[idx][1])

        default:
            res = append(res, s[idx])
            i++
        }
    }
    return res
}

func Min(x,y int) int {
    if x < y {
        return x
    }
    return y
}

func Max(x,y int) int {
    if x < y {
        return y
    }
    return x
}
                                
                            

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

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

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

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

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

                                
package main
import (
	"fmt"
	"math/rand"
	"time"
)
func randNumsGenerator(n int) <-chan int {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	out := make(chan int)
	go func() {
		for i := 0; i < n; i++ {
			out <- r.Intn(n)
		}
		close(out)
	}()
	return out
}
func main() {
	for num := range randNumsGenerator(10) {
		fmt.Println(num)
	}
}
                                
                            

Даны n каналов типа chan int. Надо написать функцию, которая смерджит все данные из этих каналов в один и вернет его.
Для этого напишем функцию, которая будет асинхронно читать из исходных каналов, которые ей передадут в качестве аргументов, и писать в результирующий канал, который вернется из функции.
- Создаем канал, куда будем сливать все данные. Он будет небуферезированный, потому что мы не знаем, сколько данных придет из каналов.
- Дальше асинхронно прочитаем из исходных каналов и закроем результирующий канал для мерджа, когда все чтение закончится.
- Чтобы дождаться конца чтения, просто обернем этот цикл по каналам в wait group.

                                
package main
import (
	"sync"
	"fmt"
)
func joinChannels(chs ...<-chan int) <-chan int {
	mergedCh := make(chan int)
	go func() {
		wg := &sync.WaitGroup{}
		wg.Add(len(chs))
		for _, ch := range chs {
			go func(ch <-chan int, wg *sync.WaitGroup) {
				defer wg.Done()

				for id := range ch {
					mergedCh <- id
				}
			}(ch, wg)
		}
		wg.Wait()
		close(mergedCh)
	}()
	return mergedCh
}

func main() {
	a := make(chan int)
	b := make(chan int)
	c := make(chan int)
	go func() {
		for _, num := range []int{1, 2, 3} {
			a <- num
		}
		close(a)
	}()
	go func() {
		for _, num := range []int{20, 10, 30} {
			b <- num
		}
		close(b)
	}()
	go func() {
		for _, num := range []int{300, 200, 100} {
			c <- num
		}
		close(c)
	}()
	for num := range joinChannels(a, b, c) {
		fmt.Println(num)
	}
}
                                
                            

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

Главное — не забыть закрыть каналы, чтобы ничего нигде не заблокировалось.

                                
package main
import (
	"fmt"
)
func main() {
	naturals := make(chan int)
	squares := make(chan int)
	go func() {
		for x := 0; x <= 10; x++ {
			naturals <- x
		}

		close(naturals)
	}()
	go func() {
		for x := range naturals {
			squares <- x * x
		}

		close(squares)
	}()
	for x := range squares {
		fmt.Println(x)
	}
}
                                
                            

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

                                
package main
import (
	"fmt"
)
func worker(id int, f func(int) int, jobs <-chan int, results chan<- int) {
    for j := range jobs {
        results <- f(j)
    }
}
func main() {
    const numJobs = 5
    jobs := make(chan int, numJobs)
    results := make(chan int, numJobs)
    multiplier := func(x int) int {
	    return x * 10
    }
    for w := 1; w <= 3; w++ {
        go worker(w,  multiplier, jobs, results)
    }
    for j := 1; j <= numJobs; j++ {
        jobs <- j
    }

    close(jobs)
    for i := 1; i <= numJobs; i++ {
        fmt.Println(<-results)
    }
}
                                
                            

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

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

                                
package main
import (
	"fmt"
)
type sema chan struct{}
func New(n int) sema {
	return make(sema, n)
}
func (s sema) Inc(k int) {
	for i := 0; i < k; i++ {
		s <- struct{}{}
	}
}
func (s sema) Dec(k int) {
	for i := 0; i < k; i++ {
		<-s
	}
}
func main() {
	numbers := []int{1, 2, 3, 4, 5}
	n := len(numbers)
	sem := New(n)
	for _, num := range numbers {
		go func(n int) {
			fmt.Println(n)
			sem.Inc(1)
		}(num)
	}
	sem.Dec(n)
}
                                
                            

Реализуйте функцию perm(), принимающую срез или строку и выводящую все возможные комбинации его (ее) символов.
Мы используем типы rune для обработки и срезов, и строк. Runes являются кодовыми точками из Unicode, а значит могут парсить строки и срезы одинаково.

                                
package main
import "fmt"
// Perm вызвает f с каждой пермутацией a.
func Perm(a []rune, f func([]rune)) {
        perm(a, f, 0)
}
// Пермутируем значения в индексе i на len(a)-1.
func perm(a []rune, f func([]rune), i int) {
        if i > len(a) {
                f(a)
                return
        }
        perm(a, f, i+1)
        for j := i + 1; j < len(a); j++ {
                a[i], a[j] = a[j], a[i]
                perm(a, f, i+1)
                a[i], a[j] = a[j], a[i]
        }
}
func main() {
    Perm([]rune("abc"), func(a []rune) {
            fmt.Println(string(a))
    })
}
                                
                            

Реализуйте функцию reverse, получающую срез целых чисел и разворачивающую его без использования временного среза.
Цикл for меняет местами значения каждого элемента среза. Значения будут следовать слева направо, и в итоге все элементы будут развернуты.

                                
package main
import "fmt"
func reverse(sw []int) {
        for a, b := 0, len(sw)-1; a < b; a, b = a+1, b-1 {
                sw[a], sw[b] = sw[b], sw[a]
        }
}
func main() {
    x := []int{3, 2, 1}
    reverse(x)
    fmt.Println(x)
}
                                
                            

                                
package main

import (
	"fmt"
	"sort"
	"strconv"
)

// Задача: из массива неповторяющихся чисел вывести диапазоны.
// Массив может быть неотсорирован

// 8 1 5 3 2 7  -> "1-3,5,7-8"
// 1 2 -> "1-2"
// 1 4 -> "1,4"

func main() {
	cases := [][]int{
		{1, 2, 3, 5, 7, 8, 11},
		{1, 3, 5, 7, 9},
		{1, 3, 4, 9, 6, 2},
		{1, 2},
		{1, 4},
	}

	for i, _ := range cases {
		fmt.Println(cases[i], "->", buildRange(cases[i]))
	}

}

func buildRange(nums []int) string {
	if len(nums) == 0 {
		return ""
	}

	if len(nums) == 1 {
		return strconv.Itoa(nums[0])
	}

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	chars := []byte{}

	rangeStart, rangeEnd := nums[0], nums[0]
	current, next := 0, 0

	for i := 0; i < len(nums); i++ {
		current = nums[i]

		if i < len(nums)-1 {
			next = nums[i+1]
		}

		if current+1 == next {
			rangeEnd = next
			continue
		}

		chars = append(chars, strconv.Itoa(rangeStart)...)

		if rangeStart != rangeEnd {
			chars = append(chars, '-')
			chars = append(chars, strconv.Itoa(rangeEnd)...)
		}

		chars = append(chars, ',')

		rangeStart = next
		rangeEnd = next
	}

	return string(chars[:len(chars)-1])
}