Posts

Imagine you have a Binary Tree, with those characteristics: * Nodes do not respect any order relation - In other words: it's <strong>not</strong> a [Binary Search Tree](http://en.wikipedia.org/wiki/Binary_search_tree) of any kind * Every node appears <em>once and only once</em> within the 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. ...

This idea comes out for an old university-time idea: to write a serverless chat application. Of course, I’m aware of the complications and the problems that using Broadcasting could create, so this problems would be took in consideration by design. But why now? I was thinking of a way to reduce the “office distances”: making easy to connect with a person who works in your own office. I know, it sounds a bit “creepy” to depend on an application to do that. After all you could just stand up and go to the colleague’s desk. And that’s what I’d normally do: nothing impossible. ...

I would have just posted it on Twitter, but I have some comments about this video. One of the first video of the iPad Simulator Watch it in Full screen at 720p: it help “feeling” the proportions used by Apple in the UI It clarify how it does execute iPhone apps: they most probably implement the iPhone API as is: indeed even the Keyboard that you get in an iPhone application is the same (no super large/super cool keyboard of the iPad ...

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 :-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. ...

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). ...

I’m “studying” this algorithmic technique: Backtracking. This is an algorithmic approach to problem solution that I trust every good Computer Scientist already uses; but taking a good theo-practical look at it is something better. A Backtracking Tree I believe you can find enough informations about it online (the 2 links I provided are more than enough), so I’ll go straight to the problem. Problem definition Given an integer n, and the set S = { 1 … n }, calculate (print) all the possible subsets of S. For example, for n = 1, all the possible subsets are { 1 } and { } (empty set). For n = 2, all the possible subsets are: { 1 2 } { 1 } { 2 } { }. In general, for the set made of the first n Integers, the number of possible subsets is 2n. ...

This is a classical problem of Computer Science: it’s used to study both Greedy and Dynamic Programming algorithmic techniques. I hate having my pocket full of copper!!! -_- Definition Given: A set of n Denominations D[0…n-1] in ascending order, representing a Monetary Coin System An money amount A, as input calculate a solution: * <strong><code>S[0...n-1]</code></strong>, with <code>0 &lt;= S[i] &lt;= (A/S[i])</code> and <code>0 &lt; i &lt; n-1</code> where: * <strong><code>A = Sum_{[i=0 -> n-1]} { D[i] * S[i] }</code></strong> * <strong><code>Min{ Sum_{[i=0 -> n-1]} { S[i] } }</code></strong> In other words Find the smallest amount of coins to make the given amount. ...

For this you need someone to teach it to you: if you made it yourself, then you are a very good Comp-Sci, and you should send your CV to Google ASAP. ;) Without branching O_o? Yes, without using any “if ( a < 0 )…”. To do that, you need to refresh how Two’s Complement works, then come back. What we really need to focus on is that, given a signed int A, the negative of that number is: B = ~A + 1. BUT, we are trying to calculate the Absolute Value, not the negative. So, something like: ...

Someone says this is an old lame trick. I think it’s simple and clever use of XOR. How/Why does it work? It’s built around the properties of the XOR ^ operator, who has the following properties: A ^ B = B ^ A (commutative) A ^ 0 = A A ^ 1 = ~A A ^ A = 0 So, you can see how it get’s applied here: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <stdio .h> int main(void) { unsigned int a, b; // ... populate somehow "a" and "b"... printf("a = %d - b = %d\n", a, b); a ^= b; // store in "a" the value of "a XOR b" b ^= a; // store in "b" the value of "a XOR b XOR b" = "a XOR 0" = "a" a ^= b; // store in "a" the velue of "a XOR b XOR a" = "b XOR 0" = "b" printf("a = %d - b = %d\n", a, b); } Neat.

What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need). Pascal’s Triangle first 6 rows The thing I wrote here is a generator of the n-th row of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a Triangular Matrix, and building every row based on the one above, solution is built in place. How does it work The result is generated “filling the row from right to left”. I start initiating the element on the right hand side to ‘1’. Then, I run something like: ...