New adventures

Well this is it. I have now done 3.5 years at TEAMworks and its time for me to toss in the towel. It has been enriching to say the least. I don't think I have been working in a more tolerance, patient and mentally challenging environment in my life.

My motivation, focus and technological evangelism took a hefty smack on the head somewhere along the road but I am finally over that now.

I joined this company with the wish and dream that I could create something from nothing utilizing all my collected experience in all sorts of technological, social and educational settings but it seems that all the effort was for nothing. There are so many things that went wrong along the way so there is no need to detail it here. But worth mentioned maybe...

...the struggle with finding experienced and skilled staff and the problem with trying to keep in all together because nobody liked each other or to scared to say anything

...the boss/CEO who decided that nobody knew anything, who didn't wanted to listen to reason and advice from obvious expertise and who went his own way with his penny wise, pound foolish mentality

...the ignoring of my requests of key personnel and skills in interaction/graphical design with the motivation that "we can do it ourselves, it takes to long time, we have to go GLOBAL NOW!!"

After 3.5 years of working here my boss is someone you are afraid of. Every person that has left the company (or has been fired) refuses to come back to the office to visit us less the boss is not there.

Hmmm... its nice to be away from that hellhole. Initially I didn't really dislike everything that had to do with that company. So, it has been said. Its done I can move on.

Pax mobiscim

Simplistic Thinking

I recently came across a Google interview questions that kind of intrigued me. It went like this:

"You have a list of numbers which some of them are negative and some of them are positive, find out the largest sum of sequential subset of numbers from this list."

For example:

-5, 20, -4, 10, -18

The solution is the subset [20, -4, 10] which its sum is 26

The solution for this question is not summary the positive numbers or sort the list because the subset needs to be sequential.

A possible not efficient answer would be to to calculate the summary of all the possible subsets in the list but the complexity of this solution is O(N^2)

However the interviewer wanted a solution of O(N) !!!

This question is so full of subtleties that it cannot fail to entice even the most interview savvy reader. In order to be able to properly answer this question the interviewee not only has to understand big O, but also this particular type of problem. One brilliant aspect of the question is that it already contain parts of the answer. The answer can be found in the requested solution of O(N). This ought to give enough information on how the algorithm should be structured (or should it?)

O(N^2) solution (Groovy)

This solution illustrates a simple solution to this problem with O(N^2) complexity in Groovy.

def findLargestSubSequence(seq)
{
def tmpSeq = [], maxSeq = []
def maxVal = -9999999

seq.eachWithIndex { val, index ->
seq[index..seq.size()-1].eachWithIndex { innerVal, innerIndex ->
tmpSeq = sequence[index..innerIndex]
if(tmpSeq.sum() > maxVal) {
maxVal = tmpSeq.sum()
maxSeq = tmpSeq
}
}
}
maxSeq // no return needed, value is returned automatically
}

println findLargestSubSequence([-5, 20, -4, 10, -18])

And the O(N^2) comes from the nested iterations of course :)

O(N) solution

This solution illustrates one (not simple) solution to this problem with O(N) complexity in Java.

int[] findLargestSubSequence(int[] sequence)
{

int mini = -1, minv = 0, maxi1 = 0, maxi2 = 0, maxv = -9999999;
int[] seq = sequnce.clone();

for(int i = 0; i <> {

if (i > 0) {
seq[i] += seq[i-1];

}
if (seq[i]-minv >= maxv) {
maxv = seq[i] - minv;
maxi1 = mini + 1;
maxi2 = i;
}
if (seq[i] < minv) {
minv = seq[i];
mini = i;
}

}
return getSubArray(seq, maxi1, maxi2); // you have to write this :)
}

Here we see that there is only one iteration. The code is pretty hard to read though as it relies on a rewriting patterns where the path towards the solution is driven by successive alteration to the source input.