Facebook

[Zorkus]

Ну как бы если что-то реально пошло не так, всегда можно пойти к кому надо и эскалировать наверх / настучать по голове вниз, whichever appropriate, это не каждый же день случается. Если приоритеты поменялись - можно назначать отдельный митинг или просто письмо послать.

[АццкоМото]

Ну как бы если что-то реально пошло не так, всегда можно пойти к кому надо и эскалировать наверх / настучать по голове вниз, whichever appropriate, это не каждый же день случается. Если приоритеты поменялись - можно назначать отдельный митинг или просто письмо послать.

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

[Zorkus]

Ну. Если вася у всех вызывает, эту, ка ты сказал, идисинкразию, то это выяснится и так, в разговорах за чаем, в письмах и прочем.

[АццкоМото]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

[agrippina]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

Только одна на весь второй раунд? Они что-ли поменяли процесс интервью?

[Komissar]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

[agrippina]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

На глассдоре их как грязи. И скучных, и не очень.

[АццкоМото]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

Только одна на весь второй раунд? Они что-ли поменяли процесс интервью?

Одна. Понятия не имею, меняли ли.

[АццкоМото]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

Даны N точек на плоскости и некая "главная" точка. Найти K ближайших к ней. Точка = пара декартовых координат.

Вот такое вот УГ. Я ж говорил, скучная.

[Dweller]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

Даны N точек на плоскости и некая "главная" точка. Найти K ближайших к ней. Точка = пара декартовых координат.
Вот такое вот УГ. Я ж говорил, скучная.

O(N*log(K)) ?

[valchkou]

Вот такое вот УГ. Я ж говорил, скучная.

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

[АццкоМото]

O(N*log(K)) ?

Ну, вроде как. Но может и лучше можно, но не факт.
Отправная точка, например, тут: http://en.wikipedia.org/wiki/Partial_sorting
Но там за O(N*log(K)) получают (в терминах задачи) отсортированные К ближайших. Возможно, в произвольном порядке можно быстрее, но в O(N) не верится

[АццкоМото]

Вот такое вот УГ. Я ж говорил, скучная.

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

Охуж этот Голливуд

[Sergunka]

Возможно, в произвольном порядке можно быстрее, но в O(N) не верится

Вполне возможно если использовать группы к примеру первая группа расстояние от 0 до 1 вторая группа от 1 до 2 и тд. Когда первая группа переполняется т.е. больше чем К, то группа бьется на двое типо от 0 до 0.5 и от 0.5 до 1.

[crypto5]

O(N*log(K)) ?

Ну, вроде как. Но может и лучше можно, но не факт.
Отправная точка, например, тут: http://en.wikipedia.org/wiki/Partial_sorting
Но там за O(N*log(K)) получают (в терминах задачи) отсортированные К ближайших. Возможно, в произвольном порядке можно быстрее, но в O(N) не верится

По вашей ссылке есть вроде пара O(n+klogk)

[crypto5]

O(N*log(K)) ?

Ну, вроде как. Но может и лучше можно, но не факт.
Отправная точка, например, тут: http://en.wikipedia.org/wiki/Partial_sorting
Но там за O(N*log(K)) получают (в терминах задачи) отсортированные К ближайших. Возможно, в произвольном порядке можно быстрее, но в O(N) не верится

По вашей ссылке есть вроде пара O(n+klogk)

И еще есть линейный базирующийся на linear-time median-of-medians selection algorithm. Я правда когда то кажется пытался понять почему median-of-medians selection algorithm линейный, но так и не понял.

[АццкоМото]

Вполне возможно если использовать группы к примеру первая группа расстояние от 0 до 1 вторая группа от 1 до 2 и тд. Когда первая группа переполняется т.е. больше чем К, то группа бьется на двое типо от 0 до 0.5 и от 0.5 до 1.

Да, но как получить эти группы? Нужно либо заранее иметь какие-то предположения о распределении расстояний, либо сортировать, что уже n*log(n), т.е. очень плохо. Ну и отсортировав мы уже получаем ответ.

[АццкоМото]

