Зарядка для мозгов ...

[roma]

Меня интересует только сколько времени вам потребовалось чтобы продумать алгоритм, написать код (С) и по возможности отладить (протестировать) его, чтобы он работал правильно для любой стартовой позиции (элемента), т.е. в качестве параметра можно задать также первый и последний элемент.

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

Сам алгоритм и решение тут публиковать не надо, интересует только время !

// Implement a function reverseAfter() to reverse the elements in a linked list
// from the first occurrence of a given value.
// e.g. given the input A B C D E F and the value D return the list A B C F E D
// You should do this inplace without creating new nodes.
// Assume the list is null terminated.
struct Node
{
struct Node* next;
int val;
};

[roma]

Ну что, никто не размял немного свои мозги?
Просто это одно из 10 заданий которые надо выполнить за 2 часа.
Поэтому меня и заинтересовало сколько времени может минимум понадобиться чтобы сделать только одно это задание ...

[roma]

Да кстати, задачу можно решить двумя способами - тупо влоб, и правильно, немного пораскинув мозгами.
Тупо влоб делается достаточно быстро (у меня заняло минут 15-20) - работает правильно - но такое решение не застчитали.
Правильно, пораскинув мозгами - нужно время сначала до него додуматься, а потом ещё время чтобы правильно всё реализовать,
чтобы всё работало правильно для любой стартовой позиции (элемента), т.е. в качестве параметра можно задать также первый и последний элемент.

[roma]

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

struct Node
{
struct Node* next;
int val;
};

struct Node* getNode( struct Node* head, int pos )
{
while (pos>0)
{
head = head->next;
pos--;
}
return head;
}

void reverse( struct Node* head )
{
int size = 0;
struct Node* start = head;
while (start->next)
{
start = start->next;
size++;
}
while (size/2>=0)
{
start = head;
int val = head->val;
struct Node* node = getNode(start, size);
head->val = node->val;
node->val = val;
head = head->next;
size -= 2;
}
}

void reverseAfter( struct Node* head, int val )
{
if( head->val == val)
reverse(head);
else
if (head->next)
reverseAfter(head->next, val);
}

int main(int argc, char* argv[])
{
struct Node* n;
struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
n1->val = 'A';
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
n2->val = 'B';
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
n3->val = 'C';
struct Node* n4 = (struct Node*)malloc(sizeof(struct Node));
n4->val = 'D';
struct Node* n5 = (struct Node*)malloc(sizeof(struct Node));
n5->val = 'E';
struct Node* n6 = (struct Node*)malloc(sizeof(struct Node));
n6->val = 'F';
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = NULL;
n = n1;
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
reverseAfter(n1, 'D');
n = n1;
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
return 0;
}

[roma]

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

struct Node
{
struct Node* next;
int val;
};

struct Node* _reverseAfter( struct Node* head, int val )
{
struct Node *first = head, *start = head, *prev = NULL, *nxt;
while( head->val != val)
{
start = prev = head;
head = head->next;
}

while(head)
{
nxt = head->next;
head->next = prev;
prev = head;
head = nxt;
}
if (start->next)
{
start->next->next = NULL;
start->next = prev;
}
else
first = prev;
return first;
}

int main(int argc, char* argv[])
{
struct Node* n;
struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
n1->val = 'A';
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
n2->val = 'B';
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
n3->val = 'C';
struct Node* n4 = (struct Node*)malloc(sizeof(struct Node));
n4->val = 'D';
struct Node* n5 = (struct Node*)malloc(sizeof(struct Node));
n5->val = 'E';
struct Node* n6 = (struct Node*)malloc(sizeof(struct Node));
n6->val = 'F';
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = NULL;
n = n1;
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
n = _reverseAfter(n1, 'D');
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
return 0;
}

[roma]

Мне просто было не понятно как можно было сделать 10 заданий за два часа.
Поэтому и попросил сделать, чтобы узнать за сколько времени минимум можно было сделать это одно задание ...

[Иван Иванович]

Мне просто было не понятно как можно было сделать 10 заданий за два часа.
Поэтому и попросил сделать, чтобы узнать за сколько времени минимум можно было сделать это одно задание ...

Эта пиндоская контора поди еще и всего 35к в год платит?

[Иван Иванович]

Мне просто было не понятно как можно было сделать 10 заданий за два часа.
Поэтому и попросил сделать, чтобы узнать за сколько времени минимум можно было сделать это одно задание ...

Эта пиндоская контора поди еще и всего 35к в год платит?

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

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

struct Node
{
struct Node* next;
int val;
};

struct Node* getNode( struct Node* head, int pos )
{
while (pos>0)
{
head = head->next;
pos--;
}
return head;
}

void reverse( struct Node* head )
{
int size = 0;
struct Node* start = head;
while (start->next)
{
start = start->next;
size++;
}
while (size/2>=0)
{
start = head;
int val = head->val;
struct Node* node = getNode(start, size);
head->val = node->val;
node->val = val;
head = head->next;
size -= 2;
}
}

void reverseAfter( struct Node* head, int val )
{
if( head->val == val)
reverse(head);
else
if (head->next)
reverseAfter(head->next, val);
}

int main(int argc, char* argv[])
{
struct Node* n;
struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
n1->val = 'A';
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
n2->val = 'B';
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
n3->val = 'C';
struct Node* n4 = (struct Node*)malloc(sizeof(struct Node));
n4->val = 'D';
struct Node* n5 = (struct Node*)malloc(sizeof(struct Node));
n5->val = 'E';
struct Node* n6 = (struct Node*)malloc(sizeof(struct Node));
n6->val = 'F';
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = NULL;
n = n1;
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
reverseAfter(n1, 'D');
n = n1;
while (n->next)
{
printf("%c, ", n->val);
n = n->next;
}
printf("%c\n", n->val);
return 0;
}

[roma]

Мне просто было не понятно как можно было сделать 10 заданий за два часа.
Поэтому и попросил сделать, чтобы узнать за сколько времени минимум можно было сделать это одно задание ...

Эта пиндоская контора поди еще и всего 35к в год платит?

Да нет, это одна из десяти задачек теста на 2 часа в Майкрософт ... Но не взяли пиндосы ...
Не засчитали решение влоб. А правильно до меня уже потом доперло и это я уже потом сам сделал.
Но за 2 часа было абсолютно нереально сделать хотя бы 7 из 10 задачек. Я успел сделать 5 или 6 ...

[Вий]

Хм, там же в условии " You should do this inplace without creating new nodes."
А у тебя mallloc'и там всякие...