Complexity

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

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