Skip to content

Instantly share code, notes, and snippets.

@lazzyms

lazzyms/README.md

Last active July 28, 2020 15:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lazzyms/d85d03ac39b947f266d53fef9be00d31 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lazzyms/d85d03ac39b947f266d53fef9be00d31 to your computer and use it in GitHub Desktop.
Download ZIP
Interview Question - the perfect curry
Raw
README.md

We want to prepare the perfect curry with ingredients P, Q, and R. "A" is a zero-indexed array of N integers. Elements of A are integers within the range [−99,999,999 to 99,999,999] The curry is a string consisting of N characters such that each character is either P, Q, or R and the corresponding index of the array is the weight of each ingredient. The curry is perfect if the sum of the total weights of P, Q, and R is equal. Write a function function makeCurry(Array); such that, given a zero-indexed array Array consisting of N integers, returns the perfect curry of this array. The function should return the string "noLuck" if no perfect curry exists for that Array. For example, given array A such that

A[0] = 3
A[1] = 7
A[2] = 2
A[3] = 5
A[4] = 4

the function may return "PQRRP", as explained above. Given array A such that

A[0] = 3
A[1] = 6
A[2] = 9

the function should return "noLuck".

Raw
thePerfectCurry.js
// Tests if selected elements add up to target
function check(a, selection, target) {
let sum = 0;
for (let i = 0; i < a.length; i++) {
if (((selection >> i) & 1) == 1)
sum += a[i];
}
return sum == target;
}
// Remove the selected elements
function exclude(a, selection) {
let res = [a.length];
let j = 0;
for (let i = 0; i < a.length; i++) {
if (((selection >> i) & 1) == 0)
res[j++] = a[i];
}
return res
}
function getCurry(a) {
console.log(a)
// Sum of all
let sum = a.reduce((accumulator, currentValue) => accumulator + currentValue);
if (sum % 3 > 0)
return "noLuck";
let target = sum / 3;
let max1 = 1 << a.length; // 2^length
console.log(max1);
for (let i = 0; i < max1; i++) {
if (check(a, i, target)) {
let b = exclude(a, i);
let max2 = 1 << b.length; // 2^length
for (let j = 0; j < max2; j++) {
if (check(b, j, target))
return formatSolution(i, j, a.length);
}
}
}
return "noLuck";
}
function formatSolution(p, q, len) {
let res = new Array(len)
res.fill('R')
let j = 0;
for (let i = 0; i < len; i++) {
if (((p >> i) & 1) == 1)
res[i] = 'P';
else {
if (((q >> j) & 1) == 1)
res[i] = 'Q';
j++;
}
}
return new String(res);
}
// let a = [3, 7, 2, 5, 4]
let a = [1, 1, 2, -1, 5, 3, 8, -6, 4, 1]
// let a = [5, 4, 3, 3, 3, 3, 3, 3]
console.log(getCurry(a))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment