Programmers humor

Throughout of my surfing in the web,  I often encounter funny jokes about programmers and source code comments,  In this post I want to present the top of them, which I liked most.

Here They are,  relax and enjoy :)

 //   
 // Dear maintainer:  
 //   
 // Once you are done trying to 'optimize' this routine,  
 // and have realized what a terrible mistake that was,  
 // please increment the following counter as a warning  
 // to the next guy:  
 //   
 // total_hours_wasted_here = 16  
 //  

 // sometimes I believe compiler ignores all my comments  

 // I dedicate all this code, all my work, to my wife, Darlene, who will   
 // have to support me and our three children and the dog once it gets   
 // released into the public.  

 //When I wrote this, only God and I understood what I was doing  
 //Now, God only knows  

 Exception up = new Exception("Something is really wrong.");  
 throw up; //ha ha  

 return 1; // returns 1  

 // I don't know why I need this, but it stops the people being upside-down  
 x = -x;  

 #define TRUE FALSE  
 //Happy debugging suckers  

 //Dear future me. Please forgive me.   
 //I can't even begin to express how sorry I am.  

 //Don't touch it or ninja will punish you  

 Q: how many programmers does it take to change a light bulb?  
 A: none, that's a hardware problem  

 Saying that Java is nice because it works on every OS is like saying that anal sex is nice because it works on every gender.  

 This is classic one :)  
 Q. Why do programmers always get Christmas and Halloween mixed up?  
 A. Because DEC 25 = OCT 31  

 Q. Why all Pascal programmers ask to live in Atlantis?  
 A. Because it is below C level.  

 Wife: I want a baby  
 Husband: Ok, I'll install it tonight  

Hope you enjoyed it,  feel free  to leave your jokes in comments

Moving elements from one stack to another

Suppose we have stack and want to move elements to another stack preserving element order, If we don't have any restrictions than it's very simple task, using temporary space we can achieve it with no extra effort.
Now let's solve this problem with restrictions, we are allowed to use only additional O(1) memory.  When I first stated this problem I thought that it was not solvable, but after few minutes of thinking I figured out simple algorithm.

Imagine that we already moved N-1 elements to new stack, they are ordered correctly and now we are going to move Nth element. We can do it in this way:

1. Pop Nth element from initial stack and save it in temporary variable
2. Move N-1 elements from destination stack to initial stack one by one.
3. Push the element saved in 1st step in destination stack.
4. Move N-1 elements from initial stack to destination stack -  those are elements which were moved in 2nd step.

And we got it, we have moved N elements in destination stack. Now we can use this approach to move all the elements and we'll be happy.

Here is the implementation of this algorithm:

    static public void main(String[] args) {
        Stack stack = new Stack();
        for (int i = 0; i < 31; i++) {
            stack.add(i);
        }
        Stack stack2 = new Stack();

        while (!stack.isEmpty()) {
            int temp = stack.pop();
            int counter = 0;
            while (!stack2.isEmpty()) {
                stack.push(stack2.pop());
                counter++;
            }
            stack2.push(temp);

            while (counter < 0) {
                stack2.push(stack.pop());
                counter--;
            }
        }


        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }


    }

The algorithm which I proposed is useful only in situations when there is strict memory restrictions,  because time complexity has grown and it is O(N^2).

Soft, Weak and Phantom references in Java

All object instances in Java are allocated on the heap and can only be accessed through object references. When we are creating object we are storing references for accessing objects in future

Object o = new Object();

Here “o” is strong reference,   beside this type of reference Java also has other types of references which  are implemented in java.lang.ref package, from Java 1.2   In this package we have three reference-object classes: Weak Reference, Phantom Reference and  Soft Reference.

Weak References:

Weak reference is a reference which doesn't have enough force to prevent Garbage Collector(GC) deleting object.  This type of references are useful when we are implementing caching functionality. Suppose we have cache of images and different threads of system are using it, when system no more needs some images, GC will not be able to delete object because cache has strong reference to it and object will stay in memory forever.  To  prevent such situations we can refer objects in cache with weak references  and  GC will delete it as soon as it detects its weakly reachability.

You can create weak reference like this:

WeakReference weakImage = new WeakReference(image);

And for accessing Image object you can use  weakImage.get()  which returns actual object, But It also can return null which means that there are no strong references to this object.

Another Way for creating WeakReference is:

ReferenceQueue q = new ReferenceQueue();

WeakReference weakImage = new WeakReference(image, q);

ReferenceQueue class gives us flexibility for tracking references,  When WeakReference starts returning null it means that object is garbage and reference will be added to the queue, which you can use for further cleanup.

