As perguntas e respostas das entrevistas de emprego: algoritmos em Java, parte 1

Os projetos de desenvolvimento usam vários algoritmos com mais frequência do que você imagina. Por exemplo, suponha que precisamos classificar alguns dados por determinados parâmetros (colunas) para que possamos navegar pelos dados sem muito esforço. Portanto, não seria nada estranho para um entrevistador de emprego perguntar sobre um algoritmo básico específico e talvez dar a tarefa de implementá-lo usando código. E já que você está neste site, vou ser tão ousado a ponto de assumir que você está escrevendo em Java. É por isso que hoje sugiro que você se familiarize com alguns algoritmos básicos e com exemplos específicos de como implementá-los em Java. Por "alguns" quero dizer:

1. Visão geral dos algoritmos de classificação de matrizes:
   • Tipo de bolha,
   • classificação de seleção,
   • ordenação por inserção,
   • Tipo de concha,
   • ordenação rápida,
   • classificação de mesclagem,
2. Algoritmos gananciosos
3. Algoritmos de descoberta de caminhos
   • pesquisa em profundidade
   • pesquisa em largura
4. Algoritmo de caminho mais curto primeiro de Dijkstra

Bem, sem mais delongas, vamos ao que interessa.

1. Visão geral dos algoritmos de classificação

Tipo de bolha

Esse algoritmo de classificação é conhecido principalmente por sua simplicidade, mas também é um dos mais lentos. Como exemplo, vamos considerar um tipo de bolha para números em ordem crescente. Vamos imaginar uma sequência aleatória de números. Faremos os seguintes passos sobre esses números, começando pelo início da sequência:

• comparar dois números;
• se o número à esquerda for maior, troque-os;
• mover uma posição para a direita.

Depois de executar essas etapas em toda a sequência, descobriremos que o maior número está no final de nossa série de números. Em seguida, fazemos outra passagem pela sequência, executando exatamente as mesmas etapas acima. Mas desta vez não vamos incluir o último elemento da lista, pois é o maior número e já está exatamente onde deveria estar quando os números são ordenados. Mais uma vez, acabaremos movendo o próximo maior número para o final de nossa sequência. Claro, isso significa que os dois maiores números estão em seus devidos lugares. Novamente, fazemos passagens pela sequência, excluindo os elementos que já estão em seus lugares, até que todos os elementos estejam na ordem desejada. Vamos dar uma olhada em como o bubble sort é implementado no código Java:

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;
             }
         }
       }
   }
}

Como você pode ver, não há nada complicado aqui. Tudo parece ótimo e seria se não fosse por uma falha - o tipo de bolha é muito, muito lento. Sua complexidade de tempo é O(N²), pois temos loops aninhados. O loop externo sobre os elementos é executado N vezes. O loop interno também é executado N vezes. Como resultado, obtemos N*N, ou N², iterações.

Classificação de seleção

Esse algoritmo é semelhante ao Bubble Sort, mas funciona um pouco mais rápido. Novamente, como exemplo, vamos pegar uma sequência de números que queremos organizar em ordem crescente. A essência desse algoritmo é iterar sequencialmente por todos os números e selecionar o menor elemento, que pegamos e trocamos pelo elemento mais à esquerda (o 0º elemento). Aqui temos uma situação semelhante ao bubble sort, mas neste caso nosso elemento classificado será o menor. Portanto, a próxima passagem pelos elementos começará a partir do elemento com índice 1. Repetiremos essas passagens até que todos os elementos tenham sido classificados. Implementação em 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++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Este algoritmo é superior ao bubble sort, porque aqui o número de deslocamentos necessários é reduzido de O(N²) para O(N). Não estamos conduzindo um elemento por toda a lista, mas o número de comparações ainda é O(N²).

ordenação por inserção

Consideramos ainda outra sequência numérica que queremos organizar em ordem crescente. Este algoritmo consiste em colocar um marcador, onde todos os elementos à esquerda do marcador já estão parcialmente ordenados entre si. A cada passo do algoritmo, um dos elementos será selecionado e colocado na posição desejada na sequência parcialmente ordenada. Assim, a parte ordenada crescerá até que todos os elementos tenham sido examinados. Você está se perguntando como obter o subconjunto de elementos que já estão classificados e como determinamos onde colocar o marcador? Mas o array formado pelo primeiro elemento já está ordenado, não é? Vamos dar uma olhada na implementação em 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 is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

Este tipo de ordenação é superior aos descritos acima, pois apesar de ter o mesmo tempo de execução O(N²), este algoritmo é duas vezes mais rápido que a ordenação por bolha e um pouco mais rápido que a ordenação por seleção.

