Нет, это не я натягиваю сову на глобус. В этой теме есть комментарий:
Литкод и их доморощенные задачи с вымученными условиями. Надо напрячься даже не чтобы решить, а чтобы понять чё хотят.
Я на него уже ссылался. То есть, не только я так думаю.
Если в задании просят найти такие i и j, что выполняется какое-то условие, то первая наивная мысль должна быть - а переберем-ка все i и j и проверим условие.
Но кандидат же по характеру условия сразу понимает, что задача — алгоритмическая, поэтому необходимо найти эффективное решение, а не "переберём все i и j", и сразу пытается думать в этом направлении.
А иначе, как вы предлагаете, — даже не O(nk), а O(n^2).
Как раз попытка ввести какое-то окно, это алгоритмический подход. У вас тут горе от ума.
Нет, это результат попытки "понять чё хотят". Результат перевода условия на "человеческий" язык.
Результат представления того, какие действия над массивом необходимо в целом провести.
Смысл в этой задаче такой же, как и у fizz-buzz. Проверить. что кандидат способен написать 2 вложенных цикла.
В это не верится, потому что задача — явно алгоритмическая и даже сформулирована математическим языком.
Можно. Но таких простых функций мало, а задачек надо - тысячи. Вот и получются вот такие абстрагированные и немного искусственные задачи с поиском дубликатов.
Только получаются почему-то не просто абстрагированные и немного искусственные, а алгоритмические задачи, которые сначала надо перевести на "человеческий" язык, "чтобы понять чё хотят".
А по реализации функций можно начать задавать дополнительные вопросы и двигаться дальше в стиле "слово за слово", я уже об этом писал.
Не считают.
То-то качество постепенно сползает вниз.
Ибо наличие код ревью, тестов и хороших утилит, вроде ubsan и им подобных - хорошо защищают от этого.
Не защищают.
Тесты не могут покрыть все случаи, а ubsan и им подобные — это тоже, как и тесты, средство уровня runtime, то есть, на проявление UB надо наткнуться, предварительно создав для этого условия, а случай, когда создаются эти условия, может быть также не покрыт.
Тесты, в основном, помогают, когда необходимо проверить, что, в целом, всё работает. В целом, а не в частности.
Тесты, как правило, не могут досконально проверить всё. Поэтому тесты хороши только против явных просчётов.
А если коллега вам скажет: реализуйте тут скользящее окно с хеш таблицей - без подготовки это вообще не понять.
Как это не понять?
По частям всё Google'ится, изучается, обретается понимание, о чём речь, даже находится, какая под это дело есть поддержка в языке, и потом реализуется.
К данному решению, которое вы привели, ещё необходимо придти.
В условиях собеседования, когда нет времени, и если кандидат ранее не сталкивался с подобными задачами, это — невозможно.
При этом ещё надо не ошибиться, что в конце необходимо дойти до самого конца массива, "сжимая"при этом окно.
Здесь требуется именно алгоритмический подход.
Вы что, предлагаете взять каждое окно из k элементов и там за k^2 обойти все пары элементов?
Естественно.
Задача бьётся на подзадачи.
На первом шаге имеется окно в k элементов, и требуется узнать, нет ли там дубликатов.
Эта подзадача выделяется в отдельный метод и решается за O(k^2), и этот метод вызывается n - k раз, отсюда O(nk^2).
Вы как-то усложнили, смешав умное решение и наивное, получив более медленное.
Нет, так получается, если не мыслить алгоритмически. Если разбивать задачи на подзадачи и так решать всю задачу.
Да, это правильное решение за O(n). Да, это "алгоритмы". Но его на этом интервью не требуют.
Смысла тогда нет давать алгоритмическую задачу и не требовать её правильного решения.
Это задача того же класса как и fizz-buzz
Для fizz-buzz не требуется алгоритмического мышления.
убедиться, что кандидат в состоянии написать простой цикл (или два).
На одном из публичных mock-интервью предлагали написать свою реализацию std::strlen, там как раз есть цикл.
Можно взять из того же семейства функций что-нибудь слегка посложнее.
Особенно логичен он при Argument-Dependent lookup, или integer promotion.
Какая-то общая логика даже там есть, например, изнутри — наружу.
Но механизм вызова виртуальных функций же — логичен? Чувствуется там смысл, особенно, если подумать?
Вы тоже согласны, что алгоритмические собеседования яндекс проводить вправе - они ему нужны.
Да, я несколько раз написал, что если они нужны, то — нужны.
Но каждый раз замечал при этом, что они — не средство для проверки знаний и умений ещё и по C++.
Но считаете, что должно быть больше С++ собеседований?
Нет, я считаю, что собеседование по C++ должно быть по C++, а не по алгоритмам.
Если если ещё нужны и алгоритмы, то это должно быть отдельное собеседование или собеседования.
Я не против C++ собеседований как таковых, но считаю, что они для больших компаний сильно дороже и сложнее, поэтому их и не вводят массово.
Видимо, они не считают, что дороже будет потом, если нанять кандидата, которого потом придётся учить, если он ещё будет учиться, и постоянно иметь риск, не налепил ли он множество неочевидных UB в коде.
UB — недопустимо, потому что компилятор имеет право в этом случае генерировать неправильный код, и современные компиляторы этим усиленно пользуются.
А без них жить в принципе можно: проверить, что кандидат способен базово писать на С++ можно и простыми leetcode задачками.
Жить-то, может быть, и можно, но — дорого. Причём собеседование — один раз, а потом сотрудник будет писать проблемный код постоянно, а не один раз.
Всякие тонкости вроде вызова виртуальных функций из конструктора всегда можно посмотреть в справке*.
Это — не вся правда.
*с алгоритмами так не работает, потому что если вы знаете, какой алгоритм вам надо поискать, то вы задачу уже решили.
Так и с механизмом виртуальных функций есть проблема: обычно, если кандидат не в курсе, ему и в голову не приходит, что здесь могут быть какие-то особенности.
Он считает, что этот механизм сразу работает до уровня самого последнего класса.
Поэтому он даже не пытается ни в какую справку смотреть и что-то там искать по этому поводу.
Вот теперь — вся правда.
Тесты и ошибки компиляции исключают львиную долю ошибок связанных с незнанием этих тонкостей.
Нет, не исключают.
Просто будет вызываться не та функция, да и всё. И это можно пропустить и не заметить.
Или, если UB привело к генерации неправильного кода, то код будет работать неправильно, вот и всё.
И хорошо, если эта неправильность будет сразу видна и обнаружится тестом, но она может проявляться в специфических случаях, не предусмотренных тестами, и поэтому будет пропущена.
И если кандидат способен думать, что решение алгоритмических задачек отлично показывает
На собеседовании — точно не показывает. Некогда на собеседовании думать.
На собеседовании используется предыдущий алгоритмический опыт, который зафиксирован в интуиции, именно она и работает.
Интеллект же применяется в минимальной степени.
то уж понять, как работает таблица виртуальных вызовов он точно сможет в первую неделю работы с кодовой базой, если там виртуальное наследование используется, в отличии от прошлых работ кандидата.
То есть, натаскается по ходу дела на интенсивно используемые в проекте части C++?
То же самое тогда можно и про алгоритмическую часть сказать.
В целом, алгоритмическое собеседование по C++ очень плохо проверяет знания и умения, собственно, по самому C++.
Аргумент, что проводить собеседование по C++ — дорого, считаю ошибочным, потому что потом будет выходить дороже.
Но если алгоритмы нужны, то — да, отдельное собеседование или отдельные собеседования по алгоритмам нужны, но без совмещения с C++, то есть, без цели этими собеседованиями проверить ещё и знания и умения по C++, потому что для этого необходимо проводить специально для этого предназначенное собеседование по C++.
Но она же easy! Там достаточно O(nk). Откуда вы там n^3 взяли - ума не приложу.
Упростил, принял k равным n.
С поправкой на k получается O(nk^2).
C std::unordered_set получается O(n).
Алгоритм такой.
Сначала во множество (std::unordered_set) добавляются элементы, пока их не станет k штук (первый цикл).
Если в процессе добавления обнаруживается, что такой уже есть во множестве, возвращается true.
Затем первый элемент в окне из k элементов удаляется из множества, а следующий за окном добавляется во множество, а окно, таким образом, движется по вектору к его концу, пока окном из k элементов не будет пройден весь вектор (второй цикл).
Если в процессе этого движения обнаруживается, что добавляемый элемент уже есть во множестве, то также возвращается true.
Если до конца массива такого не случилось, возвращается false.
Поскольку операции с std::unordered_set выполняются за O(1), а количество операций равно n, то получается O(n).
Я полагаю, что примерно такое решение должно быть найдено.
И для нахождения этого решения должна быть хоть какая-то алгоритмическая подготовка и хоть какой-то опыт решения подобных задач.
В данном случае эта подготовка и опыт заключаются в применении hash-table-based множества с хранением там копий элементов, попадающих в окно, что как раз и обеспечивает детектирование этим множеством повторений значений элементов в момент добавления очередного элемента, и hash-table-based множество обеспечивает это детектирование за O(1).
Понимание этого свойства позволяет применить для одного шага выкидывание из множества одного элемента в начале окна и добавление во множество следующего за окном элемента, а не заполнение множества каждый раз k элементами на каждом шаге, что, действительно, давало бы O(nk).
Однако, эта и другие задачи никак не связаны с C++, их можно решать на совсем другом языке, и они нужны, только если для вакансии на самом деле требуется алгоритмическая подготовка.
И точно вызовут отрицательные эмоции у кандидатов.
Вы смеётесь, что ли? Какие ещё эмоции?
Проверяется, понимает ли кандидат, как работают конкретные механизмы C++, потому что ему по работе потребуется это понимание, чтобы решать поставленные задачи.
В противном случае, он не сможет их решать.
Эмоциональные в этом смысле кандидаты однозначно не подходят.
А то бывают уникумы с большим опытом, которые на собеседовании на предложение написать простой макрос заявляют, что макросы не пишут, а пользуются вместо этого уже написанными.
Но такие кандидаты никуда не годятся.
Тут не только понимание, но и заучивание всяких определений и документации. С++ - не самый логичный язык, почти на любой вопрос "почему" ответ - лишь цитата из спецификации.
Для механизма вызова виртуальных функций это не так.
Когда, например, создаётся объект класса C, который унаследован от класса B, а B унаследован от полиморфного класса A, то сначала вызывается конструктор A.
Объект в смысле динамического полиморфизма в этот момент представляет из себя класс A, как если бы конструировался объект не класса C, а класса A.
Технически, обычно это реализуется с помощью таблиц виртуальных функций, указатель на которую прописывается первым, программно недоступным полем данных в классе, расположенным прямо перед пользовательскими полями данных.
Первое, что делает код конструктора A ещё до выполнения пользовательского кода, получив управление, это прописывает в то самое поле указатель на таблицу виртуальных функций класса A.
Именно поэтому механизм виртуального вызова, начиная с этого момента и до получения управления конструктором класса B, будет работать, как будто конструируется объект класса A, а не C.
Когда после отработки конструктора класса A управление получит конструктор класса B, он точно также, как и конструктор класса A, первым делом пропишет в то самое поле указатель на таблицу виртуальных функция класса B.
Именно поэтому механизм виртуального вызова, с этого момента и до получения управления конструктором класса C, будет работать, как будто конструируется объект класса B, а не C.
Точно так же поступает конструктор класса C.
Тем, на таблицу виртуальных функций какого класса указывает указатель в том поле, фактически, и определяется динамический тип объекта.
Условно можно считать, что таблица виртуальных функций, указатель на которую прописан в том самом поле, однозначно определяет динамический тип объекта.
К моменту исполнения кода, соответствующего спискам инициализации конструкторов, в то самое поле уже прописан правильный указатель на таблицу виртуальных функций, то есть, объект стал того динамического типа, который соответствует исполняющемуся конструктору.
Таким образом, в процессе конструирования полиморфного объекта его динамический тип меняется в соответствии с тем, какой конструктор начал исполняться.
Когда исполняются деструкторы (в обратном порядке), соответствующий код, добавленный компилятором к деструкторам, обеспечивает точно такое же изменение динамического типа полиморфного объекта при исполнении соответствующего деструктора, но уже в обратную сторону.
Если кандидат понимает описанный выше механизм, то он для класса любой сложности, хоть со множественным и виртуальным наследованием, сможет точно сказать, какой метод вызовется на любом этапе конструирования этого сложного объекта.
И если он, всего лишь, что-то там зазубрил, но не понимает этого механизма, то он не сможет дать правильный ответ.
Я только что достаточно полно описал работу механизма динамического полиморфизма в C++, но не сослался ни на одну спецификацию.
Где здесь цитаты из спецификации?
С++ - не самый логичный язык
Если его знать достаточно глубоко и понимать, как работают его механизмы, то он становится куда более логичным, чем кажется на первый взгляд.
Ну вот же в статье даны задачи. В первых двух вообще алгоритмов нет - надо только 2 цикла сделать, чтобы реализовать буквально то, что написано в задаче.
Неправда.
Если в 219. Contains Duplicate II делать "в лоб", то получается сложность O(n^3), а не O(n), потому что проверка дубликатов "в лоб" делается двумя вложенными циклами, которые дадут O(n^2).
То, что применение std::unordered_set для детектирования дубликатов в скользящем окне вы не считаете алгоритмом — это ваша личная особенность.
Вот, это те самые вопросы из опросника, о котором я говорил в самом начале.
Но проигнорировали дальнейшее мной написанное.
Дополнительные вопросы "а почему", "а что здесь выдаст typeid", "за счёт чего так получается" вскроют либо наличие понимания, какой механизм лежит в основе, либо отсутствие такого понимания.
При наличии понимания кандидат будет правильно отвечать на любой из последовательности вопросов по конкретному случаю, потому что просто будет применять это понимание, механизм в голове воспроизводить и получать правильные результаты.
Если же понимания нет, и он будет пытаться интуитивно угадать, то неизбежно будет ошибаться, а также не сможет объяснить, почему он так ответил, либо объяснения будут очень странными с точки зрения понимающего эту часть человека.
Таким образом и будет выясняться, понимает кандидат, какой механизм лежит в основе, и как он работает, или нет.
Это уже — не опросник, зазубрить не получится, требуется понимать.
Это практически то, что я приводил в качестве примера.
Не знаю, как сейчас, но больше десятка лет назад rvalue-reference'ы объяснялись отвратительно, я удивительно долго не понимал до конца, что там к чему.
По дополнительным вопросам выясняется, полностью кандидат понимает, что там к чему, или нет.
Из-за дополнительных вопросов, с помощью которых выясняется, есть ли понимание, это уже — не опросник, точно так же, как и в предыдущем случае.
И от таких опросников люди буду плеваться не меньше: Зачем эту муть из справки учить? Она есть в документации!
Если кандидат на вопросы по поводу lvalue и rvalue reference'ов так отвечает, то он сразу не проходит дальше никуда.
Это не справочная информация, которую можно забыть, она лежит в основе механизма, реализующего копирование/перемещение.
Соответственно, кандидат не будет знать, где происходит копирование, а где — перемещение.
Примерно так, как если бы математик не помнил, как складывать. Или не помнил, как складывать столбиком без заглядывания в документацию.
Цель - нанять лучших кандидатов с большой верояностью, при этом не тратя на собеседования львиную долю времени работников. Вы не забывайте про масштаб компаний.
Некачественно сделанную работу придётся переделывать. Это практически всегда дороже, чем сразу сделать как следует. И это не зависит от масштаба компании. И не зависит от веры компании в ошибочные вещи.
Можно, конечно, и не переделывать, свято веря в результат от "правильно настроенных процессов", но тогда это отразится на качестве кода, который создают нанятые сотрудники.
К тому же, масштаб компании слабо коррелирует с глупостью. Тот же Google умудрился отказаться от исключений в C++. Более жёсткий ляп трудно придумать. А сейчас, из-за совместимости, их уже не вернуть назад.
Ну так во многих задачах с литкода алгоритмов не больше, чем в "напишите shared_ptr".
Зачем явную неправду говорить? Здесь же в комментариях люди пишут:
Литкод и их доморощенные задачи с вымученными условиями. Надо напрячься даже не чтобы решить, а чтобы понять чё хотят.
А вы говорите, отличия между этими задачами и задачей "напишите shared_ptr" нет. Вы хотите, чтобы я доказывал очевидное?
Ну придумайте-ка хотя бы 5 вопросов. Чтобы они были не очень большие (и сам вопрос не очень длинный и решение можно за 40 минут написать).
Вы рассуждаете в парадигме алгоритмического собеседования, где нужно написать решение некоторой задачи за 40 минут.
На собеседовании по C++ с этим — явно проще, потому что тем — очень много, при этом много кода писать не требуется, но требуется понимать, как работают различные механизмы.
Также по ходу дела появляется множество возможностей позадавать вопросы, проясняющие, понимает ли кандидат, как работает механизм, может, соответственно, ответить на любой вопрос "а что будет, если", или нет.
Например, берём динамический полиморфизм, как он работает.
Что будет, если вызвать виртуальную функцию, прямо или косвенно из конструктора?
А из конструктора базового класса?
А из конструктора класса где-то в середине цепочки наследования?
Напишите код, демонстрирующий то-то, а потом то-то и то-то из отвеченного на вопрос.
Далее можно спросить, а если код теперь поменять таким-то образом, что произойдёт?
Спрашивать с целью выяснить, понимает человек, как работает механизм или нет.
Можно продолжить, чтобы понять, насколько досконально человек понимает работу механизма: а если вот здесь взять typeid, то какой тип будет? А почему?
Если человек понимает, как работает механизм, он сможет правильно ответить на все подобные вопросы и даже объяснить, почему здесь так, а не этак.
Потом берутся и так же раскрываются темы, например, виртуального наследования, перегрузки операторов и функций, проблемы ambiguity, возникающие при перегрузке, и так далее.
Можно поговорить про лямбды, что это такое, какой у неё тип, какие виды захвата бывают, чем они отличаются, можно ли захватить другую лямбду, а во что можно преобразовать лямбду без захвата, а можно ли менять захваченные по значению параметры, а можно ли сделать так, чтобы было можно, и как это сделать, а напишите код, демонстрирующий то-то и то-то.
Дальше можно уже по коду вопросы задавать, в том числе и такого плана, что если в коде поменять то-то и то-то, то — что будет?
Про исключения, как они ловятся, каковы правила, напишите код, демонстрирующий то-то и то-то, а если здесь поменять вот так, то что будет, а почему это будет так, а можно ли из деструктора выбросить исключение, а почему вот так просто нельзя, а как сделать так, чтобы было можно, а чем это чревато, а какие есть средства в стандартной библиотеке для борьбы с этими проблемами, а можете привести пример, а вот вам такой-то пример, что и как здесь будет происходить, а если исключение выброшено из конструктора, к чему это приведёт, а если оно выброшено из конструктора промежуточного класса сложного типа с наследованием и полями данных в виде объектов, а если оно выброшено где-то в середине процесса создания массива объектов, а что будет, если конструктор помечен noexcept, но функция, которую он вызвал, выбросит исключение...
А что такое structured binding declaration, а при каких условиях оно работает, а напишите пример, а если вот так поменять, то что будет, а почему так, а можете написать range-based loop с использованием structured binding declaration, а кстати, что такое range-based loop, а как из функции вернуть, например, два значения, а не одно, и сразу присвоить его двум переменным, а если переменные уже есть, то тогда как?
А что такое SFINAE, каков принцип его работы, что такое шаблоны, шаблоны чего могут быть, а может ли в шаблоне класса быть шаблон метода, а напишите код в качестве примера, а могут ли шаблонные функции быть виртуальными быть, а что такое инстанцирование, а напишите пример, а что такое специализация, напишите пример, а если вот так поменять, то что будет, а какие виды специализаций бывают (частичная и полная), а напишите пример частичной специализации функции (функции нельзя частично специализировать), тогда пример частичной специализации класса, что такое deduction guide, напишите пример deduction guide, а что такое parameter pack, fold expressions, какие они бывают, а что такое auto, что такое decltype, что такое decltype(auto), а как происходит вывод типов, как происходит разрешение имён, а что такое namespace, а что такое anonymous namespace, а как ими пользоваться, а напишите пример, а где можно и где нельзя объявлять namespace'ы, а что такое user-defined literals, а приведите пример, как они определяются, а какие вы знаете уже определённые в стандартной библиотеке примеры...
А чем отличаются lvalue-reference от rvalue-reference, а каков принцип работы механизма перемещающих конструкторов и assingment operator'ов, в каких случаях он даёт выигрыш, какова суть механизма этого выигрыша, а напишите код демонстрирующий тот и другой случай, а вот если код поменять вот так, то что будет, а почему вместо перемещающего assignment operator'а теперь вызвался копирующий, а каковы требования к типу, чтобы в контейнерах, параметризованных такими типами, вызывались перемещающие, а не копирующие...
И по каждой теме перечисленной выше, — напишите пример, демонстрирующий то и это, а если здесь поменять вот так, то что будет, а почему...
И это я ещё не затрагивал фишек С++20/23, только C++17, почти не затрагивал библиотеку с её контейнерами, алгоритмами и прочими аллокаторами, итераторами, умными указателями и различными другими вещами.
В рамках С++17 не затрагивал многопоточность, синхронизацию, потокобезопасность различных объектов стандартной библиотеки и прочие вопросы, связанные с этим.
Не затрагивал метапрограммирование на шаблонах.
После написания примера по каждой теме задаются вопросы на понимание. Если кандидат понимает, а не вызубрил, это сразу же будет видно. При этом можно ему какие-то несущественные детали даже подсказать, если он их подзабыл, это не повлияет на результат, потому что все равно станет ясно, понимает он или вызубрил.
В процессе написания примеров кода обнаружатся другие ошибки
Неужели это всё нужно было расписывать и объяснять?
В сторону, это как? Ну приведите примеры таких вопросов.
Так на том интервью, ссылку на которое я привёл, такие вопросы были заданы во множестве.
Когда собеседующий спросил, как можно объединить конструктор по умолчанию с конструктором с одним параметром, кандидат не понял, о чём речь, и когда собеседующий после этого прямым текстом сказал про значение по умолчанию для параметра, кандидат опять не понял, как это можно использовать для объединения конструкторов.
Собеседующий несколько раз спросил, почему кандидат не использует списки инициализации в конструкторах, но кандидат опять не понял, о чём речь.
Собеседующий спросил об идиоме swap, но кандидат опять оказался не в курсе, о чём речь.
Вот, в чём заключаются "вопросы чуть в сторону". Вопросы по ходу дела, которые неплохо раскрывают уровень кандидата.
Кроме вопросов ещё есть и просто код, который может не быть явно прокомментирован, но наверняка будет замечен.
В частности, на том собеседовании видно, что для счётчика кандидат объявил отнюдь не указатель, просто собеседующий не стал на этом заостряться.
Какие-то основы да общее представление тоже отлично учится, ибо на этих курсах не просто учат решение одной задачи, а таки натягивают ученика до уровня джуниора. Они даже типы данных помнят, и сколько бит в байте. Вот только написать что-то чуть-чуть не тривиальное без помощи не могут вообще (кроме нескольких заученных вопросов по C++).
Как определять, заучено что-то или есть понимание, я написал выше.
Собеседований нужно несколько. Какие-то надо будет повторить несколько раз. Поскольку собеседования по C++ производить на порядки сложнее (для собеседующих), повторять будут алгоритмические. Вот и пришли практически к существующей ситуации. А дальше, алгоритмические собеседования и так хорошо прореживают входной поток кандидатов, можно и отказаться от дорогого интерьвю по C++.
Собеседования нужны ровно те, которые нужны, а не те, которые "дешевле". Цель — сэкономить или нанять нужного кандидата?
А во время алгоритмического собеседования итак какой-то код на С++ кандидат напишет. Т.ч. если он совсем С++ не знает, это будет видно. А уж если человек способен думать и решать задачки, то выучить синтаксис конструкторов в С++ он точно сможет.
C++ — не тот язык, где достаточно выучить синтаксис конструкторов и прочие подобные вещи. Слабый в C++ кандидат будет писать код, изобилующий UB, код, не являющийся exception-safe и имеющий прочие недопустимые недостатки.
То есть, нанять слабого по части C++ кандидата может обойтись достаточно дорого.
Вот, вы уже согласны, что яндексу нужны алгоритмические собеседования?
А я и не утверждал, что алгоритмические собеседования не нужны. Я говорил о том, что собеседование по C++ должно проводиться отдельно от алгоритмического.
В наиболее простых случаях, где алгоритмическая подготовка почти не требуется, можно как раз наоборот поступить, и в рамках C++ ограничиться вопросами асимптотической сложности поиска в различных контейнерах стандартной библиотеки, сложности вставки и удаления в различные части различных контейнеров с учётом возникающей амортизации, а также с объяснениями, почему у каждого контейнера такие свойства, бинарным поиском и сортировками.
И соединить это с cache-friendly, потому что сами алгоритмы не в вакууме работают, а также с методами достижения cache-friendly поведения контейнеров, которые по умолчанию ведут себя не cache-friendly.
В сухом остатке:
По крайней мере, одно собеседование по C++, которое — в целом по C++, то есть, без алгоритмов, должно проводиться отдельно.
Часть, связанную с асимптотической сложностью поиска/удаления/вставки для контейнеров стандартной библиотеки, понимания, почему так в каждом случае, а также вопросы, связанные с cache-friendly, скорее всего, придётся проверять отдельным собеседованием, которое похоже на переходное от C++ к алгоритмам.
Дальше — столько собеседований по алгоритмам, сколько нужно, чтобы понять, сможет кандидат решать задачи, подразумеваемые вакансией или нет, если алгоритмическая подготовка нужна.
Впихнуть всё, что написано выше в сухом остатке в одно совмещённое собеседование длительностью 1 час — странная затея, ибо результат достаточно случаен.
Хочется, чтобы человек хорошо и продуктивно работал. Вот только единственный способ 100% это проверить - это испытательный строк. Это запредельно дорого. Поэтому берутся какие-то коррелирующие с этим критерии. Такие, что их относительно легко проверить и относительно легко сделать много разных вопросов по ним.
Да, для этого проводят собеседование, в процессе которого необходимо максимально точно выяснить уровень знаний и умений кандидата, чтобы оценить насколько он подходит для занятия конкретной вакансии.
Но это и так понятно.
В перечисленных в статье задачах тогда тоже никаких алгоритмов нет.
Странно, я там прочитал про две задачи, который похожи на задачи на leetcode, на которые даже даны ссылки.
Возможно, вопрос терминологический, но мы же беседуем по теме статьи, а не "вообще".
У shared_ptr побольше уклон в специфику C++, да, ибо тут надо именно класс написать.
И таких собеседований можно провести больше десятка, но так и не покрыть всего, что есть в C++.
Но подобных задач много не придумаешь и если все будут спрашивать про shared_ptr, то вайтишники "с 0 до мидла С++ за 2 месяца" просто выучат его реализацию и сведут до нуля полезность этого вопроса. Ибо его будут отвечать вообще все, а вам все еще надо нанять одного из 10.
Это же элементарно определяется.
Вопрос чуть в сторону, — и собеседующийся неизбежно "поплывёт", показав разительную разницу между уровнем зазубренного материала и уровнем в вопросе чуть в сторону.
Поэтому вопрос не может потерять полезность. Здесь придётся достичь понимания и умения, по-другому не получится. Я подразумеваю, что собеседовать будет разбирающийся в C++ сотрудник.
Произойдет инфляция и спрашивать будут какой-нибудь изврат на вариативных шаблонах.
Где-то, может быть, по глупости, и будут.
Но в этом нет никакой необходимости в силу огромности C++ и возможности поэтому побеседовать на понимание, взяв чуть в сторону, поэтому зубрёжка как метод обречена на провал.
И на хабре все будут плеваться, мол - нафига яндекс эту фигню спрашивает - не надо в реальной жизни писать это. А на интервью в стрессовой ситуации да без любимой IDE это вообще не напишешь.
Вы сами подсказываете ответ: незачем спрашивать "фигню". Следует спрашивать то, что максимально проясняет уровень кандидата.
Ну вот как заранее узнать, нужна она там или нет.
В смысле?
Компания ищет сотрудника на конкретную вакансию и не знает, нужна ли там алгоритмическая подготовка, а если нужна, то насколько серьёзная?
Я обычный C++ SWE, работаю с хромом. Оказывается тут нужна. Те, кто всякие сервера пишут - там тоже все такое этакое на каждом углу. А вот кто условный BigTable пилит - так там вообще алгоритм на алгоритме, алгоритмом погоняет.
Видите, всё зависит от позиции. На какие-то позиции требования — минимальные, на какие-то — максимальные.
Так что это собеседование надо будет вводить для 90+% всех должностей.
Для конкретной компании — возможно. Получается, что для 10% алгоритмическое собеседование не требуется, а для остальных требуется, но его сложность варьируется.
А если еще учесть, что все гибкое: сегодня команда пишет вот этот проект и тут алгоритмов не надо, а через квартал цели поменялись, проект мутировал и вот уже алгоритмы нужны, то стоит вообще всех SWE по алгоритмам гонять.
Тогда, как я уже говорил, нужны два собеседования, одно — по C++, другое — по алгоритмам.
А дальше возвращаемся к предыдущим проблемам вот таких C++ интервью - их массово везде не применишь
Это не так, я выше объяснил.
а раз алгоритмы все равно спрашивать надо, то можно их спросить несколько раз.
Вы выше привели пример, когда в компании, в силу специфики разрабатываемых продуктов, алгоритмы нужны.
Но есть и другие примеры.
Повторюсь ещё раз: C++ сам по себе настолько огромен и сложен, что сам по себе заслуживает не одного собеседования.
А когда его пытаются совместить с алгоритмической секцией, да ещё и вместо 4-5 часов, которые на это потребовались бы, чтобы получить хоть какой-то вменяемый результат, уложить в час, то получается "как всегда".
Если воплощать будут эти же люди - они будут воплощать точно так же, с тем же вектором.
Смотря, какие будут условия. При других условиях те же самые люди могут пересмотреть свой подход, а то и вовсе уйти с поста, на всякий случай.
если за 25 лет скатились, то "воплощение будущего" угробит отрасль окончательно.
То есть, если ничего не делать, это даст результат лучше?
Я не говорю про воровство (это вопрос отдельный. отмечу только, что у свежих назначенцев нет никаких "историй успеха"). Я говорю чисто про расходы. А они являются приоритетом над всеми остальными расходами.
Всё зависит от уровня воровства. При его высоком уровне даже небольшое его уменьшение высвобождает в разы большие средства, чем были доступны до этого.
Ну да. Выпущеное оружие, переданное вооруженным силам, считается основными фондами, поэтому выпуск оружия засчитывается в госстатистике в инвестиции...
Выпуск продукции никак инвестициями быть не может.
Более наивных рассуждений, не читал, воровали даже в 41-43 у нас, и 43-45 у немцев. С точки зрения крупных военных чинов именно для этого всё и происходит у всех свой мир и своё восприятие происходящего. Так везде, но это не важно.
Наверное, всё дело в вашем восприятии.
Я не говорил, что воровство упадёт до нуля. Но если, например, с 90% оно упадёт до 70%, то количество денег, которые будут доходить до дела, утроится.
Но мне почему-то думается, что воровство упадёт сильнее.
Не скажется, потому что самые важные направления перестали или даже не начинали финансировать, потому что один "умный" прошлый руководитель или его заместители, почему то не заметили появление Falcon 9, который обнулил по сути все другие "одноразовые" ракетоносители вообще, кроме сверхтяжа, ну даже сверхтяж отменили енисей.
Так то было в прошлом. Если прошлых руководителей заменить или "хорошо попросить" текущих работать по-другому, то скажется.
Так в этом проблема, что текущая программа, устарела, у китайцев уже готовые прототивы взлетают и от разных разработчиков если не ошибаюсь уже известо о трёх вариантах, уже сейчас.
Вы хотите сказать, что если ничего не делать, то результат будет лучше?
Вот про что я пишу, китайцы уже аналоги в тестовом варианте запускают.
Отсеять "плохих" кандидатов в первую очередь. А во вторую отделить хороших кандидатов от отличных.
А критерий "хорошести" или "плохости" на чём должен основываться? На том, насколько собеседующийся готов по своему уровню выполнять ту работу, которая подразумевается вакантным местом, или его умением решать алгоритмические задачи и эрудицией в данной области?
потому что если у вас 10 человек на одно место, то парочка весьма сильных кандидата все равно должны быть отсеяны.
Это-то — в любом случае при таких условиях, независимо от критерия.
Но здесь важен критерий, то есть, — "на что собеседуем", на умение решать алгоритмические задачи или на владение C++ в той мере, в которой это требуется вакансией?
В этом, кстати, проблема ваших вопросов. Я согласен, это ближе к обычной работе, но языком болтать про какой-то код на порядки проще, чем даже тривиальный код выдавить из себя.
Код следует писать, но его следует писать на C++, и в его основе должны быть отнюдь не алгоритмы. В C++ хватает своей специфики, которую обязательно нужно знать, без всяких алгоритмов.
И вторая проблема - их на порядки сложнее придумывать, а они будут утекать буквально за месяц и надо будет постоянно генерировать новые вопросы. И они по объему меньше чем даже простая алгоритмическая задача, так что вам даже на одно интервью их понадобится в несколько раз больше.
Всё уже придумано до нас.
На этом mock-собеседовании на 52 с половиной минуты сначала идёт короткая беседа об умных указателях ("языком болтать"), затем о std::shared_ptr (всё ещё "языком болтать"), а после этого собеседующийся пишет сильно упрощённую, можно сказать, минимально возможную реализацию std::shared_ptr, без проверки компилятором.
В процессе написания он настолько полно раскрывает уровень своих знаний по C++, что кажется, что трудно это сделать лучше, чем это сделал собеседующий с помощью std::shared_ptr и с помощью правильных вопросов по ходу дела.
Заметьте — никаких алгоритмов.
Вот это — настоящее собеседование по C++. Всего 52 минуты, — а сколько информации получено.
Это, опять же, проблема больших компаний. На их интервью народ будет специально натаскиваться, потому что большая конкуренция.
Так это же замечательно!
Если долго натаскиваться на умение писать реализацию std::shared_ptr, достичь понимания, что там к чему, что в каких случаях происходит, почему в каких-то местах так, а не этак, где какие сложности и опасности, и как их избегать, какие проблемы и каким способом в различных местах решаются, то так можно и C++ на нужный уровень выучить и научиться на нём писать.
Ровно то, что надо.
Проблема же больших компаний, как всегда, в голове.
Я в гугле даю ровно ту задачу, которую лично коммитил в прод. Там можно и динамическим программированием и бинарным поиском по ответу с жадностью делать. И она ничем принципиально не отличается от литкодовских задач.
Не везде нужна хорошая алгоритмическая подготовка. Но если она нужна, проверять её следует отдельным собеседованием. То есть, одно собеседование — по C++, пример выше я привёл. А другое собеседование — по алгоритмической подготовке.
Совместить же одно с другим получается очень плохо: ни то, ни сё.
Так что к яндексу ваш аргумент не очень относится.
То самое mock-собеседование, ссылку на которое я привёл выше, провёл как раз Team Lead из того же Яндекса.
неявный смысл меня просто не интересует, вполне достаточно явного, про последствия облучения знаю достаточно, и не из сети, а по необходимости, т.к. в мае 1986 был там где все случилось, и кое-что видел лично, плюс слегка отслеживал ситуацию позже
Из того, что вы написали, абсолютно неясно, что вы имеете ввиду, а также считаете ли вы, что 3% вероятностью рака всё и исчерпывается при получении предельной дозы.
мне просто нечего добавить, кроме того что вопрос пока открыт, время покажет
Понятно, то есть, на данный момент проблема радиации существует и актуальна, но добавить это к своим мыслям вы по какой-то причине не можете.
Как показывает опыт, проблемы как правило со временем решаются, но сколько на это потребуется времени, оценить часто не получается.
Логично ожидать, что проблема защиты от радиации в будущем будет решена, но насколько долго её будут решать, сказать затруднительно.
Итак, возвращаемся к исходному моему сообщению в этой ветке:
А зачем нам троллейбус из буханки в космосе, когда все уже летят на Марс?)
Кто все? Когда летят?
И что, проблема защиты от радиации в дальнем космосе уже решена?
откуда же мне знать что именно Вы там нашли, за свои комментарии отвечаю
Тогда по поводу 3% и неявного смысла за этим, что это — всё:
и это соответствует примерно 3% вероятности рака по причине облучения
Можете обосновать, что "3% вероятности рака" — это, действительно, все последствия от полученной дозы радиации порядка 1 Зиверта?
И что катаракта, нарушения в имунной системе, в ДНК — это всё не от радиации или что это всё выдумки и такого нет?
фрагмент статьи с близкими оценками из "Science", это известный журнал, уровня примерно как "Nature"
То есть, в сухом остатке — один раз слетать и схватить, примерно, максимальную дозу, если ничего не случится, верно?
Если случится, то легко можно не вернуться, а если и вернуться, то прожить совсем недолго, верно?
На МКС же, чтобы получить такую дозу, необходимо 5 лет там пробыть, и чтобы вернуться, если что, годами ждать не требуется.
Если бы радиацию можно было уменьшить раз в 10, чтобы запас по времени нахождения в условиях этой радиации составлял лет 10, тогда можно было бы говорить о полётах на Марс.
В нынешних же условиях очевидно, что космонавты, отправляющиеся Марс, — почти смертники.
Или вы всё ещё не согласны с этим выводом?
И не согласны, что радиация пока является существенной проблемой и препятствием для полётов на Марс?
влияние солнечного ветра (особенно протонов) + космического излучения на биологию не очень изучены
Простой поиск в Google'е находит такие фрагменты: "Благодаря такому свойству протоны нашли применение в лучевой терапии для локального облучения опухолей.". А вы говорите, что не очень изучены.
по этим оценкам 360 дней туда-сюда на Марс это примерно 660mSv, для сравнения 6 месяцев на ISS это порядка 75mSv, в NASA ограничение принято max 1000mSv типа за всю жизнь
То есть, получается, с учётом выбросов протонов, один раз слетать туда, не сильно долго задерживаться и улететь обратно, получив за всё, практически, максимальную дозу. И хорошо, если по пути ничего не случится, что вынудило бы задержаться и получить ещё бОльшую дозу.
При этом, говоря о 360 днях, запросто могут теоретизировать, то есть, не учитывать, что лучшие траектории полёта, которые дают 360 дней туда-обратно, могут не стыковаться между собой, то есть, после прилёта потребуется подождать какое-то время, прежде чем можно будет кратчайшим путём вернуться обратно.
В сухом остатке — один раз слетать и вернуться, получив максимальную дозу, если никаких накладок не случится. А если не слишком большие накладки случатся, то можно вернуться, чтобы уже вскоре умереть из-за большой полученной дозой. Большие накладки, связанные всего лишь с ожиданием, не позволят вернуться вовсе.
и это соответствует примерно 3% вероятности рака по причине облучения
Там ещё в списке есть катаракта и другие неприятные вещи. Например, первый попавшийся абзац:
"Ранее ученые уже отмечали, что астронавты страдают от потери размера мышц и костной массы, проблем с сердцем и печенью, а также дисфункции иммунной системы. Эксперименты на животных и наблюдения за астронавтами показали, что причина этому — дисфункция митохондрий, энергетических станций клетки. Они тоже страдают от космической радиации, и неправильная их работа приводит к нарушению работы органов во всем организме."
Или ещё, например:
"Одно из новых исследований также выявило клональное кроветворение, при котором клетки крови, несущие мутации, распространяются быстрее, чем другие, что несет риски развития сердечно-сосудистых заболеваний, лимфом и лейкемии. Обычно эта патология наблюдается у людей старше 70 лет, но исследователи зарегистрировали ее у многих космонавтов среднего возраста."
Это — точно не просто "примерно 3% вероятности рака по причине облучения". Скорее, речь может идти о том, что определённые старческие болезни настигают лет на 20 раньше, которые могли бы вообще не настигнуть конкретно этого человека.
Наоброт, меньше денег на космос осталось, меньше доступа к технологиям иностранным и тд.
Здесь важно, что дальше будет с деньгами на космос, а не что сейчас.
Так что уже можно ставить крест на роскосмосе, пока они не выкатят рабочий прототив который как недавно у китайцев летал, хотя бы частично многоразовый как фальком 9, о роскосмосе може не читать ничего вообще и не ждать.
Ваш выбор, не читать и не ждать.
Денег нет, кадров мало, технологии ограничены, государственной цели или коммерческой нету.
Да, стартовые условия — не очень.
За 30 лет ангару запустили наконец в этом году, хотя предыдуших тестовый запуск делали 10 лет назад в 2014......
Однако, как вы сами говорите, некоторые успехи есть.
Федерацию (Орёл) на 29 год перенесли, енисей отменили.
Наверное, это — правильно, сосредоточиться на чём-то наиболее актуальном, чем пытаться сделать сразу всё.
Я думал над этим, когда писал. Но, в связи с отсутствием у меня точной информации в этом смысле относительно новых элит, решил пока обойтись без кавычек.
Нет, это не я натягиваю сову на глобус.
В этой теме есть комментарий:
Я на него уже ссылался.
То есть, не только я так думаю.
Но кандидат же по характеру условия сразу понимает, что задача — алгоритмическая, поэтому необходимо найти эффективное решение, а не "переберём все
iиj", и сразу пытается думать в этом направлении.А иначе, как вы предлагаете, — даже не O(nk), а O(n^2).
Нет, это результат попытки "понять чё хотят".
Результат перевода условия на "человеческий" язык.
Результат представления того, какие действия над массивом необходимо в целом провести.
В это не верится, потому что задача — явно алгоритмическая и даже сформулирована математическим языком.
Только получаются почему-то не просто абстрагированные и немного искусственные, а алгоритмические задачи, которые сначала надо перевести на "человеческий" язык, "чтобы понять чё хотят".
А по реализации функций можно начать задавать дополнительные вопросы и двигаться дальше в стиле "слово за слово", я уже об этом писал.
То-то качество постепенно сползает вниз.
Не защищают.
Тесты не могут покрыть все случаи, а ubsan и им подобные — это тоже, как и тесты, средство уровня runtime, то есть, на проявление UB надо наткнуться, предварительно создав для этого условия, а случай, когда создаются эти условия, может быть также не покрыт.
Тесты, в основном, помогают, когда необходимо проверить, что, в целом, всё работает. В целом, а не в частности.
Тесты, как правило, не могут досконально проверить всё.
Поэтому тесты хороши только против явных просчётов.
Как это не понять?
По частям всё Google'ится, изучается, обретается понимание, о чём речь, даже находится, какая под это дело есть поддержка в языке, и потом реализуется.
К данному решению, которое вы привели, ещё необходимо придти.
В условиях собеседования, когда нет времени, и если кандидат ранее не сталкивался с подобными задачами, это — невозможно.
При этом ещё надо не ошибиться, что в конце необходимо дойти до самого конца массива, "сжимая"при этом окно.
Здесь требуется именно алгоритмический подход.
Естественно.
Задача бьётся на подзадачи.
На первом шаге имеется окно в k элементов, и требуется узнать, нет ли там дубликатов.
Эта подзадача выделяется в отдельный метод и решается за O(k^2), и этот метод вызывается n - k раз, отсюда O(nk^2).
Нет, так получается, если не мыслить алгоритмически.
Если разбивать задачи на подзадачи и так решать всю задачу.
Смысла тогда нет давать алгоритмическую задачу и не требовать её правильного решения.
Для fizz-buzz не требуется алгоритмического мышления.
На одном из публичных mock-интервью предлагали написать свою реализацию
std::strlen, там как раз есть цикл.Можно взять из того же семейства функций что-нибудь слегка посложнее.
Какая-то общая логика даже там есть, например, изнутри — наружу.
Но механизм вызова виртуальных функций же — логичен?
Чувствуется там смысл, особенно, если подумать?
Да, я несколько раз написал, что если они нужны, то — нужны.
Но каждый раз замечал при этом, что они — не средство для проверки знаний и умений ещё и по C++.
Нет, я считаю, что собеседование по C++ должно быть по C++, а не по алгоритмам.
Если если ещё нужны и алгоритмы, то это должно быть отдельное собеседование или собеседования.
Видимо, они не считают, что дороже будет потом, если нанять кандидата, которого потом придётся учить, если он ещё будет учиться, и постоянно иметь риск, не налепил ли он множество неочевидных UB в коде.
UB — недопустимо, потому что компилятор имеет право в этом случае генерировать неправильный код, и современные компиляторы этим усиленно пользуются.
Жить-то, может быть, и можно, но — дорого.
Причём собеседование — один раз, а потом сотрудник будет писать проблемный код постоянно, а не один раз.
Это — не вся правда.
Так и с механизмом виртуальных функций есть проблема: обычно, если кандидат не в курсе, ему и в голову не приходит, что здесь могут быть какие-то особенности.
Он считает, что этот механизм сразу работает до уровня самого последнего класса.
Поэтому он даже не пытается ни в какую справку смотреть и что-то там искать по этому поводу.
Вот теперь — вся правда.
Нет, не исключают.
Просто будет вызываться не та функция, да и всё.
И это можно пропустить и не заметить.
Или, если UB привело к генерации неправильного кода, то код будет работать неправильно, вот и всё.
И хорошо, если эта неправильность будет сразу видна и обнаружится тестом, но она может проявляться в специфических случаях, не предусмотренных тестами, и поэтому будет пропущена.
На собеседовании — точно не показывает.
Некогда на собеседовании думать.
На собеседовании используется предыдущий алгоритмический опыт, который зафиксирован в интуиции, именно она и работает.
Интеллект же применяется в минимальной степени.
То есть, натаскается по ходу дела на интенсивно используемые в проекте части C++?
То же самое тогда можно и про алгоритмическую часть сказать.
В целом, алгоритмическое собеседование по C++ очень плохо проверяет знания и умения, собственно, по самому C++.
Аргумент, что проводить собеседование по C++ — дорого, считаю ошибочным, потому что потом будет выходить дороже.
Но если алгоритмы нужны, то — да, отдельное собеседование или отдельные собеседования по алгоритмам нужны, но без совмещения с C++, то есть, без цели этими собеседованиями проверить ещё и знания и умения по C++, потому что для этого необходимо проводить специально для этого предназначенное собеседование по C++.
Упростил, принял k равным n.
С поправкой на k получается O(nk^2).
C
std::unordered_setполучается O(n).Алгоритм такой.
Сначала во множество (
std::unordered_set) добавляются элементы, пока их не станет k штук (первый цикл).Если в процессе добавления обнаруживается, что такой уже есть во множестве, возвращается
true.Затем первый элемент в окне из k элементов удаляется из множества, а следующий за окном добавляется во множество, а окно, таким образом, движется по вектору к его концу, пока окном из k элементов не будет пройден весь вектор (второй цикл).
Если в процессе этого движения обнаруживается, что добавляемый элемент уже есть во множестве, то также возвращается
true.Если до конца массива такого не случилось, возвращается
false.Поскольку операции с
std::unordered_setвыполняются за O(1), а количество операций равно n, то получается O(n).Я полагаю, что примерно такое решение должно быть найдено.
И для нахождения этого решения должна быть хоть какая-то алгоритмическая подготовка и хоть какой-то опыт решения подобных задач.
В данном случае эта подготовка и опыт заключаются в применении hash-table-based множества с хранением там копий элементов, попадающих в окно, что как раз и обеспечивает детектирование этим множеством повторений значений элементов в момент добавления очередного элемента, и hash-table-based множество обеспечивает это детектирование за O(1).
Понимание этого свойства позволяет применить для одного шага выкидывание из множества одного элемента в начале окна и добавление во множество следующего за окном элемента, а не заполнение множества каждый раз k элементами на каждом шаге, что, действительно, давало бы O(nk).
Однако, эта и другие задачи никак не связаны с C++, их можно решать на совсем другом языке, и они нужны, только если для вакансии на самом деле требуется алгоритмическая подготовка.
Вы смеётесь, что ли?
Какие ещё эмоции?
Проверяется, понимает ли кандидат, как работают конкретные механизмы C++, потому что ему по работе потребуется это понимание, чтобы решать поставленные задачи.
В противном случае, он не сможет их решать.
Эмоциональные в этом смысле кандидаты однозначно не подходят.
А то бывают уникумы с большим опытом, которые на собеседовании на предложение написать простой макрос заявляют, что макросы не пишут, а пользуются вместо этого уже написанными.
Но такие кандидаты никуда не годятся.
Для механизма вызова виртуальных функций это не так.
Когда, например, создаётся объект класса C, который унаследован от класса B, а B унаследован от полиморфного класса A, то сначала вызывается конструктор A.
Объект в смысле динамического полиморфизма в этот момент представляет из себя класс A, как если бы конструировался объект не класса C, а класса A.
Технически, обычно это реализуется с помощью таблиц виртуальных функций, указатель на которую прописывается первым, программно недоступным полем данных в классе, расположенным прямо перед пользовательскими полями данных.
Первое, что делает код конструктора A ещё до выполнения пользовательского кода, получив управление, это прописывает в то самое поле указатель на таблицу виртуальных функций класса A.
Именно поэтому механизм виртуального вызова, начиная с этого момента и до получения управления конструктором класса B, будет работать, как будто конструируется объект класса A, а не C.
Когда после отработки конструктора класса A управление получит конструктор класса B, он точно также, как и конструктор класса A, первым делом пропишет в то самое поле указатель на таблицу виртуальных функция класса B.
Именно поэтому механизм виртуального вызова, с этого момента и до получения управления конструктором класса C, будет работать, как будто конструируется объект класса B, а не C.
Точно так же поступает конструктор класса C.
Тем, на таблицу виртуальных функций какого класса указывает указатель в том поле, фактически, и определяется динамический тип объекта.
Условно можно считать, что таблица виртуальных функций, указатель на которую прописан в том самом поле, однозначно определяет динамический тип объекта.
К моменту исполнения кода, соответствующего спискам инициализации конструкторов, в то самое поле уже прописан правильный указатель на таблицу виртуальных функций, то есть, объект стал того динамического типа, который соответствует исполняющемуся конструктору.
Таким образом, в процессе конструирования полиморфного объекта его динамический тип меняется в соответствии с тем, какой конструктор начал исполняться.
Когда исполняются деструкторы (в обратном порядке), соответствующий код, добавленный компилятором к деструкторам, обеспечивает точно такое же изменение динамического типа полиморфного объекта при исполнении соответствующего деструктора, но уже в обратную сторону.
Если кандидат понимает описанный выше механизм, то он для класса любой сложности, хоть со множественным и виртуальным наследованием, сможет точно сказать, какой метод вызовется на любом этапе конструирования этого сложного объекта.
И если он, всего лишь, что-то там зазубрил, но не понимает этого механизма, то он не сможет дать правильный ответ.
Я только что достаточно полно описал работу механизма динамического полиморфизма в C++, но не сослался ни на одну спецификацию.
Где здесь цитаты из спецификации?
Если его знать достаточно глубоко и понимать, как работают его механизмы, то он становится куда более логичным, чем кажется на первый взгляд.
Неправда.
Если в 219. Contains Duplicate II делать "в лоб", то получается сложность O(n^3), а не O(n), потому что проверка дубликатов "в лоб" делается двумя вложенными циклами, которые дадут O(n^2).
То, что применение
std::unordered_setдля детектирования дубликатов в скользящем окне вы не считаете алгоритмом — это ваша личная особенность.Но проигнорировали дальнейшее мной написанное.
Дополнительные вопросы "а почему", "а что здесь выдаст typeid", "за счёт чего так получается" вскроют либо наличие понимания, какой механизм лежит в основе, либо отсутствие такого понимания.
При наличии понимания кандидат будет правильно отвечать на любой из последовательности вопросов по конкретному случаю, потому что просто будет применять это понимание, механизм в голове воспроизводить и получать правильные результаты.
Если же понимания нет, и он будет пытаться интуитивно угадать, то неизбежно будет ошибаться, а также не сможет объяснить, почему он так ответил, либо объяснения будут очень странными с точки зрения понимающего эту часть человека.
Таким образом и будет выясняться, понимает кандидат, какой механизм лежит в основе, и как он работает, или нет.
Это уже — не опросник, зазубрить не получится, требуется понимать.
Не знаю, как сейчас, но больше десятка лет назад rvalue-reference'ы объяснялись отвратительно, я удивительно долго не понимал до конца, что там к чему.
По дополнительным вопросам выясняется, полностью кандидат понимает, что там к чему, или нет.
Из-за дополнительных вопросов, с помощью которых выясняется, есть ли понимание, это уже — не опросник, точно так же, как и в предыдущем случае.
Если кандидат на вопросы по поводу lvalue и rvalue reference'ов так отвечает, то он сразу не проходит дальше никуда.
Это не справочная информация, которую можно забыть, она лежит в основе механизма, реализующего копирование/перемещение.
Соответственно, кандидат не будет знать, где происходит копирование, а где — перемещение.
Примерно так, как если бы математик не помнил, как складывать.
Или не помнил, как складывать столбиком без заглядывания в документацию.
Некачественно сделанную работу придётся переделывать.
Это практически всегда дороже, чем сразу сделать как следует.
И это не зависит от масштаба компании.
И не зависит от веры компании в ошибочные вещи.
Можно, конечно, и не переделывать, свято веря в результат от "правильно настроенных процессов", но тогда это отразится на качестве кода, который создают нанятые сотрудники.
К тому же, масштаб компании слабо коррелирует с глупостью.
Тот же Google умудрился отказаться от исключений в C++.
Более жёсткий ляп трудно придумать.
А сейчас, из-за совместимости, их уже не вернуть назад.
И тут же:
Нет уж, теперь ждите фактов.
Не удивлюсь, если и с фактами начнёте спорить.
Я уже писал о том, что "поживём — увидим", тут нечего предсказывать.
А осталось подождать, потому что никто не желает здесь даже рассматривать возможность альтернативных вариантов, упорно веря в своё видение.
Или я предсказуем в том, что не собираюсь веру менять у людей? Действительно, не собираюсь.
Поэтому следующие аргументы у меня могут быть только в виде фактов, но здесь придётся подождать, пока факты не свершатся, те или иные.
Думаю, доходчиво.
Это дело поправимое.
"Съесть-то он — съест, но кто ж ему даст" (c)?
Да, но до осени и зимы недолго осталось.
Иногда?
Осталось подождать и посмотреть, что будет происходить, и как оно сложится на самом деле.
Зачем явную неправду говорить?
Здесь же в комментариях люди пишут:
А вы говорите, отличия между этими задачами и задачей "напишите shared_ptr" нет. Вы хотите, чтобы я доказывал очевидное?
Вы рассуждаете в парадигме алгоритмического собеседования, где нужно написать решение некоторой задачи за 40 минут.
На собеседовании по C++ с этим — явно проще, потому что тем — очень много, при этом много кода писать не требуется, но требуется понимать, как работают различные механизмы.
Также по ходу дела появляется множество возможностей позадавать вопросы, проясняющие, понимает ли кандидат, как работает механизм, может, соответственно, ответить на любой вопрос "а что будет, если", или нет.
Например, берём динамический полиморфизм, как он работает.
Что будет, если вызвать виртуальную функцию, прямо или косвенно из конструктора?
А из конструктора базового класса?
А из конструктора класса где-то в середине цепочки наследования?
Напишите код, демонстрирующий то-то, а потом то-то и то-то из отвеченного на вопрос.
Далее можно спросить, а если код теперь поменять таким-то образом, что произойдёт?
Спрашивать с целью выяснить, понимает человек, как работает механизм или нет.
Можно продолжить, чтобы понять, насколько досконально человек понимает работу механизма: а если вот здесь взять
typeid, то какой тип будет? А почему?Если человек понимает, как работает механизм, он сможет правильно ответить на все подобные вопросы и даже объяснить, почему здесь так, а не этак.
Потом берутся и так же раскрываются темы, например, виртуального наследования, перегрузки операторов и функций, проблемы ambiguity, возникающие при перегрузке, и так далее.
Можно поговорить про лямбды, что это такое, какой у неё тип, какие виды захвата бывают, чем они отличаются, можно ли захватить другую лямбду, а во что можно преобразовать лямбду без захвата, а можно ли менять захваченные по значению параметры, а можно ли сделать так, чтобы было можно, и как это сделать, а напишите код, демонстрирующий то-то и то-то.
Дальше можно уже по коду вопросы задавать, в том числе и такого плана, что если в коде поменять то-то и то-то, то — что будет?
Про исключения, как они ловятся, каковы правила, напишите код, демонстрирующий то-то и то-то, а если здесь поменять вот так, то что будет, а почему это будет так, а можно ли из деструктора выбросить исключение, а почему вот так просто нельзя, а как сделать так, чтобы было можно, а чем это чревато, а какие есть средства в стандартной библиотеке для борьбы с этими проблемами, а можете привести пример, а вот вам такой-то пример, что и как здесь будет происходить, а если исключение выброшено из конструктора, к чему это приведёт, а если оно выброшено из конструктора промежуточного класса сложного типа с наследованием и полями данных в виде объектов, а если оно выброшено где-то в середине процесса создания массива объектов, а что будет, если конструктор помечен
noexcept, но функция, которую он вызвал, выбросит исключение...А что такое structured binding declaration, а при каких условиях оно работает, а напишите пример, а если вот так поменять, то что будет, а почему так, а можете написать range-based loop с использованием structured binding declaration, а кстати, что такое range-based loop, а как из функции вернуть, например, два значения, а не одно, и сразу присвоить его двум переменным, а если переменные уже есть, то тогда как?
А что такое SFINAE, каков принцип его работы, что такое шаблоны, шаблоны чего могут быть, а может ли в шаблоне класса быть шаблон метода, а напишите код в качестве примера, а могут ли шаблонные функции быть виртуальными быть, а что такое инстанцирование, а напишите пример, а что такое специализация, напишите пример, а если вот так поменять, то что будет, а какие виды специализаций бывают (частичная и полная), а напишите пример частичной специализации функции (функции нельзя частично специализировать), тогда пример частичной специализации класса, что такое deduction guide, напишите пример deduction guide, а что такое parameter pack, fold expressions, какие они бывают, а что такое auto, что такое decltype, что такое decltype(auto), а как происходит вывод типов, как происходит разрешение имён, а что такое namespace, а что такое anonymous namespace, а как ими пользоваться, а напишите пример, а где можно и где нельзя объявлять namespace'ы, а что такое user-defined literals, а приведите пример, как они определяются, а какие вы знаете уже определённые в стандартной библиотеке примеры...
А чем отличаются lvalue-reference от rvalue-reference, а каков принцип работы механизма перемещающих конструкторов и assingment operator'ов, в каких случаях он даёт выигрыш, какова суть механизма этого выигрыша, а напишите код демонстрирующий тот и другой случай, а вот если код поменять вот так, то что будет, а почему вместо перемещающего assignment operator'а теперь вызвался копирующий, а каковы требования к типу, чтобы в контейнерах, параметризованных такими типами, вызывались перемещающие, а не копирующие...
И по каждой теме перечисленной выше, — напишите пример, демонстрирующий то и это, а если здесь поменять вот так, то что будет, а почему...
И это я ещё не затрагивал фишек С++20/23, только C++17, почти не затрагивал библиотеку с её контейнерами, алгоритмами и прочими аллокаторами, итераторами, умными указателями и различными другими вещами.
В рамках С++17 не затрагивал многопоточность, синхронизацию, потокобезопасность различных объектов стандартной библиотеки и прочие вопросы, связанные с этим.
Не затрагивал метапрограммирование на шаблонах.
После написания примера по каждой теме задаются вопросы на понимание. Если кандидат понимает, а не вызубрил, это сразу же будет видно. При этом можно ему какие-то несущественные детали даже подсказать, если он их подзабыл, это не повлияет на результат, потому что все равно станет ясно, понимает он или вызубрил.
В процессе написания примеров кода обнаружатся другие ошибки
Неужели это всё нужно было расписывать и объяснять?
Так на том интервью, ссылку на которое я привёл, такие вопросы были заданы во множестве.
Когда собеседующий спросил, как можно объединить конструктор по умолчанию с конструктором с одним параметром, кандидат не понял, о чём речь, и когда собеседующий после этого прямым текстом сказал про значение по умолчанию для параметра, кандидат опять не понял, как это можно использовать для объединения конструкторов.
Собеседующий несколько раз спросил, почему кандидат не использует списки инициализации в конструкторах, но кандидат опять не понял, о чём речь.
Собеседующий спросил об идиоме swap, но кандидат опять оказался не в курсе, о чём речь.
Вот, в чём заключаются "вопросы чуть в сторону".
Вопросы по ходу дела, которые неплохо раскрывают уровень кандидата.
Кроме вопросов ещё есть и просто код, который может не быть явно прокомментирован, но наверняка будет замечен.
В частности, на том собеседовании видно, что для счётчика кандидат объявил отнюдь не указатель, просто собеседующий не стал на этом заостряться.
Как определять, заучено что-то или есть понимание, я написал выше.
Собеседования нужны ровно те, которые нужны, а не те, которые "дешевле". Цель — сэкономить или нанять нужного кандидата?
C++ — не тот язык, где достаточно выучить синтаксис конструкторов и прочие подобные вещи. Слабый в C++ кандидат будет писать код, изобилующий UB, код, не являющийся exception-safe и имеющий прочие недопустимые недостатки.
То есть, нанять слабого по части C++ кандидата может обойтись достаточно дорого.
А я и не утверждал, что алгоритмические собеседования не нужны.
Я говорил о том, что собеседование по C++ должно проводиться отдельно от алгоритмического.
В наиболее простых случаях, где алгоритмическая подготовка почти не требуется, можно как раз наоборот поступить, и в рамках C++ ограничиться вопросами асимптотической сложности поиска в различных контейнерах стандартной библиотеки, сложности вставки и удаления в различные части различных контейнеров с учётом возникающей амортизации, а также с объяснениями, почему у каждого контейнера такие свойства, бинарным поиском и сортировками.
И соединить это с cache-friendly, потому что сами алгоритмы не в вакууме работают, а также с методами достижения cache-friendly поведения контейнеров, которые по умолчанию ведут себя не cache-friendly.
В сухом остатке:
По крайней мере, одно собеседование по C++, которое — в целом по C++, то есть, без алгоритмов, должно проводиться отдельно.
Часть, связанную с асимптотической сложностью поиска/удаления/вставки для контейнеров стандартной библиотеки, понимания, почему так в каждом случае, а также вопросы, связанные с cache-friendly, скорее всего, придётся проверять отдельным собеседованием, которое похоже на переходное от C++ к алгоритмам.
Дальше — столько собеседований по алгоритмам, сколько нужно, чтобы понять, сможет кандидат решать задачи, подразумеваемые вакансией или нет, если алгоритмическая подготовка нужна.
Впихнуть всё, что написано выше в сухом остатке в одно совмещённое собеседование длительностью 1 час — странная затея, ибо результат достаточно случаен.
Неверная же аллегория, противоположная.
Если вам важнее ваши верования, нежели реальность, так и скажите.
Да, для этого проводят собеседование, в процессе которого необходимо максимально точно выяснить уровень знаний и умений кандидата, чтобы оценить насколько он подходит для занятия конкретной вакансии.
Но это и так понятно.
Странно, я там прочитал про две задачи, который похожи на задачи на leetcode, на которые даже даны ссылки.
Возможно, вопрос терминологический, но мы же беседуем по теме статьи, а не "вообще".
И таких собеседований можно провести больше десятка, но так и не покрыть всего, что есть в C++.
Это же элементарно определяется.
Вопрос чуть в сторону, — и собеседующийся неизбежно "поплывёт", показав разительную разницу между уровнем зазубренного материала и уровнем в вопросе чуть в сторону.
Поэтому вопрос не может потерять полезность.
Здесь придётся достичь понимания и умения, по-другому не получится.
Я подразумеваю, что собеседовать будет разбирающийся в C++ сотрудник.
Где-то, может быть, по глупости, и будут.
Но в этом нет никакой необходимости в силу огромности C++ и возможности поэтому побеседовать на понимание, взяв чуть в сторону, поэтому зубрёжка как метод обречена на провал.
Вы сами подсказываете ответ: незачем спрашивать "фигню".
Следует спрашивать то, что максимально проясняет уровень кандидата.
В смысле?
Компания ищет сотрудника на конкретную вакансию и не знает, нужна ли там алгоритмическая подготовка, а если нужна, то насколько серьёзная?
Видите, всё зависит от позиции.
На какие-то позиции требования — минимальные, на какие-то — максимальные.
Для конкретной компании — возможно.
Получается, что для 10% алгоритмическое собеседование не требуется, а для остальных требуется, но его сложность варьируется.
Тогда, как я уже говорил, нужны два собеседования, одно — по C++, другое — по алгоритмам.
Это не так, я выше объяснил.
Вы выше привели пример, когда в компании, в силу специфики разрабатываемых продуктов, алгоритмы нужны.
Но есть и другие примеры.
Повторюсь ещё раз: C++ сам по себе настолько огромен и сложен, что сам по себе заслуживает не одного собеседования.
А когда его пытаются совместить с алгоритмической секцией, да ещё и вместо 4-5 часов, которые на это потребовались бы, чтобы получить хоть какой-то вменяемый результат, уложить в час, то получается "как всегда".
Смотря, какие будут условия.
При других условиях те же самые люди могут пересмотреть свой подход, а то и вовсе уйти с поста, на всякий случай.
То есть, если ничего не делать, это даст результат лучше?
Всё зависит от уровня воровства.
При его высоком уровне даже небольшое его уменьшение высвобождает в разы большие средства, чем были доступны до этого.
Выпуск продукции никак инвестициями быть не может.
Наверное, всё дело в вашем восприятии.
Я не говорил, что воровство упадёт до нуля.
Но если, например, с 90% оно упадёт до 70%, то количество денег, которые будут доходить до дела, утроится.
Но мне почему-то думается, что воровство упадёт сильнее.
Так то было в прошлом.
Если прошлых руководителей заменить или "хорошо попросить" текущих работать по-другому, то скажется.
Вы хотите сказать, что если ничего не делать, то результат будет лучше?
Если не догонять, то и не догнать.
А критерий "хорошести" или "плохости" на чём должен основываться?
На том, насколько собеседующийся готов по своему уровню выполнять ту работу, которая подразумевается вакантным местом, или его умением решать алгоритмические задачи и эрудицией в данной области?
Это-то — в любом случае при таких условиях, независимо от критерия.
Но здесь важен критерий, то есть, — "на что собеседуем", на умение решать алгоритмические задачи или на владение C++ в той мере, в которой это требуется вакансией?
Код следует писать, но его следует писать на C++, и в его основе должны быть отнюдь не алгоритмы. В C++ хватает своей специфики, которую обязательно нужно знать, без всяких алгоритмов.
Всё уже придумано до нас.
На этом mock-собеседовании на 52 с половиной минуты сначала идёт короткая беседа об умных указателях ("языком болтать"), затем о
std::shared_ptr(всё ещё "языком болтать"), а после этого собеседующийся пишет сильно упрощённую, можно сказать, минимально возможную реализациюstd::shared_ptr, без проверки компилятором.В процессе написания он настолько полно раскрывает уровень своих знаний по C++, что кажется, что трудно это сделать лучше, чем это сделал собеседующий с помощью
std::shared_ptrи с помощью правильных вопросов по ходу дела.Заметьте — никаких алгоритмов.
Вот это — настоящее собеседование по C++.
Всего 52 минуты, — а сколько информации получено.
Так это же замечательно!
Если долго натаскиваться на умение писать реализацию
std::shared_ptr, достичь понимания, что там к чему, что в каких случаях происходит, почему в каких-то местах так, а не этак, где какие сложности и опасности, и как их избегать, какие проблемы и каким способом в различных местах решаются, то так можно и C++ на нужный уровень выучить и научиться на нём писать.Ровно то, что надо.
Проблема же больших компаний, как всегда, в голове.
Не везде нужна хорошая алгоритмическая подготовка.
Но если она нужна, проверять её следует отдельным собеседованием.
То есть, одно собеседование — по C++, пример выше я привёл.
А другое собеседование — по алгоритмической подготовке.
Совместить же одно с другим получается очень плохо: ни то, ни сё.
То самое mock-собеседование, ссылку на которое я привёл выше, провёл как раз Team Lead из того же Яндекса.
Поэтому думаю, что это — аргумент.
Из того, что вы написали, абсолютно неясно, что вы имеете ввиду, а также считаете ли вы, что 3% вероятностью рака всё и исчерпывается при получении предельной дозы.
Понятно, то есть, на данный момент проблема радиации существует и актуальна, но добавить это к своим мыслям вы по какой-то причине не можете.
Как показывает опыт, проблемы как правило со временем решаются, но сколько на это потребуется времени, оценить часто не получается.
Логично ожидать, что проблема защиты от радиации в будущем будет решена, но насколько долго её будут решать, сказать затруднительно.
Итак, возвращаемся к исходному моему сообщению в этой ветке:
Кто все?
Когда летят?
И что, проблема защиты от радиации в дальнем космосе уже решена?
В контексте обсуждаемого вопроса это — именно стартовые условия.
Задуманное воплощаться будет в будущем, а не прошлом.
Вот видите, и вы считаете, что в будущем воплощаться будет.
Да, теперь не дадут воровать деньги на военные расходы.
Для этого произведены существенные кадровые назначения.
Нет, инвестиции как раз наращивают, тем способом, который пока доступен.
Когда же инвестиции станут доступны в целом, начнётся резкий рост.
Очевидно, что это очень положительно скажется и на космических программах.
То есть, на данный момент, предпосылки таковы, что перспективы реализации данной космической программы весьма неплохи.
А как оно сложится в реальности, увидим в будущем.
Тогда по поводу 3% и неявного смысла за этим, что это — всё:
Можете обосновать, что "3% вероятности рака" — это, действительно, все последствия от полученной дозы радиации порядка 1 Зиверта?
И что катаракта, нарушения в имунной системе, в ДНК — это всё не от радиации или что это всё выдумки и такого нет?
То есть, в сухом остатке — один раз слетать и схватить, примерно, максимальную дозу, если ничего не случится, верно?
Если случится, то легко можно не вернуться, а если и вернуться, то прожить совсем недолго, верно?
На МКС же, чтобы получить такую дозу, необходимо 5 лет там пробыть, и чтобы вернуться, если что, годами ждать не требуется.
Если бы радиацию можно было уменьшить раз в 10, чтобы запас по времени нахождения в условиях этой радиации составлял лет 10, тогда можно было бы говорить о полётах на Марс.
В нынешних же условиях очевидно, что космонавты, отправляющиеся Марс, — почти смертники.
Или вы всё ещё не согласны с этим выводом?
И не согласны, что радиация пока является существенной проблемой и препятствием для полётов на Марс?
Простой поиск в Google'е находит такие фрагменты: "Благодаря такому свойству протоны нашли применение в лучевой терапии для локального облучения опухолей.". А вы говорите, что не очень изучены.
То есть, получается, с учётом выбросов протонов, один раз слетать туда, не сильно долго задерживаться и улететь обратно, получив за всё, практически, максимальную дозу. И хорошо, если по пути ничего не случится, что вынудило бы задержаться и получить ещё бОльшую дозу.
При этом, говоря о 360 днях, запросто могут теоретизировать, то есть, не учитывать, что лучшие траектории полёта, которые дают 360 дней туда-обратно, могут не стыковаться между собой, то есть, после прилёта потребуется подождать какое-то время, прежде чем можно будет кратчайшим путём вернуться обратно.
В сухом остатке — один раз слетать и вернуться, получив максимальную дозу, если никаких накладок не случится. А если не слишком большие накладки случатся, то можно вернуться, чтобы уже вскоре умереть из-за большой полученной дозой. Большие накладки, связанные всего лишь с ожиданием, не позволят вернуться вовсе.
Там ещё в списке есть катаракта и другие неприятные вещи.
Например, первый попавшийся абзац:
"Ранее ученые уже отмечали, что астронавты страдают от потери размера мышц и костной массы, проблем с сердцем и печенью, а также дисфункции иммунной системы. Эксперименты на животных и наблюдения за астронавтами показали, что причина этому — дисфункция митохондрий, энергетических станций клетки. Они тоже страдают от космической радиации, и неправильная их работа приводит к нарушению работы органов во всем организме."
Или ещё, например:
"Одно из новых исследований также выявило клональное кроветворение, при котором клетки крови, несущие мутации, распространяются быстрее, чем другие, что несет риски развития сердечно-сосудистых заболеваний, лимфом и лейкемии. Обычно эта патология наблюдается у людей старше 70 лет, но исследователи зарегистрировали ее у многих космонавтов среднего возраста."
Это — точно не просто "примерно 3% вероятности рака по причине облучения". Скорее, речь может идти о том, что определённые старческие болезни настигают лет на 20 раньше, которые могли бы вообще не настигнуть конкретно этого человека.
А сами вы себе правильные вопросы не можете задать?
А сколько всего можно там пробыть, чтобы "схватить" максимально допустимую за всю жизнь дозу, после чего уже никуда летать нельзя?
И во что эта доза обойдётся по здоровью годам к 50?
Какую часть от максимально допустимой дозы схватит космонавт, слетавший на Марс, побывший там месяц-другой и вернувшийся назад?
Надо ещё иметь ввиду, что во время полёта туда и обратно от Солнца могут быть неоднократные выбросы протонов, что может неожиданно увеличить дозу.
Здесь важно, что дальше будет с деньгами на космос, а не что сейчас.
Ваш выбор, не читать и не ждать.
Да, стартовые условия — не очень.
Однако, как вы сами говорите, некоторые успехи есть.
Наверное, это — правильно, сосредоточиться на чём-то наиболее актуальном, чем пытаться сделать сразу всё.
Я думал над этим, когда писал.
Но, в связи с отсутствием у меня точной информации в этом смысле относительно новых элит, решил пока обойтись без кавычек.