Recently I gave an online coding interview where I was asked the following question -
Largest possible square that can be built by cutting two sticks:
We want to cut sticks so that we achieve 4 sticks of the same length. (there can be leftover pieces). What is the longest square side that we can achieve?
use this function def square(A, B) Input: two integers A, B Output: Return the side length of the largest square that we can have, if not possible function should return 0.ex1: Input: A = 13, B = 11 Output: function will return 5 because we can cut two sticks of length 5 from each of the given sticks.
ex2: Input: Given A = 10, B = 21 Output: the function will return 7 because we can split the second stick B into three sticks of length 7 and shorten the first stick A by 3.
ex3: Input: Given A = 2, B = 1 Output: the function will return 0 as it is not possible to make any square from the sticks provided
ex4: Input: Given A = 1, B = 8 Output: the function will return 2 because we can cut stick B into 4 parts
I was not able to solve it during the test but came up with solution later. I want to verify if my solution is correct and if I have considered all corner cases. Here is my solution in 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 7Your solution is correct, but you can avoid the loops.
When a is less than b, there are essentially three solutions to compare:
b. The size is one quarter of bb and one from aaIn the second case, you need to see whether b/3 is greater than a, in which case the size to use is a, otherwise you can use b/3.
Code:
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 7Your answer is correct. An alternative I've created will allow for any amount of sides, and any amount of sticks:
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]));If it looks scary, I'll break it down:
Sticks is an array, so you can use sticks.reduce() to add up all the stick values, dividing that by the amount of sides gets us the absolute maximum length of each stick in the shape. But just using that function would allow for something like this: sides = 4, sticks = [10, 2] and the output would incorrectly be 4.
So instead we loop through all the potential stick lengths, starting from the max value (which we calculated at the start). We can apply the function a => { return Math.floor(a/s) } to all the sticks values with sticks.map() which allows us to have all the sticks be divided into the length we're iterating through. Then adding them all up will give us the amount of sides we can make with the stick length s. If that value is more than or equal to the sides we want, return the value we are iterating over. Otherwise try the next stick length (-1).
If s gets to zero, we just return 0.