Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Здравствуйте, gandjustas, Вы писали:
G>>Твое желание чтобы соискатели на собеседовании решали такие задачи — каприз, не подкрепленный необходимостью.
ПМ>Пока практика показывает, что это самый действенный метод отсеять людей, которые не умеют программировать.
Это твоя практика, хотя с чего ты взял что они не умеют?
G>>Уверен что они были более сложные? Может они просто более неизвестными тебе были? ПМ>Да, уверен.
Я уже писал что есть склонность преувеличивать сложность незнакомых задач и преуменьшать сложность знакомых.
Здравствуйте, gandjustas, Вы писали:
G>Это твоя практика, хотя с чего ты взял что они не умеют?
Проверил на примере одной простой задачи.
G>>>Уверен что они были более сложные? Может они просто более неизвестными тебе были? ПМ>>Да, уверен. G>Я уже писал что есть склонность преувеличивать сложность незнакомых задач и преуменьшать сложность знакомых.
ПМ>или в одну строчку: ПМ>result = (((x .&. (x — 1)) `xor` x) + x) .|. (x .&. (x — 1))
ПМ>Вот решение для ближайшего большего, собственно. Вполне адекватная задача для собеседования при условии, что человеку будут даваться подсказки и что он умеет обращать списки. Сформулировал задачу, как это сделал ты — пол решения. Разобрался, как работает сложение/вычитание на уровне битов — еще четверть . Собрал решение из готовых блоков — заключительная четверть. Никаким хакером для решения этой задачи быть не надо, лично я — даже не программист, а деплоймент-инженер.
молодец, деплоймент-инженер! понты так и прут
ты тестировал свое решение? нет? а я протестировал твое
import Data.Bits
import Numeric
import Data.Char
binary x = showIntAtBase 2 intToDigit x ""
f x = (((x .&. (x - 1)) `xor` x) + x) .|. (x .&. (x - 1))
g x = putStrLn $ (binary x) ++ " --> " ++ (binary (f x))
$ ghci bits_public_morozov.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( bits_public_morozov.hs, interpreted )
Ok, modules loaded: Main.
*Main> g 3
11 --> 110
*Main>
тогда как минимальное число после 11 это очевидно 101
особый минус тебе за то, что запостив свое решение в 15:06 ты не прочитал мою подсказку, запощенную в 12:09
G>Я уже писал что есть склонность преувеличивать сложность незнакомых задач и преуменьшать сложность знакомых.
плюсую
надо сказать, что задачу про обращение списка я не решал, а узнал решение раньше, читая что-то по хаскелю, так что я не могу объективно оценить ее сложность
впрочем, если человеку объяснить на пальцах (на кубиках ) идею алгоритма обращения, тогда можно уже требовать его безошибочного программирования... опять же вовсе не уверен насчет 5 минут -- там в частных случаях можно запутаться
Здравствуйте, m e, Вы писали:
ME>надо сказать, что задачу про обращение списка я не решал, а узнал решение раньше, читая что-то по хаскелю, так что я не могу объективно оценить ее сложность
В хаскеле мутабельный список — очень неестественная структура. Поэтому хаскелистов у меня другие задачи.
На одном относительно недавнем собеседовании у меня прямо, можно сказать, на входе попросили на бумажке написать алгоритм поиска самой длинной повторяющейся подстроки в строке.
Конечно, я помню о существовании сложного поиска с суффиксными деревьями, и даже помню, что он O(n+r), но за 20 минут (столько времени дано на задачу) все, что я смог написать — ужасно неэффективный "поиск в лоб" с перебором от каждой буквы. И то, не уверен, что алгоритм работает, т.к. ни тестов, ни чего другого за это время не написать.
Хорошо хоть следующие 20 минут прошли в обсуждении разных способов огранизации tiered storage. Но там у интервьювера были столь глубокие и обширные знания, что я не мог вообще ничего нового или интересного ему сказать. Только общие банальности.
Здравствуйте, lxa, Вы писали:
lxa>Что-то странное Вы написали, ближе к истине IMHO будет следующий вариант для большего числа, без обработки ошибок:
тяжело читать твой код, но похоже он правильный -- за исключением х=0, когда он выдает полную лажу (во всяком случае у меня) -- ты делаешь там левый шифт или на ооооооочень много или на -1, что UB
твой код правильный в том смысле, что при х=1111100000000000 он выдает не следующий больший х, а следующий больший х по модулю 2**32, или циклически больший (это наверно ясно? но объяснять лень) -- т.е. невозможность найти больший х в рамках unsigned int легко ловится по тому признаку, что next(x)<=x
ниже я записал свое понимание твоего кода в читаемой с моей точки зрения форме (например оптимизации, вроде "x+=... вместо y=x+..." надо оставлять компилятору, и писать ясно), исправил ошибку с 0 и добавил throw:
#include <iostream>
#include <string.h>
unsigned int number_of_trailing_zero_bits(unsigned int x) //Count the consecutive zero bits (trailing) on the right in parallel
{
unsigned int result = 32;
x &= -signed(x);
if (x) result--;
if (x & 0x0000FFFF) result -= 16;
if (x & 0x00FF00FF) result -= 8;
if (x & 0x0F0F0F0F) result -= 4;
if (x & 0x33333333) result -= 2;
if (x & 0x55555555) result -= 1;
return result;
}
inline unsigned int clear_lowest_unit_bit(unsigned int x) { return x & (x-1); }
inline unsigned int lowest_unit_bit(unsigned int x) { return x ^ clear_lowest_unit_bit(x); }
inline unsigned int create_unit_bits(unsigned int n) { return (1u << n) -1; }
inline unsigned int number_of_pretrailing_unit_bits(unsigned int x)
{
return number_of_trailing_zero_bits(x+lowest_unit_bit(x)) - number_of_trailing_zero_bits(x);
}
unsigned int next(unsigned int x)
{
unsigned int y = x + lowest_unit_bit(x); /// это мы получаем тот самый сдвиг одного бита налево... но коммент должет быть длиннееunsigned int result = y | (create_unit_bits( number_of_pretrailing_unit_bits(x) ) >> 1) ;
if( result <= y) /// FIXME а компилятор не решит ли соптимизировать это нафиг?throw"no next";
else
return result;
}
теперь где я остановился в самостоятельном (без гугля) решении -- в целом у меня был тот же алгоритм, но
1. был тупо цикл, двигающий группу единиц до столкновения с границей
2. я чуть дольше возился вместо элегантного вычисления y
3. и думал по поводу "а как без цикла посчитать количество последовательных единиц и нулей" -- а придумывать че-то типа такого алгоритма как выше мне было лень
ME>>надо сказать, что задачу про обращение списка я не решал, а узнал решение раньше, читая что-то по хаскелю, так что я не могу объективно оценить ее сложность
ПМ>В хаскеле мутабельный список — очень неестественная структура. Поэтому хаскелистов у меня другие задачи.
это несущественно
если знаешь разворот немутабельного списка, то развернуть мутабельный можно легко по аналогии
Здравствуйте, visitor_pattern, Вы писали:
_>Я как то предлагал подобным людям писать в своем резюме — "отказываюсь отвечать на вопросы про прикладное программирование на собеседовании и решать каки-либо задачки". Но как-то не нашлось в их душах согласия с этой позицией.
Ты будешь смеяться, но у меня в резюме практически так и написано. На поток желающих предложить очередную "once in a lifetime opportunity" никак не повлияло, надмозгов с гномиками, сортировками, недо-брайнбенчами и прочей ересью как отрезало.
Здравствуйте, landerhigh, Вы писали:
L>Ты будешь смеяться, но у меня в резюме практически так и написано. На поток желающих предложить очередную "once in a lifetime opportunity" никак не повлияло, надмозгов с гномиками, сортировками, недо-брайнбенчами и прочей ересью как отрезало.
Ну да, ни одна приличная контора таких капризных девочек приглашать не станет, потому что следующей предьявой будет "отказываюсь тестировать свой код", "отказываюсь приходить на работу вовремя" или что он там еще откажется делать.
L>>Ты будешь смеяться, но у меня в резюме практически так и написано. На поток желающих предложить очередную "once in a lifetime opportunity" никак не повлияло, надмозгов с гномиками, сортировками, недо-брайнбенчами и прочей ересью как отрезало.
ПМ>Ну да, ни одна приличная контора таких капризных девочек приглашать не станет, потому что следующей предьявой будет "отказываюсь тестировать свой код", "отказываюсь приходить на работу вовремя" или что он там еще откажется делать.
М>а как вам задача типа этой: есть число 32 бит. получить ближайшее меньшее или большее число с таким же точно числом установленных бит. признаюсь, что у меня на решение ушло полчаса (при записи ответа в одну строку на си). по тупому, конечно, ее любой может решить. или... не любой?
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Здравствуйте, landerhigh, Вы писали:
L>>Ты будешь смеяться, но у меня в резюме практически так и написано. На поток желающих предложить очередную "once in a lifetime opportunity" никак не повлияло, надмозгов с гномиками, сортировками, недо-брайнбенчами и прочей ересью как отрезало.
ПМ>Ну да, ни одна приличная контора таких капризных девочек приглашать не станет, потому что следующей предьявой будет "отказываюсь тестировать свой код", "отказываюсь приходить на работу вовремя" или что он там еще откажется делать.
Public, у нас разные понятия о приличных конторах. Смотри выделенное.
Здравствуйте, m e, Вы писали:
ME>func для нечетных чисел находит вовсе не предыдущее, а следующее число с равным количеством единиц
ME>
ME>f: 11110 -> 11101
ME>func: 00001 -> 00010
ME>
Разве это противоречит условиям "получить ближайшее меньшее или большее число"?
func(1) --> 2
От 1 (0001) ближайшее большее с равным числом бит — это 2 (0010).
ME>для нечетных чисел, похоже, тебе придется поступиться принципами и сделать цикл
ME>
Здравствуйте, gandjustas, Вы писали: G>А нахрена оно нужно? Если 1 еще может встретиться в реальной жизни, то 2 и 3 — просто высосаны из пальца.
Ну не скажи — быстрый и компактный словарь это тебе не хухры-мухры.
теме мы пришили к выводу, что задача обращения списка слишком сложна и нетривиальна, чтобы давать её на собеседованиях. Предлагаю составить список хороших, годных задач, которые можно давать сеньёр-девелоперам без опасений, что стресс усталость или отсутсвие опыта решения подобных задач в течение полугода помешают им их решить.
ПМ>Пожалуй сам и начну.
ПМ>Задача 1. Уровень Mid Developer Java/C#
ПМ>Напишите программу, выводящую на экран Ваше имя.
ПМ>Оценивается умение кандидата работать с system out, знание паттернов, умение писать своё имя без грамматических ошибок.
Вброс засчитан.
Теперь осталось узнать когда тебя забанят
) идею алгоритма обращения, тогда можно уже требовать его безошибочного программирования... опять же вовсе не уверен насчет 5 минут -- там в частных случаях можно запутаться
