Java собеседование. Коллекции

• random shuffle
• переход к O(n*log(n)) сортировкам, если операций стало больше критического максимума
• и т.д.

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }
}

public static Node<T> ReverseInPlace<T>(Node<T> root)
{
    Node<T> prev = null;
    Node<T> curr = root;
    while (curr != null)
    {
        var next = curr.Next;
        curr.Next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

int K = 3; //количество необходимых чисел
int N = 15; //количество элементов в массиве.
var random = new Random();
var randomIndexes = new int[K]; // случайные индексы элементов, которые мы должны вытащить из массива
				
for (int i = 0; i < K; i++)
{
	var prev = i > 0 ? (randomIndexes[i - 1] + 1) : 0;
	randomIndexes[i] = random.Next(prev, N - (K - i - 1));
}
var shift = random.Next(0, N);
for (int i = 0; i < K; i++)
{	
	randomIndexes[i] = (randomIndexes[i] + shift) % N;
}

... // тут возвращаем все элементы с найденными индексами

class FastSet{
  int N;  // size of array
  int CurVersion; // current version of data, clearings counter
  object[] Values;  // values
  int[] Versions;   // versions of elements

  public FastSet(int _N){
     N=_N;
     Values=new object[N];
     CurVersion=1%N;     // or N==1 ? 0 : 1
     Versions=new int[N];  // versions of all elements are 0, just out of date
  }
  public void Clear(){
     int NewVer=(CurVersion+1)%N;
    Versions[CurVersion]=Versions[NewVer]=CurVersion;
    Values[CurVersion]=null;   // for case N=1
    CurVersion=NewVer;
  }
  public void Put(int ind,object val){
    if(ind<0 || ind>=N) return;
    Values[ind]=val;
    Versions[ind]=CurVersion;
  }
  public object Get(int ind){
    if(ind<0 || ind>=N || Versions[ind]!=CurVersion) return null;
    return Values[ind];
  }
}