What they ask in an interview: an overview of algorithms, part 1

Good afternoon everyone! Various kinds of algorithms are used in projects more often than it might seem. For example, we need to sort some data according to certain parameters (columns) so that we can navigate through them without much effort. Therefore, there is nothing strange in the fact that at job interviews they may be asked about one or another basic algorithm, and possibly given the task to implement it using code. And since you're on this site, I'm going to assume that you're writing in Java. Therefore, today I suggest that you familiarize yourself with some basic algorithms and with specific examples of their implementation in Java. By some I mean:

1. Overview of array sorting algorithms:
   • bubble sort,
   • selection sort,
   • insertion sort,
   • shell sort,
   • quick sort,
   • merge sort.
2. Greedy algorithm.
3. Pathfinding algorithms:
   • detour,
   • bypass in width.
4. The transport algorithm is Dijkstra's algorithm.

Well, without further ado, let's get down to business.

1. Overview of sorting algorithms

bubble sort

This sorting algorithm is known primarily for its simplicity, but at the same time it has one of the slowest execution speeds. As an example, consider bubble sort for numbers in ascending order. Imagine a chain of randomly placed numbers for which the following steps will be performed, starting from the beginning of the chain:

• compare two numbers;
• if the number on the left is greater, then swap them;
• move one position to the right.

After going through the entire chain with these steps, we will find that the largest number is at the end of our series of numbers. Next, exactly the same pass along the chain is performed with the above steps. But this time, we won't include the last element of the list, since it's the largest and is already in last place, as it should be. Again, we will get the last element at the end of our series of numbers in question. Accordingly, the two largest numbers will already be in their places. And again, the passage along the chain is started, with the exception of the elements that are already in their places, until all the elements are in the required order. Let's look at the implementation of bubble sort in Java code:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

As you can see, there is nothing complicated here, and everything seems to be great, if not for one “but” ... Bubble sort is very, very slow, with O(N²) time complexity , since we have nested loops. The outer pass through the elements is performed N times, the inner one is also N times, and as a result we get N * N , N² iterations You can study this type of sorting in more detail in this article .

Selection sort

This algorithm is similar to bubble sort, but it works a little faster. Again, as an example, take a series of numbers that we want to arrange in ascending order. The essence of the algorithm is to sequentially search through all the numbers and select the smallest element, which we will take and swap with the extreme element on the left (element 0). Here we get a situation similar to bubble sort, but in this case, we will have the smallest sorted element. Therefore, the next pass through the elements will start at the element at index 1. Again, these passes will be repeated until all elements have been sorted. Implementation in Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

This algorithm outperforms bubble sort by reducing the number of permutations needed from O(N²) to O(N): we don't run one element through the entire list, but still, the number of comparisons remains O(N² ) . For those wishing to learn more about this algorithm, I recommend this material .

Insertion sort

Once again, for example, let's take a series of numbers that we want to arrange in ascending order. This algorithm consists in setting a marker, to the left of which the elements will already be partially sorted among themselves. At each step of the algorithm, one of the elements will be selected and placed in the desired position in the already sorted sequence. So the sorted part will grow until all elements have been viewed. You ask: where to get that part of the elements that are already sorted and after which you need to put a marker? But the array from the first element is already sorted, isn't it? Let's look at the implementation in Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

This kind of sort is superior to the above, because despite the fact that the running time is the same - O(N²) , this algorithm is twice as fast as bubble sort and slightly faster than selection sort. More details - here .

Shell sort

This sort, by its nature, is a modified insertion sort. What I'm talking about? Let's go in order. A step is chosen, and this choice has many approaches. We will not go into too much detail on this issue. Let's divide our array in half and get some number - this will be our step. So, if we have 9 elements in the array, then our step will be 9/2 = 4.5 . We discard the fractional part and get 4 , since array indices are only integers. With this step, we will make connections for our groups. If an element has index 0, then the index of the next element in its group is 0+4 , which is 4 . The third element will have an index of 4+4 , the fourth -8+4 , and so on. The second group will have the first element 1,5,9…. In the third and fourth groups, things will be exactly the same. As a result, from the array of numbers {6,3,8,8,6,9,4,11,1} we get four groups: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} They retain their places in the general array, but for us they are marked as members of the same group: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Further inside these groups the insertion sort described above takes place , after which the groups will look like: I - {1,6,6} II - {3,9} III - {4,8} IV - {8,11} In the general array, the cells occupied by groups will remain the same, but inside them the order will change, according to the order groups above: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } The array is a little more ordered, isn't it? The next step will be divided by 2: 4/2 = 2 We have two groups: I - {1,4,6,8,6} II - {3,8,9,11} B total array: { 1 , 3 , 4 , 8 , 6 , 9 , 8 ,11 , 6 } We go through both groups using the insertion sort algorithm, and we get an array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Now our array is almost sorted. The last iteration of the algorithm remains: we divide the step by 2: 2/2 = 1. We get a group, the entire array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } : {1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Let's see how we can render this sort in Java code:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

At the moment, the effectiveness of Shell sorting is not really justified, since the results differ in different situations. Estimates obtained from experiments lie in the range from O(N ^3/2 ) to O(N ^7/6 ) .

Quick sort

This is one of the most popular algorithms, and therefore it is worth paying special attention to. The essence of this algorithm is that in the list with elements, a pivot element is selected - in fact, any element with respect to which the remaining values ​​\u200b\u200bshould be sorted. Values ​​less than it are on the left, values ​​greater than it are on the right. Further, the right and left parts are also selected by the reference element and the same thing happens: the values ​​\u200b\u200bare sorted relative to these elements, then the reference elements are selected from the formed parts - and so on until we get a sorted row. This algorithm in Java is implemented using recursion:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0)// condition выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем middle
           recursionFastSort(array, i, max);
   }
}

