Hand crafted longest common sub sequence

Question

I know that the below solution is not the best one and I am in the way to learn that stuff till then I have applied the brute force to see how far I can go with my intuition.

console.clear();
function allButLast(arr) {
 return arr.slice(0, arr.length - 1);
}
function last(xs) {
 return xs.slice(-1);
}
function map(xs, cb) {
 return [].map.call(xs, cb);
}
function powerset(xs) {
 if (xs.length === 0) return [[]];
 var res = powerset(allButLast(xs));
 return res.concat(map(res, function(el) { return el.concat(last(xs)); }));
}
console.log(powerset([])); // [[]]
console.log(powerset([1])); // [[], [1]]
console.log(powerset([1, 2])); // [[], [1], [2], [1, 2]]
console.log(powerset([1, 2, 3])); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
function increasing(xs) {
 var i = 1,
 l = xs.length;
 for (;i < l; i++) {
 if (xs[i] < xs[i - 1]) return false;
 }
 return true;
}
console.log(increasing([1, 2]));
function LIS(xs) {
 var res = [];
 [].forEach.call(powerset(xs), function(subset){
 if (increasing(subset) && subset.length > res.length) res = subset;
 });
 return res;
}
console.log(LIS([2, 3, 1, 4, 0, 5])); // [2, 3, 4, 5]

I have tried to be as much naive as possible because sometimes the best solution doesn't come to your mind most probably in the case of interview etc. I need to know if the code is clear and readable?

• Tolani: Please could you add more context to your post. What you are trying to achieve should not only be in your question title but also in your question body

Answer 1

Interesting question,

I would say for an interview, if you are given a task and you think you need combinations or permutations, then there is a good chance it's a trick question. Those are terrible for performance and I would avoid them as the plague during interviews.

Secondly, your code is hard to read. Only because of the comment on the very last line did things come together for me.

Other than that;

• Try to be consistent

  function allButLast(arr) {
   return arr.slice(0, arr.length - 1);
  }
  function last(xs) {
   return xs.slice(-1);
  }
  

  These functions both get an array, but in one the argument is called arr, in the other one xs. They should have the same name, I would go for list.

• I like your powerset routine, and might borrow it

• I dont understand [].reduce.call in sum, why not just xs.reduce ? From an interview perspective it makes me think you dont understand how reduce works :/

On the whole this implementation should be light years faster, though I only tested it with your test case which I got right the first time, so I have good hopes ;)

console.log(LIS([2, 3, 1, 4, 0, 5])); // [2, 3, 4, 5]
//Find the longest common sub sequence
function LIS( list ){
 var indexes = {},
 //Possibly too verbose variable name ;)
 lastIntegerofLargestSequence,
 largestSequenceLength = 0,
 output = [];
 
 for( n of list ){
 
 //Have we processed a predecessor yet?
 if( indexes[n-1 ] !== undefined ){
 //There is a predecessor, if we have never found n,
 //then put n with predecessor's length + 1
 if( indexes[n] === undefined ){
 indexes[n] = indexes[n-1] + 1;
 //Otherwise ONLY put that predecessor length + 1
 //if that would make a better (longer sequence) 
 }else if( indexes[n-1] + 1 > indexes[n] ){
 indexes[n] = indexes[n-1] + 1; 
 }
 //First number in a possible sequence
 }else if( indexes.n === undefined ){ //That 0 ;/
 indexes[n] = 1;
 } 
 
 //Keep track of the largest sequence
 if( indexes[n] > largestSequenceLength ){
 largestSequenceLength = indexes[n];
 lastIntegerofLargestSequence = n;
 }
 }
 for( var i = lastIntegerofLargestSequence - largestSequenceLength + 1; i <= lastIntegerofLargestSequence ; i++ )
 output.push(i);
 
 console.log(output)
}

• CodeYogi: Overall good suggestions, but a few thoughts I really struggled to write that powerset subroutine and I have to console.log to check its correctness (hopefully I won't get this much time in any interview), regarding [].reduce.call I would make a separate function like map because I need a clear functional interface and small functions makes the intent of the code clear. I still need to understand your code. Last but not least I got this question in an interview and was expected to solve on the fly, don't know what interview culture is nowadays but it feels absurd to me.
• konijn: As a somewhat older person, I feel for you, it is definitely harder now. Keep practicing, hackerrank.com is great for building skills.