Здравствуйте, Тёмчик, Вы писали:

Если ты не можешь на написать на на С++17 в 2017, в этом есть какой то смысл.

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, Олег К., Вы писали:

Мне кажется в 2017 достаточно написать

template<class FwdIt, class Compare = std::less<>>
void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
auto const N = std::distance(first, last);
if (N <= 1)
return;
auto const pivot = std::next(first, N / 2);
std::nth_element(first, pivot, last, cmp);
quickSort(first, pivot, cmp);
quickSort(pivot, last, cmp);
}

Здравствуйте, andy., Вы писали:

A>Здравствуйте, Тёмчик, Вы писали:

A>Если ты не можешь на написать на на С++17 в 2017, в этом есть какой то смысл.

template<class FwdIt, class Compare = std::less<>>
void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
auto const N = std::distance(first, last);
if (N <= 1)
return;
auto const pivot = std::next(first, N / 2);
std::nth_element(first, pivot, last, cmp);
quickSort(first, pivot, cmp);
quickSort(pivot, last, cmp);
}

Здравствуйте, andy., Вы писали:

A>Мне кажется в 2017 достаточно написать
Мне кажется достаточно написать std::sort уже лет 20. Но для собеседования не прокатит.

Здравствуйте, andy., Вы писали:

A> auto const pivot = std::next(first, N / 2);

Если использовать nth_element, то pivot это неправильное название.

A> std::nth_element(first, pivot, last, cmp);

Здесь по смыслу и духу quicksort не std::nth_element нужен (который к тому же внутри обычно реализуется как обрезанный quick/intro-sort), а std::partition.

Здравствуйте, Artem Korneev, Вы писали:

AK>Не.. В этом плане у меня как-то по-другому получается. Последнее время интересные предложения поступают по рекоммендациям коллег, а не от рекрутеров. Поэтому собеседование получается одно. А алгоритмы освежаю из чисто практических соображений. Я не перечитываю книгу целиком, я перечитываю несколько глав из того что соприкасается с моими текущими задачами. Помогает привести мысли в порядок.
AK>То же самое и с книгами по архитектуре приложений.
Хорошо вам в США. Я правда не очень понимаю, зачем "освежать алгоритмы из практических соображений"- ты либо практически используешь алгоритмы в работе, ну тогда освежать ничего не надо. Там скорее интересуешься новыми веяниями, читаешь соответсвующие журналы. Либо ты на работе тупеешь, а на интервью везде алгоритмы спрашивают (ну просто так заведено)- тогда практические соображения как раз освежить эти вопросы с собеседований в памяти.

AK>>>Вчера вот просили написать реализации очереди используя массив и используя стэк.
Тё>>Правда интересно, как (и главное зачем) эффективно зафигачить FIFO через LIFO.

AK>Про "эффективно" тут трудно говорить, а сама по себе задача известная и подробно разобрана в "Cracking the coding interview".
AK>Берём два стэка и при необходимости меняем порядок элементов, перекидывая из одного стэка в другой.
Либо рекурсивный вызов. Если эффективность не требуется- значит ничего нового мне эта книжка бы не дала. Книжка наверное для определённой аудитории.

Тё>>Очередь с приоритетом через стек не просили?

AK>Не, такого не просили.
Потому, что про это не было в "Cracking the coding interview"?

Здравствуйте, Тёмчик, Вы писали:

Тё>не очень понимаю, зачем "освежать алгоритмы из практических соображений"- ты либо практически используешь алгоритмы в работе, ну тогда освежать ничего не надо.

Ну так задачи ж всё время разные. Я с одного раза запомнить все алгоритмы не смогу. Кроме того, отдельная тема — применимость алгоритмов и структур данных. Мне не всегда сходу очевидно, что какую-то часть своей системы я могу соптимизировать, применив ту или иную структуру данных. А тут, бывает, почитаю какую-нибудь историю из жизни у Скиены или Кнута и вдруг осеняет, что у меня схожий случай.

Тё>>>Очередь с приоритетом через стек не просили?
AK>>Не, такого не просили.
Тё>Потому, что про это не было в "Cracking the coding interview"?

При всём желании, в одно интервью нельзя вместить все задания из книги.
А задания, в общем-то, не только по книге попадаются. Например, меня попросили написать реализацию слияния соседствующих/пересекающихся интервалов — задача, сама по себе, вполне простая, единственный нюанс в том, чтобы правильно обрабатывать более двух сливающихся интервалов. Правда, написать попросили на чистом Си, я на нём последний раз писал ровно 5 лет назад — 17 апреля 2012-го был мой последний день работы в РБК, где я писал на C, C++ и Erlang.

Здравствуйте, andy., Вы писали:

A>Мне кажется в 2017 достаточно написать

