String search in O(n + m)

  • 1047 words

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: function ... read more

Count bits set in parallel

  • 1262 words

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

Largest square array of same integers

  • 1171 words

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, ... read more

The "Polite" Merge Sort

  • 768 words

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

Fibonacci's numbers calculator

  • 1973 words

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

YouTube >> The Go Programming Language

  • 121 words

A video that I need to watch myself (I just managed to watch 25% of it), but I thought was good to post it here: just to remind how good it is to think “out of the box”. Even in Programming Languages. </param></param></param></embed> Presenter: Rob Pike Presented on: 30th Oct 2009 Go is a new experimental systems programming language intended ... read more

Find the non repeating char in O(n) time and O(1) space - v2

  • 440 words

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

Babbo Natale? O_o

  • 34 words

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

Find the non repeating char in O(n) time and O(1) space

  • 757 words

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