Random Code Post

Facebook Puzzle for Korn Shell.

The code follows:

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;

#define isA(x) ( ('a'<= (x) && (x) <= 'z') || \
   ('A' <= (x) && (x) <= 'Z') )
#define isL(x) ( ('a' <= (x) && (x) <= 'z') )
#define toL(x) ( (x) + 'a' - 'A' )

// Is the sum of the bits that are set
//  less than or equal to 26?
int LESS_THANEQ_26(int x) {
 int count = 0;
 for( int i = 0; i < 26; ++i ) 
  if( x & (1<<i) )
   count += (i+1);
 return !!(count <= 26);
}


// Returns how many bits are set in *nearly* constant time.
inline int COUNT(int x) { 
 x = x - ((x>>1)&033333333333) - ((x>>2)&011111111111);
 return (((x+(x>>3)) & 030707070707) % 63);
}

// gcd(a,b,c) = gcd(a,gcd(b,c)) = gcd(gcd(a,b),c))
// lcm(a,b,c) = lcm(a,lcm(b,c)) = lcm(lcm(a,b),c))
// lcm(a,b) = a*b/gcd(a,b)
unsigned long long gcd( unsigned long long a, unsigned long long b ) {
 if( a == 0 ) { 
  return b;
 }
 return gcd( b % a, a );
}
unsigned long long lcm(unsigned long long a, unsigned long long b)
{ 
 return a * b / gcd(a,b);
}
// Main LCM method to call.
// It will actually call lcm().  This method
// chains all the lcm() calls together.
int LCM(int x) {
 // nothing within the set
 if( x == 0 )  {
  return 0;
 }
 
 unsigned long long a = 1;
 
 for( int i = 0; i < 26; ++i ) {
  if( x & (1<<i) ) { 
   a = lcm(a,i+1);
  }
 }
  
 return (int)(a);
}

// Memoiz keeps the max values of rotations.
int memoiz[27];

// Keeps masks of the bits that are set.
// If a bit is set, then that describes how many
// numbers are in that swap cycle.
int poss[500000];

 
int go() {

 int totalPossValidEntries = 0;

 for( int j = 0; j < (1<<26); ++j ) {
  // At most 6 bits can be set.
  int c = COUNT(j);

  if( c > 6) {
   continue;
  }
   
  poss[totalPossValidEntries++] = j;
 }
 
 // Now the total count is doable for calculating
 // the lcm.
 for (int i = 0; i < totalPossValidEntries; ++i )
  if( LESS_THANEQ_26(poss[i]) )
   memoiz[COUNT(poss[i])] >?= LCM(poss[i]);
   
 // now dp the results.
 for( int i = 0; i <= 26; ++i )
  for( int j = 0; j < i; ++j )
   memoiz[i] >?= memoiz[j];
 
 return 0;
}

int main(int argc, char **argv) {
 go();
 unsigned uniqueElem = 0;
 for( int i = 1; i < argc; ++i ) {        
  for( int j = 0; j < strlen(argv[i]); ++j) {
   if(isA(argv[i][j])) {
    if(isL(argv[i][j])) {
     uniqueElem |= 
      1<<(argv[i][j] - 'a');
    } else {     
     uniqueElem |= 
      1<<(toL(argv[i][j]) - 'a');
    }   
   } 
  }
 }
 cout << memoiz[COUNT(uniqueElem)] << endl;

 return 0;
}

Bitwise Ops and Its Applications

Bitwise Operations

Let's go over some basics. The most basic bitwise operations are |, &, ~, ^, and their respective assignment versions: |=, &=, ^=.

| is the OR operation. It will perform the OR of two (2) operands.
& is the AND operation. It will perform the AND of two (2) operands.
^ is the XOR operation. It will perform the XOR of two (2) operands.
~ is the "tilde" operation. It will flip the bits of a given integral type.

(Also, << and >> are left and right shifts)

Therefore, we can use integral types to perform these bitwise operations under.
I will assume everyone knows what the basic bitwise operations actually do.

Therefore, to go over why something like this would be useful. It is handy to keep track of lists without keeping bigger or larger datastructures, especially when the data is small. Meaning, that you just want to keep track of the indexes or numbers that are in or out of the list. With that said, using bitwise on integral types is ideal.