A>template<class FwdIt, class Compare = std::less<>>
A>void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
A>  auto const N = std::distance(first, last);
A>  if (N <= 1)
A>    return;
A>  auto const pivot = std::next(first, N / 2);
A>  std::nth_element(first, pivot, last, cmp);
A>  quickSort(first, pivot, cmp);
A>  quickSort(pivot, last, cmp);
A>}

Мне чисто для интересу — где здесь перестановки?

Здравствуйте, Ikemefula, Вы писали:

I>Мне чисто для интересу — где здесь перестановки?
Внезапно в std::nth_element, очевидно да?

Здравствуйте, gandjustas, Вы писали:

I>>Мне чисто для интересу — где здесь перестановки?
G>Внезапно в std::nth_element, очевидно да?

Нет.

Здравствуйте, De-Bill, Вы писали:

I>>Написание хеш-таблицы это примерно экзамен за первый курс унивеситета.

DB>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.

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

DB>>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.
I>Непонятная аналогия. Реализация хеш-таблицы требует самых разных умений, скажем, работа и с массивами, и со списками, кое какой теории и разных других вещей, иначе ничего не выйдет.

Приколачивание колёс к бревну тоже требует разных умений. Умение держать молоток, умение приставлять гвоздь пальцами к месту, в которое этот гвоздь нужно вбить, умение попадать молотком по гвоздю а не по пальцам. Ничуть не менее лёгкие умения, чем умение работать с массивами и связанными списками. Только эти умения не имеют ничего общего с автомбилестроением. Также как и реализация массива списков ничего не имеет общего с построением эффективного контейнера или с оптимизацией использования библиотечного.

Здравствуйте, De-Bill, Вы писали:

DB>>>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.
I>>Непонятная аналогия. Реализация хеш-таблицы требует самых разных умений, скажем, работа и с массивами, и со списками, кое какой теории и разных других вещей, иначе ничего не выйдет.

DB>Приколачивание колёс к бревну тоже требует разных умений. Умение держать молоток, умение приставлять гвоздь пальцами к месту, в которое этот гвоздь нужно вбить, умение попадать молотком по гвоздю а не по пальцам. Ничуть не менее лёгкие умения, чем умение работать с массивами и связанными списками. Только эти умения не имеют ничего общего с автомбилестроением. Также как и реализация массива списков ничего не имеет общего с построением эффективного контейнера или с оптимизацией использования библиотечного.

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

Здравствуйте, Олег К., Вы писали:


ОК>>>Это ты сейчас в википедию заглянул?
G>>Нет

ОК>Я не верю тебе

проекции.. по себе судите.

ОК>но допустим ты хранишь столько хлама у себя в голове.

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

Здравствуйте, netch80, Вы писали:

N>Image: okasaki_chisto_funkcionalnye_struktury_dannyh.jpg
Чисто конкретно

Здравствуйте, Cyberax, Вы писали:

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

Здравствуйте, gandjustas, Вы писали:

G>Думаешь интервьювер найдет? И надо оно ему? Это же помнить наизусть весь код надо и только для того, чтобы потешить самолюбие.
Мне попадались некоторые конторы с настолько обострённым equal opportunities, что там все вопросы интервью заранее согласовывались и утверждались кучей бездельников"менеджеров". Так что человеку, который целыми днями задаёт одни и те же вопросы, будет совсем несложно выучить "правильные" ответы с точностью до последней запятой.

Здравствуйте, StandAlone, Вы писали:

SA>Валяй, сыпь свою соль.
SA>Заодно, раз пошла такая пьянка, расскажи (и по)чему равен оптимальный fill factor.
Ты ж с жабником разговариваешь. У них наверняка есть какая-нить абстрактная фабрика абстрактных фабрик, которая родит нужный адаптер для моста, который сам чё-то там посчитает

Здравствуйте, koandrew, Вы писали:

K>Здравствуйте, StandAlone, Вы писали:

SA>>Валяй, сыпь свою соль.
SA>>Заодно, раз пошла такая пьянка, расскажи (и по)чему равен оптимальный fill factor.
K>Ты ж с жабником разговариваешь. У них наверняка есть какая-нить абстрактная фабрика абстрактных фабрик, которая родит нужный адаптер для моста, который сам чё-то там посчитает

По умолчанию fill factor 0.75. Я xz сколько он "оптимальный"- наверное от ограничений зависит. Вообще, когда для кого-то не очевидна связь хэш функции и псевдо-случайного генератора, там сложно найти общий язык.

Здравствуйте, koandrew, Вы писали:

C>>Вот потому архитектов и надо драть по алгоритмам, чтобы понять кто реально опыт имеет, а кто просто занимается написанием бумажек с квадратиками и стрелочками.
K>При этом на работе он будет преимущественно как раз писать бумажки с квадратиками да стрелочками
Ага. Но тут ведь проблема в том, что неправильные квадратики со стрелочками неправильно работают. И без реального опыта сложно будет понять почему.