Привет, Хабр.
Я тут на днях сходил на собеседование в одну серьёзную фирму, и там мне предложили перевернуть односвязный список. К сожалению, эта задача заняла весь первый раунд собеседования, а по окончанию интервьювер сказал, что все остальные сегодня заболели, и поэтому я могу идти домой. Тем не менее, весь процесс решения этой задачи, включая пару вариантов алгоритма и последующее их обсуждение, а также рассуждения о том, что вообще такое переворачивание списка, под катом.
Решаем задачу
Интервьювер был довольно приятным и дружелюбным:
— Ну, давайте для начала решим такую задачу: дан односвязный список, нужно его обратить.
— Сейчас сделаю! А на каком языке лучше это сделать?
— На каком вам удобнее.
Я собеседовался на C++-разработчика, но для описания алгоритмов на списках это не лучший язык. Кроме того, я где-то читал, что на собеседованиях сначала надо предложить неэффективное решение, а потом последовательно его улучшать, так что я открыл ноутбук, запустил vim и интерпретатор и набросал такой код:
revDumb : List a -> List a
revDumb [] = []
revDumb (x :: xs) = revDumb xs ++ [x]Пока интервьювер всматривался в код, я решил сразу проявить инициативу и указал, что это на самом деле плохой алгоритм, потому что он имеет квадратичную сложность из-за неэффективного дописывания элемента в конец, и сразу написал улучшенный вариант, выполняющийся за линейное время:
revOnto : List a -> List a -> List a
revOnto acc [] = acc
revOnto acc (x :: xs) = revOnto (x :: acc) xs
revAcc : List a -> List a
revAcc = revOnto []— Тут мы проходимся по списку один раз, и каждый раз дописываем новый элемент в начало, а не в конец, так что алгоритм линейный.
Сравниваем решения
Я ожидал каких-нибудь вопросов от интервьювера, но он лишь переводил взгляд с экрана на меня и обратно. Ещё немного подождав, я решил снова проявить инициативу (ведь компании же любят инициативных?) и хоть что-то говорить, чтобы заглушить неудобную тишину:
— Ну, вообще говоря, не факт, что эти две функции делают одно и то же, поэтому давайте их проанализируем и докажем, что они действительно эквивалентны, то есть, на любом входе выдают одно и то же значение.
С этими словами я снова взял клавиатуру и начал печатать
revsEq : (xs : List a) -> revAcc xs = revDumb xsИнтервьювер ничего не говорил, так что я продолжил:
— Ну, сгенерируем определение и сделаем case split по единственному аргументу.
Несколько нажатий — generate definition, case split, obvious proof search — и среда разработки превратила ту строку в
revsEq : (xs : List a) -> revAcc xs = revDumb xs
revsEq [] = Refl
revsEq (x :: xs) = ?revsEq_rhs_1Я слышал, что интервьюверы любят, когда при решении задач кандидаты описывают свой мыслительный процесс, поэтому продолжил рассуждать вслух:
— Ну, с базовым случаем для пустого списка все очевидно, тайпчекер даже вон сам вывел, а вот теперь придётся немного подумать. Очевидно, что доказывать свойства рекурсивных функций имеет смысл по индукции, поэтому получим доказательство для меньшего списка и посмотрим, что нам после этого нужно будет сделать:
revsEq : (xs : List a) -> revAcc xs = revDumb xs
revsEq [] = Refl
revsEq (x :: xs) = let rec = revsEq xs in ?wut— Если теперь посмотреть на дырку ?wut, то мы увидим среди прочего
rec : revOnto [] xs = revDumb xs
--------------------------------------
wut : revOnto [x] xs = revDumb xs ++ [x]— Естественно захотеть подставить revDumb xs из пропозиционального равенства, даваемого rec. Заменим последнюю строчку на:
revsEq (x :: xs) = let rec = revsEq xs in
rewrite sym rec in ?wutи получим цель
--------------------------------------
wut : revOnto [x] xs = revOnto [] xs ++ [x]— Вынеcем это в отдельную лемму и сфокусируемся на её доказательстве:
lemma1 : (x0 : a) -> (xs : List a) -> revOnto [x0] xs = revOnto [] xs ++ [x0]Я снова делаю generate definition, case split по xs, obvious proof search для первой ветки и получаю
lemma1 : (x0 : a) -> (xs : List a) -> revOnto [x0] xs = revOnto [] xs ++ [x0]
lemma1 x0 [] = Refl
lemma1 x0 (x :: xs) = ?lemma1_rhs_2— Снова доказываем утверждение по индукции, но теперь всё интереснее. Можно получить доказательство для lemma1 x xs, а можно для lemma1 x0 xs. Из соображений симметрии первое нам, скорее всего, подойдёт больше, так что перепишем последнюю строчку в
lemma1 x0 (x :: xs) = let rec = lemma1 x xs in ?wutи посмотрим на дырку ?wut:
rec : revOnto [x] xs = revOnto [] xs ++ [x]
--------------------------------------
wut : revOnto [x, x0] xs = revOnto [x] xs ++ [x0]— Возникает естественное желание заменить revOnto [x] xs из цели на выражение справа от знака равенства в rec. Попробуем:
lemma1 x0 (x :: xs) = let rec = lemma1 x xs in
rewrite rec in ?wut— Посмотрим, во что превратилась наша цель доказательства:
--------------------------------------
wut : revOnto [x, x0] xs = (revOnto [] xs ++ [x]) ++ [x0]— Ух, какой там ужас. Давайте воспользуемся ассоциативностью конкатенации списков:
lemma1 x0 (x :: xs) = let rec = lemma1 x xs in
rewrite rec in
rewrite sym $ appendAssociative (revOnto [] xs) [x] [x0] in ?wut— Теперь цель выглядит по-божески:
--------------------------------------
wut : revOnto [x, x0] xs = revOnto [] xs ++ [x, x0]— Так это же почти утверждение нашей оригинальной леммы! Разве что, наша лемма работает только для аккумулятора, содержащего один элемент, а тут необходимо работать с двумя элементами. Традиционно для математики упростим себе задачу, усилив доказываемое утверждение, и запишем новую лемму:
lemma2 : (acc, lst : List a) -> revOnto acc lst = revOnto [] lst ++ accПривычным движением заставляю IDE сделать всю грязную работу. При этом case split мы делаем по lst, а не по acc, так как revOnto рекурсивно определён по lst:
lemma2 : (acc, lst : List a) -> revOnto acc lst = revOnto [] lst ++ acc
lemma2 acc [] = Refl
lemma2 acc (x :: xs) = ?wut1В wut1 нам надо доказать
--------------------------------------
wut1 : revOnto (x :: acc) xs = revOnto [x] xs ++ accСнова воспользуемся индукцией для второго случая:
lemma2 acc (x :: xs) = let rec = lemma2 (x :: acc) xs in ?wut1Теперь мы имеем
rec : revOnto (x :: acc) xs = revOnto [] xs ++ x :: acc
--------------------------------------
wut1 : revOnto (x :: acc) xs = revOnto [x] xs ++ accПерепишем цель с использованием rec:
lemma2 acc (x :: xs) = let rec = lemma2 (x :: acc) xs in
rewrite rec in ?wut1и получим новую цель
--------------------------------------
wut1 : revOnto [] xs ++ x :: acc = revOnto [x] xs ++ acc— Правая часть снова что-то напоминает. Действительно, тут мы могли бы воспользоваться нашей lemma1 для единичного элемента, но заметим, что lemma2 тоже подходит, так как lemma1 x xs даёт то же утверждение, что lemma2 [x] xs:
lemma2 acc (x :: xs) = let rec1 = lemma2 (x :: acc) xs in
let rec2 = lemma2 [x] xs in
rewrite rec1 in
rewrite rec2 in ?wut1Теперь наша цель выглядит так:
--------------------------------------
wut1 : revOnto [] xs ++ x :: acc = (revOnto [] xs ++ [x]) ++ accТут снова можно воспользовать ассоциативностью конкатенации, после чего цель будет решить легко:
lemma2 : (acc, lst : List a) -> revOnto acc lst = revOnto [] lst ++ acc
lemma2 acc [] = Refl
lemma2 acc (x :: xs) = let rec1 = lemma2 (x :: acc) xs in
let rec2 = lemma2 [x] xs in
rewrite rec1 in
rewrite rec2 in
rewrite sym $ appendAssociative (revOnto [] xs) [x] acc in Refl— Заметим, что lemma1 нам теперь не нужна, и мы можем её выкинуть, переименовав lemma2 просто в lemma. И теперь мы, наконец, можем на неё сослаться в нашем исходном доказательстве, получив итоговый вариант:
lemma : (acc, lst : List a) -> revOnto acc lst = revOnto [] lst ++ acc
lemma acc [] = Refl
lemma acc (x :: xs) = let rec1 = lemma (x :: acc) xs in
let rec2 = lemma [x] xs in
rewrite rec1 in
rewrite rec2 in
rewrite sym $ appendAssociative (revOnto [] xs) [x] acc in Refl
revsEq : (xs : List a) -> revAcc xs = revDumb xs
revsEq [] = Refl
revsEq (x :: xs) = let rec = revsEq xs in
rewrite sym rec in lemma [x] xsУ меня оставалось ещё минут 15, интервьювер по-прежнему ничего не говорил, поэтому я решил продолжить.
— Ну, если хотите, мы можем ещё что-нибудь обсудить.
— Хорошо, предположим, вы вот написали это всё. Но вы же даже ни разу не запустили этот код! Как вы можете быть уверены, что вы действительно написали функцию обращения списка? Где тесты?!
Проверяем решение
— Прекрасно! Я рад, что вы об этом заговорили! Действительно, а откуда мы вообще знаем, что наше решение верное? Что вообще значит «перевернуть список»? Представляется разумным следующее определение: если xs — некоторый список, то xs' будет его «переворот» тогда и только тогда, когда левая свёртка исходного списка с любой функцией и любым начальным значением даёт тот же результат, что правая свёртка перевёрнутого списка с той же функцией и тем же начальным значением. Давайте это запишем!
revCorrect : (xs : List a) ->
(f : b -> a -> b) ->
(init : b) ->
foldl f init (revDumb xs) = foldr (flip f) init xs— Так как мы уже доказали, что revDumb равно revAcc (технически мы доказали forall xs. revDumb xs = revAcc xs, а равенство функций следует из экстенсиональности, которую мы, увы, не можем интернализировать), то нам неважно, какую из функций обращения списка рассматривать, так что мы для простоты возьмём revDumb.
В очередной раз делаем привычные заклинания, вызываем индуктивную гипотезу и получаем
revCorrect : (xs : List a) ->
(f : b -> a -> b) ->
(init : b) ->
foldl f init (revDumb xs) = foldr (flip f) init xs
revCorrect [] f init = Refl
revCorrect (x :: xs) f init = let rec = revCorrect xs f init in ?wutНаша цель сейчас выглядит так:
rec : foldl f init (revDumb xs) = foldr (flip f) init xs
--------------------------------------
wut : foldl f init (revDumb xs ++ [x]) = f (foldr (flip f) init xs) x— Снова пользуемся равенством из индуктивной гипотезы:
revCorrect (x :: xs) f init = let rec = revCorrect xs f init in
rewrite sym rec in ?wutполучая
--------------------------------------
wut : foldl f init (revDumb xs ++ [x]) = f (foldl f init (revDumb xs)) x— Начиная с этого момента revDumb xs нам не нужен. Нам достаточно сформулировать и доказать довольно очевидное свойство левых свёрток: свёртка всего списка с функцией f эквивалентна функции f, вызванной с результатом свёртки префикса списка и последнего элемента списка. Или в коде:
foldlRhs : (f : b -> a -> b) ->
(init : b) ->
(x : a) ->
(xs : List a) ->
foldl f init (xs ++ [x]) = f (foldl f init xs) x— Доказательство совсем простое, и поэтому мы его сразу напишем и воспользуемся этой леммой для доказательства исходного утверждения. Итого:
foldlRhs : (f : b -> a -> b) ->
(init : b) ->
(x : a) ->
(xs : List a) ->
foldl f init (xs ++ [x]) = f (foldl f init xs) x
foldlRhs f init x [] = Refl
foldlRhs f init x (y :: xs) = foldlRhs f (f init y) x xs
revCorrect : (xs : List a) ->
(f : b -> a -> b) ->
(init : b) ->
foldl f init (revDumb xs) = foldr (flip f) init xs
revCorrect [] f init = Refl
revCorrect (x :: xs) f init = let rec = revCorrect xs f init in
rewrite sym rec in foldlRhs f init x (revDumb xs)— Так а тесты-то где?
— А они не нужны. Мы же формально доказали, что мы обращаем список.
— … Хм, похоже, время вышло. Ну, спасибо за то, что пришли к нам на интервью, всего доброго, мы вам перезвоним.
Правда, почему-то до сих пор не перезвонили.
Комментарии (338)
red75prim
16.08.2019 16:36+2Хорошо, а теперь оцените объем памяти, требуемый для исполнения этой функции.
0xd34df00d Автор
16.08.2019 16:40+1Время интервью вышло, так что отвечу кратко: возьму uniqueness types, а дальше достаточно умный компилятор всё сделает без дополнительных аллокаций.
ss-nopol
16.08.2019 16:49А как это доказать?
0xd34df00d Автор
16.08.2019 16:55Так же формально за полчаса не получится. Чуть менее формально — потому что компилятор знает, что каждый элемент используется не более одного раза, поэтому он спокойно может мутировать указатели вместо создания новых элементов.
Компилятор Idris'а, на самом деле, не настолько умён, в него слишком мало ресурсов вкладывается (я удивлюсь, если reverse с uniqueness types он скомпилирует в инплейс), но вот какой-нибудь ghc, когда может подобные вещи вывести (ибо в хаскеле пока нет афинных типов), вполне себе так оптимизирует код.
Чё-то я тут слишком серьёзный, похоже.
Izaron
16.08.2019 18:42Это наверное такой мем от функциональщиков — я раз несколько на Хабре в статьях о ФП видел утверждение, что "компилятор оптимизирует", или что "оптимальный код — забота компилятора". Кажется, иногда это говорили всерьез.
Fenzales
16.08.2019 22:40Ну насчет хаскелля не скажу, но, например, в лиспе, lparallels действительно даёт возможность просто писать многопоточный код по сравнению с императивными языками. Да и вообще выявлять, и, главное, оптимизировать узкие места проще (впрочем, не исключаю confirmation bias задач, которые я решал на лиспе)
prefrontalCortex
20.08.2019 11:28Что за lparallels, о которых вы говорите? Гугл не выдаёт ничего внятного.
IkaR49
16.08.2019 16:42+1Подчиненный перед лицом начальствующим должен иметь вид лихой и придурковатый, чтобы умом своим не смущать начальства.
perfect_genius
16.08.2019 19:11Почему не оформлено как цитата? Или вы всё ещё живы?
Magn
16.08.2019 20:16+2Потому что это и не цитата. Просто забавная выдумка, автор которой не известен.
IkaR49
16.08.2019 21:28+10Ну, как минимум, потому, что с телефона это оформлять неудобно. Да и:
"Главная проблема цитат в интернете в том, что люди сразу верят в их подлинность". (с) В. И. Ульянов (Ленин)
time2rfc
16.08.2019 16:47+3Статья вызывает улыбку. Но кроме всего прочего поднимет проблему важности soft skill наряду с развитыми hard skill.
0xd34df00d Автор
16.08.2019 16:52+1Мне бы, пожалуй, скорее хотелось бы поднять вопрос скучных задачек на собеседованиях. Но его уже и так сто раз поднимали.
berez
16.08.2019 22:30+2Это для вас они скучные.
А у меня знакомый набирал людей на разработку — так кандидаты не знали, сколько бит в байте и сколько байт в 32-разрядном инте. Что такое указатель — вообще страшная тайна, шаманство какое-то…
Punk_Joker
16.08.2019 22:34+1Тоже на С++?
berez
17.08.2019 10:49Угу. Там работа с оборудованием на довольно низком уровне — посему кандидатам неплохо было бы знать, как типы данных лежат в памяти.
Andrey_Rogovsky
17.08.2019 15:25Когда меня брали на, то давали схемы и потом просили описать пути электронов после подачи питания.
И да — это важно знать, если ты пишешь микрокод контроллера шины.
Milfgard
16.08.2019 22:35+6>не знали, сколько бит в байте
Это вы им показали 9-битные и попросили обосновать?berez
17.08.2019 11:00+1Там действительно мой знакомый, и проект у них вполне практический. И оборудование достаточно стандартное — процессоры x86 почти везде, кое-где вроде как пытались внедрить ARMы. Так что байты там нормальные, восьмибитные.
Но выясняется страшное: приходят собеседоваться специалисты, которые вообще никогда не задумывались о том, как именно данные хранятся в памяти. А им по работе надо пакеты между нодами туда-сюда гонять по чахлым каналам связи…DistortNeo
17.08.2019 15:17Неспроста в университетах обучение идёт с основ: базовая логика, структуры данных, ассемблер, С и только потом уже идут C#, Java, Python. Многим это не нравится, потому что не получается сразу начать писать практический код. Но по факту если человек начинает изучение программирования сразу с языка скриптового уровня, то ему потом становится сложно подтягивать базу, потому что это требует времени.
0xd34df00d Автор
16.08.2019 22:46+3Так я тоже не знаю.
Сколько бит в байте, зависит от архитектуры. Стандарт С определяет байт как размер
char, для связи которого с разрядностью тоже нужно знать об архитектуре и настройках компилятора.a5b
17.08.2019 03:59Стандарт С ISO 9899:1999 http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
определяет что в char можно записать как минимум значения 0..255 или -127..128 (0..UCHAR_MAX, SCHAR_MIN..SCHAR_MAX) 5.2.4.2.1 Sizes of integer types "Their implementation-defined values shall be equal or greater in magnitude (absolute value) to those shown, with the same sign." и что в char должно быть не менее 8 бит (CHAR_BIT 8), т.е. стандартом допускаются машины с более длинным char.
Байт определен независимо от char как адресуемая единица памяти, без уточнения числа бит: 3.6 byte "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment" "A byte is composed of a contiguous sequence of bits, the number of which is implementation defined"
(POSIX определяет байт как октет, т.е. 8 бит)
Книга комментариев к стандарту http://www.coding-guidelines.com/cbook/cbook1_1.pdf на стр 190 приводит примеры
"Motorola DSP56300 which has a 24 bit word… Analog Devices SHARC has a 32-bit word" и уточняет на 191 стр, что в байте не может быть менее 8 бит "The number of bits must be at least 8, the minimum value of the CHAR_BIT macro" (в стандарте это 6.2.6.1 General сноска 40 "A byte contains CHAR_BIT bits")0xd34df00d Автор
17.08.2019 05:14+2Хм, там же последняя фраза в той сноске (в 6.2.6.1/3) говорит
A byte contains CHAR_BIT bits, and the values of type unsigned char range from 0 to 2CHAR_BIT? 1
qw1
18.08.2019 10:16Выходит, что в байте CHAR_BIT бит, а в char — не менее CHAR_BIT бит. Значит, в общем случае неверно, что
Стандарт С определяет байт как размер char
0xd34df00d Автор
18.08.2019 20:135.2.4.2.1/2 намекает на ограничение сверху, так что там, по идее, строгое равенство.
qw1
18.08.2019 20:40+1То есть, такая машина невозможна в C:
1. Память — набор 16-битных ячеек, т.е. прибавляя к указателю 1,
void* next = (void*)((size_t)current+1);
получается указатель на следующий 16-битный байт.
2. Регистры есть как 16-битные (int), так и 8-битные (char)
При этом, загрузка ячейки в char урезает содержимое до младших 8 бит, как и при любых конвертациях в целый тип меньшего размера.
int* ptr;
char value = *ptr; // младшие 8 бит
int value = *ptr; // весь 16-битный байт из одной ячейки памяти.0xd34df00d Автор
18.08.2019 20:45Похоже на то (по крайней мере, 8-битные регистры будут оперировать чем-то отличным от
char): минимально адресуемый кусок памяти — 16 бит, значит,CHAR_BITдолжен содержать 16 бит, значит, вcharдолжно быть 16 бит (или даже «хотя бы 16 бит», если ослабить формулировку и взять вашу).
Я недостаточно хорошо знаю стандарт С, чтобы судить, разрешает ли он типы меньшие, чем
char, в конкретных реализациях. В плюсах-то всё просто: естьboolс очевидно меньшим пространством возможных значений.qw1
18.08.2019 20:56Ну хорошо, а если в машине есть 24-битные регистры (char) и 32-битные (int), а память остаётся 16-битной. В этом случае я не вижу противоречий со стандартом.
0xd34df00d Автор
18.08.2019 20:58Тогда чему равен
CHAR_BITS?qw1
18.08.2019 21:01CHAR_BITS=16
0xd34df00d Автор
18.08.2019 21:05the values of type unsigned char range from 0 to 2CHAR_BIT ? 1.
Мне сходу не удалось найти причины
charиunsigned charсовпадать по размеру, но ЕМНИП это так. Так что, получается,charы могут быть только 16-битными.
da-nie
17.08.2019 10:22+1Правильно.
А ещё посмотрите, как в Си++ и в Си (в stdbool.h) определяется тип bool и как они бинарно совместимы между собой на уровне библиотек (т.е. если взять библиотеку от С и подключить к проекту с Си++). :)
tyomitch
17.08.2019 10:53Ох, знали бы вы, сколько багов происходят от того, что два куска программы компилируются с разным определением bool!
wataru
17.08.2019 13:22так кандидаты не знали, сколько бит в байте
Хм… недавно была новость, что кто-то там судился с гуглом, что их на собеседовании завалили, потому что они старые были. Один из аргументов был, что интервьювер посмел допустить, что в байте 8 бит. А ведь "senior" разработчики предположительно с очень старым железом работали. А там от 6 до 40 бит могло быть.
Так что, если ваши кандидаты было достаточно в возрасте, то вы зря на них серчаете.
berez
17.08.2019 20:27Так что, если ваши кандидаты было достаточно в возрасте, то вы зря на них серчаете.
Мопед не мой, и контора не моя — так что набирал не я. :)
Насколько я знаю, приходили в основном довольно молодые люди — лет 27-35.
И если бы кандидат просто сказал, что по-разному бывает и вот работал он на системе, где в байте 6 бит — никто бы не осерчал, я вас уверяю. Наоборот, это ж прекрасный повод обсудить разные архитектуры. Но у кандидатов просто был ступор — что, мол, за вопросы такие дурацкие, кому в здравом уме может понадобиться знание о размерах типов данных?
saboteur_kiev
18.08.2019 03:55IMHO это троллинг. Популярная архитектура — 8бит.
Где используется нестандартная — менее 1% от всего?
IMHO это не причина вообще зацикливаться на этом.0xd34df00d Автор
18.08.2019 04:15Да, поэтому достаточно сказать «стандарт утверждает то-то и то-то, поэтому в общем случае это зависит от целевой архитектуры и настроек компилятора, но в интересующих нас случаях это почти наверняка будет 8 бит».
Если интервьювер ожидал два слова «8 бит!», и такой ответ будет для него минусом, то лучше это выяснить сразу.
ledocool
17.08.2019 13:27А вы знаете сколько бит в байте? Я вот оже думал, что знаю. Сказал что 8 — обсмеяли с пруфами.
Теперь прежде чем отвечать про биты и байты, я спрашиваю о том, какая архитектура подразумевается.saboteur_kiev
18.08.2019 03:57Пруфы были предоставлены в железном виде, или в музей водили?
Надо было обсмеять их в ответ и спросить, когда последний раз программировали для невосьмибитной архитектуры для продакшена.ledocool
18.08.2019 09:56Меня в википедию сводили, так что чувствую себя как девушка, которую на свидание в макдональдс пригласили. (Им это вроде бы не нравится) А так общение было целиком и полностью теоретическим и за кружечкой водки, поэтому почему нет?
До этого момента я шибко не задумывался о размерностях байтов. Думал восьмерку выбрали как наиболее удобную и о существовании невосьмерок не подозревал.da-nie
18.08.2019 10:37А с порядком байт в многобайтных переменных вас познакомили? :) Не все архитектуры little-endian. Очень прикольно переносить какой-нибудь С/С++ с одной платформы на другую, если используются низкоуровневые фишки (например, чтобы протокол обмена реализовать).
ledocool
18.08.2019 12:50Не, про такое не рассказывали, но я сам где-то и что-то читал. Да и какой в задницу C++ если я тихонько быдлокодерствую на php? Там вообще можно с улицы прийти и сбацать.
da-nie
18.08.2019 12:54А есть ещё дополнительный и прямой код для знаковых чисел. Вояки что-то прямой код любят, как я смотрю. То ли они допкода не знают, то ли это какой-то пережиток 50-х.
Кстати, ip-адреса на big-endian построены в сокетных библиотеках. И функция переворачивания в подарок тоже предусмотрена. :)0xd34df00d Автор
18.08.2019 20:14Ничего, из C++20 поддержку отличных от two's complement представлений выпилили.
ledocool
18.08.2019 20:15+1Это хорошо, что она предусмотрена, а то по ощущениям очень скоро никто не сможет написать сокетную библиотеку. XD
monah_tuk
20.08.2019 05:38Ещё иногда strict aliasing rule по рукам бьёт. Взять для примера труктуры для описания типа сокета:
При этом разработчики компиляторов понимают, что что-то не так в консерватории и, как минимум, GCC разрешает type punning:
Хотя, с т.з. стандарта это тоже UB.
saboteur_kiev
19.08.2019 00:23Вот как раз это очень даже полезная и актуальная информация, поскольку встречается сплошь и рядом. И не только на Си возникают проблемы.
monah_tuk
20.08.2019 04:40Есть ещё и middle endian. А тот же ARM вообще можно переключать между Big и Little.
da-nie
18.08.2019 10:35Не поверите — сейчас тоже есть всякие DSP с 32 битным char (особенно, отечественные современные копии привета из 80-х). И, что характерно, оно используется. Мы, например, такое используем прямо сейчас.
klirichek
17.08.2019 13:48Ну, размер байта — это сама по себе хорошая тема сразу оценить, сидит ли перед вами чисто практик, или у человека есть ещё и более глубокие знания.
(8-битные числа — это октеты так-то)
DmitryKoterov
17.08.2019 15:16Вот кстати да. Мимоходом всегда интересуюсь, сколько различных целых значений может хранить один байт. И знаете, процентах в 30 люди не знают. Кто-то говорит, что 2^256 или 2^128. Из знающих же многие пишут 2^8 (это хороший знак, в принципе).
Как-то жаловался одному товарищу, что, может, я зря это спрашиваю. Он такой: «Да ты чо, это ж самые самые азы computer science, которые проходят на первых лекциях, их просто обязаны понимать все» — это меня немного успокоило.
Izaron
17.08.2019 17:25Слышал историю, как в Гугле знакомый знакомого проводил заключительное интервью с чуваком, у которого было уже 4 собеса с идеальным фидбеком.
Он дал ему следующее задание для разогрева — есть массив из n даблов, это курс обмена USD <-> EUR по каждому из n дней. В начале есть 1 USD. Нужно ровно один раз поменять его в EUR, а потом в один из последующих дней назад в USD. Сколько может быть максимум в конце?
Он не смог решить это за ЧАС, и чуть не попал на работу, если бы не этот знакомый знакомого.
qw1
18.08.2019 10:27Есть ли решение со сложностью лучше, чем O(n^2)? Может, кандидат его искал больше часа, подумав, что очевидное решение «в лоб» не подходит?
qw1
18.08.2019 10:37В целом я придумал решение за O(n•logn).
Spoiler headerНужно использовать двоичную кучу. Перебирая первый искомый индекс (цикл по n), выбирая в оставшейся части массива макс. элемент из кучи, и просеивая кучу, удаляя текущий элемент (log n).wataru
18.08.2019 10:41Есть же за линию решение! Идем по массиву и поддерживаем минимум. Каждый раз смотрим, является ли лучшим решение поменять в известном минимуме и назад по текущему курсу.
Это как ваше решение с кучей, но, если цикл пустить с конца, то максимум можно просто пересчитывать за константу.
qw1
18.08.2019 11:10Первоначальный поиск одного минимального элемента — O(n), но как поддерживать минимум за константу, выкидывая пройденный элемент?
Например, в массиве 1,8,12,4,1 минимум = 1.
Когда мы выкинули первый (или последний) элемент, как за O(1) пересчитать минимум?wataru
18.08.2019 12:07Мы пересчитываем минимум в префиксе массива:
Для массива {3, 4, 2, 5, 1} — минимумы будут {3, 3, 2, 2, 1}. Пересчитывается тупо cur_min = min(a[i], cur_min).
А потом для каждого элемента сначала берем предыдущий минимум, а потом текущий элемент.
Вы уже заметили, что для каждого первого дня надо в качестве второго дня брать максимум в суффиксе массива. Аналогично можно для каждого второго дня (обмена назад) брать минимум из всех дней до него. Этот минимум для всех префиксов можно вот так за O(1) пересчитать, потому что тут каждый раз ровно один элемент добавляется в множество, по которому берется минимум.
DistortNeo
18.08.2019 13:01+1Конечно. O(N), причём за 1 проход. Это пример очень простой задачи на динамическое программирования. Итерируем по дням и для каждого дня храним 2 числа: MaxUSD и MaxEUR:
MaxEUR[k] — максимальное количество EUR, которое у нас может быть на руках на k-й день.
MaxUSR[k] — максимальное количество USD, которое у нас может быть на руках на k-й день, при условии ровно одного обмена 1 USD -> EUR -> USD.
c[k] — курс обмена
0-й день — база индукции: MaxUSD[0] = 0, MaxEUR[0] = 0.
k-й день: MaxUSD[k] = max(MaxUSD[k — 1], MaxEUR[k — 1] / c[k])
MaxEUR[k] = max(MaxEUR[k — 1], c[k])wataru
18.08.2019 13:45Вы даже более сложную задачу решили. В условии надо менять ровно один раз туда и ровно один раз обратно. Ваше же решение может менять сколько угодно раз.
И у вас опечатка в последней строчке кода — забыли c[k] на MaxUSD[k-1] умножить.
qw1
18.08.2019 13:56MaxEUR[k] = max(MaxEUR[k — 1], c[k])
Как раз это учитывает ваше предыдущее замечание: если в k-тый день меняем доллары на евро, то все предыдущие обмены игнорируются, начинаем с суммы $1 (я ещё подумал, почему граничное условие MaxUSD[0] = 0, так оно и гарантирует, что был хотя бы один обмен и сработало MaxEUR[k] = c[k]).
DistortNeo
18.08.2019 14:04И у вас опечатка в последней строчке кода — забыли c[k] на MaxUSD[k-1] умножить.
Нет, не забыл. c[k] надо умножать на MaxUSD[k-1], если мы можем сколько угодно раз менять валюту. Но по условию мы можем менять только один раз, а изначально у нас был только 1 USD.
unclechu
20.08.2019 13:01так кандидаты не знали, сколько бит в байте
Ну так это смотря в каком байте. Не любой байт октет.
zuko3d
17.08.2019 03:43+1Скучные задачи, увы, обязательны. И для интервьюера они скучны намного больше, т.к. кандидат видит эту задачу впервые (ну или второй-третий раз), а интервьюер эту задачу видит десятый или сотый раз. Но если такую задачу не дать, а дать сразу интересную (как для Senior'a) и кандидат с ней не справится — то не ясно, то ли задача была слишком сложной (кандидат — джун или миддл), то ли кандидат слабый (даже не джун). А т.к. большинство кандидатов по уровню не выше мидла, то и до интересных задач обычно не доходит дело.
Это из своего личного опыта говорю (как в роли кандидата, так и в роли интервьюера).
JPEG
17.08.2019 11:09Тут у интервьюэра софт скилз на нуле. Или :) он умно дождался конца, чтобы формально отфутболить знающего идрис чувака.
hamaile
16.08.2019 16:58Пока читал пост, было ощушение, что вернулся на пятнадцать лет назад и сижу на лекции в университете, где понимаю только знаки препинания.
Вероятно вашему собеседнику вы сломали всю логику собеседования и он пропустил всю часть собеседования и перешёл к шагу «попить кофе после дурацкого собеседования, как же они меня все достали»
Всёж большинство собеседований (по собственному опыту) состоят из обязательной части, где задают очевидные вопросы и ожидают ответы в стиле ЕГЭ и дополнительной, где уже можно обсудить интересные особенности.
CrazyOpossum
16.08.2019 17:00А можно ссылку на .vimrc?
А вообще зачётно, в духе постов Aphyr.0xd34df00d Автор
16.08.2019 17:16Вечером выложу куда-нибудь, а то уже не у основной машины.
Конкретно для идриса там ничего особо интересного кроме https://github.com/idris-hackers/idris-vim и https://github.com/dense-analysis/ale .
JC_IIB
16.08.2019 17:27Статья однозначно мегазачет, а за ссылку на Aphyr вам отдельное спасибо. Я полнейший балбес, раз умудрился такое пропустить.
amarao
16.08.2019 17:44А каким образом ваши формальные доказательства покрывают отсутствие багов в Irdis? Т.е. я много раз видел ситуацию, когда программист был 100% уверен в результате (оно не может быть другим) — а оно было, причём по самым дурацким причинам. Например, потому что в динамическом линкере именно данная последовательность бинарных байт вызывала ошибочку и перезаписывала INC на NOOP (бага, бага, закрыта в новой версии, но в продакшене старая непатченная версия). Т.е. логика нам говорит "баги нет", а ядро нам говорит "segmentation fault" для нашего бинаря.
Тесты — они такие...
0xd34df00d Автор
16.08.2019 17:50Более того, формальные доказательства не покрывают правильное понимание решаемой задачи. Если заказчик от меня веб-сайт хотел, а я ему формально верифицированную криптовалюту сделал, то толку-то.
А с юнит-тестов ровно по вашей логике толку примерно столько же. Все скомпилированное приложение целиком надо тестировать.
amarao
16.08.2019 18:43+1На самом деле, скомпилированные юнит-тесты уже проверят этот код. Упор на слово "скомпилированные", потому что получится, что unit-test'ы — это такие неявные интеграционные тесты между компилятором, исходным текстом и ОС, где это всё запускается.
… Потому что может быть даже печальнее, например,
idris 1.irdis File "1.irdis", line 1 revDumb : List a -> List a ^ SyntaxError: invalid syntax
(да, alias irdis=python).
0xd34df00d Автор
16.08.2019 19:00Но ведь, опять же, по вашей же логике их вовсе недостаточно. Вдруг в компиляторе/линкере/етц есть баги такие, что юнит-тесты отрабатывают, а всё вместе в составе конечного приложения — нет?
youROCK
16.08.2019 19:07Только юнит тестов никогда не достаточно для полноценной проверки того, что всё работает в сборе. Совсем без юнит тестов тоже может быть тяжело, потому что полноценные интеграционные тесты обычно идут долго, и соответственно не дают фидбека сразу. Получается, что лучше иметь и то и другое (в идеале :))
0xd34df00d Автор
16.08.2019 19:14Ну, если всерьез говорить, то я пишу тесты, чтобы убедиться, что я правильно понял целевую задачу (этакие интеграционные тесты-спеки), и в идеале доказательства на все остальное.
youROCK
16.08.2019 20:18+2Надеюсь, вы всё-таки не используете Idris в продакшене :). Ну или у компании, в которой вы работаете, будут большие проблемы с поиском замены для Вас, когда вы уволитесь.
0xd34df00d Автор
16.08.2019 20:30+1Если серьёзно, то компилятор идриса к продакшену ещё не готов, и я при всей моей любви буду против использования его для чего бы то ни было достаточно серьёзного (поэтому сейчас читаю CPDT, ага).
JC_IIB
16.08.2019 20:44Ну так они и в FAQ честно пишут, мол, «Idris is primarily a research tool for exploring the possibilities of software development with dependent types, meaning that the primary goal is not (yet) to make a system which could be used in production.» (С)
0xd34df00d Автор
16.08.2019 21:04+2Главное — чтобы Эдвин Брэди после переписывания идриса (изначально написанного на хаскеле) на идрисе не начал переписывать идрис снова. А то так никогда до продакшена и не дойдет.
PashaNedved
16.08.2019 19:23Тестирование программы может весьма эффективно продемонстрировать наличие ошибок, но безнадежно неадекватно для демонстрации их отсутствия.
Edsger Wybe Dijkstra0xd34df00d Автор
16.08.2019 19:30Именно!
PashaNedved
16.08.2019 19:40+1Это ведь не отменяет необходимости (не совсем правильно подобранное слово) писать тесты, а ваше утверждение
А они не нужны. Мы же формально доказали, что мы обращаем список.
выглядит весьма категорично.0xd34df00d Автор
16.08.2019 19:45А что добавят тесты в этом случае?
Ну, кроме проверок, что ядро тайпчекера работает корректно, но по этой же логике вам надо писать тесты на фреймворк тестов.
PashaNedved
16.08.2019 20:08+1А что добавят тесты в этом случае?
+100 к уверенности.
Я не понимаю ваш код, напишите тесты для меня/интервьюера/etc0xd34df00d Автор
16.08.2019 20:12Ну уверенность дело субъективное, у меня от тестов при наличии доказательства не сильно больше не становится.
А непонимание кода… Ну для него не тесты нужны.
PashaNedved
16.08.2019 20:38+2В штате компании будут работать программисты разной квалификации, да и вполне вероятно, что вы когда-нибудь уволитесь, а код-то останется.
Как ни крути, с тестами лучше, чем без тестов.
А непонимание кода… Ну для него не тесты нужны.
Но тесты могут поспособствовать понимаю.
CrazyOpossum
16.08.2019 20:11но по этой же логике вам надо писать тесты на фреймворк тестов.
Вообще-то надо. Тесты — код первого порядка и должен подчиняться всем требованиям релизного кода: стили, ревью, ограничения на выбор зависимостей (и расширений в случае Хаскеля) и наличие тестов.
Другое дело, что писать тесты на внешний код — ну такое.0xd34df00d Автор
16.08.2019 20:13Ну вот так же и код ядра тайпчекера — внешний код.
Тут языкам с тактиками вообще хорошо, которые критерию de Bruijn'а удовлетворяют.
Civil
16.08.2019 21:36+2Тесты в данном случае повысит вероятность, что когда кто нибудь поменяет код по какой нибудь причине, изменения в поведении заметят.
0xd34df00d Автор
16.08.2019 21:43Так доказательство корректности придется менять точно так же, как тесты.
Civil
16.08.2019 21:51+1А можно автоматически проверить что доказательство по прежнему относится к этому коду?
0xd34df00d Автор
16.08.2019 21:57+2Ну, если вы поменяете реализацию существенным образом, но не поменяете доказательство, то доказательство перестанет тайпчекаться, и весь модуль не соберётся.
Civil
16.08.2019 22:28+1А если недостаточным для тайпчека, но достаточным для лёгкого изменения логики?
0xd34df00d Автор
16.08.2019 22:48Значит, вы доказали не все существенные аспекты вашего алгоритма.
Я бы даже сказал, что в этом всем формальном программировании есть обратная проблема: при не влияющих на семантику изменениях иногда (или даже часто) приходится менять доказательство. По крайней мере, в языках с явным построением proof term'а (вроде идриса).
wataru
17.08.2019 13:33Тесты не только для вас. Если в коде нет опечаток, то код работает именно так, как вы его написали. Довольно много программистов абсолютно уверенны в своем коде. Они же прочитали его 100500 раз и, может быть, в уме или на бумажке уже доказали его. Но иногда такой код все-таки делает не то, что нужно.
Ваше доказательство тут — это тоже код. Вы уверенны что нигде не допустили ошибки? Напишите-ка доказательство для доказательства?
Наличие тупо тестов, которые как пробка простые и без логики, все-таки необходимо. Во-первых, для Вас, чтобы убедится что в доказательстве нет ошибок. Во-вторых, для тех, кто ваш код читать будет, чтобы было очевидно что он делает хотя бы в некоторых случаях.
0xd34df00d Автор
17.08.2019 15:30Ваше доказательство тут — это тоже код. Вы уверенны что нигде не допустили ошибки? Напишите-ка доказательство для доказательства?
А вы просите написать тесты для тестов?
wataru
17.08.2019 15:39Обычно тесты сильно проще той магии, что вы тут используете. Буквально input = ...; output = Call(input); Assert(output = ...).
0xd34df00d Автор
17.08.2019 15:42Так доказываемое утверждение тоже достаточно простое. Буквально
revDumb xs = revAcc xs— проще любых тестов. Или, если отталкиваться от определения обращения,foldl f init (revDumb xs) = foldr (flip f) init xs. Тоже легко прочитать и понять, что утверждается.wataru
17.08.2019 15:49А вот само доказательство — с двумя леммами и кучей кода — ну нифига не простое.
0xd34df00d Автор
17.08.2019 15:51А его вам проверять не надо, его машина проверит.
wataru
17.08.2019 16:02Я не очень понимаю, как эта проверка работает. Можно ли там в доказательстве написать какой-нибудь бред вида True = False, только завуалированный, и из него вывести правильность любого утверждения?
0xd34df00d Автор
17.08.2019 16:06Нет, иначе толку с этих формальных доказательств-то.
Ну, в реальности, конечно, всегда остаётся возможность багов в реализации, но логика, лежащая в основе всех этих языков, консистентна и подобной ерунды не допустит.
netch80
17.08.2019 21:50Просим, и пишем.
У меня уже дважды по-крупному случалось, что тестовая среда начинала гнать false positives.
Да, может, в чём-то сами виноваты — переусложнили обстановку. Но не уверен, что более простая схема взлетела бы.
Поэтому приёмы убедиться, что тесты сами что-то проверяют — обязательны.
И это не TDD?шное «сначала должно упасть» — нет, проверяться на это должно и давно существующее, хотя бы в характерных избранных точках и ситуациях.
Но тут существенно, конечно, что тест должен читаться в разы проще тестируемого кода. Иначе — нет смысла. В исходном постинге это явно не соблюдается…
sshikov
17.08.2019 13:36Как вы только что процитировали, тесты позволяют реально только продемонстрировать наличие ошибок. Но не их отсутствие. Что бы вы хотели ими продемонстрировать? Что код работает правильно? Так они этого не показывают (в общем случае). Что правильно работает один случайно выбранный пример?
Если мы формально доказали, то стоит обсудить доказательство, допущения, сделанные в процессе доказательства, и т.п.
А если вы не понимаете доказательство, то скорее всего вы не понимаете, что формально означает обратить список (и это в общем типично для многих нетривиальных задач) — то откуда у вас после тестов уверенность-то возьмется +100%, что задача решена верно? Для этого уж как минимум придется прикрутить что-то типа property based testing, а там снова будут доказательства, и все по-новой…
Ну то есть, что для вас субъективно это важно — верю, но это именно суббъективное чувство. У меня вот тоже от наличия тестов его не прибавляется — а только от наличия того самого «понимания кода». Тесты к нему имеют некоторое отношение, но не прямое.PashaNedved
17.08.2019 16:14Как вы только что процитировали, тесты позволяют реально только продемонстрировать наличие ошибок. Но не их отсутствие. Что бы вы хотели ими продемонстрировать?
То, что код протестирован. Чем выше процент покрытия тестами, тем проще отладка. А отсутствие тестов, что демонстрирует?
откуда у вас после тестов уверенность-то возьмется +100%, что задача решена верно?
не +100%, а +100 к параметру уверенность. И не задача решена верно, а программа компилируется и запускается.0xd34df00d Автор
17.08.2019 16:17Чем выше процент покрытия тестами, тем проще отладка.
Смысл всей этой формальной ерунды в том, что вы формализовали спеку, доказали соответствие этой спеке, и потом вам ничего в рантайме проверять или отлаживать не надо, потому что вы уже всё доказали.
sshikov
17.08.2019 16:29+1>То, что код протестирован
Ну мыж только что обсудили, что это не дает гарантий? Никаких. Или вы Дейкстру процитировали, но с ним не согласны?
>А отсутствие тестов, что демонстрирует?
На мой взгляд — что кто-то дурью маялся. Не вообще, а конкретно вот тут.
Ну то есть, я хочу сказать что — бывают языки, где вы не можете доказать формально почти ничего. Бывают сложные системы, где стоимость такого доказательства запредельно велика. В таком случае я соглашусь, что лучше иметь тесты, и какое-никакое покрытие ими.
Но при возможности и наличии формального доказательства? Зачем?PashaNedved
17.08.2019 17:23Или вы Дейкстру процитировали, но с ним не согласны?
Тестирование программы может весьма эффективно продемонстрировать наличие ошибок, но безнадежно неадекватно для демонстрации их отсутствия.
Тесты могут показать наличие ошибок, а могут и не показать, но они никогда не покажут наличие отсутствия ошибок. Акцент на второй части предложения после запятой.
Тесты практически ничего не гарантируют, кроме покрытия.
Ну то есть, я хочу сказать что — бывают языки, где вы не можете доказать формально почти ничего. Бывают сложные системы, где стоимость такого доказательства запредельно велика. В таком случае я соглашусь, что лучше иметь тесты, и какое-никакое покрытие ими.
Вот именно, дело в покрытии, а какой именно процент покрытия должен быть и на что вообще писать тесты, а на что нет — зависит от бизнеса.sshikov
17.08.2019 17:38>Акцент на второй части предложения после запятой.
Ну я ровно так это и понимаю. Вы можете писать мало тестов, или много — но гарантии отсутствия ошибок все равно нет. При этом тесты стоят денег, и требуют времени (что где-то одно и тоже).
А тут у нас реальный, достаточно редкий на сегодня случай, когда есть формальное доказательство правильности некоторого небольшого куска кода. Ну и зачем нам вот прямо тут тесты? У нас правда нет более нужных вещей, на которые можно деньги потратить?
Скажем, запустить, и убедиться что все заработало — ну я еще могу это понять. В конце концов — померять время выполнения и потребляемые ресурсы (которые формальным доказательством не были охвачены). Ну то есть — нефункциональные тесты.PashaNedved
17.08.2019 18:04А тут у нас реальный, достаточно редкий на сегодня случай, когда есть формальное доказательство правильности некоторого небольшого куска кода. Ну и зачем нам вот прямо тут тесты? У нас правда нет более нужных вещей, на которые можно деньги потратить?
Насколько я понял — случай выдуманный.
Может действительно нет причин писать тест в этом случае, а может есть косвенные причины, но мы этого не знаем.
С одной стороны имеем формальное доказательство, что задача выполнена. С другой стороны, есть достаточно явное указание на то, что решение задачи не может быть верифицировано, ввиду отсутствия тестов.sshikov
17.08.2019 18:20>Насколько я понял — случай выдуманный.
Насколько я понял, верификация обращения списка — не выдуманная ни разу.
> мы этого не знаем
Ну мы может и не знаем Idris, но это вообще-то не повод говорить, что он не работает.
У нас есть доказательство работоспособности. Правильно ли оно само — я сказать не могу, но идея доказательства по крайней мере вопросов не вызывает (что левая свертка на оригинальном списке работает так же, как правая на инвертированном). Оно использует вполне фундаментальные свойства списков, и чтобы написать любой осмысленный тест (кроме самых тривиальных), вам все равно придется такие же свойства сформулировать, и проверить, что они выполняются.PashaNedved
17.08.2019 18:41Ну мы может и не знаем Idris, но это вообще-то не повод говорить, что он не работает.
Мы не знаем по каким причинам интервьюер указывал на отсутствие тестов. Насколько я понимаю, прямых причин нет, но могут быть косвенные — установленные требования бизнеса, например.sshikov
17.08.2019 19:31+1Вы не уловили. foldl для оригинального списка с любой функцией и любым начальным значением == foldr для инвертированного. Доказательство — это и есть тест. Берете любую пригодную функцию, и любое значение, и проверяете, что результаты идентичны. Тесты из доказательства выводятся на раз-два, по крайней мере в этом частном случае. Наоборот — далеко не так просто.
PashaNedved
17.08.2019 20:13Я понимаю то, что бессмысленно писать тесты, если есть формальное доказательство в целях проверки кода.
Но есть и другие требования бизнеса и коммуникация с другими разработчиками, я это уже писал.
В штате компании будут работать программисты разной квалификации, да и вполне вероятно, что вы когда-нибудь уволитесь, а код-то останется.
Как ни крути, с тестами лучше, чем без тестов.
Толку-то если приняв оффер, на работе вы будете писать доказательства такого уровня, что их мало кто будет понимать. А тесты дублируют код, их почти всегда просто понять.sshikov
17.08.2019 21:00>А тесты дублируют код, их почти всегда просто понять.
Ну вот напишите (на любом удобном языке ;) тест к данному примеру? На самом деле это нифига не просто, и понять такие тесты будет не всегда просто.
>вы будете писать доказательства такого уровня
Боюсь что не будете, к сожалению. На сегодня это слишком сложно для промышленного применения.
tyomitch
17.08.2019 10:34+1unit-test'ы — это такие неявные интеграционные тесты между компилятором, исходным текстом и ОС, где это всё запускается.
Ещё стоит добавить процессор, память и всё сопутствующее, потому что в них тоже бывают баги, необнаружимые статическим анализом кода.
saboteur_kiev
16.08.2019 18:53Ну, интервьювер по глупому сказал, чтобы вы использовали любой удобный для вас язык.
А теперь представим, что он irdis не знает, следовательно в вашем коде он разобраться не может. Если предположить. что это метаязык, суто может быть и уловит, но главное было все-таки хотя бы просто запустить на нескольких примерах, чтобы увидеть что ваша программа действительно работает.
А вы этого не сделали, тестов рабочих не предоставили, просто углубились в математические формальности.
Предположим, они берут вас на работу, и просят реализовать простую вещь. В результате получают множество раз переписанный, оптимизированный и вылизанных пулл реквест, который ни разу не запускался на локальном дев енвайрнменте, и в CI он идет без единого теста, то есть первый запуск будет где-то аж на UAT, а то и вообще в PROD?0xd34df00d Автор
16.08.2019 19:02А вы этого не сделали, тестов рабочих не предоставили, просто углубились в математические формальности.
А вы правда тесты ставите выше доказательств корректности алгоритмов? Речь же не об особенностях операционной семантики языка, скажем.
В результате получают множество раз переписанный, оптимизированный и вылизанных пулл реквест, который ни разу не запускался на локальном дев енвайрнменте, и в CI он идет без единого теста, то есть первый запуск будет где-то аж на UAT, а то и вообще в PROD?
Так вакансия ж на C++ была, поэтому, увы, так не получится, придётся тесты писать :(
saboteur_kiev
17.08.2019 00:41А вы снова суть не уловили.
Интервьювер правильно сказал — что вы программу даже не запустили, я уж не говорю про тесты. Тесты даже необязательно писать, просто запустить программу и показать что она обратила список, который вы туда передали аргументов, или даже захардкодили.
Если я не знаю вашего irdis, то формальному доказательству я может и поверю, но как я могу проверить что он правильно реализован с точки зрения кода?
Ведь нельзя сказать, что любой математик, который может формально доказать теорему пифагора, способен запрограммировать ее решение?0xd34df00d Автор
17.08.2019 01:40+1Тесты даже необязательно писать, просто запустить программу и показать что она обратила список, который вы туда передали аргументов, или даже захардкодили.
Зачем? Какую дополнительную информацию это даёт, при условии, что вы знаете Idris?
Если я не знаю вашего irdis
А если не знаете, то какая разница, запустил я программу или нет? Может, я там в обработке нажатий от клавиатуры системную функцию
reverseвызвал, а не свои эти вот, и она все ваши проверки отработает. Или захардкодил входной список и захардкодил выходной.
то формальному доказательству я может и поверю, но как я могу проверить что он правильно реализован с точки зрения кода?
А вам не надо это проверять. Реализацию проверяет сам язык (в этом вся прелесть proofs-as-terms и тайпчекинга).
Утверждение, которое доказывается, во-первых, ИМХО, достаточно читабельно. Во-вторых, даже если я сильно ошибаюсь, то чем тесты лучше? Может, опять же, я там захардкодил ответ на пару входных списков, и где-то в коде у меня что-то вроде
if input == "1 2 3" then print "3 2 1" if input == "1" then print "1"
Ведь нельзя сказать, что любой математик, который может формально доказать теорему пифагора, способен запрограммировать ее решение?
Нельзя, конечно. Но если математик доказал, что запрограммированное решение правда решает теорему Пифагора (что бы это ни значило), то этому верить, наверное, можно, по меньшей мере, с той же уверенностью, что и тестам?
Kemet
17.08.2019 09:49+1С таким подходом я нисколько не удивляюсь, что не позвонили. Они просто сразу поняли весь спектр возможных проблем, начиная с межличностных.
0xd34df00d Автор
17.08.2019 15:33А если вас попросят написать тесты для фреймворка тестов на интервью, вы это тоже с радостью сделаете или будете отказываться?
Я не очень люблю делать бессмысленные действия, и, действительно, лучше это выяснить сразу. Не назвал бы это межличностной проблемой, впрочем.
DnV
19.08.2019 04:36А завтра вам в голову придёт, что весь продукт компании, над которым вам предстоит работать — бессмысленный. Не стоит вам с таким подходом вообще наниматься на работу.
0xd34df00d Автор
19.08.2019 15:01Вы абсолютно правы, и вопрос о том, связан проект с какой-то ерундой, или же им заниматься интересно, он важный.
Впрочем, если уж мы заговорили об этом… Вы никогда не задаётесь вопросами целесообразности того, что вам предлагают делать?
Kemet
19.08.2019 11:53+1Всё не просто, а очень просто. Что-то доказывать нужно человеку, а не компилятору. Потому что именно он принимает решение и берёт на себя ответственность. И если что, фейсом по клаве будут возюкать его. Ну а потом он будут делать тоже самое с тобой. И есть вероятность, что все остальные тоже присоединятся к этому увлекательному действу. Даже те, кто плюсовал карму и ржал в комментах. Ну я вот тоже ржал — смешно же. По не позвонил бы.
Потому что вся статья это просто попытка поднять чсв за чужой счет. А нарциссизм он того — до добра не доводит. Потому что всегда нужно помнить одну простую вещь — даже теория относительности относительна.
А тут какие-то формальные доказательства, безоглядная надёжа на компилятор, и вера в постановщика задачи, ну и задранное чсв.
В общем, я бы не взял такого сотрудника, ибо страшно далёк он от реальности.0xd34df00d Автор
19.08.2019 15:02безоглядная надёжа на компилятор, и вера в постановщика задачи
Вера в тесты, получается, лучше?
Kemet
19.08.2019 17:09+2Нееет, дело не в вере, а в ответственности. А ответственность на вере это такая зыбкая штука. А у тебя получается вера. Вера в формальное доказательство правильности решения, в правильность задачи, в яп, в компилятор/интерпретатор, библиотеки и тд. Вера, как известно, не приемлет логики. Критерий истины — практика. Поэтому тебя и спрашивают " где тесты, Карл?". Где результат?
«не верю (с)»0xd34df00d Автор
19.08.2019 17:15Где результат?
Вон терм нужного типа, он тайпчекается. Вот и результат. Вполне себе на практике.
" где тесты, Карл?"
А в чём их смысл при таких вводных-то? Ведь то, что тесты проходят, опирается на веру в компилятор/интерпретатор, библиотеки, фреймворк тестов и прочее подобное.
Gryphon88
19.08.2019 17:30+1Насколько я понял Kemet и некоторых прочих комментаторов, они пытаются указать на разницу между текстом программы и собственно программой. Программа является рабочей, если она хоть раз выполнила своё предназначения, иначе она просто объект современного искусства. Так что в описанной ситуации программу стоило бы хоть раз запустить.
0xd34df00d Автор
19.08.2019 17:48А чем запуск тайпчекера на тексте программы принципиально отличается? Вы же не маркером на доске доказательство пишете, а в виде кода в компьютере, и проверку этого доказательства в том или ином виде регулярно запускаете.
Gryphon88
19.08.2019 17:51+1Сермяжностью, прикладным характером. Запустил программу — получил развёрнутый лист, программа работает. Всё предельно понятно.
saboteur_kiev
19.08.2019 21:14Вы же не маркером на доске доказательство пишете, а в виде кода в компьютере, и проверку этого доказательства в том или ином виде регулярно запускаете.
Ну вот написанный код, который ни разу не был выполнен, практически ничем от написанного на доске маркером не отличается.0xd34df00d Автор
19.08.2019 21:23По коду, написанному маркером на доске, тайпчекер не пробегается, и машина его корректность не проверяет.
RussDragon
19.08.2019 13:00+1Вы, видимо, не до конца понимаете задачу тестов. Они нужны не для того, чтобы доказать корректность алгоритма, а чтобы, как минимум, обезопасить код и проект от неочевидных ошибок при изменении реализации.
Вы вот взяли и написали такой крутой алгоритм разворота списка. Доказали его формально. Залили на прод. А завтра пришел программист Вася, у которого с математикой всё не так хорошо, и добавил/изменил пару строчек. И сразу вылил, тестов же нет. А на следующий день боевой сервер упал и фирма потеряла 100500 тысяч долларов.
Любая мало-мальски крупная разработка, в первую очередь, про безопасность и тройные проверки, которые, с вашей точки зрения, бессмысленные.JC_IIB
19.08.2019 13:13чтобы, как минимум, обезопасить код и проект от неочевидных ошибок при изменении реализации.
«Тестирование программного обеспечения не может доказать, что система, алгоритм или программа не содержит никаких ошибок и дефектов и удовлетворяет определённому свойству. Это может сделать формальная верификация.» (С)
И сразу вылил, тестов же нет. А на следующий день боевой сервер упал и фирма потеряла 100500 тысяч долларов.
Ну если в фирме считается нормальным «сразу выливать» без пул-реквестов и код-ревью, то поделом.saboteur_kiev
19.08.2019 14:27Ну а если код ревью может сделать единственный математик в компании, а потом он уволится, что делать?
0xd34df00d Автор
19.08.2019 15:04+1Вы, видимо, не до конца понимаете суть формальных доказательств.
Доказательства — они там, рядом, в том же файле, что и основная реализация, и проверяются при каждой сборке. У вас физически не получится изменить реализацию так, что доказательство станет ложным, и при этом что-то куда-то вылить: модуль просто не соберётся.
Спасибо за ваш комментарий, я стал чуть лучше понимать суть претензий.
bayarsaikhan
16.08.2019 17:57Подумали, что overqualified.
red_andr
16.08.2019 19:52+4Даже не просто overqualified, а что то уровня профессора computer science, который почему то пришёл на позицию junior programmer, с которой он сбежит на следующий же день.
0xd34df00d Автор
16.08.2019 21:22+1что то уровня профессора computer science
Ну точно надо мне прекращать метания, бросать тырпрайз и идти в академию.
Izaron
16.08.2019 18:46+1Кажется, я видел похожий пост, только там, как в анекдоте, не "развернуть список", а "решить FizzBuzz", и не "функциональное программирование", а "машинное обучение", и не "тесты не нужны — мы формально доказали", а "надо было взять более глубокую нейронную сеть": https://habr.com/ru/post/301536/
0xd34df00d Автор
16.08.2019 19:01О, прекрасно, спасибо! Я как раз, наконец, начал писать пост про формальную верификацию fizzbuzz.
mapron
17.08.2019 07:36В копилку, тоже замечательный пост про дурацкий вопрос:
habr.com/ru/post/301924
vedenin1980
16.08.2019 19:41а «решить FizzBuzz»
Мне больше нравится вот это решение FizzBuzz'a FizzBuzzEnterpriseEdition. там, конечно, не машинное обучение, но тоже доставляет.lorc
16.08.2019 21:11+2Я сейчас обратил внимание, что на гитхабе используется коричневый цвет для обозначения java-кода. Совпадение?
vedenin1980
16.08.2019 21:19+2Разруха не в
клозетахязыках, а в головах! (с) Собачье сердце
Говнокодить и оверэнженерить можно на любом языке, так же практически на любом современном высокоуровневым мало-мальски популярном языке можно писать хороший и эффективный код.
Тот же FizzBuzzEnterpriseEdition можно переписать абсолютно на любом языке.
arthuriantech
16.08.2019 19:02Когда увлекаешься собственным остроумием, нужно вовремя остановиться)
algotrader2013
16.08.2019 19:44+2Вот-вот, где-то на этот счет была хорошая фраза. Что-то вроде «некоторые плохие программисты пишут код для того, чтобы каждым его символом напомнить о своем остроумии»
Whuthering
16.08.2019 20:09+2Выражение лица интервьювера на протяжении всего собеседования:
уберите детей от мониторовmakarychev13
16.08.2019 20:30+3Если это реальная история, то вы повели себя очень некорректно
0xd34df00d Автор
16.08.2019 20:32+7К счастью, меня давно не просят разворачивать списки на собеседованиях. К сожалению, на собеседования не дают брать свой ноутбук со всякими идрисами и агдами. А вообще, если честно, не уверен, что делать в ответ на просьбу развернуть список на интервью.
И надо, видимо, мне потюнить свои писательские навыки, раз это можно всерьёз воспринять. Ну или не надо.
Fenzales
16.08.2019 22:44+2Действительно можно подумать, что это произошло на самом деле, но тюнить не надо — щепотка юмора придала пикантности.
tyomitch
17.08.2019 10:44+1На телефонных скринингах часто просят развернуть строку или список, чтобы отличить настоящих кандидатов с опытом от проходимцев, сочинивших себе резюме от начала до конца.
JC_IIB
16.08.2019 20:45+5А в чем некорректность, кстати? Интервьюер сказал — можете писать на том языке, на котором вам удобнее. Автору было удобно на Idris, в чем проблема?
funca
16.08.2019 23:54+2Как говорил Ленин: формально все верно, а по сути — издевательство.
По сути, то есть чисто с практической точки зрения, выбор технологий должен быть обоснован. Наш же лирический герой не задал ни одного вопроса на тему функциональных и нефункциональных требований для разработки и эксплуатации приложения: кто, для чего и в каких условиях им будет пользоваться. Системные требования. Требования по развертыванию и поддержке. Получив ответы можно было бы сделать логичный вывод, что выбранная технология это пустая трата времени и начать диалог по существу вакансии.0xd34df00d Автор
17.08.2019 00:02+1Я не спорю, что по сути издевательство, в этом-то и есть весь лирический конфликт
и трагедия лишнего человека, но вот
не задал ни одного вопроса на тему функциональных и нефункциональных требований для разработки и эксплуатации приложения: кто, для чего и в каких условиях им будет пользоваться. Системные требования. Требования по развертыванию и поддержке.
Это точно ожидается, когда вас просят перевернуть список или, я не знаю, проверить сбалансированность скобочного выражения?
funca
17.08.2019 00:24Думаю да, если речь о коммерческой разработке. Откуда берутся входные данные, упираемся ли мы в ограничения по оперативной памяти и адресации, а если упираемся, тогда что? Какие сбои и ошибки нужно отрабатывать? Как будет осуществляться приемочное тестирование? Кто будет поддерживать код, какие у них есть скиллы, какая документация нужна? — разве все это не повлияет на конечное решение, его объем и трудоемкость? Как вы оцените сроки разработки?
У инженерных задач, в отличие от абстрактно математических, есть как минимум пара отличий. Во-первых, это всегда задачи с ограничениями. Во-вторых, отсутствие каких-либо требований в исходной постановке говорит о необходимости их уточнить.
Решение такогонебыловтребованияхуменяналокалхостевсеработает это далеко не продукт. А сам такой подход к работе говорит об уровне специалиста.0xd34df00d Автор
17.08.2019 01:43Кажется, я где-то видел аналогичную иронию на тему написания функции копирования файла, с уточнением требований уровня поддержки имён файлов, содержащих одновременные RTL и LTR письменности, плагинов для протоколов и подключаемых стратегий обработки ошибок. Но не суть.
Когда мне предлагают обсудить реализацию, например, распределённого кеша, отказоустойчивой шины сообщений и тому подобных вещей, то да, первые минут 10 я обсуждаю требования, и потом мы с интервьювером разыгрываем партию из уточнения/изменения требований и моей реакции на это. Но там до кода дело не доходит, и язык программирования там не очень важен. Но это немножко другое, наверное.
Femistoklov
17.08.2019 08:54funca
17.08.2019 13:31Отличная статья. Тоже читал. На мой взгляд история показывает, что невозможно найти контакт, если собеседники придерживаются граничных условий. На то они и граничные. Точки соприкосновения, общие интересы всегда где то по середине. Это и надо искать. Универсальное решение может быть неподходящим, из-за необходимости учесть множество факторов, подчас противоречивых. Грамотный инженер должен уметь получить нужные для решения задачи сведения, задав минимум вопросов по существу, а не вообще все, что может только придумать.
lagranzh
16.08.2019 22:33+7Статья — сплошное самолюбование. Интервьюер тупой, видит код разворота списка и впадает в прострацию. Но автор — молодец, не растерялся и добил его танцем.
Что такое идрис (из коментов слово узнал), как он позволяет формально доказывать верность программ и что за навороченая систем типов у него, и т.д. так и осталось не понятным.
Вобщем, я понял только что автор владеет идрисом как чак норис пистолетом и, наверное, восхитился.0xd34df00d Автор
16.08.2019 22:54Не, я так себе им владею, до сих пор elaborator reflection даже не осилил.
А что за система типов — это долгая история. В пятничную статью, боюсь, не уложусь.
Sazonov
16.08.2019 22:51+1Двоякое впечатление на самом деле. Я сейчас работаю в большой аутсорсинговой компании и у нас есть определенный регламент интервью, который приходится соблюдать. И он даже на позицию solution architect подразумевает вопросы типа «что такое виртуальный метод?».
Но я вас прекрасно понимаю :). Поэтому заранее предупреждаю от том, что начну с детских вопросов, потому что их основная цель — снять первое напряжение на собеседовании.
Alex_ME
16.08.2019 23:21+3У меня коллега любит спрашивать очевидные детские вопросы, и про виртуальный метод, и даже про указатели. Конечно, не на такие высокие должности, но когда я своими глазами увидел, как люди, утверждающие, что пишут на С или С++ плавают на таких вопросах...
saboteur_kiev
17.08.2019 00:45У меня человек, утвердающий что хорошо знает баш, не знал что такое шебанг и код возврата.
Очевидные детские вопросы не только показывают знания человека, но также показывает как именно он на них отвечает, поэтому не обязательно искать сложные вопросы. Как раз простые вопросы могут показать как человек оперирует терминологией и понимает ли он базу.
Sazonov
17.08.2019 04:19У меня как-то был собес на с++ позицию. Человек по резюме выглядел как твёрдый миддл, с претензией на сеньора. Но собеседование закончилось, когда он не смог объяснить чем ссылка отличается от указателя. Ответ «я всегда использую указатели» меня по понятным причинам не устроил.
orizonti
17.08.2019 15:33По большому счету они ничем не отличаются, по каким причинам вас не устроил ответ непонятно, если человек качественно и эффективно решает задачи только с применением указателей то в чем проблема, в данном случае вы проявили формализм, граничащий с идиотизмом.
qw1
18.08.2019 11:06Как минимум, есть синтаксические различия, и их можно было назвать.
если человек качественно и эффективно решает задачи только с применением указателей то в чем проблема
В том, что этот человек не сможет читать/понимать/поддерживать чужой код со ссылками.yudinetz
18.08.2019 16:47-Чем отличается А от Б?
-Не знаю…
-Вы что, не видите, есть же синтаксические различия, А — это А, а Б — это Б. Пишутся по-разному! Как можно не видеть такую простую вещь? No hire.qw1
18.08.2019 17:53+1Но ссылки настолько core feature, что мидлу не знать её просто нельзя.
— Чем отличаются десятичные и шестнадцатеричные целочисленные константы?
— Ну, не знаю, я пользовался только десятичными…
0xd34df00d Автор
18.08.2019 20:15Лично я бы с позиции интервьювера более чем удовлетворился бы ответом «ссылки — это указатели, которые нельзя ребиндить и которые нельзя создать неинициализированными».
Alex_ME
16.08.2019 23:20Прочитал первый абзац, написал разворот списка на С++ со старыми добрыми указателями, а потом прочитал остальную статью и немного выпал.
0xd34df00d Автор
16.08.2019 23:23+3О, а на плюсах можно развлечься с разворотом списка типов на вариадик темплейтах в компил-тайме.
pdima
18.08.2019 13:40а оценить асимптотику сложности решения?
Cerberuser
19.08.2019 16:44То есть, время компиляции в зависимости от длины списка? В рантайме-то оно, если я правильно понял идею, будет линейным (поскольку сведётся к цепочке копирований).
0xd34df00d Автор
19.08.2019 16:57В рантайме оно будет вообще константным, ибо темплейты — чистый компил-тайм.
funca
16.08.2019 23:41+2Двоякое чувство. Взглянем со стороны нанимателя. С одной стороны любознательность, кругозор и нестандартный взгляд на вещи это прикольно. С другой — цель технического интервью понять: интересна ли кандидату работа и будет-ли он справляться. Если нужен с++ разработчик, то не брать это вполне логичный вывод. Ведь за отведенное время соискатель не продемонстрировал ни интереса к языку, ни практических навыков. Это совсем не значит, что лирический герой не крут, просто на данную должность нужны другие супермены.
0xd34df00d Автор
17.08.2019 02:01Предлагаю порефлексировать и с позиции нанимающегося. Вот, например, если мне самому встать на место лирического героя, то я вспомню, что у меня в резюме примерно на второй строчке (сразу после имени) есть ссылка на гитхаб, а на гитхабе у меня довольно много кода на C++, и часть этого кода на момент написания не собиралась релизными версиями доступных компиляторов (хотя последние несколько месяцев я почти не коммичу ничего плюсового, но это неважно, там до того порядком). И если после этого работодателю необходимо, чтобы я продемонстрировал интерес к языку и практические навыки, то я могу представить следующие варианты:
- Работодателю, ну, просто не очень интересно. Но тогда зачем он сейчас проверяет мои навыки, если они ему неинтересны?
- Работодателю интересно, но у него процесс. Но это неинтересно уже мне, потому что опыт подсказывает, что у него процесс будет и чтобы жалюзи отрегулировать (нет, я не смеюсь, работал в фирме, где для этого надо заводить тикет во внутреннюю систему учёта чего-то там), и чтобы мне на этом гитхабе ещё один проектик создать.
- Работодатель мне тупо не доверяет, что это мой гитхаб, а не чей-то левый или что кто-то другой мне там не коммитит.
То есть, возможно, работодатель очень крут, просто ему нужны другие супермены.
vedenin1980
17.08.2019 02:28Предлагаю порефлексировать и с позиции нанимающегося.
Давайте определим цели технического интервью. Они не только в определении умения программировать. Цели:
1. Определить общую адекватность и будет ли кандидат следовать установленным правилам компании,
2. Психологическую совместимость с будущим начальникам и коллегами,
3. Умение адекватно работать с требованиями и вести диалог с «заказчиком» (даже если это тот же коллега), в том числе с закачиками, которые просят нарисовать "семь перпендикулярных линий".
4. Собственно навыки программирования,
Если ответ на любые из первых трех пунктов резко негативный, то собственно навыки программирования уже вряд ли будут иметь значение. Если на вопрос вроде развернуть список, человек встанет и уйдет, вполне очевидно ответ на первые 3 пункта будет получен за минимальное время.0xd34df00d Автор
17.08.2019 02:32Предложение начать интервью с пения гимна компании справится с этим куда быстрее и эффективнее (и я знаю места, где практикуют что-то немного похожее).
vedenin1980
17.08.2019 02:44Это зависит от того какой психологический профиль сотрудника нужен компании (черезмерное подчинение это тоже не всегда хорошо для бизнеса), если нужен именно тот, который без возражений будет петь — попросят спеть.
Тут надо понимать, что у работодателя вполне четкие критерии, кто им нужен, поэтому сразу отсееять тех, кто по каким-то причинам не подходит — разумно.
Ну, вот возьмут они героя этой статьи, а он так же будет троллить коллег и заказчиков при реальных заданиях. Вот если бы вы были владельцем бизнеса, вы бы считали что разумно иметь такого сотрудника?
P.S. Я не говорю, что нужно у всех просить развернуть список. Я о том, что нужно понимать, что и зачем у тебя спрашивают, очень часто техническое интервью это не только и не столько проверка именно технических навыков.0xd34df00d Автор
17.08.2019 02:51Про владельца бизнеса не скажу, но если бы я набирал себе команду, то списки вертеть просил бы только у джунов (и то не факт, это больно избитая задача). А там, авось, и троллить в ответ не будут.
А вопросы ведь в две стороны работают. Даже в две с половиной: они показывают не только то, кого ищет мой будущий тимлид, условно, но и с кем мне в среднем предстоит работать.
vedenin1980
17.08.2019 03:20Вопросы ничего не показывают. Это может быть тест на адекватность, может быть у них очень много тех кто пытается выдать себя за эксперта, может это просто вопрос для «разогрева», может в компании строгая форма интервью и т.п.
Я бы задумался, если все вопросы на интервью оказались бы такими или там начали спрашивать, что-то вообще странное вроде точной даты выпуска 1 версии Java и т.п.funca
17.08.2019 12:39+1Поддерживаю, инженер в современном проекте должен уметь не только писать код. Софт скиллы не менее важны. Потребность в соло-разработчиках, с навыками коммуникации как у «склонного к насилию психопата, который знает, где вы живёте» (sic), даже у поддержки случается крайне редко. Троллинг как квинтэссенция формализма хорош в меру и определенных местах. На Хабре поржать, да людей в пятницу развлечь — это супер (ещё раз спасибо автору за материал). Однако выбор троллинга в качестве основного инструмента для переговоров, таких как собеседование, ну так себе решение.
Обычно начинаю интервью с внешне простых вопросов. Если кандидат в принципе адекватен, то быстро предлагает варианты. По ходу вместе с кандидатом немного меняем требования, докидываем деталей. Смотрим граничные случаи, области применимости текущего решения, возможности для расширения. Формат создаёт определенный стресс, но таковы реали итеративной разработки. Это становится отправной точкой для дальнейшей дискуссии относительно других требований, предъявляемым к сотрудникам в компании, инженерной культуре, прцессах (стек технологий, таск трекинг, quality gates, change management, документирование, ревью, тестирование, ci/cd, активности, и вот это все). Интересно наличие как общей эрудиции, так и практического опыта использования или внедрения (в зависимости от уровня и позиции).
JC_IIB
17.08.2019 10:41+2Давайте определим цели технического интервью
Определить общую адекватность
Психологическую совместимость
Умение адекватно работать с требованиями
А это точно техническое интервью?vedenin1980
17.08.2019 10:50-1точно техническое интервью
Разумеется. Кто вам сказал, что на техническом интервью проверяют только технические навыки? Вопросы, конечно, обычно технические, но по ответам и поведению практически всегда смотрят и на soft skills.
Если вы тимлид и берете человека в свою команду, то вам очень важно понимать не только умеет ли он программировать, но и впишется ли он в команду и сможете ли вы с ним работать. Это чуть ли не самые важные навыки при работе в команде.
saboteur_kiev
18.08.2019 04:05>Давайте определим цели технического интервью
>Определить общую адекватность
>Психологическую совместимость
>Умение адекватно работать с требованиями
А это точно техническое интервью?
Ну первое и третье — вполне даже технические вещи. Рекрутеры, в большинстве случаев, неспособны определить адекватность человека и умение работать с техническими требованиями.
На собеседованиях я нередко вижу, что человек не понимает суть вопроса. Его спрашиваешь одно, а человек, как двоечники в институте, начинают отвечать на совершенно другое, словно надеясь что пронесет.
Иногда даже пытаешься выяснить — человек не знает, и пытается таким образом съехать с темы, или человек реально неспособен понять что его спрашивают, но бывает что он действительно не понимает, еще и идет в агрессию.
При этом рекрутер такой момент проверить не может в силу отсутствия технических знаний.
AlexanderY
17.08.2019 06:52Я недавно был на стороне интервьювера, только по удаленке. Несколько человек тоже присылали ссылку на Гитхаб, пара человек даже в категоричной форме «если не устраивает, адьос».
Я ваш Гитхаб не видел, конечно, но вот у тех, кто присылал — просто код без комментариев, без README — непонятно, какую задачу решали. Я же хочу решение задачи увидеть — как человек мыслит, как знает свой инструмент, что у него с архитектурой.
А по такому коду могу разве что Code Style посмотреть. И что толку от этого?0xd34df00d Автор
17.08.2019 15:36+1Я же хочу решение задачи увидеть — как человек мыслит, как знает свой инструмент, что у него с архитектурой.
Но вы ведь для этого не будете просить переворачивать списки или считать скобки?
saboteur_kiev
18.08.2019 04:07Но вы говорите, что ваш код на гитхабе даже не компилится современными компиляторами…?
Получается что его ни запустить, ни отдебажить нельзя, только почитать readme?0xd34df00d Автор
18.08.2019 04:17Теперь уже можно (увы, ибо раньше в этом был свой шарм, когда релизный компилятор это не осиливает). Просто было время, когда C++17 (а чуть раньше — 14) уже вышел, а полноценных компиляторов к нему не завезли.
Ничего, скоро выйдет C++20, можно будет снова поупарываться.
Ну и да, для оценки шаблонной магии код запускать тоже не обязательно.
AlexanderY
19.08.2019 08:00+1Верно, я не прошу решать «задачки», но если честно, наше тестовое тоже не особо интересное. Приходится идти на эту «жертву», потому что я понимаю — никто не будет тратить пару дней на выполнение «интересного» задания. То, что даем мы — просто точка, от которой можно оттолкнуться.
funca
17.08.2019 13:12Попробую ответить только за гитхаб) так как остальные моменты с отсутствием общих интересов очевидны — можно закончить интервью или финализировать за печенюшками на кухне и экскурсией по офису.
Не часто приходят кандидаты имеющие одновременно популярные и технически проработанные проекты на гитхабе, чтобы глядя на решение хотелось сказать вау! За последние пару лет не видел ни одного. Чаще это утилитарные вещи, собранные для решения определенных задач в определенных жизненных условичх. На вопрос демонстрирует ли проект все лучшие навыки кандидата, максимум на что он способен, всегда получаю отрицательный ответ.
В этом плане интереснее контирбьютинг в другие проекты. Он показывает не только способность разобраться в чужом коде, предложить адекватное решение, но так же общее неравнодушие и базовые навыки коммуникации с другими людьми. Смотрю не только код, но так же внимательно читаю переписку в issue, оцениваю реакцию в комментариях к PR.0xd34df00d Автор
17.08.2019 15:40Ну, опять же, все лучшие навыки и задача из исходного поста не демонстрирует.
А вот с контрибьютингом — поддерживаю, это важно. Конкретно мой гитхаб в этом плане выглядит весьма уныло, масштаба тыщи коммитов в этом году и пара-тройка ничего не значащих PR'ов да полтора issue.
wataru
17.08.2019 14:02+1И если после этого работодателю необходимо, чтобы я продемонстрировал интерес к языку и практические навыки
Т.е. наниматель — редиска, потому что посмел пригласить самого Вас на позицию жалкого C++ разработчика? В некотором смысле, условная девочка из HR, которая прислала вам приглашение, немножечко не права.
Но, корректное поведение с Вашей стороны было бы проигнорировать эту вакансию. Или, возможно, потроллить рекрутера. Но если Вы согласились на интервью, а тем более пришли куда-то — то тут ваш троллинг уже совсем ни к месту. Вы приняли условие вакансии и создаете драму совершенно на пустом месте.
0xd34df00d Автор
17.08.2019 15:36Э, почему ж редиска, если я на позицию С++-разработчика претендую?
Редиски скорее те работодатели, которым свой гитхаб указываешь, а они phone screening устраивают с проверками на базовое понимание программирования.
Или списки разворачивать просят.wataru
17.08.2019 15:44Гитхаб может быть набит кучей чужого кода. Резюме просто списано с первого найденного в гугле резюме.
Кандидатов обычно много и все такие замечательные. По душам поговорить про высокие материи с каждым слишком дорого. Поэтому phone screening, где вас спросят написать FizzBuzz или развернуть список — это вполне адекватно.
Вас же не бесит, что надо анкеты какие-то заполнять, CV по общепринятому стандарту делать? Ну вот решение тривиальных задачек — это еще одна бюрократическая неприятность, которую надо преодолеть.
0xd34df00d Автор
17.08.2019 15:51+1Гитхаб может быть набит кучей чужого кода.
См. п. 3.
где вас спросят написать FizzBuzz
Вас же не бесит, что надо анкеты какие-то заполнять, CV по общепринятому стандарту делать?
А какие анкеты? Единственные бумажки, которые я заполнял за последнее время — это NDA на задачки и/или проприетарную информацию, которую я могу узнать на собеседовании (второе прям даже воодушевило, это ж значит, что мы будем реальные задачи обсуждать, а не как списки переворачивать!).
А CV у меня… Ну я скачал где-то шаблон для латеха и в нём делаю.
wataru
17.08.2019 15:57+1Да без проблем!
О боже ж ты мой! 450+ строк кода без комментариев! Это даже круче FizzBuzz Enterprise Edition. Стесняюсь спросить, но… Все это нужно для реализации, или большая часть — это доказательство?
0xd34df00d Автор
17.08.2019 16:00Это даже круче FizzBuzz Enterprise Edition.
Спасибо, я старался!
Большая часть — доказательство и, ээ, формализация (ну вот что такое деление, например?), плюс вспомогательные вещи — те же натуральные числа или процедуру деления я реализовал с нуля сам. Реализация — последние 5-6 строк.
Gryphon88
18.08.2019 00:22Большая часть — доказательство и, ээ, формализация (ну вот что такое деление, например?), плюс вспомогательные вещи — те же натуральные числа или процедуру деления я реализовал с нуля сам.
Насколько велика «стандартная библиотека» Идриса? Просто хочется из коробки иметь ряд доказанных вещей, натуральные числа своими руками это не сколько неудобно.0xd34df00d Автор
18.08.2019 00:26Натуральные числа и, например, их неравенства там точно есть. Формально верифицированного деления в нужном мне виде, ЕМНИП, нет.
Думаю, если воспользоваться стандартной библиотекой, то можно будет выкинуть процентов 60 кода. Что, впрочем, для такой задачи всё равно неинтересно, так как мне было любопытно, сколько арифметики мне придётся реализовать для такой задачи.
saboteur_kiev
18.08.2019 04:11Я начинаю сомневаться, что 0xd34df00d разработчик.
Зачем ему вакансия разработчиков, если ему прямая дорога в прикладные математики или как это называется?
На работе обычного senior С++ разработчика, или не дай бог тимлида, он же просто перегорит от необходимости писать обычный код, без формальных доказательств, еще и писать тесты.0xd34df00d Автор
18.08.2019 04:21Я, кстати, таки всерьёз подумываю в чистую математику идти. Так-то в дипломе у меня написано «прикладной математик», но там как раз всей этой ерунды с формальными доказательствами не было, увы.
Но да, то, какой код (все эти темплейты на плюсах, кстати, с тестами) и как надо писать — вполне себе послужило критерием недавнего выбора нового места работы.
sshikov
17.08.2019 16:10+1Хм. Знаете, это вероятно выдуманное интервью, и в реальном случае было бы примерно так (где-то посредине): «Достаточно, а теперь перейдем к технической части нашей беседы ;)». У соискателя спросили о чем-то одном. Если интервьюирующий не смог быстро оценить ответ, и перейти к следующим вопросам — это его проблемы, вам не кажется? Если ему интересны реально навыки в разработке на C++ — ну тогда не надо разрешать писать примеры на любом языке, уточнил бы сразу. Ну т.е. — ССЗБ.
Alesh
17.08.2019 00:03+4И не перезвонят. В резюме же было написано, требуется программист С++, а не тролль 80lv со знанием Idris :)
maxim_ge
17.08.2019 00:18+2Занятно. На Прологе через аккумулятор синтаксически покороче будет, хотя по сути то же самое:
revOnto([H|T],A,R):- revOnto(T,[H|A],R). revOnto([],A,A). revAcc(L,R):-revOnto(L,[],R).
А вот «тупенький» вариант выглядит более неуклюже:
revDumb([],[]). revDumb([H|T],R):- revDumb(T,RevT), append(RevT,[H],R).
Было бы, конечно, круто использовать предикаты второго порядка:
revDumb([],[]). revDumb([H|T], R):- append(revDumb(T, RevT), H,R).
Но доказать не могу.lagranzh
17.08.2019 02:20я хаскель не знаю, но глядя на код, тоже о прологе подумал :)
Gryphon88
18.08.2019 00:04И я. Не подскажете, языки идеологически близки, или автор Индриса не это имел в виду?
0xd34df00d Автор
18.08.2019 00:08ИМХО идрис ближе к хаскелю, чем к прологу.
Gryphon88
18.08.2019 00:13Я именно про идеологию. Пролог создавался с идеей, что для решения задачи достаточно описать «мир», начальное состояние и конечное желаемое состояние. Дли Идриса насколько подробно надо очерчивать сам путь от исходного к конечному состоянию?
0xd34df00d Автор
18.08.2019 00:18Весьма подробно.
Наверное, самое близкое к автоматическому поиску пути — поиск доказательства утверждения. У идриса из коробки для этого довольно мало средств (но есть elaborator reflection, который по факту позволяет скриптовать тайпчекер, и который я пока не осилил), и ближайшим аналогом тут скорее будут тактики из Coq.
maxim_ge
17.08.2019 00:43+2Я недавно на собеседовании со стороны работодателя задавал вот такой нескучный вопрос:
Два конфокальных зеркальных эллипсоида соединены зеркальным же кольцом, как показано на рисунке, внутри вакуум.
В фокусах два горячих тела Alice и Bob (не отвлекайтесь), для краткости А и В.
Все фотоны из А попадают в В, но только часть фотонов из В попадает в А, некоторые отражаются обратно в В.
В итоге имеем перекачку тепла из А в В без внешнего источника энергии, то есть вечный двигатель второго рода.
Вопрос: где засада?
Тянуто отсюда
Парень был тоже из ИТМО(как и я), очень толковый, хорошо пообсуждали. Но не прошел других коллег (они, что интересно, тоже из ИТМО).
zabbius
17.08.2019 01:45Я нифига не физик, но предположу, что фотоны из A и из B будут иметь разную энергию. Соответственно, один фотон из B в А перенесет энергии больше, чем один фотон из A в B или типа того.
Bronx
18.08.2019 21:14Если до начала эксперимента А и Б были одинаковой температуры, а в равновесном состоянии Б оказалось горячее А, то это означало бы, что тепло из А передалось в Б без совершения работы. Добавляя/удаляя малый полу-эллипсоид можно было бы получить постоянную перекачку тепла из А в Б и обратно, т.е. вечный двигатель.
qw1
18.08.2019 21:50+2Является ли вечным двигателем маятник, перекачивающий энергию из потенциальной в кинетическую, и обратно?
Bronx
19.08.2019 07:39Нет, не является, но он и не является термодинамической системой. Если у вас есть способ вывести систему из термодинамического равновесия (т.е. уменьшить энтропию), не совершая над ней работы, то вы можете построить вечный двигатель второго рода, выкачивающий бесплатную энергию из окружающей среды. См. ниже вариант такого двигателя.
DistortNeo
18.08.2019 21:52+1Тепло перекачивается из А в Б и обратно, но суммарная энергия системы остаётся неизменной. В чём заключается вечный двигатель-то?
P.S. Суть вечного двигателя — в возможности неограниченного извлечения энергии. Здесь же энергия не извлекается.
0xd34df00d Автор
18.08.2019 21:55Но, похоже, нарушением второго начала термодинамики таки пахло бы.
qw1
18.08.2019 22:34Видимо, проблема в вышеприведённых рассуждениях в том, что предполагается, что энергия сконцентрирована только в точках A и B. Температуры A и B должны сравняться, а весь излишек энергии будет летать между зеркалами. При изменении геометрии что будет с теми фотонами, которые окажутся в «откусываемой» области?
0xd34df00d Автор
19.08.2019 00:27При изменении геометрии что будет с теми фотонами, которые окажутся в «откусываемой» области?
Окажут давление на зеркало, если область именно откусывать.
DistortNeo
19.08.2019 10:15Тогда бы и солнечные электростанции были бы нарушением второго начала термодинамики. А ведь ничего не нарушается!
Кстати, парадокс с эллипсами можно даже упростить: взять белое тело и поместить его в полость чёрного тела. Даже если тела будут неидеально белые и чёрные, белое тело всегда будет холоднее чёрного, и можно извлекать энергию из разности температур.
Парадокс же разрешается тем, что абсолютно белых тел не существует. Если тело что-то излучает, то оно должно это же излучение и поглощать, иначе получается демон Максвела.
Bronx
19.08.2019 07:16- Открываем систему и приводим её в равновесие с окружающей средой. Температуры тел А и Б становятся равными Т.
- Закрываем систему, вводим малый эллипс. А остывает ниже Т, Б нагревается выше Т.
- Открываем систему, снимаем тепло с Б, используя среду как холодильник, также снимаем тепло из внешней среды, используя A как холодильник, совершаем работу.
- Повторяем до бесконечности.
Получили вечный двигатель второго рода.
nickolaym
17.08.2019 02:13-1Засада в том, что если фотон из А попадает в Б, то по той же самой траектории фотон из Б попадает в А.
Это не модель АЧТ в виде камеры-обскуры с дыркой: тут дырка будь здоров какая.
Можем посмотреть, при каких условиях наступает равновесие.
Пусть А и Б равномерно светят во все стороны.
При этом весь поток из А направлен в Б.
Некоторая доля q потока из Б направлена в А, а остальная (1-q) направлена в Б.
Тогда, если Б излучает ровно в q раз больше, чем А, потоки энергии уравниваются.
Как связаны пропорции размеров эллипсоидов и телесный угол облучения Алисы Бобом — хз, надо считать. Было бы желание.
У doctor-notes притянуты разговоры про температуру вселенной, всё такое… это совершенно избыточно.
lagranzh
17.08.2019 02:25Засада в том, что если фотон из А попадает в Б, то по той же самой траектории фотон из Б попадает в А.
Я не физик, но нипель для фотонов существует. Это стекло с одной стороны серебрянкой покрашеное.
MTyrz
17.08.2019 03:18Я тоже не физик, но идея zabbius'а мне кажется более близкой к истине.
Длина волны теплового излучения обратно пропорциональна температуре излучающего тела, и заодно энергии излучаемого фотона. Как только В нагреется выше А, он начнет излучать более синие фотоны, доставляя А с каждым фотоном большее количество энергии. При установившемся равновесии В будет горячее А, но вот посчитать это мне уже слабО.
И разумеется, это если высказанная идея верна.
Bronx
18.08.2019 21:09При этом весь поток из А направлен в Б.
Это неверно: при конечных размерах A и Б (строго точечные АЧТ вообще не излучают) на "верхушках" эллипсоидов будут зоны, где отражённый луч будет падать обратно на излучившее их тело. Телесный угол этой зоны будет тем больше, чем ближе тело к стенке. Тело А ближе к верхушке малого эллипсоида чем Б к верхушке большого, значит А будет греть саму себя сильнее, чем Б самого себя без учёта зеркала. Зеркало восстанавливает баланс.
dim2r
17.08.2019 10:14Обратно фотоны не вернутся простым путем через 2 отражения в точку В, так как должно быть 90 градусов угол в нижнем углу, а там изза скругления он не равен 90. Второй эффект в том, что объекты неточечные и свет не ходит простыми путями. Есть куча нелинейных эффектов, связанная с волновой природой света.
mrchirkopf
17.08.2019 15:42Могу ошибаться, но засада состоит в том, что по условиям задачи А и Б стоят в фокальных точках конфокальных зеркал, без указания к какому именно зеркалу фокус относится (к близлежащему или удалённому), но это и не так интересно. Ошибка состоит в том, что находясь в фокусе зеркала фотоны падая на него должны идти паралельно оптической оси, а так как А и Б на ней лежат (согласно рисунку), то условие все фотоны из А попадаю в Б не выполняется.
wataru
17.08.2019 15:47+1Вы свойства параболы и эллипса не спутали? Любой фотон из одного фокуса эллипса всегда попадает в другой фокус.
DistortNeo
17.08.2019 16:02А нет никакой засады. Да, в замкнутой системе тело В будет горячее, чем тело А — это глупо отрицать. До бесконечности этот процесс идти не может, т.к. чем горячее тело, тем больше энергии оно испускает, поэтому рано или поздно наступит равновесие.
Но вечный двигатель построить все равно не получится, т.к. суммарная энергия системы будет уменьшаться, и оба тела просто остынут.
Max_vst
17.08.2019 01:22Могу предположить, что не перезвонили из-за того, что ожидали написание программы на бумаге.
0HenrY0
17.08.2019 01:35Иногда собеседование — это просто собеседование.
HR'ы делают вид, что работают, набирая десятки резюме для конкурса, в которых победитель известен заранее, а количество интервью нужно только для отчетов и премий.
Кандидаты уже имеют хорошую работу, но периодически ходят на собеседования для поддержки знаний в тонусе, поднятие скила.
rpiontik
17.08.2019 09:20Ну вот… очередной кандидат завалил простейший тест. ИТ вырождается. Нынче нормального спеца не найти.
0xd34df00d Автор
17.08.2019 17:40И не говорите. А потом эти же кандидаты вопрошают, нужно ли высшее образование для ИТ.
TimeCoder
17.08.2019 11:16-1Я бы тоже не взял вас на работу. У каждой задачи есть область решений, приведу пример. Где-то в 6 классе я в решении квадратного уравнения написал ответ в виде комплексных чисел (в поле действительных корней не было). И потом с чувством всезнайства доказывал учительнице, что я прав. Формально — да. Фактически — это была задача на проверку конкретного набора знаний, и в этих рамках правильный ответ: корней нет. Да, можно презирать рамки и лететь в бескрайние просторы разума. Вот только я кучу времени от урока потратил на споры, вреда от того умничания было больше, чем пользы. Также и здесь: вопросы собеседования нужны для проверки знаний в области структур данных и алгоритмов. Это набор решений, применяемых в индустрии. В том числе это важно для того, чтобы ваше решение было понятно коллегам. Да, от этого отдаёт некой обыденностью, но 90% повседневных задач программиста базируются на уже известных алгоритмах и подходах. Из кубиков складывается домик. Вы приходите и приносите свои круглые кубики, понятные далеко не всем, и как бы удивляетесь, а что не так. Это высокомерно, а попросту говоря «понт».
Ещё один пример. Был у меня на работе такой же коллега, знает всё, на каждую задачу выдавал крутые презентации с кучей формул, алгоритмов, мозг! Только вот в итоге он не довёл ни одной задачи до конца, и был уволен. Он просто тонул в сложности своих же решений, деталях, там где нужно было просто взять и сделать. Его «правильное» и очень продвинутое решение занимало слишком много времени, его тяжело было поддерживать всем остальным, т.е. человек жил в своей, удобной ему реальности.
KvanTTT
17.08.2019 15:19Где-то в 6 классе я в решении квадратного уравнения написал ответ в виде комплексных чисел (в поле действительных корней не было). И потом с чувством всезнайства доказывал учительнице, что я прав.
Я надеюсь, что учительница все же знала, что такие числа существуют?
Ещё один пример. Был у меня на работе такой же коллега, знает всё, на каждую задачу выдавал крутые презентации с кучей формул, алгоритмов, мозг! Только вот в итоге он не довёл ни одной задачи до конца, и был уволен. Он просто тонул в сложности своих же решений, деталях, там где нужно было просто взять и сделать.
Значит не такой уж и "мозг". Мозг — это способность балансирования между знаниями и практичностью.
0xd34df00d Автор
17.08.2019 15:43Фактически — это была задача на проверку конкретного набора знаний, и в этих рамках правильный ответ: корней нет.
Ну так вы это и показали: действительных корней нет.
Ещё один пример. Был у меня на работе такой же коллега, знает всё, на каждую задачу выдавал крутые презентации с кучей формул, алгоритмов, мозг! Только вот в итоге он не довёл ни одной задачи до конца, и был уволен. Он просто тонул в сложности своих же решений, деталях, там где нужно было просто взять и сделать. Его «правильное» и очень продвинутое решение занимало слишком много времени, его тяжело было поддерживать всем остальным, т.е. человек жил в своей, удобной ему реальности.
Ну вот, думается, уволен он не потому, что формулы-алгоритмы, а потому, что тонул и не успевал. Первично таки второе.
ameli_anna_kate
17.08.2019 12:49+2Вполне возможно, что несколько скучных вопросов для разгона, что бы человек не много расслабился на собесе, ответив на них быстро и правильно. Эх вы, автор, надо было подождать, глядишь и интересные вопросы пошли бы.
Возможно, вы на столько круты, что разгон не нуждаетесь, но большинство кандидатов нервничают. Собеседование — это стресс для людей.
Или вы изначально не очень заинтересовались данной вакансией, или вас все устраивает в вашей текущей работе, а пошли скорее для внутренней галочки. И тд.
Возможно, если бы это была компания, в которую вы хотели годами, с предложением на 20-30 процентов больше от вашей текущей зарплаты, с великолепными бонусами(от наши кофе леди принесут вам свежевыжатый смузи на экологически чистых фруктах и не тяжёлой воде по утрам, до наш эксклюзивный шеф-повар приготовит авторский ужин), в шаговой доступности от дома. Ну или возможностью работать удаленно, не знаю, о чем вы там мечтаете. В команду с Тим лидом, книги которого читаете и в душе считаете кумиром. Вы бы повели себя несколько иначе на собеседовании.
user_man
17.08.2019 12:57>> revDumb (x :: xs) = revDumb xs ++ [x]
Либо это идрис «не торт», либо данная конструкция никогда не остановится. Первый элемент списка вечно ставится в конец, после чего весь список кидается на вход функции, которая опять первый элемент ставит последним, и так до тепловой смерти вселенной.
Да, зря тесты не были запущены. И да, формально — задание не выполнено. А неформально — не выполнено со страшно умным видом.wataru
17.08.2019 14:13Не специалист по этому языку, но, кажется, рекурсивый вызов делается только для конца списка, а потом к нему уже добавляется первый элемент в конец. Приоритет операций видимо такой. Хотя, наличие скобок сильно упростило бы понимание.
user_man
18.08.2019 11:07Да, в функциональщине нужно долго и нудно запоминать приоритеты всех видов конструкций. В том числе поэтому они не рекомендуются для массового использования.
wataru
18.08.2019 12:01Ну, справедливости ради, в том же С++ тоже надо приоритеты учить. Особенно логических и битовых "и" и "или".
user_man
19.08.2019 13:11В Хаскеле, например (а он похож по синтаксису на Идрис), есть 22 оператора с приоритетами от 3 до 9 и двумя ассоциативностями — левой и правой. Приоритетов №9 — два, №8 — два, №7 — 4, №6 — 2, №5 — 2, №4 — 8, №3 — 2. Это без учёта приоритета аргументов функции и конструкций типа &.
И это всё должен знать каждый участник команды разработки, просто что бы понимать код коллег. Без такого знания будут муки и адское затягивание сроков.
В Си-подобных языках из приоритетов, кроме стандартных арифметических, вот разве что битовые операции. И всё. Плюс обязательность использования скобок, что само по себе устраняет массу вопросов типа того, который мы сейчас обсуждаем.0xd34df00d Автор
19.08.2019 15:07В Хаскеле, например (а он похож по синтаксису на Идрис), есть 22 оператора
В хаскеле сильно больше операторов, и можно создавать свои. Потенциально в хаскеле счётное множество операторов.
И это всё должен знать каждый участник команды разработки, просто что бы понимать код коллег. Без такого знания будут муки и адское затягивание сроков.
Вы не поверите, но нет. Я вообще не помню приоритеты операторов, и ничего, живу как-то, пишу код, понимаю чужой код, сроки не затягиваю. Просто всё довольно разумно сделано.
В Си-подобных языках из приоритетов, кроме стандартных арифметических, вот разве что битовые операции. И всё.
15. Похоже, пришло время нудного заучивания.
user_man
20.08.2019 12:36>> В хаскеле сильно больше операторов
Речь о стандартных, поэтому не надо передёргивать.
>> Я вообще не помню приоритеты операторов
Тогда с чего вы решили, что ваш код — правильный?
>> Похоже, пришло время нудного заучивания
Убираем из этого списка скобки и прочее очевидное, получаем за исключением арифметики (включая очевидные булевы операции) в разы меньше, чем в функциональщине.0xd34df00d Автор
20.08.2019 15:06Речь о стандартных, поэтому не надо передёргивать.
Я вот открыл модуль
Control.Arrow, который идёт вbase, который идёт с де-факто стандартным компилятором, и там сходу минимум 11 операторов, а это явно даже не половина.
Да и какая разница, стандартные операторы или нет, если почти все проекты не ограничиваются стандартной библиотекой, и, соответственно, вполне могут пользоваться дополнительными операторами? Я ровно поэтому боюсь той же lens, потому что там слишком много операторов (но основная проблема в том, что они как-то не очень, как бы это по-русски-то, discoverable).
Тогда с чего вы решили, что ваш код — правильный?
На идрисе доказал, на хаскеле почти всё такое же «прочее очевидное», да и вообще просто так получается. Да и опыт подсказывает, что если приоритеты перепутать, то там несовпадение типов будет.
А кстати, когда вы на С пишете, вы точно помните весь стандарт и всю семантику абстрактной машины, чтобы быть уверенным, что ваш код правильно скомпилируется?
0xd34df00d Автор
18.08.2019 20:19К счастью, конструкций там не так много: вызов функции.
А если чуть серьёзнее, то почти всегда в выражении из операторов типы разных подвыражений разные, поэтому некорректный порядок поймается на уровне типов.
Да и, по субъективному опыту, я никаких приоритетов операторов не запоминал, и при этом почему-то проблем с этим не испытывал.
user_man
19.08.2019 13:19>> поэтому некорректный порядок поймается на уровне типов
В данном случае не поймается — на входе функции список, на выходе конкатенации тоже; на выходе функции список, на входе конкатенации тоже. То есть хоть так, хоть так — будет валидный код.0xd34df00d Автор
19.08.2019 15:09В данном случае это поймается тоталити чекером.
user_man
20.08.2019 12:46Понятия не имею, что за магическая тулза имеется в виду, но компилятор — не поймает.
0xd34df00d Автор
20.08.2019 14:58Всё же перед тем, как подобные заявления делать, стоит немножко разобраться в предмете.
%default total revDumb : List a -> List a revDumb [] = [] revDumb (x :: xs) = revDumb (xs ++ [x])
Type checking ./Bad.idr Bad.idr:5:1-39: | 5 | revDumb (x :: xs) = revDumb (xs ++ [x]) | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Main.revDumb is possibly not total due to recursive path Main.revDumb --> Main.revDumb
0xd34df00d Автор
17.08.2019 15:48Либо это идрис «не торт», либо данная конструкция никогда не остановится. Первый элемент списка вечно ставится в конец, после чего весь список кидается на вход функции, которая опять первый элемент ставит последним, и так до тепловой смерти вселенной.
Применение функций всегда, во всех известных мне ML-подобных языках, имеет больший приоритет, чем любые операторы, поэтому rhs парсится как
(revDumb xs) ++ [x], так что всё там в порядке. Да и в идрисе есть тоталити чекер, который наrevDumb (xs ++ [x])бы ругнулся.
Да, зря тесты не были запущены.
Эх, сколько же людей верят в тесты, но не верят в формальные доказательства.
user_man
18.08.2019 11:13Тест показал бы (не)корректность интерпретации приоритетов операций конкретным разработчиком.
0xd34df00d Автор
18.08.2019 20:16Формальное доказательство и отсутствие ругани тоталити чекера на partiality показало это, ИМХО, лучше.
Alesh
17.08.2019 13:35+1Не знаю было ли в задумке автора этого креатива дать хороший прием именно для собеседующего, но он дал. Попросить реализовать несложный алгоритм, на языке по выбору собеседуемого это хороший ход, особенно если вакансия подразумевает программиста владеющего конкретным языком. Если испытуемый выбрал не целевой язык вакансии, испытующий получит интересную информации к размышлению, как о технической подготовки кандидата, так и о личных качествах.
sshikov
17.08.2019 16:24>вакансия подразумевает программиста владеющего конкретным языком
Хм. И какие же выводы вы для себя сделали о технической подготовке кандидата в C++?
Скажем прямо — из текстов вакансий далеко не всегда очевидно, будет ли указанный навык (язык, платформа) единственно возможным/обязательным, или будет выбор. Зачастую и проект заранее не известен. Если интервьюер прямо разрешает писать на любом языке — демонстрация познаний о другом языке для меня лично ни о чем плохом не говорит тоже.Alesh
17.08.2019 23:26+1Если взять в качестве примера историю в посте, то о технической подготовке испытуемого как программиста С++ я бы сделал как минимум следующий вывод. Программист идёт на вакансию по не родному для него языку, и с большой вероятностью не любит на нем программировать. Это точно не гуру С++, и интересных решений от него ждать на этом языке не стоит, даже если выясниться, что уровень владения C++ высокий В общем сеньором только на безрыбье.
0xd34df00d Автор
17.08.2019 23:51-1и интересных решений от него ждать на этом языке не стоит
Жаль, а то могу ж производные в компилтайме взять, или вот недоORM наваять на темплейтах.
sshikov
18.08.2019 08:30Честно говоря, не вижу, откуда вы делаете такие выводы. Что значит родной язык? Я вот писал и пишу примерно на десятках языков, довольно разных. Профессионально, то есть получаю за это деньги.
Я не обобщаю это на всех и на любые проекты, не всегда так можно, но так бывает. Более того, в моей практике человек, который на высоком уровне владеет хотя бы парой разных языков, обычно выдает решения значительно более интересные и полезные, чем узкий специалист.
>даже если выясниться, что уровень владения C++ высокий
В том-то и дело, что ни одного вопроса по нему не задано. То есть эти выводы выглядят как сильно надуманные (из опыта). Как прием для оценки кандидата — да, это хорошо, но если вам интересны конкретные навыки — то лучше про них прямо и спросить. А так получается что-то типа «Ах, он любит идрис, очевидно он не гуру C++».wataru
18.08.2019 10:18В том-то и дело, что ни одного вопроса по нему не задано.
Согласен, тут гипотетический интервьюер как-то странно спрашивает про любой язык. Формально, так можно и на brainfuck наткнуться. Обычно, если вакансия C++, то и на интервью именно C++ и просят.
Alesh
18.08.2019 11:46«Родной язык» наверно не совсем к месту выражение, но я думал будет понятно. Это тот который у вас в резюме идет первым в списке ваших рабочих языков. Тот на котором вы пишите что-то свое или пробуете какой-то интересный алгоритм, если не важен выбор языка.
Да, в примере не одного вопроса по С++ не задано, и это тоже вполне логично. Мало кто осмысленно возьмет в команду тролля. Поэтому желания задавать дополнительные вопросы после такого выступления, мало у кого возникнет.
saboteur_kiev
19.08.2019 00:27Попросить реализовать несложный алгоритм, на языке по выбору собеседуемого это хороший ход
Проблема в том, что кандидат не просто реализовал несложный алгоритм на языке по своему выбору, а реализовал на нем формальное доказательство работы алгоритма. Саму реализацию алгоритма сделал уже в самом конце, и то, скорее для отмашки.
То есть IMHO выполнил огромный оверинженеринг для простой задачи.0xd34df00d Автор
19.08.2019 00:28Саму реализацию алгоритма сделал уже в самом конце, и то, скорее для отмашки.
Э, нет, с реализации всё и началось. В этих всех языках довольно трудно доказывать свойства функций, которые вы ещё не написали.
Alexander_Tamirov
17.08.2019 15:52Интересно, у меня одного впечатление, что я очередную серию «Доктор Хаус» посмотрел…
Автор препарировал интервьювера))ameli_anna_kate
17.08.2019 17:00Да, странно как-то. Может действительно все заболели и этот интервьюер в предыдущие собеседования в основном сидел рядом, больше слушал, чем задавал вопросы. Обычно есть среднее время на вопрос. Если человек затупил, пошел в какие-то не те дебри, то ему задают наводящие вопросы, рассказывают ожидаемое решение или просто переходят к следующему заданию.
Скорее всего, когда предлагают реализовать на удобном языке, то подразумевают выбор в разумных пределах. Либо там с самого начала стало ясно, что не подходит, просто интервьюер постеснялся выгнать с собеседования кандидата, практически сразу, и просто молчал, давая возможность тому заниматься самолюбованием.
Alexander_Tamirov
17.08.2019 19:35… давая возможность тому заниматься самолюбованием
Ну, да… И это тоже)) Но красиво написано. Есть поверие, что «вся наша деловая жизнь — это шоубизнес».
Автор талантлив))ameli_anna_kate
17.08.2019 22:31Ага, красиво. Собеседование во многом зависит от умения человека говорить, один даже не все зная натрындит, а второй, будучи отличным разработчиком, тупит на лёгкие вопросы, так как не в своей зоне комфорта.
Не плохой был бы ответ в стиле: "Вы слишком круты для нашей компании". Хотя нет, наверно, сейчас за такой ответ могут и в суд подать.
Я вообще фронт, у нас нет проблем в длине массива и необходимости прибегать к спискам. Можно эмитировать с помощью вложенных друг в друга объектов. Автор, как вам js?
Alexander_Tamirov
17.08.2019 23:01Вы мазохист?)) у автора статьи спрашивать такое!!! Сейчас начнутся размышления про слабую типизацию в JavaScript engine на сервере и кастомную компиляцию движка, чтобы убыстрить тесты на 14 ms… Не, лучше не надо.
0xd34df00d Автор
17.08.2019 23:55Автор, как вам js?
Сталкиваюсь только в браузере и, в общем, доволен этим состоянием дел.
Ещё завидую тем, кто на js пишет, там всё время движняк какой-то, бабелы какие-то, вебпаки,
тгульпы, ангуляры, всё течёт, всё меняется. У меня бы уже голова лопнула.
kovserg
17.08.2019 17:25Охренеть сколько срача вызвал односвязный список? Интересно какой угар был бы если спросили про красно-черное дерево.
typedef struct node { node* next; int value; } *pnode; pnode reverse(pnode list) { pnode p,t,n; for(p=0,t=list;t;t=n) { n=t->next; t->next=p; p=t; } return p; }
malishich
17.08.2019 18:37Если в вашем проекте использовался односвязный список и вам понадобилось делать его «развороты» то это хорошее подспорье отказаться от него в пользу хотя бы двусвязного списка. А так это выглядит как героическая борьба с проблемами которые сами же себе и создали.
wataru
17.08.2019 23:39+1А так это выглядит как героическая борьба с проблемами которые сами же себе и создали.
Разворот односвязного списка — не такая сложная задача, чтобы значительно увеличивать потребление памяти всей программы лишь для упрощения кода ее решения (2-3 строчки с тремя переменными).
Когда это не стало баяном, этот вопрос был лишь разминкой, из категории простых, чтобы кандидата расслабить перед основным вопросом посерьезнее.
0xd34df00d Автор
17.08.2019 23:52Кроме того, в ФП-стайл-программировании с иммутабельными данными сделать двусвязный список — не очень тривиальная задача (на каком-нибудь хаскеле придётся очень активно пользоваться ленивостью и завязывать узел).
NeocortexLab
17.08.2019 19:06Т.к. ЯП предлагался любой, то я выбираю Python:
MaxVetrov
17.08.2019 23:22+1— Ну, давайте для начала решим такую задачу: дан односвязный список, нужно его обратить.
Берем forward_list и делаем reverse() :)
0HenrY0
18.08.2019 11:32+1— Ну, давайте для начала решим такую задачу: нужно забить гвоздь.
— Сейчас сделаю! А каким инструментом лучше это сделать?
— Каким вам удобнее.
— Так… Для начала возьмем микроскоп.
— Вы уверены, что правильно поняли задачу? На рабочем столе нет микроскопа.
— А он и не понадобиться. Я Вам теоретически докажу, что забить гвоздь микроскопом возможно.sshmakov
18.08.2019 13:59Попугай: Можно измерить твой рост в попугаях…
Удав: Как это???
П.: Сколько попугаев в тебе поместится, такой у тебя и рост!
У.: Очень надо… Я не собираюсь глотать столько попугаев!
П.: Ну, во–первых, глотать никого не надо, а во–вторых, и одного попугая хватит. Меня!
catharsis
19.08.2019 13:59Полезный сигнал, полученный интервьюером минимален: "кандидат вроде бы интересуется Computer Science, дальше я не понял".
Интервьюер конечно не прав в том чтобы разрешить писать на чем угодно и молчать все собеседование, но его оторвали от работы, он может себе позволить, а кандидату собеседование обычно важнее. Ну и понимать что от вас хотят — навык нужный везде.
А тесты нужны на тот случай когда кто-нибудь в будущем "поправит" ваш код.
0xd34df00d Автор
19.08.2019 15:09А тесты нужны на тот случай когда кто-нибудь в будущем "поправит" ваш код.
Так и доказательства тогда придётся править.
catharsis
19.08.2019 14:26+1I’m confident that the primary reason people try to come up with exotic answers to simple programming questions during an interview is because they feel the need to impress, or “wow”, their interviewer.
They may feel somewhat insecure about the whole situation where they’re put on the spot, so they think if they appear to be the most clever, creative and brilliant mind that has walked through the interview doors, they will be a shoo-in for the job.
OTOH, folks who don’t seem to be out to impress everyone seem to come up with simple, elegant and efficient solutions that are both readable and functionally solid for all edge cases. When going into an interview, putting yourself through the added stress of trying to force a brilliant or “clever” solution to a problem will definitely work against you.
Also, it’s always a good idea to ask clarifying questions during an interview; it shows that you are a good communicator, which is important on any team, especially software development / engineering teams.
Now, the above reasons I have discussed aren’t going to apply to everyone, obviously. It’s just a pattern I’ve noticed in myself when I was a younger, less experienced software developer in college, attempting to explain my solutions and answer simple questions in my CS classes and labs. I’m fairly confident that this is a common issue among lesser experienced programmers.
Из обсуждения задач FizzBuzz и swap variables
imranontech.com/2007/01/24/using-fizzbuzz-to-find-developers-who-grok-coding/#comment-499570xd34df00d Автор
19.08.2019 15:13Now, the above reasons I have discussed aren’t going to apply to everyone, obviously. It’s just a pattern I’ve noticed in myself when I was a younger, less experienced software developer in college, attempting to explain my solutions and answer simple questions in my CS classes and labs. I’m fairly confident that this is a common issue among lesser experienced programmers.
Ясно.
Жаль, что мотивация вроде «такие задачки задают — ну, всё понятно с ними, работать я тогда здесь всё равно не собираюсь, так что хоть в объяснении $exoticname потренируюсь» в голову не приходит.
saneea
19.08.2019 15:09Эм… разве мы не можем просто бежать по списку и проходя каждый элемент менять ссылку на «следующий элемент» ссылкой на предыдущий пройденный элемент? Линейная сложность, один проход по списку. Я б на java это сделал так:
static class Node {
public int data;
public Node next;
}
static Node reverse(Node head) {
Node prev = null;
for (; true;) {
Node next = head.next;
head.next = prev;
if (next == null) {
return head;
}
prev = head;
head = next;
}
}
Или я не понял задачу?
sebres
19.08.2019 19:15Эм… разве мы не можем просто бежать по списку и проходя каждый элемент менять ссылку на «следующий элемент» ссылкой на предыдущий пройденный элемент?...
Можем… но это не так весело… ну и тут автор как бы и "тонко" потроллил, опять же блеснул знаниями функциональщины, да и в математику "сбегал"...
А так то да (если in-place, т.е. не нужна копия/оригинал списка) — как ответ достаточно что-нибудь типа — "поменяем" три значения в цикле (ну и какой-нибудь простейший тест):
Скрытый текстclass Node: @staticmethod def reverse(head): prev = None; while head: head.next, prev, head = prev, head, head.next return prev ## def __init__(self, d=None, next=None): if hasattr(d, '__iter__'): n = self; prev = None for d in d: n.d = d if prev: prev.next = n prev = n n = Node() prev.next = None return self.d = d; self.next = next; def __repr__(self, aslist=False): n = self; s = [] while (n): s.append(n.d); n = n.next; return s if aslist else str(s) def __eq__(self, lst): if isinstance(lst, Node): lst = lst.__repr__(True) return self.__repr__(True) == lst def test_reverse(): assert(Node.reverse(Node([1])) == [1]) assert(Node.reverse(Node([1,2,3])) == [3,2,1]) # in-place change: n = Node([1, 2, 3, 4]) assert(n == [1, 2, 3, 4]) m = Node.reverse(n) assert(m == [4, 3, 2, 1]) # m is inversed list now assert(n == [1]) # n is single (last) element now Node.reverse(m) # n will be restored to original assert(n == [1, 2, 3, 4])saneea
19.08.2019 19:19каюсь, не заметил тега «ненормальное программирование», не понял что сарказм))
0xd34df00d Автор
19.08.2019 19:36а кстати чому idris?
Хаскель для доказывания вещей слабоват, Агда меня юникодом пугает, Coq я пока не осилил (и не большой фанат тактик, доказывания в стиле ФП мне больше по нраву), а всякие там Isabelle — совсем другой стиль.
Так что щито поделать.
worldmind
19.08.2019 15:11Да, на этой планете явно что-то не так, когда человек с такими знаниями вынужден искать работу на C++.
Были бы инвестиции я бы вас таких собрал и посадил бы делать какие-то общественно-важные проекты, вроде децентрализованной системы голосования для прямой демократии.0xd34df00d Автор
19.08.2019 15:14+1Были бы инвестиции — я бы в чистую математику пошёл.
worldmind
19.08.2019 15:20Ну тогда надо трактор заводить
0xd34df00d Автор
19.08.2019 15:21Я уже. Но академические успехи у меня были не блистательные (GPA так себе), да и 5 лет уже с выпуска прошло, в академию надо как-то с другой стороны заходить будет.
worldmind
19.08.2019 15:22Сделать проект для порфолио а потом слать резюмю?
0xd34df00d Автор
19.08.2019 16:17Тут в роли проектов публикации, а мне ещё пока писать не о чем.
worldmind
19.08.2019 16:24ну я надеюсь ты напишешь статью о децентрализованной системе голосования (хотя бы на уровне спецификации), конечно же формально верифицированной, хотя это не совсем наука, но что-то близкое, а главное могущее вызвать интерес сми, а значит и цитирование.
worldmind
19.08.2019 15:21Кстати, в чистой математике полно работы на тему алгоритмов голосования, чёртов Эрроу всю малину испортил.
alex_neishkasha
Потому что надо быть проще :D
Archangel339
Зачем? Ведь грамотно всё разжевал…