Soft Reference:

Soft Reference behaves like weak references, except  when GC determines object is softly reachable, then it may clear this object or not. But we can be guaranteed that this object will be cleared before virtual machine throws OutOfMemoryError .  This mean that softly reachable objects will stay in memory until memory occupied be them is not critical and we have enough memory for creating other objects.

Phantom Reference:

Phantom references are different from soft and weak references,  it's get() method always returns null. The only use of this reference is to track when object is enqueued. But why we need it if we already have other references?

Let's introduce such class:

 public class SoftRef {  
   static SoftRef ref = null;  
   String t;  
   public SoftRef(String t) {  
     this.t = t;  
   }  
   static public void main(String[] args) {  
     SoftRef obj = new SoftRef("test Obj");  
     obj = null;  
     System.gc();  
   }  
   @Override  
   protected void finalize() throws Throwable {  
     super.finalize();  
     ref = this;  
     System.out.println("deleted");  
   }  
 }  

This class has weird finalize method, it is resurrecting itself – creating strong reference to itself therefore GC will not delete it.   Java Language Specification clams that finalize() method will be invoked maximum once, so it guarantee that object can't resurrect always.

In this case WeakReferences will be enqueued before object is really deleted and reference will become dead beside object stay alive.   Here  PhantomReferences can help,  Phantom references are enqueued when objects are deleted from memory and get() method always returns null to prevent resurrecting object.  So  phantom references are good for determining exactly when object is deleted from memory.

Double Brace Initialization in Java

Sometimes Double Brace Initialization is treated as a hidden feature of Java, But let's look closer to the syntax. In a normal way when we are declaring and initializing Collection we would use following code snippet:

 List normal = new ArrayList();
normal.add("string_1");
normal.add("string_2");
normal.add("string_3");

Now we can use double brace initialization and rewrite code:

 List list = new ArrayList() {{
      add("string_1");
      add("string_2");
      add("string_3");
   }};

What we got is not a new feature, we are just declaring anonymous class and second braces creates an initializer block, which will be invoked when class is created.

As we can see this approach is nice for initializations and we can use it in following case:

     method(new ArrayList() {{
       add("string_1");
       add("string_2");
       add("string_3");
     }});

But it is slightly inefficient, instead of creating new instance of class we are creating new class and if we have 100 such initializations we will receive 100 new classes. I don't suggest to use it under high performance requirements.

Linked List shuffling

Every programmer should know what a linked list is, here is brief a description from wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

In this post I want write how to shuffle linked list.

In a very simple way when you are shuffling array you can make it in two steps:

1. for every index you can generate some random index - time complexity is O(N)
2. swap corresponding elements. - time complexity is O(1)

This algorithm works in O(N) time, where N is size of array.

Let's try to implement this approach for our linked list. first step is the same, but second one isn't as easy as it seems. In linked list you can't access elements by index, therefore you must iterate whole list and examine all elements. This takes N operation and you would get O(N*N) complexity.

My aim is to show you another algorithm, which will work in O(N LogN) time.

In my algorithm I'm using Divide and Conquer approach.

1. divide list into halves
2. reshuffle both lists
3. merge reshuffled list.

This algorithm works in O(N*LogN), because list will be divided LogN times and complexity of merging is O(N). Here is my implementation of this algorithm:

 #include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
//list item
struct Item{
Item* next; // pointer to the next element in list
int value; // value of element
Item(){
  next = NULL;
}
};
int Min(int a, int b){
return a<b?a:b;
}
//construction list
Item* constructList(int N){
Item* root = new Item();
Item* t = root;
t->value = 0;
for(int i = 1; i < N; i++) {
  t->next = new Item();
  t = t->next;
  t->value = i;
  }
return root;
}
//root = first element of list
//len = length of list
void shuffle(Item* root, int len){
if(len==1) return; //if len==1 than there is nothing to shuffle
Item* r2 = root;
//splitting list,  get first element of second list r2
int i = 0;
while(i < len/2) r2 = r2->next,i++;
//shuffle first list
shuffle(root, len/2);
//shuffle second list
shuffle(r2, len-len/2);
//merging lists
for(int i = 0; i < Min(len/2, len - len/2); i++){
  if(rand()%2) {
        //swap values of two element
        int value = root->value;
        root->value = r2->value;
        r2->value = value;
  }
  //goto next element
  root = root->next;
  r2 = r2->next;
}
}
int main(int argc, char *argv[])
{
srand(time(NULL));
Item* root = constructList(20);
Item* iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
printf("\n");
shuffle(root, 20);
iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
system("PAUSE");
return EXIT_SUCCESS;
}