Just another Programmer

0.999..... equals 1

2011-04-25T01:49:00.000-07:00

see - http://en.wikipedia.org/wiki/0.999...

Visual Studio shortcuts

2010-09-14T10:45:00.000-07:00

Some of the shortcuts which are extremely necessary !

Ctrl + ] - for matching brackets
Shift + alt + enter for maximizing the code window to fullscreen.
Ctrl + tab to shift across code files
Ctrl+f3 - go to definition ( class or method)
Also Ctrl-K + Ctrl-C or Ctrl-K + Ctrl-U to comment and uncomment code is a great one.
Ctrl k + ctrl F for auto indenting code

Download the poster available in this msdn link which has a poster containing all essential shortcuts. This will be handy for any visual studio developer.
download link

cheers!

When things go completely right - there is something wrong somewhere

2010-08-28T15:07:00.000-07:00

Things never go the way you want. This hypothesis is nearly always true. But to me - "when things go more than what you want there is some problem somewhere".

I have changed my job and joined THE big software firm. As always , the problem with the big firm is 'process'. Everything has its own process and so every thing , be it an request or suggestion, the turn around time is usually large. Adding to this, the release cycle is in its near end , and I am left with no work. Idle for more than a month , I decided to go ahead with implementing some challenging stuff.

As my interest in machine learning and information retrieval is growing like an exponential upward curve , I decided to do "text classification". The algorithm classifies the given text into some category. Given a web page / document it classifies them automatically into some topics , say news , sports , religion or celebrities or anything.

Its basically a machine learning algorithm. It creates or generates a learning function from the training data. Using this learning function , we classify the test data into one of the categories. I went ahead implementing the naïve bayes classification algorithm as prescribed in Information Retrieval text book. My aim is to build the prototype first and then do extensive tuning and find some important information which improved the classifier accuracy. When am building the prototype , I started reading papers online to see how we can tune this algorithm. My major interest is in finding some better tuning algorithm. But what happened is a miracle. ..

As always , I don’t normally make programming errors and the code is running the first time. Guess what , I felt the fundamental model very simple ,and have implemented the tuning stuff also. After the program ran ,results were weird . The accuracy rate is below 40%. I couldn’t spot the error. After struggling considerable amount of time , I decided , ok this is not going to work and just for the sake of it I removed the extra tuning algorithm and ran the simple one. And there it is 100% accurate classification. I wasn’t happy. I didn’t jump in the air because its 100%. I am quite sure , classification algorithms cant predict them accurately that too 100%. This is one of the moments where scoring an 100 is not good. If you score an hundred ,it could be almost sure that this is due to some programming bug. Adding to my woes, I have removed my so called tuning algorithm. It has defeated my very purpose of doing this project which is to find some heuristics on top of the existing one. disappointed. I realized - " not always scoring an 100 is good" . All the effort , its gives 100% accuracy after having implemented the simple model. Now how do I get the enthusiasm to work and learn complex algorithms. Simple one did everything it has to do. Dejected. Felt something wrong , something fundamentally wrong.

Then started thinking why its 100%. How come it could predict so accurately. The problem is , I have to test with large number of test cases. All my carefully selected test-cases did the trick somehow. Finally I tested the whole program with more number of test cases, and I got the accuracy down to 92%. Happy ! Delighted. Because I believe this is the right number and also because it makes me work on advanced heuristics algorithm to increase the classifier accuracy.

One moment where it exceeded my expectations , still I wasn’t happy with what I got ! Expectations - achieve more or less - there is some problem somewhere ! Now that its 92% , it gives me the greatest opportunity to explore advanced methods and heuristics to go towards 100% ! I never want to reach the ultimate 100 , as it will cease my opportunities to learn more. There should always be another mile stone !

note:

information retrieval book is avaialble here link
this is actually done , by taking details from the assignment given at stanford for IR course - link

Interests: You got to find what you really want to do!

2010-08-20T05:47:00.000-07:00

I have spent number of days deciding what I truly want to do. I have decided my domain of work will be search , search advertising which involves information retrieval , machine learning and statistical models. so here it is...


Information retrieval

 Index construction and compression
 Boolean and probabilistic retrieval models - BPT
 Vector space model - Linear algebra
 Scoring and ranking in search system
 Evaluation and feedback systems
 Text classification and categorization
 Web search additional challenges

Machine learning (Tom Mitchell)

 Decision Tree Learning 
 Artificial Neural Networks 
 Bayesian Learning 
 Instance-Based Learning 
 Genetic Algorithms 
 Learning Sets of Rules 
 Analytical Learning 
 Reinforcement Learning 

Graph theory

 Enumeration
 Path problems 
 Coloring , covering and partitioning
 Network flow
 Properties and different graphs 

Game theory
Optimization
Natural language processing
Data mining

Mathematics

 Probability and statistics
 Discrete mathematics
 Linear algebra
 calculus

Algorithms and Data structures

I feel lucky to have identified my areas of interest. Currently I am reading IR and going to follow up with machine learning and statistics.

Have some good knowledege in algorithms and graph theory.
These are more related to web , search and information retrieval and audience intelligence algorithms.

I wish I keep getting opportunities to work on these areas all through my career and I want to touch every topic in this in the near future! Right now , am doing Vector space models and text classification algorithms in IR

distance formula : a picture is worth thousand words.

2010-08-19T13:47:00.000-07:00

There are no dumb questions

Primer : Probability

2010-07-22T02:31:00.000-07:00

This blog is very basic and Yes everybody in the world know this.

P(A) = n(A)/n(S)
P(A u B) = P(A)+P(B)-P(A n B)

Probability - how likely the event will occur. If we toss a coin , it is likely that the head will occur once in two tosses. But this may not be true. Two consecutive tosses may yield both tails. So how 1/2. If this experiment is repeated a huge number of times , it is observed that the odds with which the head will fall is 1/2. obvious the coin is unbiased.

Two events , are said to be independent if the outcome of one event doesn’t impact the outcome of the other. Those events are called as independent events. Lets say there are two coins and I toss them simultaneously , the outcome of one coin has no effect on the other coin and hence they are independent.

Now whats the probability of getting both heads when two coins are tossed simultaneously. Its 1/4

P(A n B) - getting both heads . P(A).P(B)

Two events are said to be mutually exclusive if the occurrence of one event , results in the absence of another event. If event A occurs event B doesn’t occur and vice versa. Here P(A n B) = 0 - mutually exclusive.

Conditional Probability

Defn : If A and B are not independent , given that the event B has occurred what is the probability of event A to occur.

Lets take one example. Rolling a die.
A : number 5
B : odd number

Lets say ,its given that B has occurred in an experiment. Now what is the probability of A. its 1/3. How did we get. The sample space is now 3 since the event B has occurred and the odds that it will be number 5 is one amongst three.

P(A | B) { A given B} = P(A n B)/P(B)

