Posts tagged code

3 o’clock javascript

Mar 28th

Posted by Detro in Curiosity

No comments

I was writing some code to react at a textarea.onKeyUp. I take the size of the current textarea.val().length, update an element and do some other stuff.

Yawn
yawn

The first version of the code looked like:

$('#message').keyup(function(e){
   $('#chars_num').html( new_len );
   $('#sms_num').html( Math.floor($('#message').val().length / 161) +1) );
});

Working good, but was clearly slow: every keystroke was “giving back the cursor” too slowly for a fast typer like me. I went to take a look at twitter, and their text box was WAY FASTER.
More >

Binary Tree Rebuilder

Feb 5th

Posted by Detro in IT / Comp-Sci / Code

No comments

Imagine you have a Binary Tree, with those characteristics:

  • Nodes do not respect any order relation – In other words: it’s not a Binary Search Tree of any kind
  • Every node appears once and only once within the tree
A nice Binary Tree
A nice Binary Tree

Then, your little brother passes by your desk and, to upset you, deletes the tree from your computer memory/HD (yeah, I know, I’m pathetic at inventing hypothetical situations :-P ).

Fortunately though, you previously did a Pre-Order and an In-Order visit of your tree, and stored the result in an 2 nice array.

Can you rebuild the original tree structure out of this 2 array?

How are you going to rebuild it?

Yes, you can! (Sorry, I couldn’t resist). And it’s quite easy as well. What you have to do, is the following:

  • Take the first element of the PreOrder Array and use it as root of a new tree
  • Find the position of this New Node in the InOrder Array, scanning it from 0 to n-1 (n is the number of Nodes)
  • IF next element in the PreOrder Array is on the left of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from 0 to the position of the New Node in the InOrder Array -1.
  • IF next element in the PreOrder Array is on the right of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from the position of the New Node in the InOrder Array +1 to n-1.
  • Return the New Node

By the way, this doesn’t work. To fix it we should be more generic, specifying things a little bit better. Things like:

  • Every recursive calls takes into account a portion of the InOrder array; in the case of the first call it’s the entire array
  • There is going to be as much recursive calls as the number of elements in the PreOrder array

Of course, is a tree what we are talking about here: recursion is a MUST. More >

Prime Numbers Generator

Jan 23rd

Posted by Detro in Curiosity

3 comments

I believe I don’t have to describe what primes are, what are their properties and what not. This post is more a tribute to geek-ness of 2 friends-and-colleagues (@lucabox) that have fun thinking of algorithms to solve stupid (or less stupid), and always useless problems ;-) .

Optimus Prime
Optimus Prime :-P – yeah yeah, a stupid joke

Briefing

This code is based on the assumption that we want to generate very very large primes, so it uses unsigned long long to store the values, instead of classical unsigned int. Live with that.

Also, give that there is nothing much better then a “try-dividing-by-every-previous-prime” out there (there are alternatives, but I’m not aware of more complex ones), I took a look to some properties of Primes, and putted into the algorithm those properties as conditions for early stop:

  1. Say P[i] are the previously calculated Primes; If trying dividing value V by every P[i] we find that P[i] > sqrt(V), stop dividing and classify V as a newly found prime
  2. No need to check any even number: they are divisible by 2, so no primes by definition
  3. No need to allocate more space then an array of the size of the requested prime ordinality: everything can be done in place

More >

“Bidirectionally multiplied” array

Jan 22nd

Posted by Detro in IT / Comp-Sci / Code

No comments

Another small problem before I go to sleep tonight:

There is an array A[N] of N numbers.
You have to compose an array Output[N] such that Output[i] will be equal
to multiplication of all the elements of A[N] except A[i].

For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1]
will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

What is funny of the problem, is the fact that the O(n) constraint, makes it sound like is going to be hard to solve. Doesn’t it? Well, it’s not.

The solution is quite simple, so I suggest you take your 10 minutes to think about it, then continue to see the code. More >

1234»