Enunciado y contexto
Dado un arreglo words y un entero k, devuelve las k palabras más frecuentes. Desempata en orden lexicográfico ascendente.
La entrevista se centra en mantener un conjunto de candidatos de tamaño k y decidir si la raíz del heap representa al peor o al mejor candidato. Java se utiliza únicamente para demostrar un comparador; el algoritmo es independiente del lenguaje.
Qué evalúa el entrevistador
Conteo
Utilizar un hash map para contar cada palabra y distinguir la longitud del arreglo n del conteo de palabras únicas m.
Reglas de ordenamiento
Mayor frecuencia gana; a igual frecuencia se utiliza el orden lexicográfico menor. La raíz del min-heap debe ser el peor candidato para que se puedan eliminar las entradas excedentes.
Complejidad
El ordenamiento completo es O(m log m). Un heap de tamaño k es O(n + m log k), útil cuando k es mucho menor que el número de palabras únicas.
Correctitud
Explicar por qué el orden del heap para la expulsión difiere del orden de la salida final: el heap elimina al peor candidato, mientras que la respuesta debe listar primero a los mejores candidatos.
Preguntas de clarificación para hacer
- ¿Las palabras están en minúsculas en inglés y distinguen entre mayúsculas y minúsculas?
- ¿Se garantiza que k esté entre 1 y el número de palabras únicas?
- ¿El orden lexicográfico es ASCII, Unicode o según una configuración regional de negocio?
- ¿Debe procesarse la entrada como un flujo continuo (stream)?
- ¿La salida debe ser estable o se acepta cualquier orden?
- ¿Las frecuencias pueden exceder un entero de 32 bits?
Estructura de respuesta de 30 segundos
“Contaría las frecuencias con un hash map. Para cada palabra única mantengo un min-heap de tamaño k cuya raíz es el peor candidato: menor frecuencia o mayor orden lexicográfico en caso de empate. Después de insertar, hago pop cuando el heap excede k. Finalmente, emito las entradas del heap en frecuencia descendente y orden lexicográfico ascendente. El conteo cuesta O(n), el mantenimiento del heap O(m log k) y el espacio es O(m).”
Análisis paso a paso a profundidad
Paso 1: Contar frecuencias
Mapear cada palabra a su conteo. Un registro en streaming podría usar agregación externa o un contador aproximado, pero este problema asume que el mapa de palabras únicas cabe en memoria.
Paso 2: Definir el peor candidato
El candidato A es peor que B cuando A tiene menor frecuencia; en caso de empate, A tiene un orden lexicográfico mayor. El comparador coloca a ese candidato en la raíz del heap.
Paso 3: Mantener el tamaño k
Insertar cada entrada del mapa de frecuencias y hacer pop cuando el heap supere k. Por lo tanto, el heap retiene las k entradas con mayor probabilidad de pertenecer a la respuesta final.
Paso 4: Producir la salida
Las extracciones del heap van de peor a mejor, por lo que no pueden devolverse directamente. Invierte las entradas recolectadas o ordénalas con frecuencia descendente y lexicográfico ascendente.
Paso 5: Demostrar la correctitud
Siempre que el tamaño exceda k, elimina al peor miembro del conjunto actual. Ese miembro no puede superar a ninguno de los k miembros retenidos. Por inducción, el heap final contiene las Top K globales.
Paso 6: Manejar casos límite
Prueba k=1, frecuencias iguales, una sola palabra única, muchos duplicados y k=m. El comparador no debe invertir los empates accidentalmente.
Respuesta modelo de alta calidad
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String word : words) {
count.merge(word, 1, Integer::sum);
}
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
int byFrequency = Integer.compare(count.get(a), count.get(b));
if (byFrequency != 0) return byFrequency;
return b.compareTo(a); // larger lexicographic value is worse
});
for (String word : count.keySet()) {
heap.offer(word);
if (heap.size() > k) heap.poll();
}
List<String> answer = new ArrayList<>();
while (!heap.isEmpty()) answer.add(heap.poll());
Collections.reverse(answer);
return answer;
}
}El conteo cuesta O(n). Con m palabras únicas, las operaciones del heap cuestan O(log k), para un tiempo total de O(n + m log k) y un espacio de O(m).
Errores comunes
- Colocar al mejor candidato en la raíz del heap → la respuesta correcta es expulsada → coloca al peor candidato en la raíz.
- Invertir el comparador de empates → el orden de salida es incorrecto → conserva primero las palabras lexicográficamente menores ante igual frecuencia.
- Devolver directamente los elementos extraídos del heap → la salida va de peor a mejor → invierte o realiza un ordenamiento final.
- Afirmar O(n log k) después de un ordenamiento completo → la complejidad es falsa → el ordenamiento completo cuesta O(m log m).
- Probar únicamente frecuencias diferentes → el comportamiento ante empates no se prueba → incluye frecuencias todas iguales y muchos empates.
- Ignorar k=m → expulsión innecesaria o errores de límites → permite que el heap contenga todas las palabras únicas.
- Usar ordenamientos dependientes de la configuración regional accidentalmente → los resultados varían entre entornos → declara el orden requerido explícitamente.
- Mencionar un hash map sin análisis de espacio → la escala queda poco clara → declara la complejidad de n, m y k.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿Seguirías usando un heap cuando k está cerca de m?
El ordenamiento completo puede tener mejores constantes y un código más simple. Un heap sigue siendo válido, pero O(m log k) se aproxima a O(m log m).
Pregunta de seguimiento 2: ¿Qué pasa si la entrada es un stream ilimitado?
Los conteos exactos aún requieren estado. Usa ventanas, agregación externa o aproximación; el Top K exacto necesita suficiente estado de frecuencia retenido.
Pregunta de seguimiento 3: ¿Qué pasa si las palabras únicas exceden la memoria?
Aplica particionamiento mediante hash a disco, cuenta cada partición y fusiona candidatos, o usa ordenamiento externo. No cargues el arreglo completo en memoria.
Pregunta de seguimiento 4: ¿Cómo darías soporte a palabras que no distingan mayúsculas y minúsculas?
Normaliza con una configuración regional explícita antes de contar. Define si la salida preserva la grafía original y evita contar formas equivalentes dos veces.
Pregunta de seguimiento 5: ¿Cómo probarías el comparador?
Haz aserciones con frecuencias iguales y orden lexicográfico opuesto, k=1, k=m y entradas con muchos duplicados; compara casos aleatorios contra una referencia de ordenamiento completo.
Fuente 1: LeetCode 692
El problema define frecuencia descendente, empates lexicográficos ascendentes y un seguimiento de O(n log k), estableciendo la salida y el objetivo de complejidad.
Fuente 2: NeetCode Top K
NeetCode demuestra los enfoques de mapa de frecuencia y Top K, y resalta las compensaciones entre el comparador y el uso de heap versus ordenamiento.
Fuente 3: Oracle PriorityQueue
Oracle documenta el ordenamiento de PriorityQueue mediante el orden natural o Comparator, respaldando el comparador de min-heap personalizado y la semántica de poll.