По вашей ссылке есть вроде пара O(n+klogk)

Точно. И даже хуже того:
Even better is if we don't require those k items to be themselves sorted. Losing that requirement means we can ignore all partitions that fall entirely before or after the kth place. We recurse only into the partition that actually contains the kth element itself.
function quickfindFirstK(list, left, right, k)
if right > left
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
if pivotNewIndex > left + k // new condition
quickfindFirstK(list, left, pivotNewIndex-1, k)
if pivotNewIndex < left + k
quickfindFirstK(list, pivotNewIndex+1, right, k+left-pivotNewIndex-1)
The resulting algorithm requires an expected time of only O(n), which is the best such an algorithm can hope for.

Я знал, что такое есть, но не помнил про O(n) и в любом случае не сообразил бы как точно сделать это без гугления.

[АццкоМото]

И еще есть линейный базирующийся на linear-time median-of-medians selection algorithm. Я правда когда то кажется пытался понять почему median-of-medians selection algorithm линейный, но так и не понял.

А это разве не поиск k-th largest/smallest? В такой интерпретации я тоже не понял, почему он линейный, но умные дядьки говорят, значит так и есть

[Sergunka]

Вполне возможно если использовать группы к примеру первая группа расстояние от 0 до 1 вторая группа от 1 до 2 и тд. Когда первая группа переполняется т.е. больше чем К, то группа бьется на двое типо от 0 до 0.5 и от 0.5 до 1.

Да, но как получить эти группы? Нужно либо заранее иметь какие-то предположения о распределении расстояний, либо сортировать, что уже n*log(n), т.е. очень плохо. Ну и отсортировав мы уже получаем ответ.

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

[crypto5]

Вполне возможно если использовать группы к примеру первая группа расстояние от 0 до 1 вторая группа от 1 до 2 и тд. Когда первая группа переполняется т.е. больше чем К, то группа бьется на двое типо от 0 до 0.5 и от 0.5 до 1.

Да, но как получить эти группы? Нужно либо заранее иметь какие-то предположения о распределении расстояний, либо сортировать, что уже n*log(n), т.е. очень плохо. Ну и отсортировав мы уже получаем ответ.

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

Такое вроде есть по ссылке АццкоМото, там они используют подобие quick sort или merge sort, каждый раз деля множество точек пополам и отбрасывая группу где явно нету Kth smallest

[АццкоМото]

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

Не понял

[Sergunka]

Вполне возможно если использовать группы к примеру первая группа расстояние от 0 до 1 вторая группа от 1 до 2 и тд. Когда первая группа переполняется т.е. больше чем К, то группа бьется на двое типо от 0 до 0.5 и от 0.5 до 1.

Да, но как получить эти группы? Нужно либо заранее иметь какие-то предположения о распределении расстояний, либо сортировать, что уже n*log(n), т.е. очень плохо. Ну и отсортировав мы уже получаем ответ.

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

Такое вроде есть по ссылке АццкоМото, там они используют подобие quick sort или merge sort, каждый раз деля множество точек пополам и отбрасывая группу где явно нету Kth smallest

Да я не спорю, я просто мысли в слух говорю.

[Boriskin]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

Даны N точек на плоскости и некая "главная" точка. Найти K ближайших к ней. Точка = пара декартовых координат.

Вот такое вот УГ. Я ж говорил, скучная.

Забавно, Гугель спрашивал из похожей сферы - найти "самую одинокую звезду в Млечном пути", если известны кординаты все звезд. Я с ходу ничего лучче квадратичного алгоритма не придумал, хотя наверняка можно...

[crypto5]

Чо, кому-нибудь нужна задача со второго раунда? Скучная, на мой вкус.

давай

Даны N точек на плоскости и некая "главная" точка. Найти K ближайших к ней. Точка = пара декартовых координат.

Вот такое вот УГ. Я ж говорил, скучная.

Забавно, Гугель спрашивал из той же сферы - найти "самую одинокую звезду в Млечном пути", если известны кординаты все звезд.

Решение сильно зависит от определения метрики одинокости ))