Shell sort

Essa classificação é essencialmente uma classificação de inserção modificada. Do que estou falando? Vamos colocar as primeiras coisas em primeiro lugar. Devemos primeiro escolher um intervalo. Existem muitas abordagens para fazer essa escolha. Não entraremos em muitos detalhes sobre isso. Vamos dividir nosso array ao meio e obter algum número — esse será nosso intervalo. Portanto, se tivermos 9 elementos em nossa matriz, nosso intervalo será 9/2 = 4,5. Descartamos a parte fracionária e obtemos 4, pois os índices do array só podem ser inteiros. Usaremos esse intervalo para formar nossos grupos. Se um elemento tiver índice 0, o índice do próximo elemento em seu grupo será 0+4, ou seja, 4. O terceiro elemento terá o índice 4+4, o quarto — 8+4 e assim por diante. No segundo grupo, o primeiro elemento será 1,5,9... No terceiro e quarto grupos, a situação será a mesma. Como resultado, da matriz numérica {6,3,8,8,6,9,4,11,1} obtemos quatro grupos: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Eles mantêm seus lugares na matriz geral, mas nós marcamos como membros do mesmo grupo: {6,3,8,8,6,9,4,11,1} A seguir, inserção sort é aplicado a esses grupos, e então eles se parecem com isto: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Na matriz geral, o as células ocupadas pelos grupos permanecerão as mesmas, mas sua ordem interna mudará, conforme a ordem dos grupos acima: {1,3,4,8,6,9,8,11,6} A matriz tornou-se uma um pouco mais ordenado, não é? O próximo intervalo será dividido por 2: 4/2 = 2 Temos dois grupos: I — {1,4,6,8,6} II — {3,8,9,11} Na matriz geral, temos : {1,3,4,8,6,9,8,11,6} Executamos o algoritmo de classificação por inserção em ambos os grupos e obtemos esta matriz: {1,3,4,8,6,9,6, 11, 8} Agora nosso array está quase ordenado. Precisamos realizar uma iteração final do algoritmo: dividimos o intervalo por 2: 2/2 = 1. Obtemos um grupo composto por todo o array: {1,3,4,8,6,9,6,11 ,8} Executando o algoritmo de classificação por inserção, obtemos: {1,3,4,6,6,8,8,9,11} Vamos dar uma olhada em como podemos dar vida a essa classificação no código Java:

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 = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

No momento, o desempenho do Shellsort não é fácil de caracterizar, pois os resultados diferem em diferentes situações. As estimativas experimentais variam de O(N ^3/2 ) a O(N ^7/6 ).

Ordenação rápida

Este é um dos algoritmos mais populares, por isso vale a pena prestar atenção especial. A essência desse algoritmo é que um elemento pivô é selecionado em uma lista de elementos. Classificamos todos os outros elementos em relação ao elemento pivô. Valores menores que o elemento pivô estão à esquerda. Valores maiores do que estão à direita. Em seguida, os elementos pivô também são selecionados nas partes direita e esquerda, e a mesma coisa acontece: os valores são classificados em relação a esses elementos. Em seguida, os elementos pivô são selecionados nas peças recém-formadas e assim por diante até obtermos uma sequência ordenada. A seguinte implementação Java deste algoritmo usa recursão:

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 for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than middle
           recursionFastSort(array, i, max);
   }
}

Sem dúvida, o algoritmo quicksort é o mais popular, pois na maioria das situações ele roda mais rápido que outros. Sua complexidade de tempo é O(N*logN).

Mesclar classificação

Este tipo também é popular. É um dos muitos algoritmos que se baseia no princípio de "dividir e conquistar". Tais algoritmos primeiro dividem o problema em partes gerenciáveis ​​(quicksort é outro exemplo de tal algoritmo). Então, qual é a essência desse algoritmo?

Dividir:

A matriz é dividida em duas partes de aproximadamente o mesmo tamanho. Cada uma dessas duas partes é dividida em mais duas, e assim por diante até que restem as menores partes indivisíveis possíveis. Temos as menores partes indivisíveis quando cada array tem um elemento, ou seja, um array que já está ordenado.

Conquistar:

