Задача довольно любопытная.
Её можно вполне (и нужно) включить в копилку Подборки задач по C и C++
Такую задачу предлагает одна из фирм (из числа разработчиков MySQL) соискателям на работу в их команде - вот их формулировка ideone.com.
Но я здесь повторю их формулировку:
Формулировка (в комментарии) сама по себе по форме идиотская - неоднозначная, невнятная, да и недописанная до конца (последняя фраза в скобках) ... но я сейчас её уточню ниже и растолкую.// Написать (компилировать не нужно) вставку и поиск для дерева остатков
// (radix tree)
//
// Ключом является целое беззнаковое 32-битное число. Высота дерева должна
// определяться константой, т.е. в зависимости от значения этой константы мы
// получаем корректно работающее дерево различной высоты.
//
// Дерево остатков - это дерево высотой N (степень двойки), хранящее в листьях
// значения V по целочисленным беззнаковым ключам K. Пусть bits(X) - это число
// всех бит в X или sizeof(X) * 8 в терминах C. Каждый узел дерева хранит
// 2 ^ (bits(K) / N) (`^` - возведение в степень) указателей на узел следующего
// уровня или значение (если узел является листом). На i-м уровне указатель на
// узел (i + 1)'го уровня определяется в массиве i'го узла как (при адресации, в
// которой менее значимые биты ключа определяют индексы в верхних уровнях дерева).
#define N 4
typedef struct {
// ......
} RtNode;
RtNode rt_root;
void rt_insert(unsigned int key, void *val) {
// ...
}
/* Returns NULL if there is no element with such key. */
void *rt_lookup(unsigned int key) {
// ...
}
P.S. Написать образец такого кода они предлагают за 1/2 часа - без компиляции и проверки ... Может быть это и возможно если ежедневно писать/править подобный код, но без конкретной подготовки, "набитой руки", я предполагаю что это глупость. Я, столкнувшись с этим в разговоре, просто отказался участвовать в этой глупости, но задача сама по себе интересная, и я сам для себя реализовал её, с компиляцией и тестированием за 3-4 часа.