Olympiad problems in industrial programming. Part 1

When I was working as a Backend developer at the best company in the world, I came across (or wanted to face) tasks that are very similar to those found in Olympiad programming. It is about them that we will be talking. This is the first part of the article, in which I will present one task with a detailed explanation. If you are also interested in algorithms and data structures, then I ask for a cut!

Problem 1.

Given: a list of unique objects (for simplicity we take numbers) that have a regularity in the sequence.

Limitations:

• number of elements up to 10 ^ 5;
• It’s expensive to create a new list, therefore you need to change the same list.

It is necessary to mix the elements of the list so that not a single element of the list is in the same place, and also that the pattern in the sequence is violated, that is, simply cyclically moving the elements to the right or left is not enough.

Solution:

Let the number of elements in the list be n. Since we need to ensure that each element does not stand in its place, we will generate a random number for each element with index i that changes from (n-1) to 1 - the index from 0 to i is not inclusive. Thus, having received a random index j, which is not equal to the current index i, we interchange the elements located at i and j positions.

For example:

Our list = [1,7,5,2,6].

Fill in the trace table for better clarity of the algorithm, where i are denoted by rightIndex and j is leftIndex.

rightIndex	leftIndex	List
4	1	[1,6,5,2,7]
3	2	[1,6,2,5,7]
2	0	[2,6,1,5,7]
1	0	[6,2,1,5,7]

We write out the initial list and the list that resulted from the execution of the algorithm.

[1,7,5,2,6]

[6,2,1,5,7]

As we can see, all the elements have moved to different places, and there is not a single element that remains in its place. If you notice, then rightIndex always changes from the last index of the list to 1. And leftIndex is randomly generated so that it is strictly less than that corresponding to it at each iteration of the loop, rightIndex. Due to this property, the final result is achieved.

We will write the above method in C #. We parameterize it so that it can be used for any objects (numbers, strings, custom data types).

// Метод расширения для параметризованного списка, который перемешивает список
public static void Shiffle(this IList list)
{
   var random = new Random();
   int maxIndex = list.Count - 1;
   for (int i = 0; i < maxIndex; i++)
   {
      int rightIndex = maxIndex - i;
      int leftIndex = random.Next(0, rightIndex);
      list.Swap(leftIndex, rightIndex);
   }
 }

// Меняем два элемента местами в списке с заданными индексами
public static void Swap(this IList list, int index1, int index2)
{
  T c = list[index1];
  list[index1] = list[index2];
  list[index2] = c;
}

I posted this function in my repository. GitHub link  here .

If you do not agree with the correct operation of the algorithm or if you do not fully understand, then write in the comments, I will answer you.

If you have a faster solution, or a simpler one (naturally explaining and naturally with such restrictions), then please indicate in the comments, I will be grateful.