Este código funciona usando un vector de bits (representado por los bits de un entero de 32 bits). La mejor manera de entender este código es pensar en el checker en términos de su representación binaria.
Como el checker es un entero de 32 bits asignado a 0, su representación binaria es:
000000000000000000000000000000000
- ¿Es realmente importante el análisis de algoritmos para codificar entrevistas cuando solo puede descubrir complejidades de casos generales (como nlog (n), etc.)?
- ¿Conocer solo C es una desventaja en las entrevistas técnicas?
- ¿Cuáles son algunos de los temas / conceptos más importantes para el examen APAC de Google para estudiantes universitarios de 2016?
- ¿Qué tan importante es conocer los patrones de diseño para entrevistas para un desarrollador experimentado?
- Al hacer una entrevista de codificación de pizarra y te quedas atascado, ¿está bien explicarle al entrevistador cómo usarías Google para encontrar una respuesta?
Ahora tenemos 32 ceros. Como verá en la explicación que sigue, cada cero representa una letra del alfabeto, así:
000000000000000000000000000000000
-------zyxwvutsrqponmlkjihgfedcba
Además, cambiamos un poco de 0 a 1 si hemos visto el personaje correspondiente. Si vemos un personaje por segunda vez, el bit ya será 1, por lo que sabremos si lo hemos visto antes. Si hemos visto el mismo personaje dos veces, entonces nuestra cadena tiene duplicados.
Ahora veamos el código. Después de establecer el
checker en cero, el código recorre cada carácter de la cadena. Luego, calcula qué letra del alfabeto es ese carácter restando ‘a’ (la resta cambia ‘a’ a su representación ASCII, 97).
Entonces, si tenemos la cadena “abc”, hacemos un bucle:
una:
Valor ASCII = 97
97 – ‘a’ = 97 – 97 = 0
si:
Valor ASCII = 98
98 – ‘a’ = 98 – 97 = 1
C:
Valor ASCII = 99
99 – ‘a’ = 99-97 = 2
Dado que el código resta “a”, esencialmente supone que la cadena contiene letras minúsculas solamente .
Ahora analicemos la primera comprobación “si”. Primero, lo hace (1 << val) . Entonces, si tiene la letra “g”, obtenemos val = 6 . En consecuencia, (1 << val) es 1000000 . Luego hacemos un bit a bit Y:
000000000000000000000000000000000 :: checker, bit vector)
000000000000000000000000001000000 :: (1 << val), mask for "g"
El bit a bit Y simplemente verifica si el valor en la ranura para “g” está establecido en 1. Si es así, devolvemos falso. La razón es esta: más adelante, estableceremos el espacio para cada letra en “1” a medida que recorremos las letras. Si previamente hemos establecido un espacio en “1”, entonces ya hemos visto la letra correspondiente a ese espacio.
El código para establecer el espacio para una letra en “1” cuando nos encontramos con la letra es:
checker |= ( 1 << val );
Hacemos un OR bit a bit para establecer el bit en la ranura correspondiente a “g” en 1.
Espero que tenga sentido. Entonces, si tuviéramos la palabra “dab”, entonces la variable de checker se vería como la siguiente en binario:
000000000000000000000000000001011
Por lo tanto, el código es básicamente como tener una tabla hash e iterar sobre las letras, agregando cada una a la tabla hash con un valor de 1. Si alguna vez intenta agregar una letra a la tabla hash que ya está allí, tiene un duplicado .