Собеседование на программиста в Amazon

Давайте и дальше тратить время на изучение сортировки массивов.

Сортировка — один из первых вопросов, рассматривающихся в любом базовом курсе по алгоритмам. Во-первых, потому что она, как подзадача, входит во многие более сложные алгоритмы. Во-вторых, потому что это удобная для начала тема: постановка задачи близка каждому человеку, есть большое количество принципиально различных и при этом не слишком сложных и объемных для восприятия (но при этом эффективных) алгоритмов решения. В-третьих, в какой-то степени это, наверно, уже традиция.

Поэтому, если на вопросах об алгоритмах сортировках человек «плавает», то можно уверенно сказать, что в данной области (алгоритмические знания) никаких обширных и систематизированных знаний у него нет. Конечно, есть множество вакансий для которых они и не нужны, но это уже другой вопрос…

Перевод С++ проекта на разработку с юнит-тестированием/TDD

Если интерфейсные классы не содержат данных

Они содержат указатели на таблицу виртуальных функций, пусть эта деталь реализации от нас компилятором и скрывается

Relinx — ещё одна реализация .NET LINQ методов на C++, с поддержкой «ленивых вычислений»

Да, я бы на вашем месте хорошенько продумал и в явном виде прописал, кто чем владеет и как и кому это владение в процессе переходит. Мы же на языке без сборки мусора программируем, тут это важно. Ещё бы подумал над тем, что одни функции-члены класса у вас возвращают новый экземпляр relinx_object, а другие — меняют сам исходной объект (например, skip, мб какие-то ещё). Я понимаю, что в случае skip это вызвано идеей оптимизации, но выглядит такой интерфейс контринтуитивно.

Relinx — ещё одна реализация .NET LINQ методов на C++, с поддержкой «ленивых вычислений»

В репозитории на github у вас по-прежнему:

relinx_object(relinx_object &&) = default;

Если вы, возможно, не поняли в чем её проблема, то попробую объяснить ещё раз: не для всех контейнеров move-конструктор реализован, как простой swap указателей на данные. Соответственно, итераторы (которые у вас просто копируются при таком задании конструктора), указывающие на данные старого контейнере, могут не быть корректными итераторами для перемещенного контейнера. Самый простой пример: массивы статической длины, если у вас Container будет типа std::array<int>, то перемещение этого массива — это просто побитовое копирование данных из старого объекта в новый, а, соответственно, _begin и _end нового объекта будут указывать внутрь старого массива. Если старый объект после этого уничтожается (например, он был временным объектом), то имеем use-after-free. Я бы накидал вам код для наглядности, но не смог быстро разобраться, что за новый параметр StoreType вы добавили в последней редакции, надеюсь и так понятно.

Причем из-за выбранного вами дизайна, когда у вас один и тот же объект может быть как простой невладеющей парой итераторов, так и владеть собственным контейнером, кроме того для второго случая не всегда _begin указывает на начало владеемого контейнера (т.к. он может быть сдвинут с помощью skip, может и каких-то других функций), я не представляю как это можно легко исправить, не теряя при этом в эффективности (потому что понятно, что данные, лежащие по _begin и _end, всегда можно просто тупо скопировать).

Что ещё бросилось в глаза при беглом изучении

template<typename Container>
auto from(Container &&c) -> decltype(auto)
{
    return relinx_object<typename std::decay<decltype(std::begin(c))>::type>(
        std::begin(c), std::end(c));
}

Даже для prvalue аргумента (когда параметр выводится как rvalue ссылка Container&&) все равно используется невладеющий вип конструктора (по паре итераторов), соответственно, какой-нибудь такой код не сработает:

vector<int> func();
auto r = from(func());
// ниже этой строчки r использовать нельзя,
// т.к. вектор, который вернула func(), уже уничтожен

Более того, версия from, принимающая std::initializer_list, благодаря какой-то неочевидной шаблонной магии, вызывает вышеупомянутую версию функции, поэтому даже такой код не будет работать:

auto r = from({1, 2, 3});
// дальше этой строчки r использовать нельзя

В общем, пока у вас все экземпляры relinx_object живут только до конца выражения, то всё хорошо, при более длительном времени жизни начинаются приключения.

Вторая проблема — у вас внутри объекта лежит огромная куча каких-то непонятных данных, объект, создаваемый из простой пары указателей (Iterator = T*), занимает в памяти вместо ожидаемых 16 байт аж целых 128. Не знаю как насчет остальных, но _indexer, _def_val_container и _default_value определенно лишние, они используются везде как типичные временные переменные:

