-
-
Save ironboy/e89816596b9afe047810 to your computer and use it in GitHub Desktop.
/* | |
Five Programming Problems | |
a software developer should be able | |
to solve in less than an hour | |
https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour | |
Thomas Frank, Solutions in JS, time taken: | |
45 minutes (almost all time spent on problem 4 and 5) | |
Update: | |
Got stuck on failed edge cases on problem 4. | |
Eventually solved it with brute force. | |
For me problem 4 turned out to be the hardest one to solve. | |
(Although the actual sort solution is devilishly simple and elegant.) | |
Comment: All statements marked "copy list - avoid destryoing original" | |
reflects that JS always handles arrays by reference and it's polite | |
not to destroy someone elses array (by sorting, shifting, popping) | |
when they entrust it to your function :D | |
*/ | |
/* | |
Problem 1 | |
Write three functions that compute the sum of the numbers in a given list | |
using a for-loop, a while-loop, and recursion. | |
*/ | |
function sumFor(list){ | |
var sum = 0; | |
for(var i = 0; i < list.length; i++){ | |
sum += list[i]; | |
} | |
return sum; | |
} | |
function sumWhile(list){ | |
var sum = 0; | |
list = list.slice(); // copy list - avoid destroying original | |
while(list.length){ | |
sum += list.shift(); | |
} | |
return sum; | |
} | |
function sumRec(list){ | |
list = list.slice(); // copy list - avoid destroying original | |
function rec(list){ | |
return list.shift() + (list.length && rec(list)); | |
} | |
return rec(list); | |
} | |
/* | |
Problem 2 | |
Write a function that combines two lists by alternatingly taking elements. | |
For example: given the two lists [a, b, c] and [1, 2, 3], | |
the function should return [a, 1, b, 2, c, 3]. | |
*/ | |
function altCombine(list1,list2){ | |
var combined = []; | |
list1 = list1.slice(); list2 = list2.slice(); // copy lists - avoid destroying originals | |
while(list1.length || list2.length){ | |
list1.length && combined.push(list1.shift()); | |
list2.length && combined.push(list2.shift()); | |
} | |
return combined; | |
} | |
/* | |
Problem 3 | |
Write a function that computes the list of the first 100 Fibonacci numbers. | |
By definition, the first two numbers in the Fibonacci sequence are | |
0 and 1, and each subsequent number is the sum of the previous two. | |
As an example, here are the first 10 Fibonnaci numbers: | |
0, 1, 1, 2, 3, 5, 8, 13, 21, and 34. | |
*/ | |
function fibonacciNaive(howMany){ | |
// this solution won't really work | |
// because with howMany = 100 | |
// we will try to handle bigger numbers | |
// than Number.MAX_SAFE_INTEGER | |
howMany = howMany || 100; | |
var nums = [0,1]; | |
while(nums.length < howMany){ | |
nums.push(nums[nums.length-2] + nums[nums.length-1]); | |
} | |
return nums; | |
} | |
function fibonacci(howMany){ | |
function addBigNums(a,b){ | |
a = String(a).split(''); | |
b = String(b).split(''); | |
var sum = [], mem = 0, part; | |
while(a.length || b.length){ | |
part = String( | |
Number(a.pop() || 0) + Number(b.pop() || 0) + | |
Number(mem) | |
).split(''); | |
sum.unshift(part.pop()); | |
mem = part.join(''); | |
} | |
sum.unshift(mem); | |
return sum.join(''); | |
} | |
howMany = howMany || 100; | |
var nums = ["0","1"]; | |
while(nums.length < howMany){ | |
nums.push( | |
addBigNums(nums[nums.length-2],nums[nums.length-1]) | |
); | |
} | |
return nums; | |
} | |
/* | |
Problem 4 | |
Write a function that given a list of non negative integers, | |
arranges them such that they form the largest possible number. | |
For example, given [50, 2, 1, 9], the largest formed number is 95021. | |
*/ | |
function largestPosNum(list){ | |
// thanks to github.com/cerneal and svpino for this solution | |
list = list.slice(); // copy list - avoid destroying original | |
return list.sort(function(x, y){ | |
return (x+''+y < y+''+x) ? 1 : -1; | |
}).join('')/1; | |
} | |
function largestPosNumBrute(list){ | |
// a (slower, brute force variant) | |
// go through all permutations to find the largest number | |
var largest = 0; | |
function permute(list, mem) { | |
var cur; | |
mem = mem || []; | |
list.forEach(function(x,i){ | |
cur = list.splice(i,1); | |
var num = mem.concat(cur).join("")/1; | |
largest = !list.length && largest < num ? num : largest; | |
permute(list.slice(),mem.concat(cur)); | |
list.splice(i,0,cur[0]); | |
}); | |
} | |
permute(list); | |
return largest; | |
} | |
/* | |
Problem 5 | |
Write a program that outputs all possibilities to put + or - or | |
nothing between the numbers 1, 2, ..., 9 (in this order) such | |
that the result is always 100. | |
For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100. | |
*/ | |
function allPossibilities(){ | |
// brute force solution | |
// first calculate all possible combinations | |
// of numbers and operators | |
var mem = ["1"], combos; | |
for(var i = 2; i <= 9; i++){ | |
combos = []; | |
mem.forEach(function(x){ | |
combos.push(x + i, x + " +" + i, x + " -" + i); | |
}); | |
mem = combos; | |
} | |
// Now filter out the ones that equal 100 | |
return combos.filter(function(combo){ | |
// split a combo into numbers, sum them using reduce | |
return combo.split(" ").reduce(function(x,y){ | |
return x/1+y/1; | |
}) == 100; // and check if the sum is 100 | |
}) | |
// format output by adding some spaces | |
.map(function(x){ | |
return x.replace(/([+-])/g,'$1 '); | |
}); | |
} |
Hi, The example at problem 4 is wrong. The largest number is 95210...
Hi, The example at problem 4 is wrong. The largest number is 95210...
Example is correct, as you need to use 50 without splitting it. That's what makes it interesting!
Here's my solution in SingleView EPM.
`var list&[] := [50,2,1,20,9];
var expr$ := 'if length(to_string(@A&)) > length(to_string(@b&)) then
substr(to_string(@A&), 0, length(to_string(@b&))) <= to_string(@b&)
else to_string(@A&) <= substr(to_string(@b&), 0, length(to_string(@A&)))';
sort(list&[], parse(expr$));
print(list&[]);`
If your question is correct then number four can easily be solved as ==>
Function largestPossibleNum(arr){
Let myArray = arr;
return myArray.sort().reverse().join('')
}
Console.log(largestPossibleNum([50,2,1,9]))
you seem to have bug in 4th problem.
test with input: [33,13331,44,9,99,999,101]
it returns: 999999443313331100. You can see number "101" (which was in input) is not present in the answer.