Muchos problemas difíciles de LeetCode son problemas fáciles con solucionadores de restricciones

 (buttondown.com)
6 puntos por GN⁺ 2025-09-13 | 2 comentarios | Compartir por WhatsApp
  • Incluso los problemas difíciles de LeetCode se pueden resolver mucho más fácilmente usando un solucionador de restricciones
  • En lugar de programación dinámica compleja o algoritmos propios, se puede usar un solucionador de restricciones como MiniZinc para resolver de forma sencilla problemas de optimización matemática
  • Los lenguajes de programación tradicionales tienen dificultades para expresar este tipo de problemas de optimización matemática, por lo que el enfoque basado en restricciones destaca especialmente
  • Incluso cuando aparecen casos excepcionales o restricciones adicionales, los cambios al modelo en un solucionador de restricciones son mínimos
  • La complejidad en tiempo de ejecución puede ser peor que la de un algoritmo optimizado escrito a mano, pero tiene muchas ventajas en flexibilidad y productividad de desarrollo

Problemas de LeetCode resueltos con un solucionador de restricciones

Elegir la herramienta correcta

  • El autor recibió el problema del “cambio con monedas” en su primera entrevista después de graduarse de la universidad

    • Dadas ciertas denominaciones de monedas, se trata de encontrar la cantidad mínima de monedas necesaria para completar una cantidad determinada
    • Usó un algoritmo voraz simple, pero no podía garantizar la solución óptima en todos los casos
    • La respuesta correcta era programación dinámica, pero como no pudo implementarla, falló en la entrevista

  • Sin embargo, en lugar de implementar el algoritmo directamente, se puede resolver muy fácilmente usando un solucionador de restricciones como MiniZinc

    • Código de ejemplo:

      int: total;
array[int] of int: values = [10, 9, 1];
array[index_set(values)] of var 0..: coins;

constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
solve minimize sum(coins);

    • Se puede ejecutar directamente el ejemplo de MiniZinc en línea

    • El solucionador encuentra progresivamente la solución óptima

Distintos problemas de optimización/satisfacción

  • Los problemas de optimización matemática que aparecen con frecuencia en LeetCode y similares (incluyendo maximizar/minimizar una función objetivo y varias restricciones)
    suelen ser difíciles de resolver en un lenguaje de programación por la implementación de bajo nivel, pero encajan bien con un solucionador de restricciones
  • Por ejemplo, distintos problemas del siguiente tipo entran en esta categoría

Ejemplo 1: problema de máxima ganancia con acciones

  • “Dada una lista de precios de acciones, encuentra la ganancia máxima que se puede obtener comprando una vez y vendiendo después”
    • Tradicionalmente requiere fuerza bruta O(n²) o un algoritmo óptimo O(n)
    • En MiniZinc se puede definir de forma simple como el siguiente problema de restricciones 
      array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
var int: buy;
var int: sell;
var int: profit = prices[sell] - prices[buy];

constraint sell > buy;
constraint profit > 0;
solve maximize profit;

Ejemplo 2: llegar a 0 sumando/restando ciertos números (problema de satisfacción)

  • “¿Se puede llegar a 0 sumando o restando tres números de la lista?”
    • No hace falta encontrar un valor óptimo, solo una solución satisfacible
    • En un solucionador de restricciones se expresa así 
      include "globals.mzn";
array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array[index_set(numbers)] of var {0, -1, 1}: choices;

constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
constraint count(choices, -1) + count(choices, 1) = 3;
solve satisfy;

Ejemplo 3: área máxima de rectángulo en un histograma

  • “Dado un histograma con la altura de cada barra, encuentra el área del rectángulo más grande que se puede formar”
    • Tradicionalmente requiere un algoritmo complejo y manejo de múltiples estados
    • Con solo restricciones se puede describir la solución de forma concisa 
      array[int] of int: numbers = [2,1,5,6,2,3];

var 1..length(numbers): x; 
var 1..length(numbers): dx;
var 1..: y;

constraint x + dx <= length(numbers);
constraint forall (i in x..(x+dx)) (y <= numbers[i]);