template<typename ForeachFunctor>
auto for_each_i(ForeachFunctor &&foreachFunctor) const noexcept -> void
{
    auto begin = _begin;
    auto end = _end;

    _indexer = 0;

    while (begin != end)
    {
        foreachFunctor(*begin, _indexer);

        ++_indexer;
        ++begin;
    }
}

В чем смысл помещения их внутрь объекта я не понимаю.

Дальше:

template<typename AvgFunctor>
auto avarage(AvgFunctor &&avgFunctor) const noexcept -> decltype(auto)
{
    return (sum(std::forward<AvgFunctor>(avgFunctor))
        / std::distance(_begin, _end));
}

Во-первых, конечно, average, во-вторых, в случае не RandomAccessIterator реализация неэффективна (два прохода вместо одного), а в случае InputIterator (по которым можно сделать только один проход, например, std::istream_iterator) вообще не сработает.

Ну и по мелочи:

using self_type = relinx_object<Iterator, ContainerType>;

с последней редакцией указывает на неверный тип.

relinx_object(ContainerType &&container) noexcept
    : _container(std::forward<ContainerType>(container))
    , _begin(std::begin(_container))
    , _end(std::end(_container)) {}

Напишите по-русски _container(std::move(container)), у вас тут аргумент нешаблонный, никакой тип не выводится.

C++ без new и delete

Код, который был приведен выше — был абсолютно тривиальный и без включенной оптимизации

О, а я был прав. В этом примере поди снова не включили?

C++ без new и delete

Да, так и будет, потому что проверка внутри delete не скрыта в недрах какой-нибудь вызываемой функции, а вставляется компилятором прямо по месту самого delete (что логично, т.к. иначе мы не смогли бы получать преимущества от знания, что в этой точке указатель всегда ненулевой). В комментарии ниже есть искусственный пример, показывающий, что в обоих случаях код будет идентичным.

C++ без new и delete

Не знаю, кто как, но люди, которые моют руки перед едой, так код писать точно не будут. А напишут его, например, так:

Только лучше так:

foo(std::move(arg0), std::move(arg1));

Экономим на лишнем инкременте/декременте счетчика и отвязываем время жизни объектов от времени жизни arg0 и arg1.

C++ без new и delete

// здесь выполняется проверка что в reset не передали тот же самый указатель

Я не уверен, кстати, что подобная проверка (если я верно понял то, что в ситуации равенства обоих указателей при ней ничего не происходит) не нарушает стандарт. Стандарт (C++11 20.7.1.2.5p4) говорит нам о поведении reset() следующее:

Effects: assigns p to the stored pointer, and then if the old value of the stored pointer, old_p, was not equal to nullptr, calls get_deleter()(old_p).

Как видим, вышеупомянутой проверки стандарт не предусматривает, а значит в точке p.reset(x); должен быть вызван деструктор для x и освобождена память. Да, можно сказать, что дальше в момент вызова деструктора p у нас возникает UB из-за повторного удаления, и поэтому мы можем делать, что захотим. Ну а вдруг такого не будет (например, ниже мы вызовем release())?

C++ без new и delete

Зачем оно там?

В реальности, там в шаблоне конструкция вида:

if (get() != nullptr)
  get_deleter()(get());

для поддержки нестандартных deleter'ов (стандарт обязывает делать такую проверку и вызывать их только для ненулевых указателей). И да, в ситуациях, когда компилятор не может доказать (в примерах выше то у него всего на виду), что указатель ненулевой, проверка останется. Но и для простого delete компилятор прямо по месту такую проверку вставит, т.к., как вы верно указали, по стандарту delete от нулевого указателя абсолютно легален и должен просто не делать ничего, а вызывать, к примеру, какой-нибудь нетривиальный деструктор, передав ему нулевой указатель, не самая лучшая идея. Вот синтетический пример, в обоих случаях идет проверка.

Вообще, по логике, если мы уверены, что в этой точке указатель не нулевой, то мы можем «подсказать» это компилятору, написав какое-нибудь не делающее ничего действие с использованием разыменования этого указателя (скажем, delete &*p;). Тогда компилятор имеет право считать, что указатель всегда ненулевой, т.к. иначе происходит UB. На практике, я чуток поигрался, и компиляторы (пока?) такие подсказки не воспринимают, нужно что-то очень явное с объектом сделать (например, вывести его на экран), чтоб такая оптимизация заработала. Возможно, у кого-нибудь получится найти рабочий способ?