É aqui que começamos o processo que deu nome ao algoritmo: merge. Para fazer isso, pegamos as duas matrizes classificadas resultantes e as mesclamos em uma. Nesse caso, o menor dos primeiros elementos dos dois arrays é escrito no array resultante. Esta operação é repetida até que todos os elementos nestas duas matrizes tenham sido copiados. Ou seja, se tivermos dois arrays mínimos {6} e {4}, comparamos seus valores e geramos este resultado mesclado: {4,6}. Se classificarmos os arrays {4,6} e {2,8}, primeiro comparamos os valores 4 e 2 e, em seguida, escrevemos 2 no array resultante. Depois disso, 4 e 8 serão comparados e escreveremos 4. Finalmente, 6 e 8 serão comparados. Assim, escreveremos 6 e somente depois disso escreveremos 8. Como resultado, obtemos o seguinte array mesclado: {2,4,6,8}. Como isso ficará no código Java? Para executar este algoritmo, será conveniente usar recursão:

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); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       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;
   }
}

Assim como na ordenação rápida, movemos o método recursivo para um método intermediário, de forma que o usuário só precise fornecer o array a ser classificado e não precise se preocupar em fornecer nenhum argumento padrão adicional. Esse algoritmo tem semelhanças com o quicksort e, sem surpresa, sua velocidade de execução é a mesma: O(N*logN).

2. Algoritmos gananciosos

Um algoritmo guloso é uma abordagem em que decisões localmente ótimas são tomadas em cada estágio, com a suposição de que a solução final também será ótima. A solução "ótima" será aquela que oferecer o benefício mais óbvio e imediato em qualquer etapa/estágio específico. Para explorar esse algoritmo, vamos pegar um problema bastante comum — o problema da mochila. Finja por um momento que você é um ladrão. Você invadiu uma loja à noite com uma mochila (mochila). À sua frente estão vários bens que você pode roubar. Mas, ao mesmo tempo, sua mochila tem capacidade limitada. Não pode transportar mais de 30 unidades de peso. Você também deseja levar o conjunto de mercadorias mais valioso que caberá na mochila. Como você determina o que colocar em sua bolsa? Então,

1. Escolha o item mais caro que ainda não foi levado.
2. Se couber na mochila, coloque-o. Se não, deixe-o.
3. Já roubamos tudo? Se não, voltamos ao passo 1. Se sim, então fugimos rapidamente da loja, pois cumprimos o que viemos fazer.

Vejamos isso, mas em Java. É assim que a classe Item ficará:

public class Item implements Comparable {
   private String name;
   private int weight;
   private int value;

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

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

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

Não há nada de especial aqui: três campos (nome, peso, valor) que definem as características do item. Além disso, como você pode ver, a interface Comparable foi implementada para nos permitir classificar nossos itens por preço. A seguir, veremos a classe Bag, que representa nossa mochila:

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

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

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

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

• maxWeight é a capacidade de nossa mochila, que é definida quando criamos um objeto;
• itens representa os objetos em nossa mochila;
• currentWeight , currentValue — esses campos armazenam o peso e o valor atuais de todos os itens na mochila, que aumentamos quando adicionamos um novo item no método addItem.

De qualquer forma, vamos agora para a classe onde toda a ação ocorre:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
} 

Primeiro, criamos uma lista de itens e a classificamos. Criamos um objeto saco com capacidade para 30 unidades. Em seguida, passamos os itens e o objeto bag para o método fillBackpack, que preenche a mochila de acordo com nosso algoritmo guloso:

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

É bem simples: começamos a percorrer uma lista de itens classificados por custo e colocando-os na sacola se a capacidade permitir. Se não houver espaço suficiente, o item será ignorado e continuaremos percorrendo o restante dos itens até chegar ao final da lista. Depois de executar o main, aqui está a saída do console que obteremos: Este é um exemplo de algoritmo guloso: a cada passo, uma solução localmente ótima é selecionada e, no final, obtém-se uma solução globalmente ótima. No nosso caso, a melhor opção é o item mais caro. Mas será esta a melhor solução? Você não acha que é possível melhorar um pouco nossa solução para encher nossa mochila com itens de valor total ainda maior? Vamos dar uma olhada em como isso pode ser feito.

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

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

Aqui, primeiro calculamos a relação valor/peso para cada item. Isso nos diz o valor de cada unidade de um determinado item. E então usamos essas proporções para classificar nossos itens e adicioná-los à nossa sacola. Vamos executar o seguinte:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

Obtemos esta saída do console: Um pouco melhor, não é? O algoritmo guloso faz uma escolha localmente ótima a cada passo, esperando que a solução final também seja ótima. Essa suposição nem sempre é válida, mas para muitas tarefas, algoritmos gananciosos produzem uma solução final ótima. A complexidade de tempo deste algoritmo é O(N). Muito bom, hein?