var int: area = (dx+1)*y;
solve maximize area;

output ["(\(x)->\(x+dx))*\(y) = \(area)"]

¿Es mejor el enfoque con solucionadores de restricciones?

  • En una entrevista técnica tiene debilidades frente a preguntas sobre complejidad temporal

    • Es difícil predecir el tiempo de ejecución de un solucionador de restricciones, y normalmente será más lento que un algoritmo óptimo hecho a medida
    • Aun así, puede ser mejor que un algoritmo de mala calidad mal implementado, y para la mayoría de programadores no es fácil escribir siempre la mejor solución a mano

  • La fortaleza real está en la flexibilidad para agregar nuevas restricciones

    • Por ejemplo, en el caso de las acciones, cambiar de una sola compra/venta a varias hace que la complejidad algorítmica aumente mucho
    • En el modelo de restricciones de MiniZinc, se pueden aceptar requisitos mucho más complejos con cambios mínimos en el código 
      include "globals.mzn";
int: max_sales = 3;
int: max_hold = 2;
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array [1..max_sales] of var int: buy;
array [1..max_sales] of var int: sell;
array [index_set(prices)] of var 0..max_hold: stocks_held;
var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);

constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
constraint profit > 0;

constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
constraint alldifferent(buy ++ sell);
solve maximize profit;

output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];

  • Los ejemplos de problemas de restricciones en línea suelen centrarse en rompecabezas como Sudoku, pero en realidad pueden usarse de forma más interesante y práctica en problemas con lógica de negocio o necesidades de optimización

    • Por ejemplo, también hay mucho potencial para aplicar técnicas avanzadas de optimización como symmetry breaking

Cierre y referencias

  • Este texto forma parte del boletín semanal del autor, que trata sobre historia del software, métodos formales, nuevas tecnologías y teoría de ingeniería de software
  • Si te interesa, puedes revisar la suscripción o el sitio web principal del autor
  • Su nuevo libro "Logic for Programmers" también está en publicación

Lecturas relacionadas

2 comentarios

 
kohs100 2025-09-15

Normalmente, los problemas de algoritmos vienen con restricciones de tiempo/espacio, ¿no? Decir que se pueden resolver con un solver de restricciones básicamente solo demuestra la capacidad de convertir el problema en un conjunto de restricciones... y la verdad no estoy seguro de que esa sea una habilidad realmente necesaria en el trabajo del día a día...
 