The basic knowledge is to look at the bits as indexes within an array for a given integral type. Then to include number i, you include bit i to the integral type. This is easy. To do that, you just bitwise-OR the integral type with the ith-bit being set. To do so, you would need to use the left shift (<<) operator. This is very useful. To unset or excludle a bit within a set you need a trick to take it from the list. There are many ways to do this; however, many of them need checks in order to not modify the actual integral type if that bit is NOT even in there. Therefore, an easy way to do this is the bitwise-AND the integral type with all bits set to 1 except the ith-bit. After this knowledge, now we know how to implement a bitset or set using an integral type without using a big datastructure. Since it is just overhead if you only are concerned with storing numbers. However, using integral types is limitd because currently the largest integral type is a uint64_t, which holds only 64 bits meaning the number range from 0 - 63. But the implementation follows:

uint64_t bitset = 0; // free all the bits within this integral type

// include the i-th bit
void include(int i)
{
   biset |= (1<<i);
}

// exclue the i-th bit
void exclude(int i)
{
   bitset &= ~(1<<i);
}

Bitwise operations are used heavily within orgranizing massive amounts of data - bitset tree structures. Also, with file systems and organizing data.

Doubly-Linked Lists

Doubly Linked Lists

I was reading this article the other day and thought I should share its contents. It's quite interesting. It has the notion of using one pointer to construct a doubly linked list of nodes. It copies the notion of the XOR-swap described in a previous article.

   x ^= y ^= x ^= y;

However, we don't need to swap, but only hold the XOR value of x and y, namely the value of

   x ^ y

Therefore, we can have one pointer hold the XOR of the prev and next nodes. And to extract the previous, you XOR the combination with the next node, and vice versa to extract the next node. This quite simple, but effecient. Also, when assigning a new value for this one pointer that holds the XOR-combination, you need to remove one of the two and replace it with a new value. The code below follows:

   #ifdef __BIT_32_REGISTER__
      #define XOR(a,b) ( (typeof((a))) ((unsigned)(a) ^ (unsigned)(b)) )
   #else  /*__BIT_64_REGISTER__*/
      #define XOR(a,b) ( (typeof((a))) \
       ((unsigned long long)(a) ^ (unsigned long long)(b)))
   #endif

   initial XOR setup:
   node->onePointer = XOR(prev,next);

   // since we know that onePointer always holds 
   // prev ^ next of the current node, we can just XOR
   // out the prev or next value:
   // 1.) let's replace the previous node with a new prev
   node->onePointer = XOR(node->onePointer,XOR(oldPrev,newPrev));

   // 2.) let's repalce the next node with a new next node
   node->onePointer = XOR(node->onePointer,XOR(oldNext,newNext));

