¿Cuál es el problema planteado en Verifying Alien Dictionary?
En este fascinante ejercicio de programación, nos enfrentamos a un reto que aparece en entrevistas de empresas tecnológicas destacadas como Facebook, Microsoft y Google. El problema "Verifying Alien Dictionary" involucra una lengua alienígena que, inesperadamente, utiliza las letras que conocemos en el español, aunque posiblemente en un orden diferente. Se nos presenta un conjunto de palabras escritas en este idioma y debemos determinar si las palabras están ordenadas de acuerdo al orden alfabético definido para ese idioma.
¿Cómo entender lo que nos piden hacer?
Este problema se basa en una comparación lexicográfica de palabras:
["apple", "app"]."hlabcdefgijkmnopqrstuvwxyz".true si las palabras están ordenadas siguiendo las reglas del alfabeto alienígena; false en caso contrario.¿Cómo interpretar las reglas para las palabras?
Para poder verificar si las palabras están ordenadas, debemos seguir estos pasos:
¿Por qué las entrevistas de trabajo valoran este problema?
Este tipo de ejercicio mide varias habilidades esenciales en programación:
Aunque no es un problema extremadamente complejo, los entrevistadores buscan ver cómo los candidatos piensan sistemáticamente y cómo abordan desafíos que pueden requerir una comprensión detallada de algoritmos básicos y estructuras de datos.
¡Consejos para resolverlo!
Tómate el tiempo necesario para formular tu solución antes de avanzar. Este es un gran ejercicio para mejorar tus habilidades de programación y lógica, así que ¡anímate y pon a prueba tus conocimientos!
En este fascinante ejercicio de programación, nos enfrentamos a un reto que aparece en entrevistas de empresas tecnológicas destacadas como Facebook, Microsoft y Google. El problema "Verifying Alien Dictionary" involucra una lengua alienígena que, inesperadamente, utiliza las letras que conocemos en el español, aunque posiblemente en un orden diferente. Se nos presenta un conjunto de palabras escritas en este idioma y debemos determinar si las palabras están ordenadas de acuerdo al orden alfabético definido para ese idioma.
Este problema se basa en una comparación lexicográfica de palabras:
["apple", "app"]."hlabcdefgijkmnopqrstuvwxyz".true si las palabras están ordenadas siguiendo las reglas del alfabeto alienígena; false en caso contrario.Para poder verificar si las palabras están ordenadas, debemos seguir estos pasos:
Este tipo de ejercicio mide varias habilidades esenciales en programación:
Aunque no es un problema extremadamente complejo, los entrevistadores buscan ver cómo los candidatos piensan sistemáticamente y cómo abordan desafíos que pueden requerir una comprensión detallada de algoritmos básicos y estructuras de datos.
Tómate el tiempo necesario para formular tu solución antes de avanzar. Este es un gran ejercicio para mejorar tus habilidades de programación y lógica, así que ¡anímate y pon a prueba tus conocimientos!
Para ayudar a otros que no entendieron a la primera y tuvieron que buscar en documentación en otros idiomas.
Primero: "lexicograficamente" para efectos de este problema es ordenar palabras de la misma manera en como un diccionario ordena las palabras.
conocer vs cono = cono deberia estar primero porque al ser mas corta, gana prioridad.
Entonces en el caso donde
palabras = [conocer, cono] orden_alfabeto= NUESTRO ALFABETO
da un RETURN false por lo que mencione mas arriba
Entonces la cosa seria algo como: recibimos dos entradas:
Debes decirme con un true/false si "palabras" esta ordenado como un diccionario si dicho diccionario tuviera un orden alfabetico como el ingresado en "orden_alfabetico"
Les comparto mi solucion en JavaScript
const alphabet0 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']
const alphabet1 = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']
function alienDictionary(wordsArray, dictionary) {
dictionary = Array.from(dictionary)
const comparer = (word1, word2) => {
word1 = Array.from(word1)
word2 = Array.from(word2)
for (let index = 0; index < word1.length; index++) {
const index1 = dictionary.findIndex(element => element === word1[index])
const index2 = dictionary.findIndex(element => element === word2[index])
if (index2 === index1) { }
else if (index2 < index1) return false
else return true
}
}
for (let index = 0; index < wordsArray.length; index++) {
if (index === 0) { }
else if (!comparer(wordsArray[index - 1], wordsArray[index])) return false
}
return true
}
console.log(alienDictionary(['habito', 'hacer', 'lectura', 'sonreir'], alphabet1))
Ejemplos
# Input
palabras = ['conocer', 'cono']
orden_alfabeto = 'abcdfghijklmnopqrstuvwxyz'
# Ouput:
False
# Input
palabras = ['habito', 'hacer', 'lectura', 'sonreir']
orden_alfabeto - 'hlabcdefgikmnopqrstuvqxyz'
# Output:
True
Use gemini para guiarme, admito que hizo bastante del trabajo, aunque me asegure de entender y sus explicaciones.
const words = \["apple", "app"];
const alphabet = "hlabcdefgijkmnopqrstuvwxyz";
function verifyAlienDictionary(words: string\[], alphabet: string) {
  // 1 hash map
  const hashMap = new Map\<string, number>();
  // console.log({hashMap});
  for (let i = 0; i \< alphabet.length; ++i) {
  const letter = alphabet\[i];
  hashMap.set(letter, i);
  }
  // console.log({hashMap});
  for (let i = 0; i \< words.length - 1; i++) {
  const word1 = words\[i];
  const word2 = words\[i + 1];
  let foundDifference = false;
  const minLength = word1.length > word2.length ? word2.length : word1.length;
  for (let j = 0; j \< minLength; j++) {
  const rank1 = hashMap.get(word1\[j]);
  const rank2 = hashMap.get(word2\[j]);
  if (rank1 !== rank2) {
  if (rank1 > rank2) return false;
  foundDifference = true;
  break;
  }
  }
  if (!foundDifference && word1.length > word2.length) {
  return false;
  }
  }
  return true;
}
const isLexiphabet = verifyAlienDictionary(words, alphabet);
console.log({isLexiphabet});
Aqui el problema en LeetCode
Lexicograficamente: de un modo relacionado con los diccionarios, o con la escritura, edición o compilación de diccionarios.
//const palabras = ['habito', 'hacer', 'lectura', 'sonreir']
//const ordenDelAbecedario = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']
const palabras = ["conocer", "cono"]
const ordenDelAbecedario = [
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'ñ', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
];
let estanOrdenadas = true
for(let indiceDeLaPalabra = 0; indiceDeLaPalabra < palabras.length; indiceDeLaPalabra ++) {
if(palabras[indiceDeLaPalabra + 1] === undefined) {
break
}
const palabra = palabras[indiceDeLaPalabra]
const siguientePalabra = palabras[indiceDeLaPalabra + 1]
for(let indiceDeLaLetra = 0; indiceDeLaLetra < palabra.length; indiceDeLaLetra++) {
const letra = palabra[indiceDeLaLetra]
const letraDeLaSiguientePalabra = siguientePalabra[indiceDeLaLetra]
if(letra === letraDeLaSiguientePalabra) {
continue
}
let posicionDeLaLetraEnElAbecedario = 0
let posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario = 0
for(let indiceDeLetraEnElAbecedario = 0; indiceDeLetraEnElAbecedario < ordenDelAbecedario.length; indiceDeLetraEnElAbecedario++){
if(ordenDelAbecedario[indiceDeLetraEnElAbecedario] === letra) {
posicionDeLaLetraEnElAbecedario = indiceDeLetraEnElAbecedario
break
}
}
for(let indiceDeLetraEnElAbecedario = 0; indiceDeLetraEnElAbecedario < ordenDelAbecedario.length; indiceDeLetraEnElAbecedario++){
if(ordenDelAbecedario[indiceDeLetraEnElAbecedario] === letraDeLaSiguientePalabra) {
posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario = indiceDeLetraEnElAbecedario
break
}
}
if(posicionDeLaLetraEnElAbecedario > posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario) {
estanOrdenadas = false
}
break
}
}
console.log(estanOrdenadas)
Mi resolución en Python:
def cargaDiccionario(alfabeto):
# el diccionario se carga con el criterio de mayor valor para la primer letra del alfabeto y numeros descendentes secuenciales hasta el menor valor para la última letra
# en el caso de abecedario accidental: a=26 y z=1
dicc_tmp={}
for i in range(0,len(alfabeto)):
dicc_tmp[alfabeto[i].upper()]=len(alfabeto)-i
return dicc_tmp
def palabras_ordenadas(palabra1,palabra2):
# esta función devuelve True si palabra1 esta correctamente ordenada en relación a palabra2, de lo contrario devuelve false
# -> No es case sensitive los textos se evaluan en mayúscula. Amor y aMOR son iguales.
# -> cadena vacía o espacios vacíos se ordenan primero, por lo tanto [' ','hola','casa'] resuelve en Verdadero
# -> Si en una cadena aparece un caracter que no está en el alfabeto, se dá por concluida la evaluación devolviendo False.
palabra1=palabra1.upper()
palabra2=palabra2.upper()
# si ambas palabras son iguales, devuelve True
if palabra1==palabra2:
return True
global dicc_alfabeto
# tomo como referencia la primer palabra
for i in range(0,len(palabra1)):
# Si no se resolvió la comparación quiere decir que hubo igualdad. Luego, si el indice i que responde al len de palabra1 es mayor al len de palabra2
# significa que hasta ahora son iguales pero palabra1 es más larga que palabra2 y por ende, palabra2 debería estar primero. asi que devolvemos false
if (i+1>len(palabra2)):
return False
# si aparece un caracter que no es una de las letras del alfabeto, devuelvo false
if (palabra1[1] not in dicc_alfabeto or palabra2[1] not in dicc_alfabeto):
return False
# Si la letra evaluada en palabra1 es menor a la misma posición de letra en palabra2, devuelve False
if (dicc_alfabeto[palabra1[i]]<dicc_alfabeto[palabra2[i]]):
return False
# Si la letra evaluada en palabra1 es mayor a la misma posición de letra en palabra2, devuelve True
if (dicc_alfabeto[palabra1[i]]>dicc_alfabeto[palabra2[i]]):
return True
# Para cualquier otra situación, se devuelve True
return True
def valida_orden_lista(lista_palabras):
for i in range(0,len(lista_palabras)-1):
print ("indice {} es {}".format(i,lista_palabras[i]))
if (palabras_ordenadas(lista_palabras[i].strip(),lista_palabras[i+1].strip())==False):
return False
return True
# Carga del alfabeto a utilizar
# alfabeto_alien='hlabcdefgijkmnopqrstuvqxyz'
# alfabeto_occid='abcdefghijklmnopqrstuvqxyz'
dicc_alfabeto=cargaDiccionario('hlabcdefgijkmnopqrstuvqxyz')
# listas de prueba
lista_palabras=['cono','conocer','foniatra']
lista_palabras=['hijo', 'hijos', 'papa', 'celular3']
lista_palabras=['hijos', ' ', 'papa']
valida_orden_lista(lista_palabras)
Despues de mucho pensarlo logre algo en scala
import scala.util.control.Breaks.break
class alien\_words {
  private def generatePositions(arr: Array\[String]): Map\[Int, Int] = {
  arr.zipWithIndex
  .map {
  case (item, index) => (index, 0)
  }.toMap
  }
  private def generateMapValueAlphabet(str: String): Map\[Char, Int] ={
  str
  .toCharArray
  .zipWithIndex
  .map { case (char, index) =>
  char -> index
  }.toMap
  }
  private def sumItemsToMap(positionsVal: Map\[Int,Int],
  mapValue:Map\[Char,Int],
  arr: Array\[String],
  index:Int):
  Map\[Int, Int] = {
  positionsVal.map {
  case (key, value) => (key, value +
  mapValue(arr(key)(index))
  )
  }
  }
  def processArray(arr: Array\[String], str: String): Boolean = {
  var positionsVal = generatePositions(arr)
 val mapValue =generateMapValueAlphabet(str)
  // Example logic: print each element of the array with the string
  var index=0
  while (true) {
  try {
  positionsVal = sumItemsToMap(
  positionsVal,
  mapValue,
  arr,
  index
  )
  var aux = positionsVal(0)
  *println*(aux)
  for (i <-1 until positionsVal.keys.size-1) {
  if (aux>=positionsVal(i)){
  aux=positionsVal(i)
  }else{
  return false
  }
  }
  index += 1
  if (index>3){
  return true
  }
  } catch {
  case e: IndexOutOfBoundsException=> return true
  }
  }
  false
  }
}
object AlienWords {
  def main(args: Array\[String]): Unit = {
  val word = Array("habito", "hacer", "lectura", "sonreir")
  val orden\_alfabeto = "hlabcdefgijkmnopqrstuvwxyz"
  val al = new alien\_words()
  // Measure execution time
  val startTime = System.*nanoTime*() // Start time in nanoseconds
  al.processArray(word, orden\_alfabeto)
  val endTime = System.*nanoTime*() // End time in nanoseconds
  val duration = (endTime - startTime) / 1e6 // Convert nanoseconds to milliseconds
  *println*(s"Execution time: $duration ms")
  }
}