If two events are independent then
P(A|B)=P(A).(P(B)/P(B) which gives P(A). Which says the occurrence of B does not change the odds of A, its still P(A) regardless.

If two events are mutually exclusive , then the probability of event A given event B has occurred is P(A|B) = 0. If B has occurred then A will not occur that’s mutually exclusive.

Bayes theorem

In simple terms, it is the relation between the conditional probability and its inverse.

P(A|B)=(P(B|A)*P(A))/P(B)

Just brushing the basics again and one final time !

Classical todo list

2010-07-13T12:01:00.000-07:00

ABSTRACTION

we are right now working in the top most layer say .net framework , java or something. we dont need to worry how actually the code is executed by the machine , how the code loads in memory or how our thread gets scheduled or when vitual memory swapping happens or anything. its all abstraction. You dont need to know whats happening at our processor level. We just know it happens. But Its always essential to understand some inner details to have the complete picture. This is highly essential to become a complete software engineer and its a pre-req for any architect. I have been in many discussion where some guy starts talking about the internals and I have no clue at that level and so the other guy kind of gets the upper hand. and so....

here is my list of todo's click this link.
Currently am focussed in understanding some architecture and operating systems concepts.

A Mathematician's lament

2010-05-24T03:01:00.000-07:00

I never knew this before. Now I can derive all formula's by drawing diagrams.

Sum of N natural numbers = (n(n+1))/2

n and n+1 are the sides of the rectangle , which gives n(n+1) as its area

Sum of Squares of N natural numbers proof.
http://www.macalester.edu/~bressoud/pub/CBN2.pdf

Binomial Theorem and its the beautiful theory behind the formula (a+b)^n

http://www.youtube.com/watch?v=Cv4YhIMfbeM

Please watch all the three parts in youtube to understand fully. I hate my math teacher !

Into the Top10 All India

2010-05-14T15:30:00.001-07:00

I have been participating codechef monthly algorithm contests for a while now. Java is my language of choice. Participated in this month algorithm contest.
Problem page : http://www.codechef.com/MAY10/

I was able to solve three problems which were fairly simple. All three problems just require strong logical skills alone. Once the logic is right , implementation has to be fairly efficient as time constraints are too strict. The program has to be optimized at arithmetic level.I ended 7th in India and by far this is my best performance so far in programming contests.

Find my name at http://blog.codechef.com/2010/05/12/may-2010-contest-results/ and here is my not-so-great handle http://www.codechef.com/users/sppraveen

My previous best contest rankings were 9th and 11th. http://blog.codechef.com/2010/02/11/february-contest-results/
Expecting top 5 in coming months :)

(You need to participate. Just register and give a try next month. Be sure you make yourself familiar by putting some practice problems. visit www.codechef.com

Basic Math : Area of Circle

2010-05-14T14:49:00.000-07:00

No work , bored of algorithms . Its in this state when I thought how (pi)r^2 became the area of circle.

First what is (pi) . Its the ratio of the circumference of the circle and the diameter. See this wiki animation to understand this
http://en.wikipedia.org/wiki/Pi

(pi) is the distance traveled by a circle to complete one full rotation which has 1 unit diameter. This value is found to be 3.141.... based on various methods.
(pi) is 3.14 when diameter (2*r) is 1.
(pi)= Circumference / diameter
(pi) = Circumference / 2 * radius

which gives

Circumference = 2 * (pi) * radius

So far so good. Having read this basics , please go to this link which explains how area of circle became (pi) * r * r. http://www.worsleyschool.net/science/files/circle/area.html

Its Vow after reading the above link as it marks the great day when I understood the theory behind the formula for area of circle.

Inverted Index - Data Structures(Under Construction)

2010-04-30T01:13:00.000-07:00

First see - part1,part2

Hash table

Hashtable Structure -
It will have 10^5 buckets. Each bucket is a word which has a pointer to the document list.
insert - O(1)
search - O(1)

There are no perfect hash functions available for string. Hence hashing will have collisions. For resolving collisions , we need to use Chaining. Its not guaranteed to be constant time, but since we have 10 ^ 5 buckets and 10 ^ 5 words we could assume that it will fairly perform very well.

Cons :

1. It doesnt support prefix match. Say am searching ebook and I have types "ebo". It will not show the ebook entry. No prefix match. It supports only exact match.

2. If the size of our distinct word increases , we should increase the number of buckets also. Something like double hashing. This generally does not scale well and will result in more collisions.

Search Trees :

Binary Search Tree :

insert : O(h)
search : O(h) => h!= log n - Since its not balanced

pros : supports prefix match. If we have typed "ebo" we could search for ebo and return all nodes below that.

cons : Not balanced which does not guarantee log n time complexity

Red Black Tree , AVL Tree

insert : O(log n)
search : O(log n)

pros : height balanced. Guaranteed logarithmic search and insertion time. Prefix match.

cons : little complex to implement.

B Tree

I think this is the data structure. Let me experiment and come back to this.

Prefix Tree / Trie

insert : O(length of the word)
search : O(length of the word)

cons : Too big memory requirements. Not suitable for big indexes. For small index , this is the best data structure.

Out of the race
Hashing
Prefix Tree/Trie
BST

still in race
self-balancing binary search tree
B Tree

B-Tree is leading , since this is the data structure used in database indexing. Lets decide on a simple and efficient one.

Note : I feel am just repeating the age old data structures.Sorry! Next post, I will try to get into more interesting stuff on dictionaries. I am reading the book "Introduction to Information Retrieval" By Prabhakar Raghavan and Christoper Manning.

Building a Desktop Search Engine - Inverted Index

2010-04-27T00:47:00.000-07:00

Lets take a look at the Inverted index and try estimating the approximate size of the index.(fits in memory?)

Indexing : Indexing is the process of creating an advanced data structure while crawling the documents , for fastest search retrieval.

What do we index :

Index all files and folders and also the contents of the file if that is readable. This helps us search some text which occurs in the file also. For file type *.txt , *.doc - index the file contents also. For *.mp3 , *.vlc and so on , index only the file name.

Inverted Index :

Document is a collection of words. The index should finally help in finding all the documents which has certain word. The collection of complete set of words in all documents is the dictionary. For each word in the dictionary - we need to store the documents which has this word. Now while searching a word , get the document list for that word and return the results.

Operations on Inverted Index

The following operations are performed frequently on the index.
1. Inserting a new word in the index
2. updating the existing word's document list
3. looking up for a word in the index to get list of documents

Steps 3 and 2 are just look-up. So insert and search are the operations performed on the index.

Fits In-memory or not - Biggest question to solve

How big the index will be. What will be the size of the complete inverted index.
Total No of Distinct words : 10^5(average)
Average number of text documents : 100 - 10000
Average size of document list for each word : 30 - 50
Average word length : 7 characters

We dont need to index stop word which appear in every document. See this - link

10 ^ 5 words take = 10 ^5 * 7 characters = 7 * 10 ^5 characters = 7 * 10 ^ 5 bytes = 0.7 MB
30 documents = Each document could be represented by a unique integer which takes 4 bytes memory . Hence 30 * 4 = 120 bytes

Index size = Total word size * Average size of document list
= 0.7MB * 120 = 84 MB

If the no of distinct words is of order 10 ^ 6 , then 840 MB would have been the size of index.

Lets assume , the total size will be around 84 MB and discuss about the data structure which could hold the complete index in-memory. This makes it simple and some research online clearly shows , the index size clearly fits in memory. If it doesnt fit , we should use index compression algorithms or store the index in the hard-disk and do one in-memory + one disk-read model(search engine model).

Lets go ahead and discuss various data structures including pros and cons

Note : This calculation is simply my assumption. We will implement in-memory data structure first then we will discuss memory+disk related data-structures.

Building a Desktop Search Engine : Writing a crawler

2010-04-26T23:07:00.000-07:00

We will build a complete end-to-end desktop search engine.

Objective : A Product similar to google desktop. This is purely for learning and experimentation purpose

What it does : A search engine for your PC. You could use it as a quick application launch tool.

To start with , lets write a single threaded crawler which recursively crawls the entire documents in your local system. lets name it - SimpleCrawler

Language : Java

 
import java.io.*;
public class SimpleCrawler
{
 public static void main(String args[])
 {
  String rootDirectory="C:\\Documents and Settings\\sppravin\\My Documents";
  crawl(new File(rootDirectory));
 }
 public static void crawl(File file)
 {
  if(!file.isDirectory())
   return;
  String files[]=file.list();
  for(String f:files)
  {
   File newFile=new File(file.getAbsolutePath()+"\\"+f);
   if(newFile.isDirectory())
    crawl(newFile);
   System.out.println(f);
  }
 }
}

All crawlers start crawling from a set of seeded listings. In our case, My Documents folder is the root and we will crawl it fully.

crawl method takes the root file , checks if this is a directory and then lists() all files under the directory. It may have sub-directories also. For sub-directories we recursively call crawl(subDirectory). We are doing a DepthFirstSearch here. Whenever it gets a file, it prints the name of the file to the console.


My Documents -> My Pictures ->mine.jpg
             -> resume.txt

It will start from the root My Documents. lists all files immediately below this. Finds My Pictures and makes a recursive call crawl(My Pictures). This crawl will print mine.jpg and returns back. It will print My Pictures followed by resume.txt

output :
mine.jpg
My Pictures
resume.txt

We can give any number of root nodes to start crawlilng or simply c:\\ to crawl the entire C drive. It does nothing but crawling and print names of all files and folders.

We are done with our SimpleCrawler.

Next step - lets build the search index out while crawling and store the index as a file in the hard disk.

Cloud computing

2010-04-24T07:16:00.000-07:00

Cloud computing - The most talked about buzz word in recent times. It deserves some understanding now.(this is certainly the future) here are my attempts to understand this buzz.

So whats a cloud - A cloud refers to a cluster of computers(usually in the range of 1000 servers). Cloud computing is simply doing some computation - say an application running on these cluster. Whats new now. All large scale enterprise applications now run using 1000's of nodes. so whats cloud.

Lets take a simple example - newsfeed application - similar to the facebook one. A machine could normally serve certain amount of requests - has a max bound. Initially if there are few users in the our sample application, one server might be enough to do the whole processing. Now , users increase hence traffic increases , which means more requests to the server and now our single machine could not handle so many real time requests. What is the solution now. Have many servers and load balance the traffic. This is normally what scaling mean. Adding more computing power. Now , lets say our peak traffic is some $x requests/sec. To handle this $x req/sec we need $y number of machines. This is termed as availability. A highly available system should be able to process real time request without any delay irrespective of the incoming traffic. We shall now add $y servers, now we made our application highly available.

On a normal day , we might not get peak $x req/sec . traffic will be $x/2 only. Now we can handle this traffic using y/2 servers. So we are not using the remaining y/2 servers computing power. all the remaining servers are ready to serve requests because application has to have high availability. Now on this normal day, we are wasting y/2 servers computing power, space and the actual power. Now the next day we get $x*2 requests - our new traffic peak. We have not predicted this high traffic and the system is going to come down. Got the problem? This is the problem which could be solved using cloud. Its automatically scalable. If the application starts getting more requests, ask for new instances in the cloud, install OS, deploy app and start serving the traffic. Traffic is less. Release some of the servers. Vow super - computing power as and when required. we can do this on-demand adding or removing servers without cloud also. But the advantage of using cloud is that , we will end up paying for what we use. This is the advantage. You pay for what you use.

It doesnt end here. lets say we need some big enterprise proprietary application. say our newsfeed application runs on a software stack which is very expensive. In cloud, we dont need to purchase these softwares also. Cloud providers generally provide these softwares also and you will be renting these softwares as long as you use them alone. Vow its cheap. No need to buy them , just rent them as long as you use it. One thing - everything happens via network - internet.

For a small company , say start-up , buying servers is very expensive. Instead now they could buy computing power from some cloud service. Use their storage which is reliable.(GB's to TB's) Data is stored in a distributed environment and hence even if the hard disk crashed, the data could be retrieved because data is stored in a redundant manner in many servers. All this overhead is automatically handled. We could bring the application up , in just couple of days buying computing power in the cloud. (Ever thought how difficult to buy servers, internet, storage, fail over systems, maintenance - all these is easy now )

For large companies, they build their own cloud platform so that all their applications run on cloud which is like a shared data center. gmail runs on cloud. they automatically scale - perhaps sometimes not(we will get back to this). Microsoft, yahoo , google , amazon is all building their own cloud infrastructure to win in the future. As mobiles get more powerful , all applications running in mobile will be hosted in the cloud which makes it more compelling.

Putting all together,
wiki says - "Cloud computing is Internet-based computing, whereby shared resources, software and information are provided to computers and other devices on-demand, like a public utility."

Another interesting definition -
Cloud computing is "A form of standardized IT capability such as internet based services , software and infrastructure - offered by a service provider that is accessible via internet protocols from any computer , is always available and scales automatically to adjust to demand ,either pay-per-use or advertising based has programmatic-based control interfaces , and enables full customer service."

the definition means ....

amazon - the service provider - they offer cloud services
You can control the cloud through internet and deploy your applications.
always available - they guarantee the server availability - on demand
scales - scale server computing , space either up or down
pay-per-use - Works like a prepaid cell phone
programmatic based control interfaces - cloud service provider exposes these interfaces to control the cloud and your applications
enables full customer service - they take care maintaining servers and other IT maintenance related work.

This new paradigm will pose enough challenges in the near future and it will change the way we look at software today!

Best inspirational scenes

2010-04-18T04:33:00.000-07:00

Pursuit of Happyness

Christopher Gardner: Hey. Don't ever let somebody tell you... You can't do something. Not even me. All right?
Christopher: All right.
Christopher Gardner: You got a dream... You gotta protect it. People can't do somethin' themselves, they wanna tell you you can't do it. If you want somethin', go get it. Period.

Watch : http://www.youtube.com/watch?v=GQlzz6jGCfI

The Shawshank Redemption

Andy Dufresne: [in letter to Red] Remember Red, hope is a good thing, maybe the best of things, and no good thing ever dies.

Watch : http://www.youtube.com/watch?v=9K30e9O3Nng

Batman Begins

Alfred Pennyworth: Why do we fall, sir? So that we might learn to pick ourselves up.

The Dawn is near when the night is Darkest

Troy

Achilles: [to his men] Myrmidons! My brothers of the sword! I would rather fight beside you than any army of thousands! Let no man forget how menacing we are, we are lions! Do you know what's waiting beyond that beach? Immortality! Take it! It's yours!

Watch : http://www.youtube.com/watch?v=d_O68HUcHos

Russel Crowe - oscar speech

"If you grow up in the suburbs of anywhere, a dream like this seems kind of vaguely ludicrous and completely unattainable. [But] this moment is directly connected to those imaginings. And for anybody who's on the downside of advantage, and relying purely on courage, it's possible." (Russell Crowe, his Oscar speech)

Watch : http://www.youtube.com/watch?v=pJNmKn8f15E

Steve Jobs - stanford speech

http://www.youtube.com/watch?v=UF8uR6Z6KLc

Sachin Tendulkar - http://www.youtube.com/watch?v=ukQBb-Ik4PE

Guru interval scene - http://www.youtube.com/watch?v=T_R36SQZq-w

Missing you all

2010-04-11T07:58:00.000-07:00

I am a computer science student and I am passionate for computer science. Till my college end , I donno where all these passion went. I was not at all passionate to learn things at college. Now I realize , even worry when I think I did not read those subjects(not for CGPA - for pure learning).
first one
Operations research and optimization - I really felt bad for missing this two. I remember the way we had this course, a ppt the day before exam which briefly describe the steps to solve. I will read and try to understand these steps without understanding the problem itself. Apply the steps get marks. what the hell?. I remember one word now - simplex and duality. I wondered why is this course required for a c6 ite . Now I could sense how important these two courses , what optimization means what kind of interesting problems and algorithms were discussed. I missed them.

I can add probability and stats to this. But i feel am not too bad at it.

Next one,
DS - I dont know. While writing my resume now , I feel this is what all I have now. I am very strong in Algorithms and data structures. When I was in college I got E grade. Just because i was doing animation I could not read this well. Probably I dint like because I dint know to write a simple recursive code or I am not good enough to appreciate the beauty of this. Now, everyday I love reading algorithms and solving puzzles.I feel I missed this.

Electives -

Networking
I dont know what a router is. I feel bad to say am a computer science student. Really even now I dont know simple because I did not do anything in networking. Although this is not my interest , I feel this course should have been in the compulsory list for every computer science student.

Data mining - I did this course. I am atleast in a state where I know what data mining could do and what it means. I should have done a project in this. What a course it is.

Artificial Intelligence - Given the professor was such a crap guy I dont feel for this course.

Information Retrieval - I wonder why we did not have this course in our academic list. The dark age of personal computers has come to an end. Its all internet , ubiquitous and data is information.

Grid/Cloud computing - Again . I thing we had grid computing (elective). The world is moving towards cloud and grid computing. This is the future and am completely fascinated. I felt I missed this.

Graph theory - I love this subject. The fact that it helps me visualize the answers rather proofs makes it superb. I did read well , though I did not make any attempt to understand it. This is by far the most beautiful course ever and I have bought our text book now to read this. I miss GAN.

Mathematics - naaaaaa never. Am personally looking for topics in maths which is must for a computer science student. I wanted only those topics which will be useful.some topics like prob stat , number theory , permutation and combination , basic algebra and few more topics. I am not a research guy!!!

And Some course I hate

Dynamics of Social Change - funny one and a crap book
Linear algebra - Why?
Electrical pracs - I dont remember course name also.
and one more circuit related junk.

I dint feel for these courses though they are too good
multimedia computing - donno what to write here
image processing - base for some specific fields
computer graphics - more and faster computing power is compelling reason
machine learning - the classic
mobile computing - future
data storage technologies - with cloud , this is the most challenging task ahead

So many courses I missed my chance. But still I have time. I feel I wanted to do a Masters which has these courses alone in its structure.But I dont think there is any like this. Looking forward to grab back all these missed chances if I get time.

Starting SPOJ

2010-03-24T13:04:00.000-07:00

I have been into programming contests for four months and I find it very tough. I am inspired by the format of contests held by codechef. Every month they have a contest with 10 days duration to solve six difficult algorithm problems. Good thing is , unlike topcoder , its an offline competition which gives a newbie enough time to think about the problem and code. Another good thing is , they give prizes , in fact lot of prizes and I won 1500 coming 11th. I felt great , but the next month I ended solving just one problem out of six.

I have been reading algorithms in CLRS book but I did not improve. All great coders say "practice is the key". To practice , the best available site is SPOJ and UVA. As many prefer , I have joined SPOJ and started solving problems. They have the biggest collection of algorithmic problems. I am thrilled seeing such a big collection. I also noted that most of the guys who finish top 10 in codechef have great records in spoj. http://www.spoj.pl/ranks/users/IN/ . They have been practicing these problems , hundreds of algorithms , thousands of problems , for more than two years. Thats awesome.

Its not inspiring to see these guys have solved 400 problems there. It makes me feel , when will I solve so many problems , learn and win these guys. I know that its not going to happen anytime soon. I should learn and thats the reason why am participating. Now , I have decided to take SPOJ fulltime. It gives me great pleasure in solving these problems. Its simply amazing to read some algorithms and I find it fascinating. I am pretty sure that many would disagree with this thought.

link - http://www.spoj.pl
So its time to start thinking and coding and thinking and coding. Will update the blog if I come across some tricky problems and perhaps if I manage to solve that tricky problem!!!

Generate all permutations for a given set of nos

2010-03-18T03:23:00.001-07:00

Below is the recursive code which generates all permutations for a given set of numbers.

 
public class Permute
{
 static boolean visited[]=null;
 static int a[]=null;
 public static void main(String args[]) throws Exception
 {
  a=new int[]{1,2,3,4};
  for(int i=0;i < a.length;i++)
  {
   visited=new boolean[a.length];
   permute("",i,a.length);
  }
 }
 public static void permute(String out,int j,int length)
 {
  visited[j]=true;
  out=out+a[j];
  if(out.length()==length)
  {
   System.out.println(out);
   return;
  }
  for(int i=0;i < a.length;i++)
  {
   if(visited[i]==false)
   {
    permute(out,i,length);
    visited[i]=false;
   }
  }
 }
}

Its equivalent to recursing all possible paths in a complete graph of N vertices.

Life at Yahoo Bangalore

2010-02-26T13:11:00.000-08:00

I have nearly completed my 2 years (this may) at yahoo Bangalore. I have been working in Sponsored search (panama) .One of the most hyped projects when I joined this place. As my blog title suggest – am just another programmer here but still proud that every line of code I have written have been used by millions of people. Having enjoyed every moment here its time to say what I really like at yahoo.

My first year was most productive period in my career. I learned the most important thing in my life - THINK. TamilNadu board and the school have taught me ways how not to think. That’s the motto in TN. If you think, understand and write answer, most probably end up getting less marks as that’s not exactly the text book says :). So did not get a chance to think as am not supposed to think at all. BITS-Pilani later made me lazy giving the complete freedom that I don’t need to attend classes ...even tests. To add, am a c6 ite(Bitsians know how good c6 is) So here I am at Yahoo after 21 years and still don’t know what thinking mean. This is when I realized seeing my architect, that thinking is the essential part. From then, every problem I face, I think about it strongly to understand it. This has changed me a lot and I have started participating in Programming competitions and have been performing pretty well for a newbie. This is the biggest thing I have learnt from the people I work with. THINK
(Please note – I did not know to think, still I got BITS. I did not attend tests or read – still I got Yahoo – This is my fate. The reality is that I know how to get things done )

Apart from learning the most important thing, it’s the freedom that I enjoy here gives me the opportunity to explore various fields.

Gaming – Fun is essential. Foosball tables all around to insist that fun is an essential part of work. I play table tennis in my breakout area. Many enthusiasts join every evening and play for atleast an hour.

Coffee – free of cost. What matters is, its not coffee vending machines, the cafeteria has a special coffee shop and I have the choice – bru coffee, tea, tikashan coffee , badam milk. Have gone to office in Sunday also, just because I get good coffee.(Also because I can make unlimited STD calls to someone special)

No timings – Most IT Company don’t have restriction, but I have crossed limits. Starting after 12 30 daily is weird. I love to be there till 10 playing , eating and ofcourse last and also the least – Coding.

I determine what I work on, when I would get it done and when to set the deadline. Once set, I have total control and I can play table tennis fully and end up doing the whole thing last day. No one cares as long as you get the work done. No timing cards, no review meetings about my daily work gives me complete freedom to do what I want.

Food – this one is impressive. Breakfast, lunch, dinner – free of cost and for a change it’s tasty. Monthly beer bash for re-energizing. Pastries, juice counters and Barista too.

Source code and open source – I have access to the source code of many yahoo properties and I get to see how the big internet company works. Have not spent enough time to learn about scale they handle. Everything, most of the technology is open source and the linux Desktop rocks – feel this is the best coding environment for a developer.

