BastterCode semana 7 - Longest Common Prefix
comentada em 01/03/2023 20:16

postado por @alyssoncs em 24/02/2023 22:04

Acho essa aqui bacaninha
LeetCode - The World's Leading Online Programming Learning Platform

Já me perguntaram em entrevista.

Curiosidade, numa entrevista, quanto tempo vc tem pra responder uma questão como essa? Ordem de grandeza, é tipo 3 minutos ou 30 minutos?

Pra mim essa aí ou a de ordenação diagonal que Giovanni tinha mandado estão boas.

Quase acabando a semana, solução bem simples em Java:

@maxete Eu imagino que depende muito de cada empresa/entrevistador.
No meu caso em particular 45min de entrevista total, mas teve bate papo, de tempo restante pra responder a questão, eu acho que foi uns 30min

postado por @Giovanni em 24/02/2023 20:35

pessoal que tá participando, nada mais adequado do que ver com vocês o próximo desafio semanal

coloquem sugestões por favor
e uma questão média para gente lançar no desafio mensal

obrigado

Eu sou noob, não tenho condições de saber qual problema é melhor ou pior kkk

Pra mim, qualquer um tá bom pra aprender e me divertir. 

Pessoal que conhece bem Python, principalmente no que diz respeito à eficiência do código:

figura 1:

figura 2:



O código da figura 2 rodou mais rápido do que o da figura 1, mesmo este último tendo um break na condição if else.

Será que foi por causa do List Comprehension no código da figura 2?
Em pesquisas na Internet, pessoal tem notado que na prática tende a ser um pouco mais rápido que outros métodos (map, reduce, filter, loop).

Tentei aqui soluções também com map e filter, mas foram mais lentas que o for loop com break.

@shadow_walker

Esses tempos e memória variam muito. Você pode enviar a mesma resposta várias vezes para perceber a variação. 

Tipo, você até consegue identificar um padrão de eficiência, mas por ordem de grandeza. Um código de 300ms é quase com certeza menos eficiente que um de 30ms. Mas entre 24 e 28ms pode ser só a variação normal do sistema deles.

Pra você ver como muda muito, no problema de uma das semanas anteriores eu rodei o mesmo código diversas vezes e variou desde 0ms até 8 ms. Percebi que o tempo muda até com a velocidade da conexão de internet.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {       
        int inf = 0, sup = strs[0].size(); 

//inf representa o menor valor da posição do prefixo comum e sup
//representa o valor imediatamente acima ao maior que a posição
//pode assumir. Como inf é inicializado como 0, há uma ambiguidade
//que o algoritmo precisa levar em consideração
        
        while ((!(sup-inf == 1))||(inf == 0)){

//O algoritmo roda até que a posição esteja imediatamente abaixo da
//posição superior e inf seja diferente de 0 (devido à ambiguidade).
//Isso quer dizer que o while não quebra sozinho se o prefixo comum
//tiver exatamente uma letra (que corresponde à posição 0 no inf).
//Ou seja, é preciso haver uma quebra manual. 

            int length = inf+(sup-inf)/2+1;

//length indica o tamanho da substring que será comparada entre palavras.
//Ela é no mínimo igual a inf+1, pois as posições indicadas por inf
//são certas e não precisam mais ser comparadas. A adição de (sup-inf)/2
//indica que apenas os caracteres até a metade da zona de incerteza são
//comparados e, logo, length decresce exponencialmente (potência de 2)
//a cada iteração.
            
            for (int i = 0; i < strs.size(); i++){

//O tamanho de strs é o n° de palavras. Ou seja, itera 1 vez por palavra

                if (length > strs[i].size() || 
            strs[i].compare(inf, length-inf, strs[0], inf, length-inf) != 0){

//se length for maior que alguma das palavras ou se a substring comparada for
//distinta, então a maior posição do prefixo comum é menor que length
   
                    sup = length-1;

                    if (sup == 0){
                        return "";} 

//se sup chega a 0, significa que não há prefixo em comum 
                               
                    break;

//se houver alguma inconsistência, o for pode quebrar

                } else if (i+1 == strs.size()) {

//se chegar ao final do for sem inconsistência, então a substring comparada
//é comum a todas aa palavras. Ou seja, inf é no mínimo a posição indicada por
//length. Como as posições começam do 0 (um prefixo em comum de 2 corresponde à
//posição 1, por exemplo), é preciso reduzir 1 de length antes de igualar a inf
                    
                    inf = length-1;

                    if (inf == 0 && sup-inf == 1){

//se inf é zero depois do loop for, aignifica que já foi testada a posição 0 e
//nesse caso não há mais ambiguidade no valor de inf (ele indica que o prefixo
//comum é no mínimo igual a um caractere). Se além disso sup-inf é igual a 1,
//então inf não pode ser maior que 0 e o prefixo comum é de apenas 1 caractere.
//Em qualquer outra situação, inf necessariamente aumentará na execução do
//algoritmo, então este if é suficiente para remover a ambiguidade de inf e quebrar
//o while devidamente

                        return strs[0].substr(0,1);
                    }        
                }
            }            
        }

//retorna a substring formada por qualquer uma das palavras desde a posição inicial
//até a posição imediatamente anterior a sup. Poderia ser usado inf+1 igualmente.
//Não é possível usar length porque ela foi declarada dentro do while
           
        return strs[0].substr(0, sup);
    }
};

Uma solução alternativa, inspirada no que o @FlyCavok comentou sobre o divide and conquer. 

Inicialmente eu usei a função substr para gerar a substring a ser comparada, mas percebi que isso seria ineficiente, já que eu só precisaria ler a substring, não escrever. Fui pesquisar as funções da biblioteca de string do C++ e descobri a função compare, que me permite comparar strings ou substrings de forma mais eficiente.

Sugestão para o próximo: LeetCode - The World's Leading Online Programming Learning Platform
problema fácil com a menor taxa de acerto

defmodule Solution do
  @spec longest_common_prefix(strs :: [String.t()]) :: String.t()
  def longest_common_prefix(strs) do
    shortest =
      strs
      |> Enum.sort_by(&String.length/1)
      |> List.first()

    max_length = String.length(shortest)

    codepoints = Enum.map(strs, &to_str_map(&1, max_length))

    shortest
    |> to_str_map(max_length)
    |> Enum.take_while(fn {idx, letter} -> Enum.all?(codepoints, &(&1[idx] == letter)) end)
    |> Enum.map(fn {_idx, letter} -> letter end)
    |> Enum.join("")
  end

  def to_str_map(str, max) do
    str |> String.codepoints() |> Enum.take(max) |> Enum.with_index(&{&2, &1}) |> Enum.into(%{})
  end
end