about 1 month ago - 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
Then, your little brother passes by your desk and, to upset you, deletes the tree from [...]
about 1 month ago - 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 – yeah yeah, a [...]
about 1 month ago - 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] [...]
about 1 month ago - No comments
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 [...]
about 1 month ago - 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 [...]
about 2 months ago - 4 comments
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, [...]
about 2 months ago - No comments
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 [...]
about 2 months ago - 2 comments
Searching a string inside another string is a very easy task. Given a string A and a string B, start a loop over A from left to right and, for every letter, start an internal loop to see if there is a match with the letters of B.
A ball of string
Pseudo code would look something [...]
about 2 months ago - 2 comments
This time it’s not something I make myself. Indeed, I still can’t “see” it 100%: I got it, but it’s a bit complex.
A cute little lady counting (bits? )
It’s a method to count the number of bits in a number in O(1), in just 5 lines of code. INHUMAN.
The “human” solutions
Of course, there [...]
about 2 months ago - No comments
Tonight it’s a challenging one. Or, better, a problem of which is really difficult to find a good solution in < O(n3). Indeed, it’s a question that an ex-colleague was asked during an interview with Big-G.
The guy, a part from being a REALLY smart guy, is also very humble, and he doesn’t want to be [...]
about 2 months ago
What about:
a+=b;
b=a-b;
a-=b;
Or just for fun:
a*=b;
b=a/b;
a/=b;
But of course, you would never use * and / this way
about 2 months ago
Yes, but I think this can suffer of overflow if “a” or “b” are too big.
But very nice indeed.