And finally PRESSURE. Working in Sponsored search is great but the work demand high availability. A P0 , production ticket mean, no matter what that has to be fixed. Yahoo is losing millions every minute and a fix would help them stop losing. Hence pressure is always there, you know only when you face a priority zero issue. So many people around asking questions , suggesting work around, getting the patch ready – that’s one tiresome thing here. Fortunately as am a fresher am not supposed to look at priority zero tickets. When I finally got the word from my manager -“you can start looking into P0 and you are the primary poc for all production incidents” – the product became so stable that I have hardly got this once. Its so surprising how am lucky always. May be my code made it stable and bug free :)

What more to add – I have a chance to attend some of the finest tech talks ever.link Also many founders are here and I have met them. Have got a chance to be with the most talented, experienced, smart, and friendly people. It has all stuff for a nice and happy life and I am enjoying every bit of it. Perhaps now you know why yahoo is not doing that good 

DP - When will I master you!

2010-01-19T13:38:00.000-08:00

I have started participating programming competitions recently. I know whats DP but never really know how to put that to use in solving complex problems.

Here is an extract from topcoder - jbernadas - Programmer of the month June 2008 in TC

------------------------------------------------------------------------
SuperRaskao: Do you know Dynamic Programming?

jbernadas, zyx3d: Yes, of course, we know Longest Increasing Subsequence, Longest Common Subsequence, Matrix Chain Multiplication, ...

SuperRaskao: Then, given a matrix A of NxN elements, with N <= 16, how would you find a permutation P such that sum{i=0..N-1} A[i][P[i]] is minimized?

zyx3d: **thinking**

jbernadas: Just try each possible permutation and keep the one that returns the minimum answer.

SuperRaskao: That gives TLE, you have to use DP.

jbernadas: How?

SuperRaskao: Use a bitmask to memorize the previously calculated values.

jbernadas: Wow.

zyx3d: Makes sense.

SuperRaskao: Go to TopCoder, and you will learn real DP.
------------------------------------------------------------------------
The above is a chat history of jbernadas when he first got motivated to participate in TC competitions. It makes so much sense. You want to know real DP, you need to solve complex problems. Reading DP in CLRS will only make you understand the topic but you will never master unless you practice them.Its tricky!

I hope I would master DP soon like these guys did! DP concept is simple and but to put it to use, it takes so much practice.

If you feel the same, here is a link to get started
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg - this link has a DP tutorial with some great DP problems to practice.

For practicing more problems , use this spoj link. http://pt1989.22web.net/c0ding/spoj.php?search=dp - This classifies the problem difficulty also.

Complexity theory

2009-12-23T02:05:00.000-08:00

Any person interested in algorithms would have heard the terms NP hard , NP complete and so on. I have hardly taken any effort to understand this.
I dont know what we gain understanding if the problems is NP hard easy or complete whatever. But once you enter the field of algorithms it became essential to know and understand these terms.

First reason which I felt why should I know this theory - For some algorithm questions , if you can find that this is related to some already known algorithm , then we would immediately try to understand how to solve that already know algorithm. But some of the already known algorithms does not have an efficient polynomial time solution to it. May be I can find one. But these problems have been under math and computer science research and they could not come up with efficient algorithms, and hence its highly unlikely that I would come up with one. Hence instead of trying to come up with an algorithm , I will just do some brute force and some approximate algorithms.
Hence if we know this problem is related to some common problem and that problem is not yet solved , then instead of trying to come up with an algorithm , just find the brute force and get it done.

This is the reason why I felt its essential to understand these terms.

So now whats P and NP

P - Any problem that could be solved in polynomial time in a deterministic machine
NP - Any problem that could be solved in polynomial time in a non-deterministic machine

So whats a polynomial time here. Any problem which takes n to the power K steps is considered polynomial, where k is a constant.
And whats a deterministic machine - I really dont know but I believe its a machine which given an algorithm and input , it can give the answer in deterministic time.
Now I got puzzled whats a non deterministic machine. I think whats not deterministic is not deterministic. No matter what the definition is , one thing is clear.