Without a doubt, the quicksort algorithm is considered the most popular, since in most situations it is faster than others, in O(N*logN) time .

Merge sort

This sorting is also popular. It refers to one of the types of algorithms that work on the principle of "divide and conquer": in them, we first of all divide tasks into minimal parts (quick sort is also a representative of such algorithms ). So, what is the essence of this algorithm?

Share:

The array is split into two parts of approximately the same size, each of these two parts is divided into two more, and so on, until the smallest indivisible parts remain. The least indivisible parts are when each array has one element, which means that such an array is automatically considered sorted.

Conquer:

This is where the process begins, which gave the name to the algorithm - merge . To do this, two resulting ordered arrays are taken and merged into one. In this case, the smallest of the first elements of the two arrays is written to the resulting array, and this operation is repeated until the elements in these two arrays run out. That is, if we have two minimal arrays {6} and {4} , their values ​​will be compared and the result will be written: {4,6} . If there are sorted arrays {4,6} and {2,8} , then the value 4 and 2 will be compared first , of which 2 will be written to the resulting array. After that it will compare4 and 8 , 4 will be written and 6 and 8 will be compared at the end . Accordingly, 6 will be written, and only after it - 8. As a result, we will get the resulting array: {2,4,6,8} . How would it look like in Java code? To process this algorithm, it will be convenient for us to use recursion:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

As in quicksort, we move the recursive method into an intermediate one so that the user does not have to bother with setting additional default arguments, but can only set the array to be sorted. Since this algorithm is similar to faster sorting, its execution speed is the same - O(N*logN) .

2 Greedy Algorithms

Greedy Algorithmis an approach in which locally optimal decisions are made at each stage and it is assumed that the final solution will also be optimal. The “optimal” solution is the one that offers the most obvious and immediate benefit at a particular step/stage. To consider this algorithm, we will choose a fairly common problem - the knapsack. Let's pretend for a second that you are a thief. You've broken into a store at night with a backpack, and you've got a bunch of stuff in front of you that you can steal. But at the same time, the capacity of the backpack is limited - no more than 30 conventional units. At the same time, you want to carry a set of maximum value items that will fit into your backpack. How do you decide what to put in? So, the greedy algorithm for the knapsack problem consists of the following steps (we assume that all items fit in the knapsack):

1. Choose the most expensive item from those not yet touched.
2. If it fits in a backpack, put it there, if not, skip it.
3. Have you taken all the items? If not, we return to point 1, if yes, we run from the store, since our goal here has been fulfilled.

Let's look at this, but in Java. This is how the Item class would look like:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

There is nothing special here: three fields - name , weight , cost - for setting the characteristics of the subject. Also, as you can see, the Comparable interface is implemented here so that we can sort our Items by price. Next, we look at the class of our backpack - Bag :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight - the capacity of our backpack, which is set when creating the object;
• items - objects in the backpack;
• currentWeight , currentCost - the current weight and cost of all items in the backpack that we increase when adding a new item in the addItem method .

Actually, let's go to the class, where all the action takes place:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

To begin with, we create a list of elements, sort it. Create a bag object with a capacity of 30 units. Next, we send the elements and the bag object to the fillBackpack method , in which, in fact, the backpack is filled according to the greedy algorithm:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Everything is extremely simple: we start going through the list of items sorted by cost and put them in a bag, if capacity allows. If it does not allow, the element will be skipped and the passage through the remaining elements will continue until the end of the list. By running main, we get the output to the console: Actually, this is an example of a greedy algorithm: at each step, a locally optimal solution is selected, and in the end you get a globally optimal solution. In our case, the best option is the most expensive item. But is this the best solution? Don't you think it's possible to upgrade our solution a bit so that we can complete a backpack with a higher total cost? Let's take a look at how this can be done:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

Here we first of all calculate the ratio of weight and price for each item. So to say, how much is one unit of this item. And already by these values ​​we sort our items and add them to our bag. Let's run:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

We get the output to the console: A little better, right? The greedy algorithm makes a locally optimal choice at each step, with the expectation that the final solution will also be optimal. This is not always justified, but for many problems greedy algorithms do give an optimum. The time complexity of this algorithm is O(N) , pretty good, right? Well, on this, the first part of this article has come to an end. If you are interested in the continuation of this article, which will talk about graphs and algorithms related to them, you can find it here .