Size: a a a

2016 November 01

A

Aldar in pro.algorithms
Detur
рекурсивно память жрет
смотря в каком языке программирования)
источник

D

Detur in pro.algorithms
в любом
источник

D

Detur in pro.algorithms
если компилятор за тебя в цикл не развернет
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
#algorithm Бинарный поиск
Задача
Пусть есть некое условие p(i) и отрезок поиска [L, R].
Условие p монотонно - то есть, найдется такое x что оно выполняется для всех чисел <= x и не выполняется для чисел > x.
Найти значение x.
Решение
Будем считать что p(L-1) = true и p(R+1) = false.
Установим в начале l=L-1 и r=R+1 и будем поддерживать инвариант p(l)=true и p(r)=false внутри цикла.

int binarySearch(int L, int R, function<bool(int)> p) {
 int l = L-1, r = R+1;
 while (l + 1 < r) { // итерируемся пока l и r не будут соседними числами
   int mid = (l + r) / 2; // если l и r не соседи то mid != l, mid != r
   if (p(mid)) {
     l = mid;
   } else {
     r = mid;
   }
 }
 return l; // для i <= l p(i) == true, для i > l (i >= r) p(i) == false
}


Примеры использования:
Дан отсортированный массив a = [a0, a1, .., an], все элементы различны. Найти в нем элемент k.
p(i) = a[i] <= k; L=0; R=n. На выходе получим максимальный индекс x такой, что a[x] <= k. Если k есть в массиве то a[x] == k.

Дан массив a = [a0 > a1 > .. > an < b1 < b2 < .. < bm]. Найти индекс минимального элемента (an).
p(i) = a[i] < a[i+1]; L=0; R=len(a)-1.
На выходе получим максимальный индекс x такой, что a[x] < a[x+1] > a[x+2].
источник

A

Aldar in pro.algorithms
источник

A

Aldar in pro.algorithms
Формализовать бинарный поиск - это хорошо
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
kapkapbopoh
Есть вопрос по алгоритму Флойда ( про поиск всех кратчайших путей ) : важен ли порядок перебора вершин?
нет, не важен
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
#hackerrank_problem #medium
Задача на бинарный поиск:  https://www.hackerrank.com/contests/master/challenges/ctci-ice-cream-parlor
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
#hackerrank_problem #medium
Задача на бинарный поиск: ctci-ice-cream-parlor.
Бонус: есть альтернативное решение за O(n), не использующее бинарный поиск.

Разбор решения будет завтра в это же время.
источник
2016 November 02

k

kapkapbopoh in pro.algorithms
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
> It seems totally crazy to hire someone just based on a score on what is essentially a site for practicing coding interview questions. At least, that's what I see it as and that's the reason I signed up for it along with leetcode.
источник

A

Aldar in pro.algorithms
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
Окасаки клеви, полезно читать не только функциональщикам
источник

A

Alex Ф-ф-фэils!🌠︙ in pro.algorithms
Aldar
Задача - развернуть односвязный список
О, было тогда)
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
Aldar
Задача - развернуть односвязный список
используя O(1) дополнительной памяти, надеюсь?)
источник

A

Aldar in pro.algorithms
это уж кто как горазд
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
источник

GM

Golden Melon in pro.algorithms
Здорово
источник

A

Aldar in pro.algorithms
источник

A

Alex Ф-ф-фэils!🌠︙ in pro.algorithms
Опубликовал группу в новостях
источник