Recientemente di una entrevista de codificación en línea donde me hicieron la siguiente pregunta:
Cuadrado más grande posible que se puede construir cortando dos palos:
Queremos cortar palitos de manera que logremos 4 palitos del mismo largo. (puede haber sobras de piezas). ¿Cuál es el lado cuadrado más largo que podemos lograr?
usa esta función def square(A, B) Entrada: dos enteros A, B Salida: Devuelve la longitud del lado del cuadrado más grande que podemos tener, si no es posible, la función debería devolver 0.ex1: Entrada: A = 13, B = 11 Salida: la función devolverá 5 porque podemos cortar dos palos de longitud 5 de cada uno de los palos dados.
ex2: Entrada: dado A = 10, B = 21 Salida: la función devolverá 7 porque podemos dividir el segundo palo B en tres palos de longitud 7 y acortar el primer palo A en 3.
ex3: Entrada: dado A = 2, B = 1 Salida: la función devolverá 0 ya que no es posible hacer ningún cuadrado con los palos provistos
ex4: Entrada: dado A = 1, B = 8 Salida: la función devolverá 2 porque podemos cortar el palo B en 4 partes
No pude resolverlo durante la prueba, pero se me ocurrió una solución más tarde. Quiero verificar si mi solución es correcta y si he considerado todos los casos de esquina. Aquí está mi solución en JavaScript:
console.log('Max Square Side'); function square(A,B) { let sum = A+B; let long = Math.max(A,B); let short = Math.min(A,B); if (sum < 4) { return 0; } while(sum%4 != 0) { sum-- } let max = sum/4; while (max != 0) { if( max * 4 <= long) { return max; } if( max * 3 <= long && max <= short ) { return max; } if( max * 2 <= long && max * 2 <= short ) { return max; } max--; } return 0; } console.log(square(2,1)); // Output 0 console.log(square(2,2)); // Output 1 console.log(square(2,12)); // Output 3 console.log(square(8,1)); // Output 2 console.log(square(13,11)); // Output 5 console.log(square(10,21)); // Output 7Su solución es correcta, pero puede evitar los bucles.
Cuando a es menor que b , hay esencialmente tres soluciones para comparar:
b . El tamaño es un cuarto de bb y una de aa En el segundo caso, debe ver si b/3 es mayor que a , en cuyo caso el tamaño a usar es a , de lo contrario, puede usar b/3 .
Código:
function square(a, b) { if (a > b) [a, b] = [b, a]; // swap to simplify the formulas below return Math.max( // Take best option: // Option: Take all 4 parts from b b >> 2, // integer division by 4 // Option: Take 3 parts from b, 1 from a Math.min(a, Math.floor(b / 3)), // Option: Take 2 parts from a, 2 from b a >> 1 ); } console.log(square(2,1)); // Output 0 console.log(square(2,2)); // Output 1 console.log(square(2,12)); // Output 3 console.log(square(8,1)); // Output 2 console.log(square(13,11)); // Output 5 console.log(square(10,21)); // Output 7Tu respuesta es correcta. Una alternativa que he creado permitirá cualquier cantidad de lados y cualquier cantidad de palos:
function shape(sides, sticks) { for(let s = Math.floor((sticks.reduce((a,b)=>{return a+b}))/sides); s > 0; s--){ if( sticks.map(a=>{return Math.floor(a/s)}).reduce((a,b)=>{return a+b}) >= sides){ return s; } } return 0; } console.log(shape(4, [10, 2])); console.log(shape(4, [10, 2, 4, 1, 9])); console.log(shape(3, [20, 9])); console.log(shape(5, [5])); console.log(shape(10, [10, 2, 40, 6, 17])); console.log(shape(4, [10, 3]));Si parece aterrador, lo desglosaré:
Sticks es una matriz, por lo que puede usar sticks.reduce() para sumar todos los valores de los palos, dividiéndolos por la cantidad de lados obtenemos la longitud máxima absoluta de cada palo en la forma. Pero solo usar esa función permitiría algo como esto: sides = 4, sticks = [10, 2] y la salida sería incorrectamente 4.
Entonces, en su lugar, recorremos todas las posibles longitudes de palo, comenzando desde el valor máximo (que calculamos al principio). Podemos aplicar la función a => { return Math.floor(a/s) } a todos los valores de sticks con sticks.map() que nos permite dividir todos los palos en la longitud que estamos iterando. Luego sumarlos todos nos dará la cantidad de lados que podemos hacer con la longitud del palo s . Si ese valor es mayor o igual a los lados que queremos, devuelve el valor sobre el que estamos iterando. De lo contrario, intente con la siguiente longitud de palo (-1).
Si s llega a cero, simplemente devolvemos 0.