English

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

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

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 like this: 1 2 3 4 5 6 7 function NaiveSearch(string s[1..n], string sub[1..m]) for i from 1 to n-m+1 for j from 1 to m if s[i+j-1] ≠ sub[j] jump to next iteration of outer loop return i return not found Time Complexity? O(n * m), where n is the size of A and m is the size of B. ...

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 are methods that look way more easy and, given that the size of a number in memory is “fixed”, the O(1) still stands. For example: 0. Based on the “evenness/oddness” of the number 1 2 3 4 5 6 7 8 9 10 unsigned int bits_counter_v0(unsigned int x) { unsigned int count = 0; while ( x != 0 ) { // If odd, add 1 count += (x % 2 == 0) ? 0 : 1; x >>= 1; } return count; } 1. Counting one bit at a time (always the least significant one) 1 2 3 4 5 6 7 8 9 10 unsigned int bits_counter_v1(unsigned int x) { unsigned int count = 0; while ( x != 0 ) { // If least-significant bit is 1, add 1 count += (x & 1) ? 1 : 0; x >>= 1; } return count; } 2. Counting 4 bit at a time with max 8 shifts, using an “hashmap” with precalculated results The fact that it can count the bits in “max 8 shifts” has the trade off of the memory used by the hashmap. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 unsigned int bits_counter_v2(unsigned int x) { unsigned int count = 0; // "Hashmap" of the values for the least significant 4 bits unsigned int int_to_bits_count[16] = { 0, // 0 00 1, // 1 01 1, // 2 10 2, // 3 11 1, // 4 100 2, // 5 101 2, // 6 110 3, // 7 111 1, // 8 1000 2, // 9 1001 2, // 10 1010 3, // 11 1011 2, // 12 1100 3, // 13 1101 3, // 14 1110 4 // 15 1111 }; while ( x != 0 ) { // Add the bits count of the least significant 4 bits count += int_to_bits_count[ x & 15 ]; x >>= 4; } return count; } Let’s see what some insane people made. ...

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 mentioned by name. So, sorry for girls looking for a young, smart, promising young man: you need to find who he is yourself. ;) ...

Another old-classic problem: the Merge Sort. Merge Sort Algorithm The problem of the classical implementation The whole algorithm is explained in the wikipedia link above, so I’ll focus on the problem here. The Merge Sort is an in-place-sorting-algorithm that requires some support memory to do it’s calculations. At the “merge step”, an amount of memory as large as the current portion of array being merged is allocated to be used as priority queue (again, the why is easy to find on the web). After this memory is used, normally get’s released. ...

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