Jack Le Hamster
BAN USERFirst, start with the current value
1*A[0] + 2*A[1] + 3*A[2] ... A.length*A[A.length-1] = value
Then notice that rotating by one to the right is equivalent of adding the sum of all elements, and subtracting the last product.
A1 + A2+A2 + A3+A3+A3 .... => add sum => Alast + A1+A1 + A2+A2+A2 + A3+A3+A3+A3
So:
value += sumOfAll(A) - A[A.length-1];
In this example:
Step1: 1x5 + 2x2 + 3x1 = 12
Step2: value = 12 + (5+2+1) - 3x1 = 12 + 8 - 3 = 17
Step3: value = 17 + 8 - 3x2 = 19
(let's rotate again just for testing)
Step4: 19 + 8 - 3x5 = 12
Then simply look for the smallest value after going through A.length steps.
Going to the next step is O(1) so the algorithm is O(n)
function findMinSum(array) {
var sum = 0;
for(var i=0;i<array.length;i++) {
sum += array[i];
}
// find current value
var value = 0;
for(var i=0;i<array.length;i++) {
value += (i+1)*array[i];
}
var min = value;
// keep changing rotation formula
for(var i=array.length-1;i>=0;i--) {
value += sum - array[i] * array.length;
if(value<min)
min = value;
}
return min;
}
document.body.innerHTML += findMinSum([5,2,1]) + "<br>"; // 12
document.body.innerHTML += findMinSum([3,2,6,8,1]) + "<br>"; // 47
Since we're not looking at the shortest path, I would try greedy best first search algorithm, as it generally finds the solution faster than regular BFS or DFS.
The calculated distance between two nodes would be the sum of the horizontal distance and the vertical distance, since we can't move in diagonals.
I think that for this problem, the goal is to press the least number of keys, rather than find the combination more efficiently.
- Jack Le Hamster June 01, 2015This solves both (1) and the generic case (2).
1. Set the length starting at 0. It will keep increasing later
2. Try digits and see what combination of size "length" was just typed. If it's a new combination, add it in a hashtable "comboHash". If it's not, cancel that last digit and try a new one.
3. If we run out of combinations of size "length", increment length
4. Check in the digits history to see what new combinations of size "length" have already been tried, and fill up our "comboHash".
5. Go back to step 2.
function output(obj) {
console.log(obj);
document.body.innerHTML += obj + "<br>";
}
function checkDigitsForSolution(solution) {
return function(digits) {
if(digits.slice(digits.length-solution.length).join("")==solution) {
output("Found combination:"+solution);
return true;
}
else {
return false;
}
}
}
function solveCombinations(checkDigits) {
var comboHash = {};
var highestReachedLength = 0;
var digits = [];
var comboCount = 0;
do {
var newDigit = -1;
for(var length=highestReachedLength;length<=digits.length;length++) {
if(length>highestReachedLength) {
// fillup comboHash
for(var c in comboHash) {
var index = comboHash[c];
var combo = digits.slice(index,index+length+1).join("");
if(comboHash[combo]===undefined) {
comboHash[combo] = index;
comboCount++;
}
}
highestReachedLength = length;
}
var lastCombinationArray = digits.slice(digits.length-length);
for(var d=0;d<=9;d++) {
lastCombinationArray.push(d);
var combination = lastCombinationArray.join("");
if(comboHash[combination]===undefined) {
comboHash[combination] = (digits.length-length);
newDigit = d;
comboCount++;
break;
}
lastCombinationArray.pop();
}
if(newDigit>=0) {
break;
}
}
digits.push(newDigit);
} while(!checkDigits(digits));
output((digits.length>100?"...":"")+ digits.join("").slice(digits.length-100));
output("Digits typed: "+digits.length);
output("Combinations tested: "+comboCount);
}
solveCombinations(checkDigitsForSolution("102"));
output("============");
solveCombinations(checkDigitsForSolution("911"));
output("============");
solveCombinations(checkDigitsForSolution("1978"));
Output:
Found combination:102
0123456789002030405060708091000101102
Digits typed: 37
Combinations tested: 73
============
Found combination:911
...4031403240255003540403340265004540514041405240424053403550127003630364036502150225013600281009000911
Digits typed: 1046
Combinations tested: 1284
============
Found combination:1978
...8784108785007786106786205787104787202878101378101478101578003278001578101678001678101778000988001978
Digits typed: 207036
Combinations tested: 228608
This is the output:
Found combination:102
0123456789002030405060708091000101102
Digits typed: 37
Combinations tested: 73
============
Found combination:911
...4031403240255003540403340265004540514041405240424053403550127003630364036502150225013600281009000911
Digits typed: 1046
Combinations tested: 1284
============
Found combination:1978
...8784108785007786106786205787104787202878101378101478101578003278001578101678001678101778000988001978
Digits typed: 207036
Combinations tested: 228608
JavaScript solution, tested on jsfiddle.net/jacklehamster/j5qbharr
Not 100% sure it's O(nk) though. It kinda looks like O(n * k^2)
function findPalinPair(array) {
function flip(str) {
return str.split("").reverse().join("");
}
function isPalin(str) {
for(var i=0;i<str.length/2;i++) {
if(str.charAt(i)!=str.charAt(str.length-1-i)) {
return false;
}
}
return true;
}
// hash will store all the possible matches
var hash = {};
var wordsSeen = {};
for(var i=0;i<array.length;i++) {
var word = array[i];
wordsSeen[word] = true;
if(hash[word]) {
return isPalin(word+hash[word])?[word,hash[word]]:[hash[word],word];
}
// first reverse the entry (tacoto=>otocat)
var rev = flip(word);
// we know that the reverse would be a match. (tacotootocat)
hash[rev] = word;
// some substrings of the reverse (like "cat") are also match
for(var j=1;j<rev.length-1;j++) {
var splitLeft = rev.slice(0,j);
var splitRight = rev.slice(j);
if(isPalin(splitLeft + word)) {
if(wordsSeen[splitLeft]) {
return [splitLeft,word];
}
hash[splitLeft] = word;
}
if(isPalin(word + splitRight)) {
if(wordsSeen[splitRight]) {
return [word,splitRight];
}
hash[splitRight] = word;
}
}
}
return null;
}
function test(array) {
var result = findPalinPair(array);
document.body.innerHTML += (result?result.join("-"):"nothing") + "<br>";
}
test(["bat","tab","cat","junk"]); // bat-tab
test(["bat","tabloid","cat","junk"]); // null
test(["bat","tabloid","cat","ototac","junk"]); // cat-ototac
test(["bat","tabloid","cat","tacoto","junk"]); // tacoto-cat
test(["tacoto","bat","tabloid","cat","junk"]); // tacoto-cat
// Test with a bunch of random numbers
function testNumber() {
var array = [];
for(var i=0;i<100000;i++) {
array.push(""+Math.floor(Math.random()*100000000));
}
test(array);
}
for(var i=0;i<10;i++) testNumber();
O(log n) solution.
function sqrt(num) { // will return 0 if not perfect square
// binary search for the number for which n^2 = num
var low = 0;
var high = num;
while(low+1<high) {
var mid = Math.floor((low+high)/2);
var sq = mid*mid;
if(num<sq) {
high = mid;
}
else {
low = mid;
}
}
// if low^2 = num, we found the number. Otherwise it's not a perfect square
return low*low==num?low:0;
}
I thought I'd describe the algorithm above.
Basically, we keep cutting out a chunk of the string, and recursively call solve on the rest of it:
So for aaaasasatb, cut "a" and call compress on "aaasasatb".
Then cut "aa", compress("aasasatb")
...
On each chunk that we cut, we see if we can shrink it, using the shrink function.
So we'll get
"1a" + compress("aaasasatb")
"2a" + compress("aasasatb")
"3a" + compress("asasatb")
"4a" + compress("sasatb")
"1aaaas"+compress("asastb") <= note that it's unable to shrink "aaaas".
...
"1aaaasasat"+compress("b")
Out of all the result above, we'll look for the shortest string, which is going to be "4a"+compress("sasatb").
The shrink function work as follow: Try to see if there's a cycle until the end with the first letter, then with the first 2 letter, first 3 letters ...
So for "sasa", see if there's a cycle with "s". NO
See if there's a cycle with "sa". YES. So turn "sasa" into "2sa".
It seems like a lot of computation, but thanks to memorization (via shrinkHash), it's quite fast!
Javascript code on jsfiddle/jacklehamster/z3gyv29a/
/* output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24
[7,8,9,3] = 24
(8*3) = 24
[7,7,7,7] = 24
NO SOLUTION = 24
[1,2,3,4] = 24
(3*(2*4)) = 24
[100,50,20,5] = 24
((100+20)/5) = 24
*/
function express(tree) {
if(tree.left) {
return "("+express(tree.left)+tree.operation+express(tree.right)+")";
}
else {
return tree.value;
}
}
function solve(array, target) {
var nodes = [];
for(var i=0;i<array.length;i++) {
nodes.push(
{
value:array[i],
bits: 1<<i
}
);
}
for(var i=0;i<nodes.length;i++) {
for(var j=0;j<nodes.length;j++) {
if(i!=j) {
if(nodes[j].value==target) {
return express(nodes[j]);
}
var nodeLeft = nodes[i];
var nodeRight = nodes[j];
if((nodeLeft.bits & nodeRight.bits) == 0) {
nodes.push(
{
operation:'+',
value:nodeLeft.value+nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'-',
value:nodeLeft.value-nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'*',
value:nodeLeft.value*nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'/',
value:nodeLeft.value/nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
}
}
}
}
return "NO SOLUTION";
}
function outputSolution(array, target) {
var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
var div = document.createElement("div");
var result = solve(array, target);
div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
document.body.appendChild(div);
}
outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);
/*
output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24
[7,8,9,3] = 24
(8*3) = 24
[7,7,7,7] = 24
NO SOLUTION = 24
[1,2,3,4] = 24
(3*(2*4)) = 24
[100,50,20,5] = 24
((100+20)/5) = 24
*/
function express(tree) {
if(tree.left) {
return "("+express(tree.left)+tree.operation+express(tree.right)+")";
}
else {
return tree.value;
}
}
function solve(array, target) {
var nodes = [];
for(var i=0;i<array.length;i++) {
nodes.push(
{
value:array[i],
bits: 1<<i
}
);
}
for(var i=0;i<nodes.length;i++) {
for(var j=0;j<nodes.length;j++) {
if(i!=j) {
if(nodes[j].value==target) {
return express(nodes[j]);
}
var nodeLeft = nodes[i];
var nodeRight = nodes[j];
if((nodeLeft.bits & nodeRight.bits) == 0) {
nodes.push(
{
operation:'+',
value:nodeLeft.value+nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'-',
value:nodeLeft.value-nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'*',
value:nodeLeft.value*nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
nodes.push(
{
operation:'/',
value:nodeLeft.value/nodeRight.value,
left:nodeLeft,
right:nodeRight,
bits: nodeLeft.bits|nodeRight.bits
}
);
}
}
}
}
return "NO SOLUTION";
}
function outputSolution(array, target) {
var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
var div = document.createElement("div");
var result = solve(array, target);
div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
document.body.appendChild(div);
}
outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);
JavaScript:
function solve(array, target) {
var result = [];
function recursolve(equation, sum) {
if (sum == target) {
result.push(equation.join(""));
} else if (sum < target) {
for (var i = 0; i < array.length; i++) {
recursolve(equation.concat([array[i]]), sum + array[i]);
}
}
}
recursolve([], 0);
return result;
}
/* output:
aaaasasatb = 4a2sa1tb
aaaaabaaaaabaaaaabaaaaab = 4aaaaab
aaaaabaaaaabaaaaabZaaaaab = 3aaaaab1Z5a1b
abcdbcdff = 1a2bcd2f
aaaabbbbabababcdabcdeeeffffefef = 4a4b2ab2abcd3e4f2ef
*/
var shrinkHash = {};
function shrink(str) {
// find best cycle
if (shrinkHash[str]) return shrinkHash[str];
for (var size = 1; size <= str.length / 2; size++) {
var chunk = str.substr(0, size);
var isCycle = true;
for (var i = chunk.length; i < str.length; i += chunk.length) {
if (chunk != str.substr(i, chunk.length)) {
isCycle = false;
break;
}
}
if (isCycle) {
return shrinkHash[str] = (str.length / chunk.length) + chunk;
}
}
return shrinkHash[str] = "1" + str;
}
function compress(str, record) {
if(shrinkHash[str]) {
return shrinkHash[str];
}
if (!str.length) return "";
var minString = "1" + str;
if (!record) record = minString.length;
for (var i = 1; i <= str.length; i++) {
var left = shrink(str.slice(0, i));
if (left.length > record) {
continue;
}
var right = compress(str.slice(i), record);
var finalString = left + right;
if (finalString.length < minString.length) {
minString = finalString;
record = minString.length;
}
}
return shrinkHash[str] = minString;
}
function solve(str) {
var html = "<b>" + str + "</b> = <i>" + compress(str) + "</i>";
var div = document.createElement("div");
div.innerHTML = html;
document.body.appendChild(div);
}
solve("aaaasasatb");
solve("aaaaabaaaaabaaaaabaaaaab");
solve("aaaaabaaaaabaaaaabZaaaaab");
solve("abcdbcdff");
solve("aaaabbbbabababcdabcdeeeffffefef");
After thinking more about my own question ;-P, I think there's this one solution that seems that it might work, though I'd have to test it:
Step 1: Keep rotating the tree clockwise until there's no left
Step 2: Output root, move root to root right
Step 3: Repeat step 1.
There are some details about the question though (and this is just what I kinda remember from the original interview question, feel free to just interpret the problem as it is written).
#1 - call-stacks do count as space, so recursion is out of the picture for O(1) space.
#2 - I'm pretty sure the solution had to be O(n) time as well.
#3 - This part I can't remember for sure, but I thought we had to restore the tree in its original state after the traversal (in which case my solution here wouldn't even work). Now I could be wrong about this.)
Not sure why replies are saying this is not a uniform shuffle.
Conceptually, it's the same as taking out elements from the old array one by one at random, and pushing them in a new array. Except that this is done in place, with the new array being the slice from 0..i-1 and the old array from i to N-1.
Flagging notes is actually taking O(n) space since you'd have to add extra data on each node.
By changing the node without taking extra space, you'd have to change the left/right pointers. (So that's another hint.)
I had this question a long time ago, and managed to pseudo-solve it. But now thinking about how to code it, I can't even imagine how it could possibly work.
- Jack Le Hamster May 05, 2015Javascript solution! You can paste it in a javascript console:
function stairs(n,array) {
if(array===undefined) array=[];
if(n>=1) {
stairs(n-1,["1"].concat(array));
}
if(n>=2) {
stairs(n-2,["2"].concat(array));
}
if(n==0) console.log(array.join(""));
}
stairs(5);
Note, I use array concatenation instead of string concatenation because it's faster.
- Jack Le Hamster April 22, 2015Doesn't work with the following graph:
.A
./\
BC
.\/
.D
./\
EF
.\/
.G
Starting at A, you're going to encounter D twice, yet it's a critical node.
Pass an array of nodes in the solve function. For each nodes, push the left and right children in an array. When done, assign each node in the array to the next one.
Call solve on those children.
At the beginning, call solve on an array of size 1 with the root only.
function solve(roots) {
var children = [];
for(var i=0;i<roots.length;i++) {
var root = roots[i];
if(root.left)
children.push(root.left);
if(root.right)
children.push(root.right);
}
for(var i=0;i<children.length-1;i++) {
children[i].next = children[i+1];
}
solve(children);
}
I meant
- Jack Le Hamster June 03, 2015