Пусть напишет программу для решения квадратных уравнений. Чисто чтобы убедиться, что он не полный ноль. Ну или программу-слипер, отключающую компьютер через заданное время бездействия мыши и клавиатуры.
Тестовое задание? Над эти обычно работают специальные отделы, и, у некоторых даже получается впихнуть туда рутинные задания текущего проекта, решения которых будут переиспользованы. В основном, это зависит от требований вакансии. Лучшего результата можно добиться лишь на живом собеседовании. Если требования расплывчаты, то я бы просто постарался бы затронуть как можно больше парадигм в одном задании (опять же, чтобы оно могло быть выполнено в рамках собеседования); чтобы, соответственно, оценить реальные знания (без гугления и copy paste) и смекалку в целом. В некоторых конторах, задание типа "напишите какое-нибудь CDUD приложение на mongodb" будет достаточно.
Есть отсортированный массив. Вставить данные из него в другой массив в случайном порядке. Оценить сложность алгоритма. Успешным было бы создание алгоритма со сложностью O.