Therefore, now we know what the single pointer should hold. And since it holds the XOR combination, we can XOR it with the prev (that's supposed to have been set with the next to come up with this XOR combination value, meaning onePointer ^ prev will remove prev, and will evaluate the value to just "next" within the XOR combination value) to remove it, and vice versa with the next pointer.

F-Question

Given a range [a,b], find out how many numbers within the range, have a prime number of bits set.
The brute force solution is too slow, especially if [a,b] are 64-bit unsigned integers, which in this case we'll assume.

Therefore, we need a way to count the bits. If perhaps we had a perfect range, meaning it was between 0 and a power of 2, then the number of bits that are prime, are the number of bits choose (prime number <= number of bits to choose from). The reason, being is that if we have n bits to choose from, and we want to pick p bits to be set to 1, then there are C(n,p) ways to choose the numbers., all of which are unique.

0000 - 0111 (where the power of 2 would be 1000 in this case)
So all we have to do is look at the bits that we can choose from, 3.
And we have two different prime number values to be chosen - 2 and 3.

Therefore, C(3,2) + C(3,3) is the total number of ways to do this.
This is the easy case. However, numbers aren't exactly given to us in such a perfect world. Multiple bits could be set for a given number x:
101011101

In this case we split the ranges into powers of 2 decreasing within MSB. Why am I doing this? Because it will be easier to calculate the number of bits within the given range. Because it basically reduces the problem to the initial power-of-2 solution we came up with earlier, except now we have a notion of fixed bits and free bits. The fixed bits have to be counted, however, the free bits have a choice. Therefore, the choose function will have to account that the free bits to choose from + fixed bits = prime number of bits. Therefore, we need to have the choose function to be C(n,k-fixed) such that k is prime, therefore, you are only going to choose k-fixed bits from the remaining n left. (It would be nice if k-fixed was >= 0)

The reason that these range values would be a power-of-2 solution is because the right most end of the range would be a "type" of power-of-2 - 1 value, meaning the difference between start and end is that you only have to look at the right most 1-bits that are set, and keep into consideration the remaining bits to the left that are "fixed" when computing the choose function. So, therein lies one last problem, generating all the powers-of-2 numbers starting from MSB and appending the new power-of-2 number. Also, there should be a function to count the number of bits that are set.

The following code shows the entire procedure: (C++)

#include <string>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

typedef unsigned long long uint64_t;

#define MAX_BITS 64

// decently quick way to count how many bits are set:
uint64_t MIT( uint64_t x ) {
    x = x - ((x>>1ULL)&0x7777777777777777ull)
          - ((x>>2ULL)&0x3333333333333333ull)
          - ((x>>3ULL)&0x1111111111111111ull);
    x = ((x+(x>>4ULL))&0x0f0f0f0f0f0f0f0full) % 255;
}

// memoiz the choose function
map<pair <uint64_t,uint64_t>, uint64_t> nck;

// keeps the list of ranges: 
vector<uint64_t> start, end;

uint64_t next( uint64_t z, uint64_t x, int &y) {
    if (y == -1) return 0;

    for (int i = y; i >= 0; --i) {
        if (x & (1ULL<<i)) {
            // next time y will start
            //  at next (lower) index
            y = i-1;
            return z | (1ULL<<i);
        }
    }
    y = -1;
    return 0;
}
void init(uint64_t x) {
    // always append zero (0) first
    start.push_back(0);

    uint64_t z = 0;

    // which bit do we set? 
    int y = MAX_BITS-1;
    while ((z=next(z,x,y)) != 0) {
        start.push_back(z);
    }
}
uint64_t nchoosek( uint64_t n, uint64_t k)
{
    if (k > n) return 0;
    if (n == k) return 1;
    if (n == 0) return 0;
    if (k == 0) return 1;

    // memoized solution? 
    if (nck.count(make_pair(n,k))) {
        return nck[make_pair(n,k)];
    }
    // memoiz the solution here:
    return nck[make_pair(n,k)] = 
            nchoosek(n-1,k-1) + nchoosek(n-1,k);
}

int isPrime( int x ){
    if (x < 2) {
        return 0;
    }

    // could optimize it for just odd's and 2
    for (int i = 2; i*i <= x; ++i) {
        if ((x % i) == 0) {
            return 0;
        }
    }
    return 1;
}

uint64_t R( uint64_t x1, uint64_t x2) {
    // get the digits that are free
    uint64_t n = MIT(x2 - x1); 

    // find the number of fixed digits
    int fixed = MIT(x2 - (x2-x1)); //MIT(x1 & ~(x2-x1));

    uint64_t sum = 0;    // sum up the diff prime(s)

    // go through all primes, starting with fixed+const
    for (int x = fixed + n; x - fixed >= 0; --x) {
        if (isPrime(x)) {
            sum += nchoosek(n,x-fixed);
        }
    }
    return sum;
}
uint64_t f( uint64_t x ) {
    // find all the ranges
    init(x);

    for (int i = 1; i < start.size(); ++i) {
        end.push_back(start[i]-1);
    }
    end.push_back(start[end.size()]);

    // go through each range, and calculate the sums
    uint64_t sum = 0;

    for (int i = 0; i < start.size(); ++i) {
        sum += R(start[i],end[i]);
    }

    return sum;
}

uint64_t bits_prime( uint64_t a, uint64_t b )
{
        uint64_t fb = f(b);

        // clear the range lists:
        start.clear(); end.clear();

        uint64_t fa = f(a);

        // inclusion exclusion rule:                                                                                                                                                                                                
        return (fb - fa + isPrime(MIT(a)));
}                                                                                                                                                            

Pointer Fun

Pointers

The term pointer is basically just another word for number. The only difference is that there is something unique about the pointer type. You are allowed to dereference it, meaning you are allowed to go to the actual (virtual) memory address and get its value located at that memory address.

Other than that, it can be addressed using an unsigned integer (if it's 32-bits) or an unsigned long long (if it's 64-bits).

Therefore, in C++, you can do something like the following.
char *c = (char *)malloc(32);

The same thing can be addressed using an unsigned int.
unsigned int i = (unsigned int)malloc(32);

The values of c and i are identical and equivalent. However, you cannot go to the memory address of c and dereference (without casts) using the variable i, type being unsigned int. However, with casts you can:

*((char *)i) = 'a';
*c = 'a'

The two expressions above yield the same exact semantics. The syntax is a bit different, but they *mean* the same thing. This is probably the hardest concept for beginner programmers of the C/C++ language to understand and fully grasp. If you understand this, then malloc() and free()ing are completely understandable. They are after all using number values, and an unsigned int is a 32-bit number value, which is the same type for a pointer on a 32-bit machine.

Casting between ints and pointers is done a lot, especially within OS/network specific applications. Manipulating pointers is essential to get into deep OS-specific applications, and therefore, this is a good way to start that type of learning. Also, anytime you get confused, just think of a pointer as an integer. Anywhere you can modify an integer with it being legal, the same holds true of a pointer type. After all, they are the same thing.

The most humorous example is when you pass a struct in by pointer, and you change an attribute of that struct. In general terms, anything you change within the function becomes changed., even if it's a pointer attribute. Some get really confused about this because when you pass something by pointer and you try to assign it a different value, the value after function calls remains unchanged. However, this is a different example, because the attributes of the struct being passed in by pointer is the actual address of the attributes. So you are actually going to its (virtual) memory address and changing it literally.

Manipulating memory is very intoxicating and fun as well.
Let's say you have this:

   typedef struct A {
        int a;
        char b;
   } A_t;
   typedef struct B {
        int c;
        A_t *a;
        short d;
   } B_t;

And you want to allocate space for the entire struct of B as well as the pointer to type A_t. But you can only use one malloc() call. How would you do this? Well the answer is to allocate space for both of them; however, you are going to have to have both structures side by side in (virtual) memory. This is quite simple.

   char *c = (char *)malloc(sizeof B_t + sizeof A_t);
   B_t *b = (B_t *)c; // first part is B_t
   b->a = (A_t *)(c + sizeof B_t); // second part is A_t

Therefore, you allocated space for both pointers, initializing the entire struct B_t.

A-Question

Suppose you are trying to print out the mirror image of a tree, a binary tree to boot.
How would you go about doing this? Well, if you know anything about tree structures, you know they are heavily recursive. There are two ways to do this, either modify the tree to be its mirror image, or come up with a way to traverse it mirror-imagedly. The funny thing is, it's virtually the same concept. However, I'm going to show you the former way. (I'll leave it as an exercise to the do latter algorithm)

This is going to be very short and sweet. The only thing you have to do is, change the pointers from right to left, and left to right, assuming you are granted the root node of the tree. Just do it recursively, like so:

   void mirrorImage( Node *root )
   {
      Node *left = root->left;
      Node *right = root->right;
      root->right = left;
      root->left = right;

      // now recurse like a heathen
      if (left) {
         mirrorImage(left);
      }
      if (right) {
         mirrorImage(right);
      }
   }

So basically you update the pointers, and then do it recursively. After all of this is finished, the result will be the mirror image of the tree.

C++ Tricks: Part II

Another set of tricks.

I am going to outline a couple of more tricks that are used for interviews and overall cool things to know:

How to identify the endianness of a machine:
The easiest way to do this is using a pointer to a short, and figuring out if the low order is a certain value that you expect from a big endian or little endian byte order.

bool isBigEndian()
{
     short s = 1;

     // big Endian if MSB == 0
     return (*((char*)&s) == 0);
}

Another trick is to use an unsigned integer as a set data structure. However, it's limited to holding only 32 values. Usually this is enough, but sometimes it's not. In any event, here's the process that goes into it.

You can look at an unsigned integer as a 32-bit integer, where the ith bit (0-indexed) is set to one (1) if and only if it is within the set, and zero (0) otherwise. Therefore, to add something to a set, there is a trick to use:

          x |= (1<<(i));

This will get the ith bit for you and bitwise-OR it and store it in the variable x. Usually it can be used like this for computing set-type problems, like the TSP-related problems, permutation, backtracking problems, and the like. Of course, to remove the set, there is a similar trick:

         x &= ~(1<<(i));

This will flip all the bits to a one (1) except for the i-th bit and bitwise-AND it with x. Therefore, the only bits that are changed within x was the i-th bit, everything else stays the same. This technique is quite useful.

Tricky way to check if a string is a palindrome. It takes n/2 checks such that n is the length of the string in consideration. The algorithm to do so is to check the mirror image of the indices since they should be identical in a palindrome. (Front<->End) The code follows:

     int len = str.size();
     for (int i = 0; i < len/2; ++i) {
          if (str[i] != str[len-1-i]) {
               return false;
          }
     }
     return true;

Obtaining the offset of a data member from a structure. This is quite useful. The key to this idea is that it is based on the rule that if you ever take the address-of (&) operator on an element that is dereferenced, it does not evaluate what's being dereferenced. The code follows:

      typedef struct B {
           int x;
           char y;
      } B_t;
      typedef struct A {
           char a;
           int b;
           short c;
           B_t d;
           long long e;
      } A_t;
      To find the offset of member 'e' within
      type A_t, you need to know the padding infrastructure.
      This could get complicated, so this is a better way:

      unsigned int offset = (unsigned int)(&((A_t*)NULL)->e);

Because it does not evaluate the NULL dereferencing e, this just calculates where the variable e is within the A_t structure. This is quite useful in things such as the list-head problem, which will be shown in an upcoming article. And since NULL is actually ((void*)0), the starting address of the structure in this case would be zero (0), which is the reason why it would give us the actual offset of where 'e' is stored at.

GCC Operators (C++)

Min/Max gcc operators:

Note: "< ?", "> ?", "< ?=", and "> ?=" should have not any spaces.


"< ? and > ? and the min and max operators"

The concept with the min and max operators is that they return an expression that is the minimum or the maximum value of two operands. Therefore, instead of doing something like:

   x > y ? y : x; OR x > y ? x : y;

You can now do:

   "x < ? y; OR x > ? y;"

Also, you can chain these operands out:

   "x < ? y < ? z < ? a < ? b < ? c;"

This is helpful when you need to find the minimum value of multiple values.

Also, there is something called min-assingment and max-assignment gcc operators.
Something in code that corresponds to:
"Set x to the minimum of y and z" OR "Set x to the minimum of x and y"

   x = ( z < y ? z : y );
   x = ( x < y ? x : y );
Alternatively:
   "x = z < ? y;"
   "x = x < ? y;"

Now, something of the form ?= is valid. Therefore, the above would look like:

   "x < ?= y; // for x = x < ? y;"
   "x = (z < ? y);"

Note, you can mix everything together. The reason that this is important is because that it doesn't compute anything more than once.

Nvidia Interview Question

"Popcount"

This is a popoular question, and hopefully you know that the MIT HAKMEM is a solution to this. But assuming you don't really know how to think on your own, the solution posed here is good enough for you to grasp.

The "POPCOUNT" question is to count how many bits are set in an unsigned 32-bit number. So basically, the brute force solution is this:

     for (int i = 0; i < 32; ++i)
         if (bits & (1<< i))
             ++count;
// count now holds how many bits are set

This is actually not so bad, right? Well, if you are actually trying to figure out how many bits are set, you need a solution that is near constant time. Because you are dealing with OS-specific code now. So it better be faster than just looping through the number of bits and counting them. (Especially, if written in a high level language)

Therefore, they'll give you a hint (assuming you can understand the interviewer). They will propose, say you can use anything, how would you make this run faster? The hint is so vague and if you haven't dealt much with this type of stuff, you are virtually screwed :)

But here's something they should tell you, assuming you have a look-up table to count up how many bits are in a byte, how would you calculate how many bits are set within a 32-bit unsigned integer? Well, that makes it so much easier to answer :) All that's needed is to manipulate the bytes when passing into the lookup table.

Therefore, say you are looking at a lookup table with 256 entries, indexed by 0 - 255. The index is the actualy byte that you are trying to calculate. The result gives you the actual count.

For example,

      bitCount[x] gives you the number of bits that are set within this 8-bit byte, namely x.

Therefore, you have to split the 32-bit unsigned integer into 8-bit bytes when passing them into this lookup table, and you just sum up the result. Easy right? Indeed.
Here's the code:

// assume y holds the 32-bit unsigned integer value
for (int i = 0; i < 4; ++i)
     sum += bitCount[ (y>>(8*i)) & 0xff ];
The "& 0xff" part tells the compiler to just get the low-end order 8-bit byte.

This was straight forward after figuring out that you could have a lookup table that yields all the results.

C++ Tricks: Part I

Impress your interviewer

"Comma Expressions Hack"
Clearly, anyone who has done C++ knows the trick where you can initialize multiple variables of the same type at one time.

For example,
int a = 0, b= 1, c = 2;

This declares three variables with the same type, namely int. However, the comma is strictly an expression separator. This is quite useful when you hate the whole ordeal of using braces ("{}") for if-statements, loop type structures, and the like. You can use comma-separated expressions for "regular" statements. What do I mean by regular? Regular, in this context, means that an expression is not a "break" or a "return". These two (2) special statements are not "regular" expressions, not to be confused with a regular expression studied in theoretical computer science.

Therefore, you can do things like this:

if( a == 0 )
     b = 3, s = "hello", d = 4;

Multiple statements within an if-statement that doesn't exercise the utilization of braces. In any event, things like this should be properly avoided if adhering to coding standards within your academic or professional setting. But it's rather useful to know.

The "swap" without an extra variable.
Swapping two variables usually requires the use of another variable.

For example,

     int a = 3, b = 4;
     int tmp = a;
     // comma trick:
     a = b, b = tmp;

Therefore, we can do this without an extra variable, namely tmp.
It uses the XOR property of variables in C++.
A little clarification might help in this situation.
Say we have a and b as ints. Let's store the XOR of a and b into a variable named c:

         c = a ^ b;

Therefore, we know that:

        c ^ a == b
        c ^ b == a

We can use this feature, without having another variable, c.
If we do it correctly, and chain the XOR operation, there's no need for the extra variable.

       a ^= b;    // think of a holding the value that c would hold
       b ^= a;   // if a holds the value of c, then c ^b == a, so now b holds the value of a.
       a ^= b;  // if a held the value that c holds, then a ^ b, is actually (c ^ a) since b holds "a"
More compactly, you can do it as such:
      a ^= b ^= a ^= b;

Therefore, without using another variable, we have just swapped two integral types.

Note: These examples are for use with the C++ programming language. Though some of the tricks might work in the language, it is not wise to assume they all do.

Jobs and Interviews

Computer Science Graduates: Do you actually want to code?

All the cool jobs are geared towards hard interviews. This is a waste of time. You might as well just get a web development jobs since they pay more anyways. I mean the reason for going to school is to get a job right? Then, do college graduates actually want to work hard? I mean they worked while in school, eh? I guess that's why Stanford CS graduates go into financing and economics. That's where the money is. They spend a lot of money studying computer science and minoring in economics and they go into the financial market, not wanting to code, but critical thinkers and financial honsho's to make money. But enough of the spiel on CS graduates going after other careers, we'll talk more on the actual interviews and jobs that CS graduates that want to code are in the market for.

There are two types of coding categories that are in the market now. First there's web development and then there's systems programming. Web development stems vast areas and technologies, whereas systems programming is central to OS, Networks, C/ASM programming. Web development is easier, as well as more cost-productive. They are able to pay you more than a systems programmer. Possibly even double the salary. But then you have a hybrid among the two. Back-end C/C++/Java/C# programmers that work for financial companies. Now what can I say about these types of jobs. It basically takes the advantages of both areas, and intermingles different areas that suck -- well, besides the money part :)

Lab49 is a company that takes a lot of the brunt of the work there. As well as financial companies like banks and financial lenders ... think JP Morgan Chase, Lehman Brothers, Visa, Amex, Mastercard, and others. They have the ability to pay their coders a hefty amount, and the work isn't too shitty. It has the need for multi-threaded applications with an actual programming language, not just scripting languages. Not that scripting languages are bad, in any sense. So back-end programmers have the core ability to create infrasturctures, as well as some web development intermingled.

Therefore, if you want to work on systems-programming type jobs but want the full potential pay as web developement can offer, then the financial industry is your target. If you don't want to have too much problematic programming or even want to think *too* much, then go for web development. I mean seriously, CS graduates don't want to think past a certain amount -- we are lazy, prideful, and want to just chill. With that in mind, go find a shitty job for your shitty degree, that requires the least amout of work to actually do with a shitty boss.


Note: Some web developement companies are really well-developed, so they try to bring the back-end style into their mix, which is good. Especially when they have enough funds to do their own research. Keep that in mind. (Google, Amazon, Ebay, ibid. et. al.)

Coding 101: Intro to Programming

Basics to Coding.

First, I will describe everything in terms of mathematics and proceed into coding.
Some things, you should know are the basic function definitions in mathematics.

This is called a function definition.
f(x,y) : { x + 2 * y }

This itself doesn't do anything, but if you "plug" in values to f(x,y) : { x + 2 * y }, you can think of it as just replacing and substitution.
For example.,

f(1,2) using f(x,y) : { x + 2 * y } -> { 1 + 2 * 2 } = 5

This is quite simple, x is the first parameter and y is the second parameter.
So everywhere you see an x you replace with the first value (in this case it's a 1), and everywhere you see a y you replace with the second value (in this case it's a 2).

Then you just output the value 5.
Therefore, f(1,2) = 5

This is in terms of mathematics. Computer Science handles this a little bit differently, but the main concepts are the exact same.
In coding, you have types for everything. So in the above example, you need types for x, y, and the return of the function. In that case f(1,2) = 5,
5 is the return type.

Mathematics makes this one-dimensional, whereas Computer Science tends to make it more generic. They have types for everything as well. For example, f(1.02,2.03) is valid input in terms of mathematics because there is no strict "type" that is enforced. However, in Computer Science there are "types" and so if x and y were of type int., this would not necessarily be a valid use of the function f.

Therefore, let's look at the description of a function.

RETURN_TYPE FUNCTION_NAME( TYPE x, TYPE y )
{
       return x + 2 * y;
}

The RETURN_TYPE is the type that is evaluated by the keyword "return" in the code above.
Let's assume we only know the primitive types:
char
int
double

Therefore, RETURN_TYPE and TYPE have to be either one of the primitive types. By the way, primitive type just means basic types.

Therefore, the function could look something like this:

int f(int x, int y)
{
      return x + 2 * y;
}

Here, f is the function name. The function name could be anything it wanted to be.
Also functions can return no type., meaning the function does not want to return anything, and it cannot return anything. So if the function has no return type, the keyword is actually "void"
void f(int x, int y) { x + 2 * y; return ; }

If you notice clearly, the expression after the keyword "return" is just a semicolon ";" meaning just leave the function.

Any variable that is used within a program needs to have a type.
This means you cannot just have something like this:

x = 5;

if x is not defined somewhere like:
int x; // declaration
OR
int x = 5; // declaration and assignment = initializtion

Also, let me point out there is something called a function definition and a function call.
A function definition is telling you what the function actually does. A function call is when you call a function. That's easy right?

Before you call a function, it has to be defined somewhere. This makes sense to. You can think of it as a car analogy. To start your car, it first has to have an engine. If you try starting your car, and you have no engine, it won't work. So first get your engine setup properly, and then you can start using it.

// FUNCTION DEFINITION
int functionName( int x, int y )
{
return x + 2 * y;
}

// FUNCTION CALL
functionName(1,2);

There are some differences here. The main difference is that you don't specify the types in the function call. But in the function definition you have to specify *everything* so that's how it makes it clearer. Also, you can think of it as assignments going on.

So a function call works like this:
functionName(1,2); --> go look up the functionName with parameters having values 1 and 2.
So then it finds a match above:
int functionName( int x, int y ) { return x + 2 * y; }

Then it looks and matches the types for the parameters, so it does something like this:
int functionName( int x = 1, int y = 2 ) { return x + 2 * y; }

Meaning, now x has the value 1 and y has the value 2, and so it just goes and does the computation there. So (x=1) + 2 * (y=2) -> 1 + 2 * 2 = 1 + 4 = 5, and then returns the result 5.

so functionName(1,2) holds the value 5.

Here's the tricky part. The entity value of "functionName(1,2)" can be replaced with the value 5, because functionName has the return type of int, so "functionName(1,2)" or the called function of functionName(1,2) has an int type.

What does this mean? It means you can use it anywhere you can use an int.
Let's say we do this.

int z = 3; // we declare z to be an int and assign in the value of 3.
This can happen since z's type is an "int" and the type of 3 is an "int" also.
(3 is an int literal, meaning it's like a constant int. It's universally known.)

Therefore, we know that funcionName(1,2) has return type int.
Therefore, "functionName(1,2)" can be used anywhere an "int" type can.

So, we know that
int z = 3; // z is an int type

z = 4; // we can do this because 4 is an int type as well.

Can we do this?
z = functionName(1,2)

Indeed, because z and functionName(1,2) both have the same type we can assign functionName(1,2) to z.

since functionName(1,2) = 5, it's almost like a replace and subsitutition that takes place.
z = functionName(1,2) is the same as z = 5 (since functionName(1,2) equals 5)

This is just a short example of how functions work. A lot of the material was tedious to get the point across. Also, functions can have no return type, or one return type. But you can have any number of parameters. (no parameters, or many parameters) In our function we only had two (2) parameters - x and y. But you can have as many as you want.


*This is dedicated to a friend -- Q*

Meebo Interview

Meebo Me!

So there's all this talk about some student at University of West Florida got an interview ticket with Meebo. Meebo is the wannabe Trillian but online website that allows you to connect to multiple IM clients at once. The idea isn't astounding, its just an implmentation done over the web. Interestingly, a computer science student at UWF actually implmented a C program that connected and login'ed a Yahoo user. So in that end, it's not unique nor difficult. It's just a matter of following the protocol that the other IMs use and implement it.

So in any event, let's go on to the interview dilemma with Meebo. Firstly, they tell you to answer their puzzles on their site and then to submit them with your resume in an email. If successful with the puzzles, a technical recruiter will grill you with questions you should already know if you were able to answer the puzzles on your own. In fact, Meebo gets many applications from students from Stanford and Pacific University, and so someone from UWF needs to stand out and show some passion, enthusiasm, as well as past projects and goals. There is a higher expectation because UWF is a smaller school, and the applicant needs to show he's got what it takes in the interview process with Meebo. THe technical recruiter, as far as I know, is very judgmental and bases his judgment on mere appearances without due regard to the facts of answering the questions. More on past projects and goals (3-5 yr range) than actually answering the questions. This is true because Meebo is trying to expand; however, the technical recruiter's knowledge is minimal and so it's easy to come up with things that are false but believable.

The only thing I have found that is against Meebo is their democracy in regards to students from schools that aren't as prestigious as Stanford University. There is almost a willingness to not even look at those students that are applying. This is truly unfair. Not all students coming out of Stanford University have passion, though they do have project they are working on. Projects don't make passion, though from a simplistic, dummed-down, amateruish point of view, it would imply that they do have passion because they are actually working on something. However, these are mere appearances, and you'd at least expect someone whose job is to inspect and detect what things motivate, inspirate, and creates passion in college graduates would be something more than "Are you working on current projects?" It's solely based on what is happenin now. Students are busy especially in their last semester, and what type of question is that anyways? There is no assessment in the past or even a consideration in their academic studies. Possibly, the technical recruiter really doesn't care that he finds someone suitable. And the fact that Meebo is trying to "double" their engineers in the year 2007, it doesn't seem that they'll be doing that with these types of bogus technical recruiters :)

The expectations from someone representing Meebo were weak and therefore, the Meebo experience wasn't worth as much a the UWF student thought it would be., despite the fact that the technical recruiter wasn't keen on how to judge applicants fairly.