Edit - A non-deterministic machine can be considered like a fastest computer with unlimited parallelism. The parallelism of the machine guarantees that it would be able to search all brute force paths/decisions in polynomial time.Hence a NP problem can complete in polynomial time in Non-deterministic machine.

NP represents a class of problems which could not be solved in polynomial time in a deterministic machine. The solution could be verified in polynomial time.

Lets say we have n numbers and we need to find the sum of n nos, we could do this in o(n) time which is linear . Hence this problem is in complexity class P.

Lets say we have n nos +ve and -ve. Now we need to find a subset whose sum equals x. Once we have got a solution to this problem, we can verify the solution is right in linear time. Thats is , just be adding the subset we could find if that equals x.

The above argument suggests, the problem could be verified in poly time(in fact it was linear) , but the solution may not be that straight forward to find.

This problem is belived to be NP complete. So far felt comfortable understanding whats P and NP. Now whats NP complete. Its believed that there exists some problems for which no poly time exists. These problems are set to be in NP complete.

Hence problems in NP and not in NP complete are those which may have a poly time solution and thats not yet found.

Now,
1. Subset sum problem could not be solved in poly time
2. In fact , an already available problem in NP complete could be reduced to this.

So given a problem C in NP, if we can quickly reduce a known NP complete problem to C, then C is in NP complete.

3CNF SAT - some problem is in NP complete. That is this problem is believed not to have any poly time algos. Now this problem can quickly be reduced to subset sum. Hence subset sum is also in NP complete.

NP complete - Problems believed not to have any poly solution.

P is infact a subset of NP. A problem in complexity space P could also be solved in polnomial time by a non-deterministic machine.

There is one more important complexity theory namely NP hard. Come on, I am giving up. Wiki says NP hard problem is something which is atleast as hard as NP complete problems.

If an optimization problem H has an NP-complete decision version L, then H is NP-hard. Hamiltonian circuit problem is finding a path in the graph, such that it touches each vertex exactly once. Once we have a solution , that is , a hamiltonian circuit we can easily verify that it touches all vertex exactly once in polynomial time. But coming up with a hamiltonian circuit is not that straight forward and it happens to be NP complete which means there are no poly time algorithm known to solve this.

Now , TSP is optimization version if hamiltonian circuit. Traveling salesman problem is exactly the same as hamiltonian circuit with one additional constraint which is to minimize the total distance. We have to select a hamiltonian circuit whose total distance is minimal. This problem is atleast as hard as the Hamiltonian ciruit problem. This optimization version problem is NP hard.

I still did not understand these stuff completely. But I believe what I have found till now is right. Let me read some more theory and get back to this post. Until then, let someone throw some light......

There are some arguments going on.does P = NP . Even if one problem which is in NP , if it is proved to have a polynomial time algorithm , then every other problem in NP is also in P which is called as P = NP. But researches believe P != NP , since many of the NP problems have been under research for years and still no poly algorithm is known. To confuse things more, P = NP is NP hard problem.

This whole complexity theory made my life hard , and so I conclude "Life is NP Hard".

Under constructive construction

DS and Algorithms base

2009-11-19T08:01:00.000-08:00

Its a compilation on what all do we need to know. I will keep adding some of the best materials , pdf's, papers , links whatsoever which would keep us thinking and learning.

Design
------

http://www.youtube.com/watch?v=aAb7hSCtvGw - How to design a good api and why it matters - joshua

DS and algos
------------

tries - http://www.cs.bu.edu/teaching/c/tree/trie/ , suffix tree and suffix array for various string based linear time searching algorithms
suffix array o(n) - http://felix-halim.net/pg/suffix-array/index.php
suffix tree - ukkonen on-line algorithm - linear time
btree and b+ tree and relation to databases. how database does indexing. what ds it uses for fast lookup - !!!Some great links Required!!!
Dynamic programming problem - Most programming competition questions based on this. link
self balancing binary tree - red black tree and avl tree
Sorting algos, Sorting in linear time, QuickSort and BST relation
string searching algorithms - min (KMP and boyer moore)
graph - properties and algorithms. Dijkstra floyd warshall must. Flow and graph properties
Range Minimum query and LCA
linesweep algorithms. convex hull 2d,3d and rotating calipers.
binary index trees

best materials
--------------
Diagrams for all algos (No theory ) - Easily the best quick reference
dp - one dp problem - just one page
tutorials from the best programming competition website- topcoder
puzzles - hard + gurmeet singh manku + Easy logic puzzles
MIT algos ds - mit video lectures
algo geeks - Link (brilliant discussion on tech questions)
cormen sols - Link
combinatorial game theory - Link
Course on Programming contests- Programming Challenges

Topic worth looking at
----------------------

Perfect and imperfect hashing
catalan number - very interesting property
huffman coding
levenshtein distance
linear programming,task scheduling,minimax algorithm,activity selection - greedy most of them
Nim game and its variants - http://en.wikipedia.org/wiki/Nim
Exact cover and dancing links algorithm - For solving sudoku in 0.01 sec Knuth paper
graph of NP complete problems - http://page.mi.fu-berlin.de/aneumann/npc.html

java
----
a java web crawler - link
Java IO for programming competitions - IO performance
SCDJWS
SCJP - SCJP book Bert bates and Kathy sierra

what i would ask in an interview?
---------------------------------

1. Explain how duckhunt video game works? Answer
2. java - implement hashmap - what hashing used. types. extendability. collision resolution and so on
3. autocomplete algorithm - edit distance , trie prefix match. how all language words. size of dictionary is huge. relevancy at that time(hot autocomplete should come). how stored. how retrieved.so on

Version of the compiled class

2009-11-09T22:07:00.000-08:00

To find the version of the compiled java class,
use javap -verbose

If the fully qualified name is com.xxx.yy.Class
use javap -verbose com/xxx/yy/Class | grep version
in the directory where com exist.

Then grep for version

minor version: 0
major version: 50

you could see the major and minor version. From the table below find the version information.


# major  minor Java platform version   
# 45       3           1.0  
# 45       3           1.1  
# 46       0           1.2  
# 47       0           1.3  
# 48       0           1.4  
# 49       0           1.5  
# 50       0           1.6

Please note that if you are using JVM 1.5 to run your application and some of your dependent jars in the classpath have the compiled class version as 1.6, your application would fail.

Either the dependent jars has to be in 1.5 or you should upgrade to 1.6 jvm.

Inside JVM - "Where does everything live" - Part A

2009-08-28T03:35:00.000-07:00

Interesting problems which this series of post will address:

1. assertTrue(heapSize > physical memory size) - Lets get into some OS(memory management-virtual memory)
2. sizeof(permgen) << sizeof(heap) ; assert if there is a performance impact
3. GC and its issues(not tuning)

We will focus mainly on how jvm manages memory specifically "what lives where"
To start with , this post has info only about stack

