Enquanto estudava o desempenho de algoritmos, me deparei com este . Ele não apenas oferece uma visão de como são as entrevistas em grandes corporações tecnológicas, mas também permite entender como resolver problemas algorítmicos de forma máxima e eficiente.
Este artigo é uma espécie de acompanhamento do vídeo. Nele, dou comentários sobre todas as soluções apresentadas, além da minha própria versão da solução em JavaScript. Também discuto os detalhes de cada algoritmo.
Lembramos: para todos os leitores do «Habr» — desconto de 10.000 rublos na inscrição em qualquer curso Skillbox com o código promocional «Habr».
A Skillbox recomenda: Curso Prático .
Formulação do problema
Nos dão um array ordenado e um valor específico. Em seguida, solicitam que criemos uma função que retorne true ou false, dependendo se a soma de quaisquer dois números do array pode ser igual ao valor determinado.
Em outras palavras, existem dois números inteiros x e y no array que, quando somados, são iguais ao valor especificado?
Exemplo A
Se nos foi dado o array [1, 2, 4, 9] e o valor 8, a função retornará false, pois nenhum par de números do array pode somar 8.
Exemplo B
Mas se for o array [1, 2, 4, 4] e o valor 8, a função deve retornar true, pois 4 + 4 = 8.
Solução 1. Força bruta
Complexidade de tempo: O(N²).
Complexidade espacial: O(1).
A solução mais óbvia é usar um par de loops aninhados.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};Esta solução não pode ser considerada eficiente, pois verifica cada soma possível de dois elementos no array e compara cada par de índices duas vezes. (Por exemplo, quando i = 1 e j = 2 — isso é basicamente o mesmo que comparar i = 2 e j = 1, mas nesta solução tentamos ambas as opções).
Como nossa solução usa um par de loops for aninhados, ela é quadrática com uma complexidade de tempo de O (N²).
Solução 2. Busca binária
Complexidade de tempo: O(Nlog(N)).
Complexidade espacial: O(1).
Como os arrays são ordenados, podemos procurar uma solução usando busca binária. Este é o algoritmo mais eficiente para arrays ordenados. A busca binária em si tem um tempo de execução de O (log (N)). No entanto, ainda é necessário usar um loop for para verificar cada elemento contra todos os outros valores.
Veja como pode ser a solução. Para que tudo fique claro, usamos uma função separada para controlar a busca binária. Também utilizamos a função removeIndex(), que retorna uma versão do array sem o índice especificado.
const findSum = (arr, val) => {
for (let i = 0; i {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};O algoritmo começa com o índice [0]. Em seguida, ele cria uma versão do array, excluindo o primeiro índice, e utiliza a busca binária para verificar se algum dos valores restantes pode ser adicionado ao array para obter a soma desejada. Essa ação é realizada uma vez para cada elemento do array.
O próprio loop for terá uma complexidade de tempo linear O(N), mas dentro do loop for estamos realizando uma busca binária, resultando em uma complexidade de tempo total de O(Nlog(N)). Esta solução é melhor que a anterior, mas ainda há espaço para melhorias.
Solução 3. Tempo linear
Complexidade de tempo: O(N).
Complexidade espacial: O(1).
Agora vamos resolver o problema, lembrando que o array está ordenado. A solução consiste em pegar dois números: um no início e outro no fim. Se o resultado diferir do desejado, nós trocamos o ponto inicial e final.
No final, ou encontraremos o valor desejado e retornaremos true, ou os pontos inicial e final se encontrarão e retornaremos false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Agora tudo parece bom, a solução parece otimizada. Mas quem pode garantir que o array estava ordenado?
E agora?
À primeira vista, poderíamos simplesmente ordenar o array primeiro e depois usar a solução acima. Mas como isso afetará o tempo de execução?
O melhor algoritmo é o QuickSort com complexidade de tempo O(Nlog(N)). Se o utilizarmos em nossa solução otimizada, sua eficiência mudará de O(N) para O(Nlog(N)). Será que é possível encontrar uma solução linear com um array não ordenado?
Solução 4
Complexidade de tempo: O(N).
Complexidade de espaço: O(N).
Sim, existe uma solução linear, para isso precisamos criar um novo array contendo a lista de coincidências que estamos procurando. O compromisso aqui está no uso mais ativo da memória: esta é a única solução no artigo com complexidade espacial superior a O(1).
Se o primeiro valor deste array for 1 e o valor procurado for 8, podemos adicionar o valor 7 ao array "valores de busca".
Então, ao processar cada elemento do array, podemos verificar o array "valores de busca" e ver se um deles é igual ao nosso valor. Se sim, retornamos true.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};A base da solução é um loop for, que, como vimos acima, tem complexidade temporal linear O(N).
A segunda parte iterativa da nossa função é Array.prototype.includes(), um método JavaScript que retornará true ou false dependendo se o array contém o valor especificado.
Para descobrir a complexidade temporal do Array.prototype.includes(), podemos considerar o polyfill fornecido pelo MDN (e escrito em JavaScript), ou usar o método no código fonte do motor JavaScript, como o Google V8 (C++).
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n ≥ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}Aqui, a parte iterativa do Array.prototype.includes() é um loop while no passo 7, que (quase) percorre toda a extensão deste array. Isso significa que sua complexidade temporal também é linear. E, como está sempre um passo atrás do nosso array principal, a complexidade temporal é O(N + (N - 1)). Usando a Notação Big O, simplificamos essa complexidade para O(N) — pois é N que mais impacta com o aumento do tamanho da entrada.
Quanto à complexidade espacial, um array adicional é necessário, cuja extensão reflete o array original (menos um, sim, mas isso pode ser ignorado), o que leva a uma complexidade espacial O(N). E o uso aumentado de memória proporciona eficiência máxima ao algoritmo.
Espero que o artigo seja útil para você como um complemento à vídeo-entrevista. Ele mostra que uma tarefa simples pode ser resolvida de várias maneiras diferentes com diferentes quantidades de recursos utilizados (tempo, memória).
A Skillbox recomenda:
- Curso Online Aplicado .
- Curso online .
- Curso prático de um ano .
Fonte: habr.com
