Code

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

Someone says this is an old lame trick. I think it’s simple and clever use of XOR. How/Why does it work? It’s built around the properties of the XOR ^ operator, who has the following properties: A ^ B = B ^ A (commutative) A ^ 0 = A A ^ 1 = ~A A ^ A = 0 So, you can see how it get’s applied here: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <stdio .h> int main(void) { unsigned int a, b; // ... populate somehow "a" and "b"... printf("a = %d - b = %d\n", a, b); a ^= b; // store in "a" the value of "a XOR b" b ^= a; // store in "b" the value of "a XOR b XOR b" = "a XOR 0" = "a" a ^= b; // store in "a" the velue of "a XOR b XOR a" = "b XOR 0" = "b" printf("a = %d - b = %d\n", a, b); } Neat.

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

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

Fancy $PS1 setting The code to make the Bash prompt looks like mine is (~/.bashrc): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 case $TERM in xterm*|rxvt*) TITLEBAR='\[\033]0;\u@\h:\w\007\]' ;; *) TITLEBAR="" ;; esac; PS1="${TITLEBAR}\n\[\033[0;0m\][\033[0;32m\]time: \ \[\033[0m\]\[\033[1;31m\]\t\[\033[0m\]\[\033[0;0m\]]-\ [\[\033[0m\]\[\033[0;32m\]host: \[\033[0m\]\ \[\033[1;31m\]\h\[\033[0m\]\[\033[0;0m\]]-\ [\[\033[0m\]\[\033[0;32m\]user: \[\033[0m\]\[\033[1;31m\]\u\ \[\033[0m\]\[\033[0;0m\]]-[\[\033[0m\]\[\033[0;32m\]bash: \ \[\033[0m\]\[\033[1;31m\]\v\[\033[0;0m\]]\n\ \[\033[0;0m\][\[\033[0;32m\]cwd: \[\033[0m\]\[\033[1;31m\]\w\ \[\033[0m\]\[\033[0;0m\]]# " Thanks to Bash Prompt HOWTO.