Personal

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

Todays and yesterday search terms bringing people (very few of them) to my blog. Why “Babbo Natale”? In Italian, “Babbo Natale” means “Santa Claus”, btw. I’m fat, but not THAT fat!!! Today  Yesterday  Weird.

My colleague and friend Luca (@lucabox) described a better solution to the problem of "Finding the first non repearing char in a string in O(n) time and O(1) space". It uses smartly the space, making the solution nicer and slicker. Or we are just 2 geeks that need to give more attention to their girlfriends :P Luca’s solution description The logic of this solution is based on the usage of an array of unsigned chars. Every char (assumed to be lowecase) has an associated small byte (1 char = 8 bits), where the bits 0x1 and 0x2 (the 2 least significant) represents, respectively, “present once in the input string” and “present multiple times in the input string”. After the input is “scanned” once, and every letter is marked with the correspondent “presence bit” (once, multiple or none), it get’s scanned a second time to find the first char of the input which has the bit “present once” set to “1”. ...

I would like to post some of the Brain Teaser (mostly algorithmic problems) I’m giving to interviewee lately, and of course some that were submitted to me in the past. But I can’t promise I will keep doing it regularly: just that I will try (blogging regularly is hard for me). The solution will be at the end of the post, just in case you would like to try to solve it first. Of course my solution it’s MY solution: it could be buggy or non-optimal. In those cases, PLEASE share your view and, better, your alternative solutions. Problem description Determine the first non-repeated character in a word. For example, in abbcaf it should return c. Do this in [O(n)](http://en.wikipedia.org/wiki/Big_O_notation) time with O(1) space. Some observation O(n) means that the complexity of time of the algorithm must grow linearly with the input. So, if in this case the input is an array of characters, an acceptable solution can contain >1 non-nested FOR cycle. O(1) means that the complexity of space of the algorithm must be constant, regardlessly of the input. Conditions For simplicity, will assume that: the input is always a lowercase string (enforcing this condition is easy and cheap) the input is made made only of the letters of the english alphabet Those conditions will then become the “base” of our solution. Of course, you are free to assume more conditions: it’s usually a good way to solve problems to start adding conditions that simplify the search of a solution, and then start a process of subtraction to arrive to have as less conditions as possible. It usually works for me. ...