GN⁺ 2025-09-13
Opinión de Hacker News

  • El mayor problema de las preguntas de entrevista tipo Leetcode es que no puedes pedir aclaraciones; como mi forma de pensar es distinta a la habitual, siento que Leetcode depende más de memorizar respuestas. Si el problema tiene suficiente contexto, puedo formarme una comprensión realista y está bien, pero la mayoría tiene explicaciones insuficientes y termino sin poder entender bien qué se supone que hay que resolver. Por eso últimamente rechazo por completo las etapas de entrevistas con Leetcode o automatizadas con IA. Las tareas, entrevistas 1:1 o compartiendo pantalla sí me parecen bien. Si el sitio de Leetcode tuviera explicaciones y respuestas realmente buenas, estudiar por cuenta propia sería mucho más fácil, pero en la práctica se me hace demasiado difícil. No es solo un tema de capacidad; es que mi forma de pensar no encaja bien con ese tipo de problemas. Seguir resolviendo preguntas tipo opción múltiple sin poder hacer preguntas me parece un sistema diseñado para que fracases. Hablo sobre todo de problemas tipo IA/Leetcode usados en preentrevistas; en entrevistas con personas de verdad, donde hay ida y vuelta de preguntas, me parece un entorno perfectamente bueno.

    • Las entrevistas LC (Leetcode) se parecen a medir qué tan rápido corres 100 metros después de entrenarlo, mientras que el trabajo real se parece más a un maratón largo donde te detienes y retomas varias veces. Aun así, hoy en día, si quieres un salario alto en una gran empresa tipo SMEGMA, tienes que jugar este juego. Por ejemplo, yo construí mi propio motor de juegos 2D, pero igual creo que no pasaría una entrevista LC donde tengas que hacer varias preguntas hard de LC y hasta dar marometas. Ya lo acepté. El motor que hice

    • No todo se resuelve memorizando soluciones; incluso si memorizas, puedes atorarte en las preguntas de seguimiento. Pero si ya memorizaste y además resuelves bien esas preguntas adicionales, entonces diría que no tienes problema con los ejercicios estilo Leetcode. Resolver problemas es una capacidad de reconocimiento de patrones, y mientras más patrones conozcas, mejor resuelves. Ahora GPT también resuelve problemas y da explicaciones, así que este tipo de habilidad se puede adquirir más fácilmente. Creo que más vale aprenderla desde ahora.

    • Lo siento muchísimo identificado. En una entrevista reciente saqué la mejor calificación en la tarea y tanto los ingenieros como el CEO tuvieron muy buena impresión de mí, pero el CTO de la nada me puso una entrevista de live coding y al final me rechazaron. Once semanas de entrevistas se fueron a la basura. Frustra que este proceso tan tonto siga existiendo. El demo/tarea que hice está aquí, enlace a monumental y resultado, y el código en GitHub.

    • Pienso que no poder hacer preguntas claras es precisamente la capacidad que en realidad intentan evaluar: ver cómo aborda un candidato la resolución del problema. Si haces que la gente solo proceda con suposiciones tajantes, todo el software terminará siendo más complejo y más desordenado. Lo realmente difícil no es escribir líneas de código, sino el proceso de resolver el problema.

    • En los lugares donde entrevisté, aunque te dieran solo una o dos preguntas de LC, si pedías aclaraciones enseguida lo convertían en conversación en tiempo real y programación en vivo. La desventaja de hacerlo así es que aumenta mucho la carga psicológica del live coding.

  • Cuando me ponen este tipo de problemas de entrevista, siento que no quieren que "uses" un constraint solver, sino que "implementes tú mismo" un constraint solver adaptado a un problema limitado.

    • Sí, y por eso creo que esta forma de entrevistar es torpe desde la raíz. En una situación real de ingeniería, puedes tomarte un café, leer papers, ir a la biblioteca, salir a caminar para pensarlo y apoyarte en herramientas existentes (constraint solvers o LLMs) para resolver el problema al 100%. Pero en una entrevista siento que ni al 0% podría resolverlo. Nunca se me ha ocurrido querer entrar a una empresa que entrevista así.

    • Sí, totalmente. La mayoría de los problemas NP pueden transformarse en problemas de restricciones. En la práctica, que un constraint solver sea o no la respuesta correcta depende muchísimo del dominio de aplicación. Y en contexto de entrevista casi nunca es la respuesta correcta. Muchas veces estos solvers son muchísimo más lentos que una programación dinámica sencilla.

    • En entrevistas de algunas empresas eso sí puede ser cierto, pero en muchas otras no. En general, muchas veces LC se usa en entrevistas por una sola razón: procesos de contratación ineficientes. Incluso los participantes saben que el sistema necesita reformarse, pero no tienen poder o están demasiado dispersos para cambiarlo. En empresas grandes, RR. HH. a veces rota las mismas preguntas entre equipos distintos por "estandarización", y las empresas pequeñas no tienen tiempo para preparar sus propios problemas y los copian de internet. En esos casos, hasta los entrevistadores técnicos suelen ser críticos de las entrevistas tipo LC y en la práctica intentan detectar candidatos destacados. En ese entorno, con solo demostrar interés o conocimiento sobre constraint solvers, a veces ya te ganas una muy buena calificación.

    • Si alguien resolvió un problema LC hard con un constraint solver y no lo contratan, entonces el tonto es el entrevistador. Gente que siquiera sepa qué es un constraint solver y además sepa formular el problema para usarlo hay poquísima. Yo lo usé en tercer año y solo escribir las restricciones ya era un trabajo lo bastante complejo como para dolerte la cabeza.

    • Esta parte es cierta y falsa a la vez. Yo he hecho este tipo de preguntas en entrevistas, y si el candidato pensaba en un constraint solver, le daba buena puntuación. En ingeniería real, los constraint solvers están subestimados y son una buena señal de si alguien sabe llegar rápido a la respuesta correcta. Claro, después haría preguntas de whiteboard de seguimiento para medir la capacidad real de programar. Pero proponer un constraint solver como respuesta no me parece algo malo.

  • Es una observación genial, pero creo que no encaja bien con las entrevistas reales. El centro de estos problemas es verificar si el candidato sabe "pensar". Resolverlo solo con restricciones muestra experiencia y nivel de conocimiento, pero no deja ver si realmente "pensó".

    • Los entrevistadores tienden a poner problemas de "Array String" del "Top Interview 150" de Leetcode. Desde mi perspectiva como desarrollador backend en Python, siento que esos problemas están muy lejos del trabajo cotidiano. La mayoría exige algoritmos de operaciones in-place sobre arrays, algo que normalmente solo hace falta en lenguajes orientados al rendimiento como C o Rust. En cambio, los problemas tipo "Hashmap" sí sirven más para mostrar cómo usas herramientas acordes al lenguaje. Además, muchos problemas tienen una dificultad mal calibrada, así que incluso ejercicios marcados como "fáciles" (por ejemplo, Majority Element) en realidad requieren algoritmos históricos como Boyer–Moore. Cuesta verlos como realmente fáciles.

    • La última ronda que vi recientemente en Meta era básicamente un proceso para comprobar cuánto habías repetido y memorizado sus problemas específicos. Si respondías distinto a la respuesta de libro, incluso se desconcertaban. Me dio la impresión de que la "inteligencia" en sí no importa tanto.

    • Los algoritmos de DP bottom-up sí requieren algo de ingenio, pero la mayoría de los problemas puede resolverse con enfoque top-down (recursión + memoización). Por ejemplo, el problema del cambio de monedas puede resolverse mejor con búsqueda A*. Pero en la práctica casi ningún programador va a usar realmente estos algoritmos. Lo verdaderamente importante es darte cuenta cuando escribes por accidente código con complejidad temporal O(n^2). Si ves accidentallyquadratic.tumblr.com, incluso gente muy capaz en proyectos famosos comete ese tipo de errores a menudo. Así que la capacidad de inventar algoritmos en un test no es lo mismo que la capacidad de detectar errores algorítmicos mientras trabajas.

    • Cuando entrevisto para evaluar resolución de problemas, me importan el proceso de pensamiento, la forma de comunicarse y cómo descomponen el problema. Es mucho más importante preparar preguntas cuya dificultad pueda ajustarse, para que todos los candidatos tengan oportunidad de mostrar su nivel. Si alguien grita una respuesta inmediata o se queda atascado mucho tiempo, en realidad el entrevistador aprende muy poco de eso. Por eso las preguntas de entrevista centradas en resolución de problemas pueden ser muy útiles, pero da pena que en la práctica se usen mal.

    • Estos problemas no evalúan realmente la "inteligencia", sino cuánto memorizaste unas 12 plantillas estandarizadas. Casi todos los candidatos terminan aprobando o reprobando por la memoria con la que llegaron preparados, no por su capacidad creativa para resolver problemas. Los problemas de LeetCode están tan gamificados que da la impresión de que solo miden disposición para prepararse.

  • La mayoría de las entrevistas parecen plantear problemas bajo la premisa de que "si un diabético no puede sintetizar insulina en casa por sí mismo, está haciendo trampa en el juego de la vida". Así como mi esposa se inyecta insulina cuando le sube la glucosa, si el problema es de restricciones, lo correcto es usar un solver. A menos que la empresa haga software de constraint solvers, no entiendo por qué tendrían que exigirte partir de la premisa de que "ese software no existe" y rehacerlo todo desde cero.

    • El punto no es evaluar si puedes sintetizar insulina en una crisis, sino si puedes memorizar el material en una semana y recitarlo bien en una entrevista telefónica, como una prueba de aptitud previa.

    • Si puedes encontrar una forma eficiente de resolver un problema con un constraint solver, entonces también puedes escribir sin problema un par de loops for y una función recursiva auxiliar para resolver cualquier problema de juguete.

    • (sin contenido significativo)

    • En defensa de las pruebas de programación, la mayoría de la gente que no puede resolver ni un problema simple de DP también suele tener un nivel flojo en el trabajo real. Seguro hay excepciones, pero esa ha sido mi experiencia.

  • Siempre que sale el tema de lenguajes de programación por restricciones, hay que mencionar a Håkan Kjellerstrand. Mantiene un sitio excelente con montones de ejemplos y problemas, incluidos muchos de MiniZinc. hakank minizinc

    • Y no solo hizo un gran sitio web, también es una persona increíblemente amable.

  • Hace muchísimo tiempo, cuando yo todavía era un novato que no había aprendido sobre constraint solvers en la carrera de computación, me topé con este problema porque un amigo me pidió hacer una app para programar horarios de un club deportivo. Al principio parecía fácil, pero cuando empecé a intentarlo no me di cuenta de que me había metido en un problemón enorme. Después entendí que fue una buena lección contra mi arrogancia, y desde entonces esa experiencia me ha ayudado mucho al hablar de cronogramas, fechas límite y expectativas.

    • Puede ser una pregunta muy básica, pero me pregunto si no sería más fácil resolverlo con "optimización lineal" en lugar de un constraint solver. Por experiencia propia, una ventaja de la optimización lineal es que puedes tratar conflictos entre reglas como pesos y encontrar una solución que minimice los "efectos secundarios".

    • Hace 25 años, cuando estaba en la preparatoria y apenas empezaba a aprender TI-Basic y VB6, trabajaba en una hamburguesería y escuché al gerente quejarse de lo difícil que era hacer el horario semanal del personal. Le dije: "¡Yo sé de computadoras, le hago un programa para eso!". Muy pronto me di cuenta de lo difícil que era realmente escribir un scheduler y lo abandoné enseguida.

  • "El autor sostiene que si pones este problema en una entrevista, no tienes salida si el entrevistado te pregunta: '¿cuál es la complejidad temporal de este algoritmo?'". Es decir, si un constraint solver no lo resuelve lo bastante rápido, entonces tampoco es la respuesta para un problema hard de Leetcode. Si el requisito de tiempo de ejecución fuera relajado, quizás serviría un método simple, pero encontrar una solución eficiente es una parte importante del desafío completo.

    • En el trabajo real casi siempre se necesita más "idear una solución que responda rápido a nuevos requisitos" que "la solución más eficiente posible". Por eso me pregunto si una entrevista con criterios de eficiencia tan alejados de la realidad tiene sentido, aunque también dependerá del rol. Coincido con la idea del autor de que la solución más eficiente no necesariamente refleja la capacidad real de trabajo. Una parte de la crítica a Leetcode va por ahí. Incluso con el mismo problema, sería más objetivo verlo desde la perspectiva de "qué tan flexible eres para adaptarte a nuevos requisitos".

  • ¿Constraint solver? Buena idea, sí he oído de eso. Pero en una entrevista, en la práctica, lo que quieren es que lo implementes tú mismo en Python mientras observan tu proceso de pensamiento. (Siento que es casi imposible convencerlos de usar un constraint solver en una entrevista).

    • Me pregunto si de verdad has hablado de esto con entrevistadores, o si solo lo estás suponiendo.

    • import z3

  • Si primero lo resuelves con DP (programación dinámica) y luego dices "ahora también lo voy a hacer con un constraint solver", te contratan en el acto.

    • +1

  • La verdadera fortaleza de los constraint solvers es qué tan fácilmente pueden adaptarse a "nuevos requisitos". Yo también viví mucho ese beneficio en Google optimizando centros de datos, donde estos solvers generalizados se adaptaban con flexibilidad a cambios en los requerimientos.