Posts tagged solution

Binary Tree Rebuilder

Feb 5th

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

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

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 >

“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 >

Money change problem: Greedy vs. Dyn.Pro.

Jan 17th

Posted by Detro in IT / Comp-Sci / Code

7 comments

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:

S[0...n-1], with 0 <= S[i] <= (A/S[i]) and 0 < i < n-1

where:

A = Sum_{[i=0 -> n-1]} { D[i] * S[i] }
Min{ Sum_{[i=0 -> n-1]} { S[i] } }

In other words

Find the smallest amount of coins to make the given amount. More >

Fibonacci’s numbers calculator

Jan 5th

Posted by Detro in Curiosity

No comments

Another simple-but-yet-interesting problem that I found challenging solving is the to Write a Fibonacci’s numbers calculator. It’s a REALLY SIMPLE problem, but still can demonstrate how superficial thinking in programming can lead to dramatically bad solutions.

What’s a Fibonacci’s number

A Fibonacci’s number is an integer number generated using the following function:

Assumed that:
f(0) = 0
f(1) = 1

for a generic “n” Integer:
f(n) = f(n-1) + f(n-2)

For example, the first 20 Fibonacci’s number are:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

The young-and-entusiast approach

Recursion! We all love the elegance of it. When we manage to write something that uses Recursions, everything seems easier and simpler to our eyes for a while. BUT, in this particular case, using recursion for implementing such simple task is really bad.

Why? Because at every call to this function, it will generate 2ⁿ recursive function calls. A bit of a nightmare for the process call stack if the whole purpose of this thing is calculating a “stupid” integer number.

Functions call tree using a recursive algorithm

Plus, given the nature of the function itself, it will recalculate the same f(x) over and over again, because f(x) is going to be a subproblem shared between a certain y and z, where both y > x and z > x.

Result? An awful implementation. With a quick Big-Oh analysis I would say that the Time Complexity of this “monster” will be O(2ⁿ).
Don’t believe it? Check out the implementation here:

#include <stdio .h>

unsigned long fibonacci_slow(unsigned short i)
{
    if ( i == 0 )
        return (0);

    if ( i == 1 )
        return (1);

    return ( fibonacci_slow(i-1) + fibonacci_slow(i-2) );
}

int main(int argc, char** argv)
{
    unsigned short i, input;
    unsigned long curr = 0, prevprev = 0, prev = 1;

    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (1);

	printf("RESULT: fibonacci(%d) = %lu\n\n", input, fibonacci_slow(input));
	return (0);
}

Running it on my Code 2 Duo laptop with n > 40 takes around 10 seconds. For n = 50 I got bored to wait after 1 minute passed by.

If you check out this book, it is going to tell you that such solution is going to take 13 days to come out with a solution, for an average machine (i.e. a machine where O(1) = 0.001 µs).

BUT, of course, I have an alternative solution. Actually, more then one. And the best runs in O(log(n))
More >