Longest subsequence

Surfing Hacker News the other day, I came across this fascinating article about Palantir's interview process. How to Rock an Algorithms Interview.

I thought I would write my thought processes to one of the Gild.com code challenges that I attempted some time back.

The problem statement is in essence, given a sequence of unsorted integers, find the count of the longest sequence of monotonically increasing numbers in the original sequence.

So, here's my thought process towards the solution:

Tip: I read it in a book somewhere, but the author says (paraphrased) "Fix the data structure, and the algorithm will become readily apparent". This has been a very useful guide in all my programming tasks.

The first thing that came to mind when I saw this problem was "stacks". The solution has to involve stacks in some way. There has to be some function within the algorithm that says, given a stack of numbers on it, check the next number in the sequence and add it to the stack only if the number is greater than the one already on stack.

Stack<int> s = new Stack<int>();

foreach (int i in list)
{
  if (i > s.top())
  {
      s.push(i);
  }
}

Given a sequence of say "1 20 10 11 12 21", the solution should be "5" (1 10 11 12 21), but the naive implementation would solve to "3" (1 20 21). I thought I would add a fix that would replace the top on the stack with the next number if the next number is less than the top.

Stack<int> s = new Stack<int>();

foreach (int new in list)
{
  int top = s.pop();

  if (new > top)
  {
     s.push(top);
     s.push(new);
  }

  if (new > s.top() && new <= top)
  {
      s.push(new); //Replace the top value with the smaller value
  } else
  {
      s.push(top); //Put back the original value...
  }
}

To be continued..

Welcome

Hi,

This is my new blog about programming and debugging.