Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Здравствуйте, мыщъх, Вы писали:
ПМ>ИМХО нет смысла давать получасовую задачу, особенно если в процессе её решения не о чем разговаривать с кандидатом. Задача неразрешима, если число — 0.
в этом случае функции next_bigger_num(x)/prev_lower_num(x) должны вернуть ошибку, не?
> Ближайшее большее — сдвиг исходного числа на один бит влево, > зануление всех бит, кроме самого старшего, установка n — 1 младших бит
чего-чего?! мы начинаем двигать самый младший бит влево до тех пор, пока на следующей позиции не окажется нуль.
или нет, даже не так. если представить биты в виде строки, для удобства инвертированной слева-направо. и нужно найти первый '1+0', после чего заменить его на '01+' (регулярна в псевдофрме).
осталось только записать решение, используя сложение, вычитание, свдиг, or, and, xor и чего еще душе угодно. и вот как его записать я не так долго думал, как отлаживал. сначала наплодил кучу промежуточных переменных, а когда стал их "сворачивать", где-то лажанулся и долго ходил кругами.
М>>предлагаю дать задачу сравнения двух деревьев. а разворот списка это, извините, в детсад и на горшке сидеть. ПМ>Нам бы хоть так...
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, minorlogic, Вы писали:
M>С++
это не си++
M> "Програмисту дали задание реализовать функцию которая возвращает текущее время с точностью до секунды.
что такое время? текущее -- это показание системных часов компьютера, да? в каком формате выдавать? местное время устроит? а если это приложение для мобильного телефона, который автоматически определяет часовой пояс и время начали определять в одном месте, после чего усыпили систему, сели на самолет, приземлились, врубили питалово... функция вернет очень странный результат вообще-то. а неучитывать такие ситуации -- нельзя.
M>int getCurrentTime(); M>Вопрос , какие вы видите проблемы и как бы вы смогли улучшить этот код?
проблема только одна. код -- не работает. точнее, работает, но делает не то, что написано в ТЗ.
и начинать улучшение кода нужно с уточнения формулировок ТЗ.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, мыщъх, Вы писали:
М>>и начинать улучшение кода нужно с уточнения формулировок ТЗ. M>Это хорошее начало , но для сеньора стоит ожидать и хорошей альтернативы?
сеньер должен сказать, что текущим время бывает только у домохозяек. проводить ликбез и объяснять чем отличается GMT от UTC собеседуемый вроде не должен. так же непонятно для каких _целей_ это нужно. если время используется в качестве уникального значение, которое никогда не повторяется и всегда возрастает, то это -- одно. если для логгирования -- это ____ВАААААЩЩЩЩЕЕЕЕ____ другое. вот у меня есть лог. в нем есть местное время. но нету часового пояса. и я не в курсе политики сохранения времени в стране получения лога, которая в самом логе тоже не отражена.
> Другими словами решение проблемы а не ее усугубления?*
а решения проблемы нет. во всяком случае в такой постановке вопроса. "ты скажи мне что те нужно, я те дам, что ты хошь"
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
>> Другими словами решение проблемы а не ее усугубления?* М>а решения проблемы нет. во всяком случае в такой постановке вопроса. "ты скажи мне что те нужно, я те дам, что ты хошь"
Тогды совсем не сеньер. "Моя хата с краю" это позиция в никуда
Здравствуйте, Паблик Морозов, Вы писали:
М>>чего-чего?! мы начинаем двигать самый младший бит влево до тех пор, пока на следующей позиции не окажется нуль.
ПМ>Понял, туплю.
Чего? Двигать? Цикл? Не, не слышал.
Проверяйте:
int f(int x)
{
int minusOneBit = (x-1)&x;
int e = x^minusOneBit;
return minusOneBit|(e>>1);
}
int func(int x)
{
if (!(x&1))
return f(x);
return ~f(~x);
}
PS: переворачивать списки — не мое, там же циклы нужны
Послушайте, зачем вы вообще ЭТО спрашиваете у кого-то? Вы СЕБЕ ищите людей с которыми ВАМ потом работать и за произведения которых ВАМ отвечать. Перестаньте обращать внимание на высокомерных супер-сениор программистов местных, минута рабочего времени которых стоит 100$ минимум. Они вам не помогут — для них самое лучшее собеседование означает выслушивание их зарплатных ожиданий и сразу выданое согласие платить им все что они хотят и премию каждый месяц в размере оклада.
Я как то предлагал подобным людям писать в своем резюме — "отказываюсь отвечать на вопросы про прикладное программирование на собеседовании и решать каки-либо задачки". Но как-то не нашлось в их душах согласия с этой позицией.
теме мы пришили к выводу, что задача обращения списка слишком сложна и нетривиальна, чтобы давать её на собеседованиях. Предлагаю составить список хороших, годных задач, которые можно давать сеньёр-девелоперам без опасений, что стресс усталость или отсутсвие опыта решения подобных задач в течение полугода помешают им их решить. ПМ>Пожалуй сам и начну. ПМ>Задача 1. Уровень Mid Developer Java/C# ПМ>Напишите программу, выводящую на экран Ваше имя. ПМ>Оценивается умение кандидата работать с system out, знание паттернов, умение писать своё имя без грамматических ошибок.
Здравствуйте, мыщъх, Вы писали:
ПМ>>ИМХО нет смысла давать получасовую задачу, особенно если в процессе её решения не о чем разговаривать с кандидатом. Задача неразрешима, если число — 0. М>в этом случае функции next_bigger_num(x)/prev_lower_num(x) должны вернуть ошибку, не?
А какой результат должна вернуть prev_lower_num(1)?
Здравствуйте, Sap78, Вы писали:
S>Здравствуйте, мыщъх, Вы писали:
ПМ>>>ИМХО нет смысла давать получасовую задачу, особенно если в процессе её решения не о чем разговаривать с кандидатом. Задача неразрешима, если число — 0. М>>в этом случае функции next_bigger_num(x)/prev_lower_num(x) должны вернуть ошибку, не?
S>А какой результат должна вернуть prev_lower_num(1)?
ошибку, очевидно. точно как next_bigger_num(0xFFFFFFFF)
речь не про это. чисто для разминки мозгов мне задачка показалось интересной (задачу придумал не я), но во-первых, это она мне интересна, потому что я вообще люблю с битами перепихиваться, а, во-вторых, даже при всей моей любви к битам не могу представить себе практического применения решения в одну строку. с преобразованием битов в строку и последующими операциями над ней на питоне -- задача вообще решается влет. причем, код ясен и понятен даже ламеру. а вот шаманство на уровне битовых операций -- оно вообще непонятно как работает и насколько корректно обрабатывает "пограничные" ситуации.
считаю, что под такую задачу можно искать или матерых хакеров, которые это делают в уме (ну в частности, на вопрос что сие значит (x & ( x + 1)) я ответил не раздумывая. меня даже плюс не смутил (в реальной жизни там минус), но это не потому, что у меня мозги работают с космической скоростью, а потому что этот шаблон я регулярно вижу на протяжении всей моей жизни.
а вот вопрос: "какое максимальное кол-во белых и черных коней можно разместить на 8x8 доске, чтобы они не угрожали друг другу и кол-во белых и черных было одинаковым" поставил меня в тупик. аналом чувствую -- задача из серии "классиков", но решение мне неизвестно. подозреваю, что 64, но неуверен. но это ж вообще шахматы. нечестно давать их на программировании...
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>считаю, что под такую задачу можно искать или матерых хакеров, которые это делают в уме (ну в частности, на вопрос что сие значит (x & ( x + 1)) я ответил не раздумывая. меня даже плюс не смутил (в реальной жизни там минус), но это не потому, что у меня мозги работают с космической скоростью, а потому что этот шаблон я регулярно вижу на протяжении всей моей жизни.
У меня другое мнение. Вот спросят меня, "что делает (x & ( x + 1))?" Я ни разу не хакер и эту хрень первый раз в жизни вижу, но что я первым делом начну делать (если интернета нет под рукой)? А начну я выписывать цифекрки:
И так до просветления. И что я увижу? Увижу то, что четные цифры оно не трогает, а у нечетных убирает все единички до младшего нуля, что эквивалентно вычитанию чего-то там (ответ зависит от степени моего просветления). Ну или просто убирает все единички до младшего нуля, потому что у четных цифр он в самом начале, т.е. и убирать-то нечего. Это и будет моим ответом на вопрос. И тот, кто этот вопрос мне задаёт, по тому, насколько быстро у меня наступит просветление и насколько оно было глубоким, сможет сделать вывод о моих способностях. А если я по ночам Hacker's Delight читал под одеялом и отвечаю на этот вопрос по памяти, то мне его, наверное, нет особого смысла задавать, проще про коней спросить. Тут-то и можно будет оценить, смогу ли я разработать какую-нибудь систему для решения новой для себя задачи и насколько далеко смогу продвинуться.
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Здравствуйте, мыщъх, Вы писали:
М>>считаю, что под такую задачу можно искать или матерых хакеров, которые это делают в уме (ну в частности, на вопрос что сие значит (x & ( x + 1)) я ответил не раздумывая. меня даже плюс не смутил (в реальной жизни там минус), но это не потому, что у меня мозги работают с космической скоростью, а потому что этот шаблон я регулярно вижу на протяжении всей моей жизни.
ПМ>У меня другое мнение. Вот спросят меня, "что делает (x & ( x + 1))?" Я ни разу не хакер и эту хрень первый раз в жизни вижу, но что я первым делом начну делать (если интернета нет под рукой)? А начну я выписывать цифекрки:
как бы x & (x — 1) проверка на то, что x это степень двойки. если поменять минус на плюс, то получим проверку, что следующее за x число это степень двойки, а сама x это битовая маска из единиц. это в том случае если результат равен нулю. все остальные случаи мы приравниваем к true.
ПМ>И так до просветления. И что я увижу? Увижу то, что четные цифры оно не трогает, а у нечетных убирает все единички до младшего нуля, что эквивалентно вычитанию чего-то там (ответ зависит от степени моего просветления).
короче ваш ответ таков: "оно там что-то делает с битами"
> А если я по ночам Hacker's Delight читал под одеялом и отвечаю на этот вопрос по памяти,
если вы возились с асмом, контроллерами или хотя бы парсили exe/elf файлы -- вы уже знаете ответ. т.к. первый же макрос который пишется на си это ALIGN_UP/DOWN. да и при разборе файловых систем без него никуда.
> то мне его, наверное, нет особого смысла задавать, проще про коней спросить.
видите? а меня кони поставили в тупик. на бумаге рисовать лень. доски дома нет. разве какую компьютерную программу скачать в ней поэксперементировать? догадываюсь, что задачу можно попытаться решить на фрагменте 8x8, а затем распростанить на всю доску
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
теме мы пришили к выводу, что задача обращения списка слишком сложна и нетривиальна, чтобы давать её на собеседованиях. Предлагаю составить список хороших, годных задач, которые можно давать сеньёр-девелоперам без опасений, что стресс усталость или отсутсвие опыта решения подобных задач в течение полугода помешают им их решить.
Да просто поговорите с человеком, чем занимался, какие задачи решал, почему именно так, а не иначе, с какими трудностями столкнулся, что по его мнению было сделано правильно, а что нет.
Напишите сами код с разными граблями типа виртуальных деструкторов и функций, генерируемых по умолчанию (это для С++, думаю в С# своих граблей хватает), попросите рассказать что тут не так.
Распечатайте листинг своего реального кода, спросите мнение (только не обижаться на критику ).
Опишите недавнюю реальную задачу, попросите рассказать, как бы кандидат подошел к ее решению.
Если кандидат вдруг впал в ступор и что-то "тупит", не стесняйтесь помочь, задать наводящие вопросы.
Если человек не гуру собеседований, он наверняка будет волноваться и переживать, что он "тупит".
Задачи вроде обращения списка очень легко решаются на "холодную" голову и могут быть проблемой даже для сообразительных людей без опыта собеседований.
Отбирая людей чисто задачками, рискуете нанять человека далекого от практики и/или работы в коллективе, который просто заучил типовой набор "100 задач от Микрософта".
Здравствуйте, мыщъх, Вы писали:
М>как бы x & (x — 1) проверка на то, что x это степень двойки. если поменять минус на плюс, то получим проверку, что следующее за x число это степень двойки, а сама x это битовая маска из единиц. это в том случае если результат равен нулю. все остальные случаи мы приравниваем к true.
Все же x & (x — 1) — это обнуление младшего единичного бита, как и x & (x + 1) — обнуление группы единичных битов, начинающихся с нулевой позиции. Проверка на степень двойки — уже следствие. Так что Паблик Морозов все верно сказал.
Вообще, основная цель задачек на собеседовании — оценка стиля мышления кандидата: склонен ли он к анализу, умеет ли строить логические умозаключения, последователен ли в решении проблем, его степень ассоциативности. Попутно можно многое узнать о его бекграунде (не все знакомы с простейшими структурами данных, не говоря уже про "большое О") и общем кругозоре. В идеале, для решения должно быть достаточно базовых знаний, а самих решений должно быть несколько (компромиссных), чтобы можно было завязать содержательную беседу. Желательно также, чтобы задача не была слишком известна; например, можно взять что-нибудь из внутреннего проекта и слегка упростить/изменить.
Рассмотрим несколько проблем, упомянутых в соседней ветке.
1. Реверсирование односвязного списка. Задача действительно элементарная, требующая понимания двух вещей — указателей и структуры "односвязный список". Никаких хвостовых рекурсий и прочих выводов знать не требуется, достаточно нарисовать несколько прямоугольников со стрелками (для некоторых нужно две схемы — начальное состояние и промежуточное), после чего решение становится очевидным, а код пишется с картинки. Вполне может выступать для отсеивания полных идиотов, не умеющих рисовать Впрочем, есть нюансы. Если кандидат выдает решение без схем, то, скорее всего, он его вызубрил. Проверяется предложением объяснить ход мыслей. С другой стороны, кандидат, выдающий решение как у gandjustas скорее всего overqualified, и либо "выпендривается", либо любит усложнять без надобности.
2. Выборка N случайных элементов массива. Тут фильтр серьезнее. Решения на shuffle и сортировке по случайным ключам достаточно очевидны, но появляется возможность поговорить о сложности, требованиях к ГСЧ и пр.
Есть решение "в лоб" — выбирать случайный элемент по одному и проверять не выбран ли он уже. Тут вопросов еще больше
Решение, указанное gandjustas выдать весьма не просто, если не знать его принцип, но после небольшой подсказки (использовать теорию вероятностей) оно находится простейшим мозговым брутфорсом. Однако, для доказательства корректности этого решения базовых знаний тервера может не хватить.
Кода больше, чем в предыдущем случае, и это максимум по объему, что можно требовать написать, имхо.
3. Нахождение максимальной общей подпоследовательности. Имхо, такие вещи спрашивать на собеседовании бесполезно. Человек, знающий о существовании динамического программирования алгоритм сформулирует с высокой вероятностью, не знающий — вряд ли переизобретет велосипед. Кода много, он весьма наворочен, так что возникнут проблемы с проверкой его корректности, в результате времени будет потрачено много, а результатов достигнуто мало.
Нужно помнить, что для проведения подобных собеседований сам интервьюер должен обладать всеми вышеперечисленными качествами и быть готовым самому на время стать собеседуемым, иначе можно сесть в лужу. Например, когда кандидат выдаст неординарное решение. И, чем сложнее задача, тем риски выше.
Также есть вакансии на которые мыслящий работник не нужен (быдлокодерство по разжеванным требованиям). В этом случае задавать задачки — терять время.
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Пожалуй сам и начну. ПМ>Задача 1. Уровень Mid Developer Java/C# ПМ>Напишите программу, выводящую на экран Ваше имя.
Ой, госсподи. Неужель так сложно реальную задачу придумать? Ну вот сходу, из реальной практики, на растерзание. Имеем массив экземпляров PlainData:
PlainData {
id;
parentId;
data;
}
Преобразовать это в массив экземпляров TreeData (вроде как это зовется лесом), поддерживающую иерархию:
TreeData {
id;
*TreeData;
data;
}
То есть на первом уровне массива будут элементы, на которых не будет ссылок из parentId, а далее уже иерархия.
Естественно писать не на бумажке, а за компом со средой разработки, гуглом и тому подобным (за такое на бумажке убивать надо!). И не за 5 минут — я б час выделил, сделать хоть как, главное чтоб работало, ну и можно было разобраться как оно работает. Задача минимум — рассказать как будешь делать, совсем хорошо — если успеешь и код написать (ступоры у всех бывают).
Могу еще пятерку различных задач из практики вспомнить при желании, в том числе те, до решения которых все руки не доходят. Именно из того проекта, на который планируется взять человека.
Плюс реальный код, который меня беспокоит в текущем проекте — нужно сказать, что в нем плохо, и как сделать лучше.
теме мы пришили к выводу, что задача обращения списка слишком сложна и нетривиальна, чтобы давать её на собеседованиях. Предлагаю составить список хороших, годных задач, которые можно давать сеньёр-девелоперам без опасений, что стресс усталость или отсутсвие опыта решения подобных задач в течение полугода помешают им их решить.
Ты обижаешься, что я раскрыл решение твоей задачи
Вот тебе взамен схожие по сложности задачки, не требующие подготовки.
1. Дано бинарное упорядоченное дерево.
Вернуть максимальный узел <= заданному.
2. То же, но вернуть не сам узел, а его родителя [злодейская ухмылка]. Что возвращать для крайних случаев (узлов не найдено, найден корневой узел) — на выбор интервьюера.
3. Для самых продвинутых можно предложить написать обход дерева.
И чтобы без рекурсии
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>2. То же, но вернуть не сам узел, а его родителя [злодейская ухмылка]. Что возвращать для крайних случаев (узлов не найдено, найден корневой узел) — на выбор интервьюера.
Добавлю. Эта задачка хороший повод для обсуждения структур данных.
Если узел имеет ссылку на родителя, то решение элементарно. Но если данных ___ОЧЕНЬ___ много, то хранить лишнюю ссылку получается накладно.
_____________________
С уважением,
Stanislav V. Zudin
теме мы пришили к выводу, что задача обращения списка слишком сложна и нетривиальна, чтобы давать её на собеседованиях. Предлагаю составить список хороших, годных задач, которые можно давать сеньёр-девелоперам без опасений, что стресс усталость или отсутсвие опыта решения подобных задач в течение полугода помешают им их решить.
ПМ>Пожалуй сам и начну.
ПМ>Задача 1. Уровень Mid Developer Java/C#
ПМ>Напишите программу, выводящую на экран Ваше имя.
ПМ>Оценивается умение кандидата работать с system out, знание паттернов, умение писать своё имя без грамматических ошибок.
Слушай, скажи как тебя зовут. Я свяжусь с вашим начальством и попрошу чтобы тебя не допускали к собеседованиям, чтобы зря не парил мозг людям.
В брайте же занимаются CRM, SharePoint, SQL, BI. Что там c Java — хз, но точно не консольные приложения. Нахрена задачи, не имеющие отношения к работе, решать?
