Guía de preguntas de la entrevista de Google: eliminar personajes recurrentes con Python

Hoy en día, las entrevistas de Google están de moda. Pero a veces, las entrevistas pueden sacar lo mejor de nosotros. Especialmente si es para un puesto que realmente queremos.

Tuve el placer de entrevistarme en varias empresas importantes como estudiante y conseguir un trabajo en Silicon Valley como ingeniero de software.

¡Mi objetivo es ayudarte a conseguir el trabajo de tus sueños que siempre has querido!

Vamos a repasar una pregunta clásica que podría aparecer en su próxima entrevista de Google.

Advertencia: si es un veterano de la codificación, probablemente ya sepa cómo resolver esta pregunta.

Si está tratando de obtener una pasantía o un trabajo a tiempo completo el próximo año, definitivamente se beneficiará de este artículo. ???

PREGUNTA: Dada una cadena como entrada, elimine cualquier carácter recurrente y devuelva la nueva cadena.

Si prefiere un video para explicar la pregunta, hice uno aquí.

Como podemos ver en el ejemplo anterior, la salida es "abc" porque eliminamos la segunda 'a', 'b' y 'c'.

Lo primero es lo primero, configuremos nuestra función en Python 2.7.

def deleteReoccurringCharacters(string):

Para abordar esta pregunta, usaremos una estructura de datos específica llamada HashSet.

Puede pensar que un conjunto es similar a una matriz, con dos excepciones principales.

  1. Esta completamente desordenado
  2. No puede contener duplicados

Debido a que no está ordenado, también necesitaremos una cadena vacía para almacenar los caracteres que hemos agregado al conjunto en orden. Esta será la cadena que devolveremos.

Configuremos ambas cosas.

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = ''

Ahora que hemos configurado las estructuras de datos que necesitamos, hablemos de nuestro algoritmo.

Debido a la forma en que un conjunto funciona en la memoria, tiene una complejidad de tiempo de búsqueda de 0 (1).

¡Esto significa que podemos usarlo para verificar si ya hemos visitado un personaje!

Nuestro algoritmo

Recorra todos los caracteres de la cadena inicial y haga lo siguiente:

Paso 1: Verifique si el carácter ya está en nuestro conjunto Paso 2: Si no está en el conjunto, agréguelo al conjunto y añádalo a la cadena

Veamos cómo se vería eso en el código.

for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char

No tenemos que preocuparnos por un caso "más", porque no hacemos nada con el personaje recurrente en sí.

Ahora todo lo que queda por hacer es devolver el outputString.

Así es como se ve el código terminado:

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char return outputString

¡Y ahí lo tienes!

Ahora bien, si se tratara de una entrevista, su reclutador le preguntaría sobre la complejidad del tiempo y el espacio.

Hagamos un pequeño análisis.

Complejidad del tiempo

La iteración a través de toda la cadena de entrada tiene una complejidad de tiempo de O (n), ya que hay n caracteres en la propia cadena.

Para cada uno de esos personajes, tenemos que verificar si hemos visto o no… Sin embargo, dado que un HashSet tiene un tiempo de búsqueda de O (1), nuestra complejidad de tiempo no se ve afectada.

Dejándonos con una complejidad de tiempo final de O (n).

Complejidad espacial

En el peor de los casos, obtenemos una cadena con todos los caracteres únicos. Por ejemplo, "abcdef".

En ese caso, almacenaríamos todos los n elementos en nuestra cadena y nuestro conjunto.

Sin embargo, también estamos limitados al tamaño del alfabeto inglés.

Esta es una buena oportunidad para preguntarle a nuestro entrevistador qué tipo de caracteres cuentan como únicos en la cadena (mayúsculas / minúsculas / números / símbolos).

Suponiendo que la cadena inicial contendrá letras minúsculas del alfabeto, dado que el alfabeto es finito, nuestro conjunto y cadena de salida nunca pueden tener más de 26 caracteres.

Dejándonos con una complejidad espacial de O (1) en el peor de los casos .

¡Ahora sabe cómo resolver una pregunta de una entrevista de Google!

Es probable que esta pregunta surja en las primeras etapas de la entrevista debido a su sencillez ... Como la prueba en línea o la primera llamada telefónica.

Si eres un aprendiz visual como yo, mira este video que hice explicando más la solución. Todos los días creo un nuevo video tutorial que gira en torno a comenzar su carrera en software.

I’ve also posted the finished code on Github here.

Thanks for watching, and good luck!

.a #33