Здравствуйте, sergey2b, Вы писали:

S>в америки стартапы дают аналогичные задачи
S>один стартап мне дал исходник программы примерно 5000 строк играюшией в суддоку и сказал что там две логические ошибки и их надо найти


1) Сколько времени дали?
2) Можно ли было тестировать?

Вообще-то, если за заметное время и со средой разарботки/тестирования, то может это и адекватно...

Здравствуйте, Erop, Вы писали:


E>1) Сколько времени дали?
E>2) Можно ли было тестировать?

E>Вообще-то, если за заметное время и со средой разарботки/тестирования, то может это и адекватно...

код компилировался gcc
да можно было запускать на своем PC
дали два дня на выходных


если бы это был коненый тест после собеседования я бы напрягся
это был тест на право быть приглашенным на собеседование в некому не известный стартап



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

Здравствуйте, MakcMN, Вы писали:


MMN>Идём по списку и меняем направление связей на противоположное. Если в конце доходим до изначального головного элемента, то цикл есть, иначе — нет. Для восстановления списка проходим по нему в обратную сторону и снова меняем направление связей на противоположное.

В случае цикла

1) трудно восстановить оригинальный список
2) трудно доказать отсутствие потерь памяти, в случае если цикл есть

Здравствуйте, sergey2b, Вы писали:


S>это был тест на право быть приглашенным на собеседование в некому не известный стартап
Ну это тест на то, что чужой код сечёшь. Было ли это в рамках должностных обязанностей тебе виднее.

Здравствуйте, Erop, Вы писали:

MMN>>Идём по списку и меняем направление связей на противоположное. Если в конце доходим до изначального головного элемента, то цикл есть, иначе — нет. Для восстановления списка проходим по нему в обратную сторону и снова меняем направление связей на противоположное.

E>В случае цикла

E>1) трудно восстановить оригинальный список

Не труднее, чем испортить.

E>2) трудно доказать отсутствие потерь памяти, в случае если цикл есть

Цепочка связей не разрывается, т.ч. ничего не теряется.

Вот реализация:

#include <cstddef>
#include <cassert>
#include <vector>


struct node
{
    node *next;
};

// Returns new head
node *reverse(node *head)
{
    node *cur = head;
    node *prev = NULL;
    while (cur != NULL)
    {
        node *const t = cur->next;
        cur->next = prev;
        prev = cur;
        cur = t;
    }

    return prev;
}

bool is_there_loop(node *head)
{
    if (head == NULL || head->next == NULL)
        return false;

    node *const new_head = reverse(head);
    reverse(new_head);

    return new_head == head;
}

void print(const std::vector<node> &nodes)
{
    printf("{");
    for (size_t i = 0, i_max = nodes.size(); i < i_max; ++i)
    {
        if (i > 0)
            printf(", ");
        printf("0x%p {next = 0x%p}", &nodes[i], nodes[i].next);
    }
    printf("}\n");
}

void check_loop(std::vector<node> &nodes, bool expectation)
{
    print(nodes);

    const bool result = is_there_loop(nodes.empty() ? NULL: &nodes[0]);
    assert(result == expectation);

    print(nodes);
    printf("is_there_loop = %s\n\n", result ? "true": "false");
}

int main()
{
    std::vector<node> nodes;

    nodes.resize(0);
    check_loop(nodes, false);

    nodes.resize(1);
    nodes[0].next = NULL;
    check_loop(nodes, false);

    nodes.resize(1);
    nodes[0].next = &nodes[0];
    check_loop(nodes, true);

    nodes.resize(2);
    nodes[0].next = &nodes[1];
    nodes[1].next = NULL;
    check_loop(nodes, false);

    // на поиграться
    nodes.resize(3);
    nodes[0].next = &nodes[1];
    nodes[1].next = &nodes[2];
    nodes[2].next = &nodes[1];
    check_loop(nodes, true);

    return 0;
}

Выводится:

{}
{}
is_there_loop = false

{0x00370850 {next = 0x00000000}}
{0x00370850 {next = 0x00000000}}
is_there_loop = false

{0x00370850 {next = 0x00370850}}
{0x00370850 {next = 0x00370850}}
is_there_loop = true

{0x00370880 {next = 0x00370884}, 0x00370884 {next = 0x00000000}}
{0x00370880 {next = 0x00370884}, 0x00370884 {next = 0x00000000}}
is_there_loop = false

{0x003708B8 {next = 0x003708BC}, 0x003708BC {next = 0x003708C0}, 0x003708C0 {next = 0x003708BC}}
{0x003708B8 {next = 0x003708BC}, 0x003708BC {next = 0x003708C0}, 0x003708C0 {next = 0x003708BC}}
is_there_loop = true

Здравствуйте, AndyCyp, Вы писали:

AC>цикл в списке, без выделения доп памяти? За метод с двумя бегунками, если ничего не путаю, в 60х годах кому то дали докторскую. Если кандидат не знает такого метода, ожидать что он его изобретет за 45 мин несколько оптимистично.

Оффтопик, но у меня всегда вызывали удивление люди, которые думают, что кандидат им сейчас за полчаса на собеседовании изобретёт решение, которое несколько месяцев придумывали далеко не самые глупые люди.

Здравствуйте, sergey2b, Вы писали:

S>я считаю перечисленное правильным и примерно так же отвечал
S>человек из амазона утверждает что правильный ответ — закодирую все сам и положу бболт на коллегу и непосредственного начальника тк имменно так поступит настоящий лидер

Датчик на Фобос-грунте заколачивал молотком настоящий лидер.

Здравствуйте, Pzz, Вы писали:

Pzz>Вот бы яндексную Алису к таким интервью подключить...

С какой стороны?