Java program has number of classes, each class may have variables, instances , statics, arrays, string constants and so on.
I wonder where all these stuff live? If its C, I would simply know where it lives by doing printf("%d",&i);
But java does not have all those pointer stuff(Thank god). It provides a layer of abstraction. You never know where everything lives in memory but the only fact is, it lives in an area called as heap.

Each program has a main thread which starts the proceedings. JVM would create some background daemon threads to do its VM activities.Generally, when you just have one class with main method, it would create some 12 threads. (1 main thread and 11 background threads) . Background daemon thread - GC is one example.

Each thread has its own thread stack or simply 'stack'. This is where all local variables live. Every method call is pushed into a stack frame. A stack frame has method local variables and pointer to the objects which live in heap. Conider the following code.


public static void main(String args[])
{
int i=0;
int j=5;
process(i,j);
}
static void process(int i,int j)
{
long k=254L;
gone();
}
static void gone()
{
}

stack would look like this
--------------------------------
gone()
process() k=254
main() i=0;j=5
--------------------------------

after completing the method execution of gone(), it will pop that out

--------------------------------
process() k=254
main() i=0;j=5
--------------------------------

So far so good. Till now we considered only local variables and they live in stack.
Note : Each thread has its own stack. Each thread will have its own copy of method local variables .

Java supports recursion. Stack is used for recursion internally.


public class a
{
 public static void main(String args[]) throws Exception
 {
  while(true)
  {
   main(new String[]{"hi"});
  }
 }
}

The above piece of code, will keep pushing main method into the stack and ultimately results in
StackOverflowError
Exception in thread "main" java.lang.StackOverflowError

Now not-stop-recursion will eventually result in Error. What if we have many threads and the total size of all stacks becomes higher?

Each thread has its own stack. Hence creating many threads in an application can also cause OutOfMemory error. Normally, stack size in unix is 256K. when you have 256 threads each with 256K stacksize then your system must be capable of allocating 256 X 256 K = 64 MB of native memory, failing to do which it will throw. Now , How to overcome?

One way is to tweak the stack size in the java options. - java -Xss512k or reduce the number of threads. ( Configure each threads stack size during thread object instantiation)
This stack size will restrict the number of threads that could be created.

Since the stack can contain only primitive data types or references to objects, it is very unlikely to happen.

To be Continued... This post will be a Mega serial

Interesting probability problems

2009-08-19T13:09:00.000-07:00

Below are two puzzles related to probability,which I found fascinating. The puzzles look simple, but most of the people get it wrong.

First puzzle :

Boy/Girl probability paradox?
At the mall you run into a high school classmate whom you haven't seen in years. While catching up on each others lives, she mentions she has two children.

A. Assume that you already know your classmate has a son. What is the probability that both her children are boys?

A moment later, a boy comes running up to her and says, "Hi, Mom." Your classmate then says, "This is my youngest child."

B. Now, what is the probability that both her children are boys?

Are the probabilities of A. and B. the same or different? If different, explain why.

Second puzzle :

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Solutions :

I am not going to write solutions here. Try out once and then compare with the answers.
First one : google "girl boy paradox"
Second one : google "monty hall problem"

Note : Please dont click comments as it has some solutions also

scratch pad : knapsack problem

2009-08-05T14:09:00.000-07:00

Key :

V - Value of each item

n - no of items

W - weight of knapsack (max weight)

wi - weight of item i

v[i,w] - best/optimized value of first i items having a total weight of w where w less than W

Problem : maximize value of items , given that maximum weight W - see knapsack in wiki

Unix Scripting Essentials

2009-06-27T22:03:00.000-07:00

I will start this post , with some basic scripts which I used moving to more complex ones. Most of the tasks were simple,
1. Find total no of lines in your source code
2. Search a class in jar repository
and so on.

"Many unix programs do quite trivial tasks in isolation, but , combined with other programs, become general and useful tools" - Kernighan

Mostly it requires understanding these basic tools. find, xargs, jar .
Pipes in unix helps us in taking the output of one program and give it as an input to another program. So here is the "search a class in jar repository one liner"


$ find . -name "*.jar" -print0 | xargs -0 -i jar tvf {} | grep "someclass.class"

find gives us a list of jar files. xargs takes these set of jar file names, and then calls jar tvf for each jar file . Then we finally grep for our class file.
We can find if the class file is there in classpath or not.

This script will just give, if the class is available or not but doesnt tell the important fact, which jar the class file exist if found.

It doesnt solve the purpose. Lets tweak this, and write a shell script which does the same stuff , but prints the jar names, each time as it looks into it.


#!/bin/sh
classfile="myclassfile.class"
for i in `find . -name "*jar"`
do 
 echo "processing $i "
 jar tvf $i | grep $classfile > /dev/null
 if [ $? == 0 ]  then    echo "==> found \"$classfile\" in $i"  
fi
done

This script is self explanatory. $? - success/failure of the last command.

find , xargs , grep together does lot of scripting tasks done easily. Let me post some other commands which I use frequently

Change some text in all files


find . -name "*.java" -print0 | xargs -0 -i sed 's/from/to/' {}

show list of directories alone


ls -al | awk '/^d/{print $0}'

Comment out lines from 20 to end


awk '{if(NR>20){print "//",$0} else print}' "sourcefile"

Find source files which has a static method call


find . -name "*.java" -print0 | xargs -0 -i grep -H "Person.getName()"

Add line nos to a file


awk '{print NR,$0}' filename

Important rule

Both awk and sed does not modify the source file directly. The output of the awk/sed program is written to standard output. If you need the output in a file, use redirection like this below


awk '{print NR,$0}' filename > targetfilename

targetfilename file will have the output now.

awk, sed could be used with find and xargs, and these when combined together help you in realizing the power of unix platform and the speed at which you can get things done.

If you are a windows user, install cygwin and you can run all these commands in windows also.
"One will appreciate the beauty only if he understands it fully." Experiment these tools and you will start loving

Necessity for Scripting

2009-06-20T08:52:00.000-07:00

Being a Programmer, it is extremely essential to know as much tools as possible. Scripting is one such tool which makes life easier. I love to code, but I have never read any scripting language. You may think why. The easy answer is ‘ I have never worked in unix/linux’. It leads to the biggest question , WTH/WTF you code but not using unix. I am not going to discuss about that now.

Every day when I work, I always require some small tasks to be done. One instance is , I need to find the no of lines in my total source code. I struggled to find the easiest way to find this. There is a top level directory which has many directories in it.There are many source files anywhere in this directory hierarchy. We need to find the total no of lines.

When I was struggling to get this done, my colleague appeared and he wrote one complex line , and there …. Was the output on terminal. It made me think, I should use right tools to get things done faster. Perhaps its easy to write a java program which does this.

