Изящная задачка про списки
Решение в лоб (без учета O(N.
Чтобы не тратить время на бойлеркод - вот заготовка файла проверки:
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct NodeTag {
struct NodeTag *next;
struct NodeTag *random;
int data;
} Node;
void printListData(Node *source)
{
Node *node = source;
do {
printf("Node %d (%p next %d (%p random %d (%p)",node->data,node, node->next ? node->next->data : -1, node->next, node->random->data, node->random );
node = node -> next;
} while (node);
}
Node *copyList(Node *head)
{
}
int main
{
srand(time(NULL;
int count = 10;
Node *sourceArray = malloc(count * sizeof(Node;
for (int i = 0; i < count; i++)
{
Node *node = &sourceArray[i];
node->data = i;
node->random = &sourceArray[(rand % count)];
if (i < count - 1)
{
node->next = &sourceArray[i + 1];
}
else
{
node->next = NULL;
}
}
printf("\nOLD LIST\n");
Node *node = &sourceArray[0];
printListData(node);
Node *newList = copyList(node);
printf("\nPRINT NEW LIST DATA\n");
printListData(newList);
return 0;
}
Если я правильно понимаю - подсчет индексов всех random элементов имеет сложность выше, чем О(n так что такое вот лобовое решение не укладывается в условие
Решение в лоб.Выглядит как O(n^2 на самом деле она решается за O(N этой задачке года два уже.
нормальная такая задачка для собеседований (и, по факту - с собеседований)
Решение в лобА можно в общих чертах? А то первое пришедшее в голову решение язык не поворачивается назвать решением в лоб
там решение без учета требования O(N). Запостил, как промежуточный вариант решения, от которого бывает проще двигаться уже к оптимальному решению.
там решение без учета требования O(N). Запостил, как промежуточный вариант решения, от которого бывает проще двигаться уже к оптимальному решению.Совсем не просто, мыслить надо в другом направлении. Я решал её пару лет назад, поэтому не претендую на правильность. Получилось примерно следующее:
Совсем не просто, мыслить надо в другом направлении. Я решал её пару лет назад, поэтому не претендую на правильность. Получилось примерно следующее:Очень изящно, спасибо!
мыслить надо в другом направлениитут ключевое, что необходимо додуматься до возможности , которая как раз и позволяет убрать пробеги по поиску элемента из решения в лоб.
тут ключевое, что необходимо додуматься до возможностиДа, но решение в лоб тут никак не поможет, от него вообще нельзя отталкиваться. Только посмотреть, сказать, что оно неправильное, и искать другое.
Придумал еще решение.
я думаю, что
интересно сколько Майку отвели времени на решение и какие подсказки он использовал (если использовал вообще)
интересно сколько Майку отвели времени на решение и какие подсказки он использовал (если использовал вообще)
интересно сколько Майку отвели времени на решение и какие подсказки он использовал (если использовал вообще)Я помню, что в этом конкретном случае времени было бесконечное количество, а вот сколько использовал - не помню. Точно меньше 20 минут, потому что эта задача из лёгких.
Я не любитель таких задачек и считаю, что они не дают возможности оценить специалиста. Но в своё время приходилось частенько решать подобную ерунду на собеседованиях. Поэтому даже не задумывался о том, что нельзя делать модификацию оригинала.
нормальная такая задачка для собеседованийна какую позицию?
в архиве:
на какую позицию?Скорее, не на какую позицию, а куда: Google, Microsoft, Яндекс. На самом деле желающих проводить собеседования с использованием подобных задачек более чем достаточно.
Оставить комментарий
Anna551
Наткнулся случайно на задачку, понравилась.Есть однонаправленный список из структур
typedef struct NodeTag {
struct NodeTag *next;
struct NodeTag *random;
int data;
} Node;
где random указывает на какой-то еще элемент этого же списка.
Требуется написать функцию, которая копирует этот список с сохранением структуры (то есть если в старом списке random первой ноды указывал на 4-ю, в новом списке должно быть то же самое - рандом первой ноды указывает на 4-ю ноду нового списка).
O(n константная дополнительная память + память под элементы нового списка.
P.S. считается, что мы не можем выделить память новый список как цельный кусок (чтобы список был честным, разбросанным по памяти списком, а не массивом с функциональностью списка)