C++ без new и delete

Вы, скорей всего, при компиляции оптимизацию не включили, вот у вас ничего и не заинлайнилось.

Разыменовывание нулевого указателя приводит к неопределённому поведению

В плюсах есть такая интересная штука — указатель-на-член данных. По сути, это тот же offset от начала структуры, только типизированный. Но стандарт требует, чтобы этому указателю можно было присвоить нулевое значение (nullptr), которое значит, что он никуда не указывает. Как же быть, ведь смещение на 0 относительно начала структуры — это вполне легитимная вещь? Просто берут и хранят не само смещение, а смещение + 1 (то есть смещение в 0 становится единицей и т.д.), мне кажется, и в вашем случае подобным трюком можно воспользоваться.

Разыменовывание нулевого указателя приводит к неопределённому поведению

В ваших примерах, несмотря на то, что оператор разыменования в коде присутствует, фактического чтения данных по этому адресу не происходит, всё остается на уровне арифметики адресов. На уровне стандарта терминология, позволяющая разграничить эти два случая, тоже существует: оператор разыменования генерирует lvalue (адрес), а процесс чтения данных по адресу осуществляется с помощью lvalue-to-rvalue conversion. Но, видимо, авторы стандарта не захотели усложнять/поленились/не учли этого, в общем, по какой-то причине не разграничили эти случаи.

Нам запретят даже говорить о криптовалютах?

Экономические теории скорее напоминают религию, чем науку.

Насколько я смог понять, экономика — некий сплав из гуманитарной и точной дисциплины. Там есть очень большой слой, который строит различные математические модели, пытается их анализировать, искать наилучшую стратегию в рамках этой модели и так далее. И есть второй, условно гуманитарный слой, который занимается спорами о том, какие базовые принципы должны быть положены в основу этих моделей, чтобы они были похожи на то, что происходит в реальном мире, ну и пытается распространять полученные в рамках анализа моделей выводы на этот самый реальный мир и находить им подтверждения. Для этого слоя, как и, в принципе, для любой гуманитарной дисциплины характерно то, что вы описали: споры, различные течения и школы и все в этом духе.

Как мы объясняли детям, кто такой программист

Мне тоже кажется, что часть про то, как раньше было тяжело и вы не представляете как вам, дети, повезло, лишняя. И общий посыл доклада, что человек должен стремиться всё уметь и программирование ему в этом очень поможет, если я, конечно, верно его уловил, слишком философский для детей что ли.

Нам запретят даже говорить о криптовалютах?

Вывод активов это не преступление.

Это когда они получены легальными методами.

Нам запретят даже говорить о криптовалютах?

Тогда каждый может проверить свой голос и спросить знакомого, действительно ли тот проголосовал так.

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

Нам запретят даже говорить о криптовалютах?

Так же и с МММ: закона о пирамидах не было — вас ни кто не принуждал играть.

Всё верно, но парень давал обещания, которые не сдержал. За это и был осужден, насколько я понимаю.

А мне тут втирают как круто будет с биткоином.

Конкретно в этой ветке вам «втирают» в чем разница между биткоином и МММ, смотрите свой же вопрос, с которого эта ветка началась.

Вот ровно об этом государство и говорит :). Что это сурогат денег и все операции с ним — ваши личные проблемы.

Нет, государство говорит: если ты, друг, будешь им пользоваться, мы тебя накажем, смотрите текст поста.

Нам запретят даже говорить о криптовалютах?

Куда-то вас не туда понесло имхо, нету никаких гарантий ни для этой валюты, ни для одной из официальных валют, везде только ваши риски. Подскочил вот курс рубля к доллару в два раза недавно, и что случилось? Кто-то вам что-то возместил? «Привет Мавроди.»

Нам запретят даже говорить о криптовалютах?

Бумажки МММ позиционируются, как акции.

Ближе уж к облигациям тогда.

Нам запретят даже говорить о криптовалютах?

Ну так тут многие также рвутся на рынок, чтобы намайнить из воздуха денег.

Это неважно, в истории человечества существовало множество видов денег, которые можно было «намайнить»: различные металлы (преимущественно драгоценные), скот, зерно, шкуры животных. Ещё раз повторюсь, основная разница в том, что в случае финансовых пирамид я (организатор пирамиды) вас обманываю, обещая некий доход, а в итоге своё обещание не выполняю, скрываясь в неизвестном направлении.