Попалась такая задача на C#.
Сейчас решение с сортировкой в случайно порядке, читай перемешиванием и брать первые N элементов. Выполняется за O(N logN).
Можно ли сделать как-то за O(N)?
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}