It recursively traverses the directories, open each source file, find no of lines the close the file and do all these stuff. Java code would have been some 20 lines, but definitely it would have taken some time. But the same thing could be done in a single line in just a minute. So it is very essential to know the right tool to use for the right purpose.

So I decided I am going to learn scripting tools. I found that there are n scripting languages , and each language does one stuff great. I found perl as the one , which is complete and with which we can get these stuff done easily. I came across awk , sed whose sole purpose of existence is to get things done in a single line. These are languages which operate on each line and could be used for editing, finding , pattern matching large amount of files.

I started learning these small tools , which will make my life comfortable in near future. If you are not satisfied with scripting , go ahead using your c++/java code to do all these stuff. It requires you to do file i/o which is unnecessary. These tools do all these file i/o and other stuff in the background and makes our life easier.

use right tools and get things faster

Are you game -singleton pattern

2008-12-04T07:21:00.000-08:00

If you are a java expert and feel u know much about singletons including my previous two posts on singleton, go through this article.
http://java.sun.com/developer/technicalArticles/Programming/singletons/
Am I becoming a singleton freak, posting this again n again .'No' I feel i know only this well !!!

oops....my password!

2008-12-03T19:29:00.000-08:00

Google being the most popular intenet brand,all of us have a gmail id and use it for all purposes.Hence securing your password is a must.Now what if you have a slight doubt that your friend/colleague knows your password and they might peek into your personal stuff.To overcome this, there is an option in gmail.
look at last few lines at the bottom of your gmail
you will find,
Last account activity: 11 hours ago on this computer. Details
click details.This will show you the ip's from which you logged in for the previous five times.If someone has logged into your account,you catch them here.I dont need to say how!. And from your side you can sign them out by clicking 'sign out all other sessions'.Perhaps the easiest way is to change the mail password . This is just to ensure that your heroics are not revealed to others.(chatting,kadalai with girls!!!)

singleton pattern hack

2008-11-17T03:39:00.000-08:00

The previous post was about making sure only one instance is created for a particular class.
We all know that a class is always referred by its fully qualified name.But still each class is initially loaded by a classLoader.
Hence we can create another classloader for this singleton class and get another instance.Thats the hack for getting two instances from a singleton class.
Extract :
Java doesn't provide the formal notion of class version. So how is it possible to implement a class loading domain? The runtime identity of a class in Java 2 is defined by the fully qualified class name and its defining class loader. This means that the same class, loaded by two different class loaders, is seen by the Virtual Machine as two completely different types.

Thanks.

Make Singleton pattern thread-safe

2008-10-04T09:00:00.000-07:00

Hi all

Any Object oriented programmer,one day or other will need to restrict creation of multiple instances.Yes the easiest but the most used,singleton pattern.
Singleton pattern

  
class singleton
{
private static Singleton newInstance=null;
private singleton()
{
}
public static Singleton getInstance()
{
1.if(newInstance==null)
2.newInstance=new Singleton();
return newInstance;
}
}

This is the classic implementation of the singleton pattern.It provides a static getInstance method to get the singleton instance.
Since it has private constructor we cannot instantiate using new operator outside.

We can get the instance by calling the static method Singleton.getInstance()

But this classic implementation is not thread safe.
As two threads calling getInstance at the same time can get two different instances as the method is not synchronized.
Say threadA is on line marked 1
ThreadB has just finished line 1
Now threadA checks whether newInstance is null and it finds it null as ThreadB has not executed line 2.
So in this case actually two instances are created as the method is not thread safe.

By making the following change the whole pattern works fine.
Add synchronized keyword.
public static synchronized Singleton getInstance()

Note: Singleton pattern helps us to restrict the no of instance for a class and it doesnt say explicitly that it allows only one instance.

Coolest hack for RHEL

2008-09-02T04:09:00.000-07:00

Hi all

Playigng mp3 in linux,especially in RHEL is a tough job for linux newbies.
The easiest way to go about this is to install the yum
Now use yum to install vlc.This works and u have vlc which can play any format.
But still this is linux, whenever u play some mp3 u might end up getting this

[00000353] alsa audio output error: write failed (Broken pipe)

The coolest way to overcome this is to change the audio channels in the vlc player.
Now open the mp3 again.It works!!!
Note : Even if this did not work.Close all applications which produces sound.

Cookies should be cleared for privacy.

2008-08-25T20:39:00.000-07:00

Hi all
Whenever we login to some site, our login information is stored as cookies in the browser.
Say we sign into gmail.com
The first time after you sign in,a cookie for gmail will be set in the browser.
For all subsequent request you make like Inbox or Sent mail ... these cookies will be sent for authentication.
This cookies will get deleted only when you sign out.
So do not close you mail account and leave the browser open.
If you just close your mail account rather signing out ,open a new tab ,type gmail.com it will directly go to your mail box.
In mozilla the cookies get cleared by default when the browser exits.So make sure even if you dont sign out close the browser so that the cookies get cleared.
Or manually clear the cookies by changing the browser preferences

wanna know when and whether your mail was read!!!

2008-08-18T21:01:00.000-07:00

This can be very very useful if you really want to know whether your mail is opened.
Send mail to any person and as soon as he opens the mail , u will get an alert saying "Ur mail opened and read".Cool nice tip
To know how to do this,
Check spypig.com which helps in this spying process.It works!!!

reverse i search for linux users

2008-08-10T23:36:00.000-07:00

This post is for Linux newbie.
To easily access the recently executed commands.Use reverse index search which searches your command history and give you the command.

For instance you executed this command earlier
#sudo mvn compile somefilename

Now press ctrl+r and start typing the command
#sudo
it will search your command hostory and automatically fill with the whole command.
If you want to go to some other command press ctrl+r again to move backwards
This will speed up your whole process.

Note : #history | grep sudo could also be used incase you forget the whole command

Make your bookmarks social

2008-08-04T20:55:00.000-07:00

What is Social Bookmarking?:

Have you ever e-mailed a friend or family member and sent them a link to a website you thought they might find interesting? If so, you have participated in social bookmarking.

What is social bookmarking? It is tagging a website and saving it for later. Instead of saving them to your web browser, you are saving them to the web. And, because your bookmarks are online, you can easily share them with friends.

Some site for social bookmarking
del.icio.us - a yahoo based one
diggit
slashdot

Adavantages

Share your bookmarks easily with other people
Tag them so that its easy to search back
Access your bookmarks from anywhere if online

Daily, you might come across some very good site and if you do social bookmarking ,you will never lose them.Create an account start bookmarking and sene me the link
Here is mine
del.icio.us/sppraveen

Invisible in gtalk?

2008-08-04T03:52:00.000-07:00

I really dont know if this should be my first post of this random collection.
But still the most simple and the straight forward one.

What if you want to be invisible in gtalk(A feature in Yahoo messenger which is missing in gtalk)
One way is to sign in through gmail and use the browser based chat facility.
This has a status bar where the invisible mode could be set.